AFTD Auto-Formalizing Theoretical Domains

finset_exists_minimal_midpoint_balanced

theoremverified

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

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.

  1. 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`.

    lines 6–10

    uses Finset.mem_filter, Finset.mem_powerset, subset_rfl

      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⟩
  2. 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'|`.

    lines 11–12

    uses Finset.exists_min_image, Finset.mem_filter, Finset.mem_powerset

      obtain ⟨B₀, hB₀s, hmin⟩ := Finset.exists_min_image s Finset.card ⟨B, hs⟩
      rw [Finset.mem_filter, Finset.mem_powerset] at hB₀s
  3. 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₀`.

    line 13

      refine ⟨B₀, hB₀s.1, hB₀s.2, fun A hAB₀ hA => ?_⟩
  4. 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`.

    lines 14–16

    uses Finset.mem_filter, Finset.mem_powerset

      have hAs : A ∈ s := by
        rw [Finset.mem_filter, Finset.mem_powerset]
        exact ⟨hAB₀.trans hB₀s.1, hA⟩
  5. `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₀`.

    line 17

    uses Finset.eq_of_subset_of_card_le

      exact 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`.

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

/-- 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)
See it in the graphDiscuss this resultChallenge it