finset_exists_minimal_midpoint_balanced
Every midpoint-balanced finite set B contains an inclusion-minimal midpoint-balanced subset B₀.
Statement
theorem finset_exists_minimal_midpoint_balanced {G : Type*} [AddCommMonoid G] [DecidableEq G] (B : Finset G) (hB : finset_is_midpoint_balanced B) : ∃ B₀ ⊆ B, finset_is_midpoint_balanced B₀ ∧ ∀ A ⊆ B₀, finset_is_midpoint_balanced A → A = 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 find an inclusion-minimal midpoint-balanced subset of a finite midpoint-balanced set B, we consider the collection of all midpoint-balanced subsets of B. Since B itself belongs to this collection, the collection is nonempty and finite, and thus contains an element B₀ of minimal cardinality. Any midpoint-balanced subset A of B₀ also belongs to this collection, so |B₀| ≤ |A|; because A ⊆ B₀, this forces A = B₀, establishing inclusion-minimality.
The family `s` of all midpoint-balanced subsets of `B` contains `B` and is therefore nonempty.
Working in a classical context so that the property of being midpoint-balanced is decidable, we define `s` as the subcollection of the powerset of `B` consisting of midpoint-balanced sets. Since `B ⊆ B` by reflexivity and `B` is midpoint-balanced by hypothesis, `B` belongs to `s`.
uses
Finset.mem_filter,Finset.mem_powerset,subset_rflclassical let s := B.powerset.filter finset_is_midpoint_balanced have hs : B ∈ s := by rw [Finset.mem_filter, Finset.mem_powerset] exact ⟨subset_rfl, hB⟩
There exists a midpoint-balanced subset `B₀ ⊆ B` of minimal cardinality among all midpoint-balanced subsets of `B`.
Because `s` is finite and nonempty (witnessed by `B`), `Finset.exists_min_image` produces an element `B₀ ∈ s` that minimizes the cardinality function `Finset.card`. Unfolding membership in `s`, `B₀` is a midpoint-balanced subset of `B`, and every `x' ∈ s` satisfies `|B₀| ≤ |x'|`.
uses
Finset.exists_min_image,Finset.mem_filter,Finset.mem_powersetobtain ⟨B₀, hB₀s, hmin⟩ := Finset.exists_min_image s Finset.card ⟨B, hs⟩ rw [Finset.mem_filter, Finset.mem_powerset] at hB₀s
Choosing `B₀` reduces the theorem to showing that any midpoint-balanced subset `A ⊆ B₀` must equal `B₀`.
We supply `B₀` as the existential witness. It already satisfies `B₀ ⊆ B` and is midpoint-balanced. To establish inclusion-minimality, we take an arbitrary subset `A ⊆ B₀` that is midpoint-balanced and must show `A = B₀`.
refine ⟨B₀, hB₀s.1, hB₀s.2, fun A hAB₀ hA => ?_⟩
The subset `A` belongs to `s`.
Since `A ⊆ B₀` and `B₀ ⊆ B`, inclusion transitivity gives `A ⊆ B`, so `A` is in the powerset of `B`. Combined with the assumption that `A` is midpoint-balanced, `A` meets the criteria for membership in `s`.
uses
Finset.mem_filter,Finset.mem_powersethave hAs : A ∈ s := by rw [Finset.mem_filter, Finset.mem_powerset] exact ⟨hAB₀.trans hB₀s.1, hA⟩
`A = B₀`, completing the proof.
Since `A ∈ s`, the minimality of `B₀` gives `|B₀| ≤ |A|`. Because `A ⊆ B₀`, a finite set containing a subset of at least its own size must equal that subset (`Finset.eq_of_subset_of_card_le`), so `A = B₀`.
uses
Finset.eq_of_subset_of_card_leexact Finset.eq_of_subset_of_card_le hAB₀ (hmin A hAs)
Finset.mem_filter- An element belongs to `Finset.filter p s` if and only if it belongs to `s` and satisfies the predicate `p`.
Finset.mem_powerset- A finite set `s` belongs to the powerset of `t` if and only if `s ⊆ t`.
subset_rfl- Every set is a subset of itself: `a ⊆ a`.
Finset.exists_min_image- Any nonempty finite set contains an element that minimizes the value of a given function into a linearly ordered type.
Finset.eq_of_subset_of_card_le- If `s ⊆ t` and `t` has cardinality at most that of `s` (for finite sets `s` and `t`), then `s = t`.
- The `classical` tactic on line 6 is a formal detail that provides decidability for the midpoint-balanced predicate, which Lean requires in order to construct the finite set of subsets via `Finset.filter`.
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.
/-- Every midpoint-balanced finite set B contains an inclusion-minimal midpoint-balanced subset B₀. -/theorem finset_exists_minimal_midpoint_balanced {G : Type*} [AddCommMonoid G] [DecidableEq G] (B : Finset G) (hB : finset_is_midpoint_balanced B) : ∃ B₀ ⊆ B, finset_is_midpoint_balanced B₀ ∧ ∀ A ⊆ B₀, finset_is_midpoint_balanced A → A = B₀ := by classical let s := B.powerset.filter finset_is_midpoint_balanced have hs : B ∈ s := by rw [Finset.mem_filter, Finset.mem_powerset] exact ⟨subset_rfl, hB⟩ obtain ⟨B₀, hB₀s, hmin⟩ := Finset.exists_min_image s Finset.card ⟨B, hs⟩ rw [Finset.mem_filter, Finset.mem_powerset] at hB₀s refine ⟨B₀, hB₀s.1, hB₀s.2, fun A hAB₀ hA => ?_⟩ have hAs : A ∈ s := by rw [Finset.mem_filter, Finset.mem_powerset] exact ⟨hAB₀.trans hB₀s.1, hA⟩ exact Finset.eq_of_subset_of_card_le hAB₀ (hmin A hAs)