finset_image_balanced_of_closed
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
- finset_midpoint_balanced_exists_nonzero_minorEvery nonempty midpoint-balanced subset B of ZMod p contains an inclusion-minimal balanced subconfiguration of size k+1 ≤ |B| with k > 0…
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.
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.
dsimp [finset_is_midpoint_balanced] constructor
The set b(S) is nonempty.
Since S is nonempty by assumption (hSne), its image under b is also nonempty by Finset.Nonempty.image.
uses
Finset.Nonempty.image· exact Finset.Nonempty.image hSne bFor 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.
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, ?_, ?_, ?_, ?_⟩
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.
· intro h exact hu i (hinj h) · intro h exact hv i (hinj h) · intro h exact huv i (hinj h)
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.
· 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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- 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