pairwiseDisjoint_k_sum_of_isAdmissible
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₂.
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).
uses
Finset.disjoint_leftintro k₁ k₂ hne rw [Finset.disjoint_left] intro x hx1 hx2
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.
uses
Finset.mem_image.mp,Finset.mem_powersetCardrcases 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
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).
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- 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