five_subsets_card_le_three_comparable
Five subsets of a set with at most three elements cannot be pairwise incomparable: two of them are nested.
Statement
theorem five_subsets_card_le_three_comparable {α : Type*} [DecidableEq α] (X : Finset α) (hX : X.card ≤ 3) (M : Fin 5 → Finset α) (hM : ∀ i, M i ⊆ X) : ∃ i i', i ≠ i' ∧ (M i ⊆ M i' ∨ M i' ⊆ M i)
- Source
- step towards op_270_five_diamond_poset_ramsey_number
- Verified
- 18 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext
The proof, explained
The proof proceeds by contradiction using Sperner's theorem. If five subsets of a set X with |X| ≤ 3 were pairwise incomparable, their restrictions to the subtype X would form an antichain of size 5 in the power set of X. By Sperner's theorem, any antichain in a ground set of size |X| has size at most the central binomial coefficient (|X| choose ⌊|X|/2⌋). For |X| ≤ 3, this coefficient is at most 3, contradicting the existence of an antichain of size 5.
Assume for contradiction that no two distinct subsets in the collection are comparable by inclusion.
We set up a proof by contradiction. Negating the existential claim gives the assumption that for any two distinct indices i ≠ j, neither M i ⊆ M j nor M j ⊆ M i.
by_contra h push Not at h
Restrict the universe to the ground set X and show that the five restricted subsets are pairwise distinct.
We let β be the subtype of elements belonging to X, and define N i to be the restriction of M i to β. To show N is injective, suppose N i = N j. Mapping both back into the ambient type via Finset.subtype_map_of_mem and applying congrArg recovers M i = M j. If i ≠ j, reflexivity of inclusion (Finset.Subset.rfl) would mean M i ⊆ M j, contradicting the incomparability assumption. Thus i = j.
uses
Finset.subtype_map_of_mem,congrArg,Finset.Subset.rfllet β := ↥X let N : Fin 5 → Finset β := fun i => (M i).subtype (· ∈ X) have hN_inj : Function.Injective N := by intro i j hij have hM_eq : M i = M j := by rw [← Finset.subtype_map_of_mem (hM i), ← Finset.subtype_map_of_mem (hM j)] exact congrArg (Finset.map (Function.Embedding.subtype _)) hij by_contra hne exact (h i j hne).1 (hM_eq ▸ Finset.Subset.rfl)
The family 𝒜 = {N 0, …, N 4} contains exactly five distinct sets.
We define 𝒜 as the image of the five-element index set under N. Since N is injective, Finset.card_image_of_injective ensures that the size of 𝒜 equals the size of Fin 5, which is 5.
uses
Finset.card_image_of_injectiveset 𝒜 : Finset (Finset β) := Finset.univ.image N have h_card : 𝒜.card = 5 := by rw [Finset.card_image_of_injective _ hN_inj] simp
The family 𝒜 forms an antichain under inclusion.
Take two distinct sets A, B ∈ 𝒜. By Finset.mem_image, A = N i and B = N j for some distinct indices i ≠ j. If A ⊆ B, then every x ∈ M i lifts into N i by Finset.mem_subtype, hence belongs to N j, and unpacks to x ∈ M j via Finset.mem_subtype. This would mean M i ⊆ M j, which contradicts the incomparability hypothesis. Hence no two sets in 𝒜 are comparable.
uses
Finset.mem_image,Finset.mem_subtypehave h_anti : IsAntichain (fun x1 x2 => x1 ⊆ x2) (𝒜 : Set (Finset β)) := by intro A hA B hB hne change A ∈ Finset.univ.image N at hA change B ∈ Finset.univ.image N at hB rw [Finset.mem_image] at hA hB rcases hA with ⟨i, -, rfl⟩ rcases hB with ⟨j, -, rfl⟩ have hij : i ≠ j := by rintro rfl exact hne rfl intro hsub have hM_sub : M i ⊆ M j := by intro x hx have hxX : x ∈ X := hM i hx have hxN : (⟨x, hxX⟩ : β) ∈ N i := by dsimp [N] rw [Finset.mem_subtype] exact hx have := hsub hxN dsimp [N] at this rw [Finset.mem_subtype] at this exact this exact (h i j hij).1 hM_sub
By Sperner's theorem, 5 ≤ (X.card choose (X.card / 2)).
Applying Sperner's theorem (IsAntichain.sperner) to the antichain 𝒜 shows that |𝒜| ≤ (|β| choose (|β| / 2)). Since |β| = X.card by Fintype.card_coe and |𝒜| = 5, this yields the inequality 5 ≤ (X.card choose (X.card / 2)).
uses
IsAntichain.sperner,Fintype.card_coehave hsperner := IsAntichain.sperner h_anti have hcard_beta : Fintype.card β = X.card := Fintype.card_coe X rw [hcard_beta, h_card] at hsperner
For any set X with at most three elements, the middle binomial coefficient is at most 3.
Since X.card ≤ 3, the cardinality can only be 0, 1, 2, or 3. Exhaustive check of each case shows that (0 choose 0) = 1, (1 choose 0) = 1, (2 choose 1) = 2, and (3 choose 1) = 3, all of which are at most 3.
have hchoose : X.card.choose (X.card / 2) ≤ 3 := by interval_cases X.card <;> decide
A contradiction is reached, completing the proof.
Linear integer arithmetic (omega) derives False from the contradictory inequalities 5 ≤ (X.card choose (X.card / 2)) and (X.card choose (X.card / 2)) ≤ 3, which together imply 5 ≤ 3.
omega
Finset.subtype_map_of_mem- Mapping a subtype finset back to the ambient finset via the subtype inclusion recovers the original set, provided every element satisfies the subtype predicate.
congrArg- If two inputs are equal, applying any function to both produces equal values.
Finset.Subset.rfl- Every finite set is a subset of itself.
Finset.card_image_of_injective- An injective function preserves the cardinality of a finite set when taking its image.
Finset.mem_image- An element is in the image of a finite set under a function if and only if it is the image of some element of that set.
Finset.mem_subtype- An element of a subtype belongs to the subtype-restricted finset if and only if its underlying element belongs to the original finset.
IsAntichain.sperner- Sperner's theorem: the size of any antichain of subsets of a finite type is at most the middle binomial coefficient of the ground set's cardinality.
Fintype.card_coe- The cardinality of a finite set viewed as a subtype equals its cardinality as a finset.
- In informal mathematics, a collection of subsets of X is immediately treated as a family of subsets of a set of size |X|. In Lean, Sperner's theorem (IsAntichain.sperner) is formulated for subsets of a finite type. Consequently, lines 7–15 and 31–41 perform the formal bookkeeping of restricting to the subtype β = X, showing that this restriction is injective (so the family still has 5 members), and verifying that inclusion in β corresponds to inclusion in the ambient type.
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.
/-- Sperner bound for a 3-element ground set: five subsets of a set of size at most 3 contain two comparable members. -/theorem five_subsets_card_le_three_comparable {α : Type*} [DecidableEq α] (X : Finset α) (hX : X.card ≤ 3) (M : Fin 5 → Finset α) (hM : ∀ i, M i ⊆ X) : ∃ i i', i ≠ i' ∧ (M i ⊆ M i' ∨ M i' ⊆ M i) := by by_contra h push Not at h let β := ↥X let N : Fin 5 → Finset β := fun i => (M i).subtype (· ∈ X) have hN_inj : Function.Injective N := by intro i j hij have hM_eq : M i = M j := by rw [← Finset.subtype_map_of_mem (hM i), ← Finset.subtype_map_of_mem (hM j)] exact congrArg (Finset.map (Function.Embedding.subtype _)) hij by_contra hne exact (h i j hne).1 (hM_eq ▸ Finset.Subset.rfl) set 𝒜 : Finset (Finset β) := Finset.univ.image N have h_card : 𝒜.card = 5 := by rw [Finset.card_image_of_injective _ hN_inj] simp have h_anti : IsAntichain (fun x1 x2 => x1 ⊆ x2) (𝒜 : Set (Finset β)) := by intro A hA B hB hne change A ∈ Finset.univ.image N at hA change B ∈ Finset.univ.image N at hB rw [Finset.mem_image] at hA hB rcases hA with ⟨i, -, rfl⟩ rcases hB with ⟨j, -, rfl⟩ have hij : i ≠ j := by rintro rfl exact hne rfl intro hsub have hM_sub : M i ⊆ M j := by intro x hx have hxX : x ∈ X := hM i hx have hxN : (⟨x, hxX⟩ : β) ∈ N i := by dsimp [N] rw [Finset.mem_subtype] exact hx have := hsub hxN dsimp [N] at this rw [Finset.mem_subtype] at this exact this exact (h i j hij).1 hM_sub have hsperner := IsAntichain.sperner h_anti have hcard_beta : Fintype.card β = X.card := Fintype.card_coe X rw [hcard_beta, h_card] at hsperner have hchoose : X.card.choose (X.card / 2) ≤ 3 := by interval_cases X.card <;> decide omega