AFTD Auto-Formalizing Theoretical Domains

finset_midpoint_balanced_card_ge_three

theoremverified

Every midpoint-balanced finite subset of an additive commutative monoid has cardinality at least 3.

Statement

theorem finset_midpoint_balanced_card_ge_three {G : Type*} [AddCommMonoid G] [DecidableEq G]
    (B : Finset G) (hB : finset_is_midpoint_balanced B) : 3 ≤ B.card
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

By definition, a midpoint-balanced set $B$ is nonempty, so it contains at least one element $b$. The balancing condition applied to $b$ yields two other elements $u, v \in B$ such that $b, u, v$ are pairwise distinct. Consequently, the three-element subset $\{b, u, v\}$ is contained in $B$, which implies $|B| \ge 3$.

  1. There exist three distinct elements $b, u, v \in B$.

    Because $B$ is midpoint-balanced, it is nonempty, so we can pick an element $b \in B$. Applying the midpoint-balanced property to $b$ gives elements $u, v \in B$ with $u \neq b$, $v \neq b$, and $u \neq v$ (such that $b + b = u + v$).

    lines 4–5

      rcases hB with ⟨⟨b, hb⟩, h⟩
      rcases h b hb with ⟨u, hu, v, hv, hub, hvb, huv, -⟩
  2. $\{b, u, v\} \subseteq B$

    For any $x \in \{b, u, v\}$, rewriting the membership condition using Finset.mem_insert and Finset.mem_singleton shows that $x = b$, $x = u$, or $x = v$. In each case, $x \in B$ follows from $b \in B$, $u \in B$, or $v \in B$.

    lines 6–12

    uses Finset.mem_insert, Finset.mem_singleton

      have hsub : {b, u, v} ⊆ B := by
        intro x hx
        simp only [Finset.mem_insert, Finset.mem_singleton] at hx
        rcases hx with rfl | rfl | rfl
        · exact hb
        · exact hu
        · exact hv
  3. The set $\{b, u, v\}$ has cardinality 3.

    We compute the size of the set by successively stripping elements using Finset.card_insert_of_notMem. Since $u \neq v$, $u \notin \{v\}$, so $|\{u, v\}| = |\{v\}| + 1 = 2$. Similarly, since $b \neq u$ and $b \neq v$, $b \notin \{u, v\}$, so $|\{b, u, v\}| = |\{u, v\}| + 1 = 3$.

    lines 13–18

    uses Finset.card_insert_of_notMem

      have hcard : ({b, u, v} : Finset G).card = 3 := by
        rw [Finset.card_insert_of_notMem]
        · rw [Finset.card_insert_of_notMem]
          · simp
          · simp [huv]
        · simp [hub.symm, hvb.symm]
  4. $3 \le |B|$

    Rewriting 3 as $|\{b, u, v\}|$, the inequality $|\{b, u, v\}| \le |B|$ follows directly by Finset.card_le_card from the inclusion $\{b, u, v\} \subseteq B$.

    lines 19–20

    uses Finset.card_le_card

      rw [← hcard]
      exact Finset.card_le_card hsub
Finset.mem_insert
An element $a$ belongs to the set formed by inserting $b$ into $s$ if and only if $a = b$ or $a \in s$.
Finset.mem_singleton
An element $b$ belongs to the singleton set $\{a\}$ if and only if $b = a$.
Finset.card_insert_of_notMem
Inserting an element $a$ into a finite set $s$ that does not contain $a$ yields a set of cardinality $|s| + 1$.
Finset.card_le_card
If a finite set $s$ is a subset of $t$, then $|s| \le |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 subset of an additive commutative monoid has cardinality at least 3. -/theorem finset_midpoint_balanced_card_ge_three {G : Type*} [AddCommMonoid G] [DecidableEq G]    (B : Finset G) (hB : finset_is_midpoint_balanced B) : 3 ≤ B.card := by  rcases hB with ⟨⟨b, hb⟩, h⟩  rcases h b hb with ⟨u, hu, v, hv, hub, hvb, huv, -⟩  have hsub : {b, u, v} ⊆ B := by    intro x hx    simp only [Finset.mem_insert, Finset.mem_singleton] at hx    rcases hx with rfl | rfl | rfl    · exact hb    · exact hu    · exact hv  have hcard : ({b, u, v} : Finset G).card = 3 := by    rw [Finset.card_insert_of_notMem]    · rw [Finset.card_insert_of_notMem]      · simp      · simp [huv]    · simp [hub.symm, hvb.symm]  rw [← hcard]  exact Finset.card_le_card hsub
See it in the graphDiscuss this resultChallenge it