AFTD Auto-Formalizing Theoretical Domains

finset_image_balanced_of_closed

theoremverified

If b is injective, u, v are midpoint witnesses with u i ≠ i, v i ≠ i, u i ≠ v i, and S is a nonempty subset closed under u and v, then b(S) is midpoint-balanced.

Statement

theorem finset_image_balanced_of_closed {G : Type*} [AddCommMonoid G] [DecidableEq G]
    {n : ℕ} (b : Fin n → G) (hinj : Function.Injective b)
    (u v : Fin n → Fin n)
    (hu : ∀ i, u i ≠ i) (hv : ∀ i, v i ≠ i) (huv : ∀ i, u i ≠ v i)
    (hmid : ∀ i, b i + b i = b (u i) + b (v i))
    (S : Finset (Fin n)) (hSne : S.Nonempty)
    (hS_closed : ∀ i ∈ S, u i ∈ S ∧ v i ∈ S) :
    finset_is_midpoint_balanced (S.image b)
Source
step towards finset_midpoint_balanced_exists_nonzero_minor
Verified
18 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • finset_is_midpoint_balancedA finite set B is balanced: it is nonempty and every b ∈ B satisfies 2b = u + v for two distinct elements u, v of B other than b.
Used by 1

The proof, explained

To show that the image set b(S) is midpoint-balanced, the proof verifies the two defining conditions. First, b(S) is nonempty because S is nonempty. Second, for any element x = b(i) ∈ b(S), the closure of S under u and v guarantees that b(u(i)) and b(v(i)) belong to b(S), while the injectivity of b transfers the distinctness among i, u(i), and v(i) to their images. Finally, the midpoint sum identity holds directly from the assumed midpoint relation for b.

  1. To show that b(S) is midpoint-balanced, it suffices to show that b(S) is nonempty and that every element x ∈ b(S) admits two distinct witnesses in b(S) distinct from x whose sum is x + x.

    Unfolding the definition of finset_is_midpoint_balanced gives two conjuncts: nonemptiness of the set, and the existence of distinct midpoint witnesses for every element. The proof splits the goal into these two obligations.

    lines 10–11

      dsimp [finset_is_midpoint_balanced]
      constructor
  2. The set b(S) is nonempty.

    Since S is nonempty by assumption (hSne), its image under b is also nonempty by Finset.Nonempty.image.

    line 12

    uses Finset.Nonempty.image

      · exact Finset.Nonempty.image hSne b
  3. For any x ∈ b(S) with x = b(i) for some i ∈ S, the candidate witnesses b(u(i)) and b(v(i)) belong to b(S).

    Given x ∈ b(S), Finset.mem_image.mp yields an index i ∈ S such that x = b(i). By the closure assumption hS_closed, both u(i) and v(i) belong to S. Hence, their images b(u(i)) and b(v(i)) belong to b(S) by Finset.mem_image_of_mem, leaving four conditions to verify: three distinctness requirements and the midpoint equation.

    lines 13–16

    uses Finset.mem_image.mp, Finset.mem_image_of_mem

      · intro x hx
        obtain ⟨i, hi, rfl⟩ := Finset.mem_image.mp hx
        obtain ⟨hui, hvi⟩ := hS_closed i hi
        refine ⟨b (u i), Finset.mem_image_of_mem b hui, b (v i), Finset.mem_image_of_mem b hvi, ?_, ?_, ?_, ?_⟩
  4. The candidates b(u(i)) and b(v(i)) are distinct from each other and from b(i).

    In each case, assuming equality would imply equality of the corresponding indices by injectivity of b (hinj). This contradicts the assumptions hu i (u(i) ≠ i), hv i (v(i) ≠ i), and huv i (u(i) ≠ v(i)), respectively.

    lines 17–22

        · intro h
          exact hu i (hinj h)
        · intro h
          exact hv i (hinj h)
        · intro h
          exact huv i (hinj h)
  5. b(i) + b(i) = b(u(i)) + b(v(i)).

    This equality is given directly by the midpoint identity hypothesis hmid evaluated at index i.

    line 23

        · exact hmid i
Finset.Nonempty.image
The image of a nonempty finite set under any map is nonempty.
Finset.mem_image.mp
If an element belongs to the image of a finite set under a function, then it is the image of some element of that set.
Finset.mem_image_of_mem
The image of an element of a finite set belongs to the image of that set.

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

/-- The image under an injective certificate map b of a non-empty subset S closed under u and v satisfying the midpoint identities and distinctness is midpoint-balanced. -/theorem finset_image_balanced_of_closed {G : Type*} [AddCommMonoid G] [DecidableEq G]    {n : ℕ} (b : Fin n → G) (hinj : Function.Injective b)    (u v : Fin n → Fin n)    (hu : ∀ i, u i ≠ i) (hv : ∀ i, v i ≠ i) (huv : ∀ i, u i ≠ v i)    (hmid : ∀ i, b i + b i = b (u i) + b (v i))    (S : Finset (Fin n)) (hSne : S.Nonempty)    (hS_closed : ∀ i ∈ S, u i ∈ S ∧ v i ∈ S) :    finset_is_midpoint_balanced (S.image b) := by  dsimp [finset_is_midpoint_balanced]  constructor  · exact Finset.Nonempty.image hSne b  · intro x hx    obtain ⟨i, hi, rfl⟩ := Finset.mem_image.mp hx    obtain ⟨hui, hvi⟩ := hS_closed i hi    refine ⟨b (u i), Finset.mem_image_of_mem b hui, b (v i), Finset.mem_image_of_mem b hvi, ?_, ?_, ?_, ?_⟩    · intro h      exact hu i (hinj h)    · intro h      exact hv i (hinj h)    · intro h      exact huv i (hinj h)    · exact hmid i
See it in the graphDiscuss this resultChallenge it