AFTD Auto-Formalizing Theoretical Domains

op_462_is_least_iff

theoremverifiedoriginal

For every natural number m, m is the least element of the set of cardinalities of finite counterexamples to Gale's conjecture in dimension 3 if and only if there exists a finite counterexample of cardinality m and min_gale_counterexample_card_three is equal to m.

Statement

theorem op_462_is_least_iff (m : ℕ) :
    IsLeast {k : ℕ | ∃ V : Finset (EuclideanSpace ℝ (Fin 3)), V.card = k ∧ is_gale_counterexample_three V} m ↔
    (∃ V : Finset (EuclideanSpace ℝ (Fin 3)), V.card = m ∧ is_gale_counterexample_three V) ∧
    min_gale_counterexample_card_three = m
Related work
folklore
Verified
24 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • min_gale_counterexample_card_threeThe minimum cardinality min_gale_counterexample_card_three of a finite counterexample to Gale's conjecture in dimension 3 is the infimum…
  • is_gale_counterexample_threeA finite subset V of the 3-dimensional Euclidean space EuclideanSpace ℝ (Fin 3) is a counterexample to Gale's conjecture in dimension 3…

Read back from the Lean

For any natural number $m$, $m$ is the least element of the set of all $k \in \mathbb{N}$ such that there exists a finite subset $V \subset \mathbb{R}^3$ (as EuclideanSpace ℝ (Fin 3)) with cardinality $k$ satisfying is_gale_counterexample_three V, if and only if: 1. There exists a finite subset $V \subset \mathbb{R}^3$ with cardinality $m$ satisfying is_gale_counterexample_three V, and 2. min_gale_counterexample_card_three = m.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

The theorem characterizes when a natural number m is the least cardinality of a 3D Gale counterexample, showing this holds if and only if such a counterexample exists and m equals the infimum of all such cardinalities. In the forward direction, being the least element implies m is in the set (making it nonempty), and antisymmetry shows m equals the infimum because the infimum is at most m and, as an element of the set itself, at least m. In the reverse direction, an element that equals the set's infimum is automatically a lower bound for the set, and thus its least element.

  1. In the forward direction, an m-point counterexample exists, and it remains to show that min_gale_counterexample_card_three = m.

    We split the bi-implication into two directions. For the forward direction, we assume that m is the least element of the set S of counterexample cardinalities. By definition of `IsLeast`, m belongs to S, which means an m-point counterexample exists. This supplies the first conjunct of the goal, leaving min_gale_counterexample_card_three = m to prove.

    lines 6–8

      constructor
      · intro h
        refine ⟨h.1, ?_⟩
  2. min_gale_counterexample_card_three = m, completing the forward implication.

    Unfolding min_gale_counterexample_card_three expresses it as sInf S. Because m ∈ S, the set S is nonempty. By antisymmetry of ≤ (`le_antisymm`), it suffices to show sInf S ≤ m and m ≤ sInf S. The first inequality holds by `Nat.sInf_le` since m ∈ S. For the second, since S is nonempty, sInf S ∈ S by `Nat.sInf_mem`; then m ≤ sInf S follows because m is a lower bound for S.

    lines 9–12

    uses le_antisymm, Nat.sInf_le, Nat.sInf_mem

        unfold min_gale_counterexample_card_three
        have hne : ({k : ℕ | ∃ V : Finset (EuclideanSpace ℝ (Fin 3)), V.card = k ∧ is_gale_counterexample_three V}).Nonempty := ⟨m, h.1⟩
        refine le_antisymm (Nat.sInf_le h.1) ?_
        exact @h.2 (sInf {k : ℕ | ∃ V : Finset (EuclideanSpace ℝ (Fin 3)), V.card = k ∧ is_gale_counterexample_three V}) (Nat.sInf_mem hne)
  3. In the reverse direction, m belongs to the set of counterexample cardinalities, leaving only the lower bound property to establish.

    For the reverse implication, we assume both that an m-point counterexample exists (so m ∈ S) and that min_gale_counterexample_card_three = m. To prove that m is the least element of S, we provide m ∈ S directly from the assumption, which leaves showing that m is a lower bound for S.

    lines 13–14

      · intro ⟨hm, hmin⟩
        refine ⟨hm, ?_⟩
  4. m is a lower bound for the set of counterexample cardinalities, completing the proof.

    Let b be any cardinality in S. We substitute m = min_gale_counterexample_card_three = sInf S. By `Nat.sInf_le`, the infimum of a set of natural numbers is at most any element of the set, so sInf S ≤ b, which gives m ≤ b.

    lines 15–17

    uses Nat.sInf_le

        intro b hb
        rw [show m = min_gale_counterexample_card_three from hmin.symm]
        exact Nat.sInf_le hb
le_antisymm
In a partially ordered type, if a ≤ b and b ≤ a, then a = b.
Nat.sInf_le
For any set s of natural numbers and any m ∈ s, the infimum of s is at most m.
Nat.sInf_mem
If a set s of natural numbers is nonempty, its infimum belongs to s.

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

/-- A natural number m is the least cardinality of a counterexample to Gale's conjecture in dimension 3 iff an m-point counterexample exists and min_gale_counterexample_card_three = m. -/theorem op_462_is_least_iff (m : ℕ) :    IsLeast {k : ℕ | ∃ V : Finset (EuclideanSpace ℝ (Fin 3)), V.card = k ∧ is_gale_counterexample_three V} m ↔    (∃ V : Finset (EuclideanSpace ℝ (Fin 3)), V.card = m ∧ is_gale_counterexample_three V) ∧    min_gale_counterexample_card_three = m := by  constructor  · intro h    refine ⟨h.1, ?_⟩    unfold min_gale_counterexample_card_three    have hne : ({k : ℕ | ∃ V : Finset (EuclideanSpace ℝ (Fin 3)), V.card = k ∧ is_gale_counterexample_three V}).Nonempty := ⟨m, h.1⟩    refine le_antisymm (Nat.sInf_le h.1) ?_    exact @h.2 (sInf {k : ℕ | ∃ V : Finset (EuclideanSpace ℝ (Fin 3)), V.card = k ∧ is_gale_counterexample_three V}) (Nat.sInf_mem hne)  · intro ⟨hm, hmin⟩    refine ⟨hm, ?_⟩    intro b hb    rw [show m = min_gale_counterexample_card_three from hmin.symm]    exact Nat.sInf_le hb
See it in the graphDiscuss this resultChallenge it