AFTD Auto-Formalizing Theoretical Domains

five_subsets_card_le_three_comparable

theoremverified

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.

  1. 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.

    lines 5–6

      by_contra h
      push Not at h
  2. 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.

    lines 7–15

    uses Finset.subtype_map_of_mem, congrArg, Finset.Subset.rfl

      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)
  3. 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.

    lines 16–19

    uses Finset.card_image_of_injective

      set 𝒜 : Finset (Finset β) := Finset.univ.image N
      have h_card : 𝒜.card = 5 := by
        rw [Finset.card_image_of_injective _ hN_inj]
        simp
  4. 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.

    lines 20–42

    uses Finset.mem_image, Finset.mem_subtype

      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
  5. 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)).

    lines 43–45

    uses IsAntichain.sperner, Fintype.card_coe

      have hsperner := IsAntichain.sperner h_anti
      have hcard_beta : Fintype.card β = X.card := Fintype.card_coe X
      rw [hcard_beta, h_card] at hsperner
  6. 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.

    lines 46–47

      have hchoose : X.card.choose (X.card / 2) ≤ 3 := by
        interval_cases X.card <;> decide
  7. 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.

    line 48

      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.

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

/-- 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
See it in the graphDiscuss this resultChallenge it