AFTD Auto-Formalizing Theoretical Domains

pairwiseDisjoint_k_sum_of_isAdmissible

theoremverified

If A is an admissible set of positive integers, then for any distinct integers k₁ and k₂, the set of sums of k₁-element subsets of A and the set of sums of k₂-element subsets of A are disjoint.

Statement

theorem pairwiseDisjoint_k_sum_of_isAdmissible {A : Finset ℕ} (hA : IsAdmissible A) :
    Pairwise fun k₁ k₂ =>
      Disjoint ((A.powersetCard k₁).image (Finset.sum · id))
               ((A.powersetCard k₂).image (Finset.sum · id))
Source
arXiv:2610.34372, Proof of Lemma 2.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…
Used by 1
  • admissible_card_sq_add_five_leIf A is a nonempty admissible subset of {1, ..., N}, then the square of the cardinality of A plus 5 is at most 6 times N.

Read back from the Lean

For any finite set of natural numbers $A$ such that $A$ is admissible (meaning any two subsets of $A$ that have the same sum also have the same cardinality), the family of sets of subset sums indexed by subset size is pairwise disjoint: that is, for all natural numbers $k_1 \neq k_2$, the set of sums of all $k_1$-element subsets of $A$ and the set of sums of all $k_2$-element subsets of $A$ are disjoint.

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 is proved by contradiction. If the sets of sums for two distinct subset sizes k₁ ≠ k₂ were not disjoint, there would exist two subsets B, C ⊆ A with sizes |B| = k₁ and |C| = k₂ that have the same sum. However, the definition of an admissible set requires that any two subsets with equal sums must have equal cardinality, forcing k₁ = k₂, which contradicts k₁ ≠ k₂.

  1. To establish pairwise disjointness, it suffices to show that no integer can simultaneously be a sum of a k₁-element subset and of a k₂-element subset for distinct k₁ ≠ k₂.

    We introduce distinct subset sizes k₁ ≠ k₂ (hne). By Finset.disjoint_left, proving that the two sets of subset sums are disjoint reduces to showing that no integer belongs to both. We assume for contradiction that some integer x belongs to both sets (hx1, hx2).

    lines 6–8

    uses Finset.disjoint_left

      intro k₁ k₂ hne
      rw [Finset.disjoint_left]
      intro x hx1 hx2
  2. There exist subsets B, C ⊆ A with |B| = k₁, |C| = k₂, and ∑ B = ∑ C.

    Since x belongs to the image of the k₁-element subsets under the sum map, Finset.mem_image.mp provides a subset B of size k₁ with ∑ B = x. Similarly, x being in the image of the k₂-element subsets provides a subset C of size k₂ with ∑ C = x. Rewriting with Finset.mem_powersetCard unpacks the conditions that B ⊆ A, |B| = k₁, C ⊆ A, and |C| = k₂, with ∑ C = ∑ B.

    lines 9–11

    uses Finset.mem_image.mp, Finset.mem_powersetCard

      rcases Finset.mem_image.mp hx1 with ⟨B, hB, rfl⟩
      rcases Finset.mem_image.mp hx2 with ⟨C, hC, hsum⟩
      rw [Finset.mem_powersetCard] at hB hC
  3. A contradiction is reached because the admissibility of A implies k₁ = k₂.

    Since A is admissible (hA), any two subsets of A with identical element sums must have the same cardinality, so |B| = |C|. Substituting |B| = k₁ and |C| = k₂ gives k₁ = k₂, directly contradicting the assumption k₁ ≠ k₂ (hne).

    lines 12–14

      have hcard := hA B C hB.1 hC.1 hsum.symm
      rw [hB.2, hC.2] at hcard
      exact hne hcard
Finset.disjoint_left
Two finite sets are disjoint if and only if no element belongs to both.
Finset.mem_image.mp
If an element belongs to the image of a set under a function, then it is the image of some element in that set.
Finset.mem_powersetCard
A finite set belongs to the powerset of size n of a set s if and only if it is a subset of s and has cardinality n.

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

/-- For an admissible set, the sets of k-element subset sums are pairwise disjoint for distinct k. -/theorem pairwiseDisjoint_k_sum_of_isAdmissible {A : Finset ℕ} (hA : IsAdmissible A) :    Pairwise fun k₁ k₂ =>      Disjoint ((A.powersetCard k₁).image (Finset.sum · id))               ((A.powersetCard k₂).image (Finset.sum · id)) := by  intro k₁ k₂ hne  rw [Finset.disjoint_left]  intro x hx1 hx2  rcases Finset.mem_image.mp hx1 with ⟨B, hB, rfl⟩  rcases Finset.mem_image.mp hx2 with ⟨C, hC, hsum⟩  rw [Finset.mem_powersetCard] at hB hC  have hcard := hA B C hB.1 hC.1 hsum.symm  rw [hB.2, hC.2] at hcard  exact hne hcard
See it in the graphDiscuss this resultChallenge it