AFTD Auto-Formalizing Theoretical Domains

not_isAdmissible_one_two_three

theoremverified

The set {1, 2, 3} is not an admissible set of natural numbers.

Statement

theorem not_isAdmissible_one_two_three : ¬ IsAdmissible {1, 2, 3}
Source
arXiv:2610.34372, Definition 1.1
Verified
30 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • IsAdmissibleA finite set A of positive integers is admissible if for any two subsets B and C of A, if the sum of elements in B equals the sum of…

Read back from the Lean

The finite set of natural numbers {1, 2, 3} is not admissible (that is, there exist two subsets of {1, 2, 3} that have the same sum of elements but different cardinalities).

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 proof proceeds by contradiction. Assuming {1, 2, 3} is an admissible set, any two of its subsets with the same sum must have the same cardinality. However, the subsets {1, 2} and {3} both have element sum 3 but have different cardinalities (2 and 1), which contradicts the admissibility condition.

  1. Assume, for contradiction, that {1, 2, 3} is admissible.

    We assume the negation of the goal, introducing the hypothesis h that {1, 2, 3} satisfies the admissibility condition: any two subsets with equal sums must have equal cardinality.

    line 3

      intro h
  2. The subsets {1, 2} and {3} are subsets of {1, 2, 3} and have the same element sum.

    The set inclusions {1, 2} ⊆ {1, 2, 3} and {3} ⊆ {1, 2, 3}, as well as the equality of their element sums (1 + 2 = 3), are verified by direct finite computation via `decide`.

    lines 4–6

      have hB : ({1, 2} : Finset ℕ) ⊆ {1, 2, 3} := by decide
      have hC : ({3} : Finset ℕ) ⊆ {1, 2, 3} := by decide
      have hsum : ({1, 2} : Finset ℕ).sum id = ({3} : Finset ℕ).sum id := by decide
  3. The cardinalities of {1, 2} and {3} must be equal: |{1, 2}| = |{3}|.

    We specialize the admissibility hypothesis h to the subsets {1, 2} and {3}, using their inclusion proofs and equal sums to conclude that their cardinalities are equal.

    line 7

      have hcard := h {1, 2} {3} hB hC hsum
  4. A contradiction is reached, completing the proof.

    Reverting the equality of cardinalities into the goal produces the implication |{1, 2}| = |{3}| → False. Since |{1, 2}| = 2 and |{3}| = 1, `decide` evaluates the arithmetic falsehood 2 = 1 to False and closes the proof.

    lines 8–9

      revert hcard
      decide

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

/-- The set {1, 2, 3} is not admissible because {1, 2} and {3} have the same sum 3 but different cardinalities. -/theorem not_isAdmissible_one_two_three : ¬ IsAdmissible {1, 2, 3} := by  intro h  have hB : ({1, 2} : Finset ℕ) ⊆ {1, 2, 3} := by decide  have hC : ({3} : Finset ℕ) ⊆ {1, 2, 3} := by decide  have hsum : ({1, 2} : Finset ℕ).sum id = ({3} : Finset ℕ).sum id := by decide  have hcard := h {1, 2} {3} hB hC hsum  revert hcard  decide
See it in the graphDiscuss this resultChallenge it