AFTD Auto-Formalizing Theoretical Domains

exists_hitting_set_of_no_large_antichain

theoremverified

Let G be a finite family of nonempty subsets of a finite set α, w a natural number, and suppose every subfamily H ⊆ G that is an antichain (no two distinct members contained in one another) has at most w members. Then there is a set S ⊆ α with at most w elements meeting every member of G.

Statement

theorem exists_hitting_set_of_no_large_antichain (α : Type*) [Fintype α] [DecidableEq α]
    (G : Finset (Finset α)) (w : ℕ) (hne : ∀ A ∈ G, A.Nonempty)
    (h : ∀ H : Finset (Finset α), H ⊆ G → (∀ A ∈ H, ∀ B ∈ H, A ≠ B → ¬ A ⊆ B ∧ ¬ B ⊆ A) → H.card ≤ w) :
    ∃ S : Finset α, S.card ≤ w ∧ ∀ A ∈ G, (A ∩ S).Nonempty
Source
step towards diamond_poset_ramsey_number_le
Verified
18 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 2
  • fan_ramsey_boundFor j ≥ 2 and k ≥ 1, every colouring of the subsets of Fin d with k colours, where d ≥ k(j-1)+1, contains a monochromatic induced copy of…
  • diamond_poset_ramsey_number_leFor all natural numbers j ≥ 2 and k ≥ 1, the k-color poset Ramsey number of the j-diamond DiamondPoset j is at most j * k.

The proof, explained

The proof selects the subcollection $M \subseteq G$ of all inclusion-minimal sets in $G$. Any two distinct minimal sets are incomparable under inclusion, so $M$ is an antichain and has at most $w$ members by assumption. By induction on set cardinality, every set in $G$ contains at least one minimal set in $M$. Choosing one element from each set in $M$ yields a set $S \subseteq \alpha$ of at most $w$ elements that hits every set in $G$.

  1. Define $M \subseteq G$ as the subcollection of inclusion-minimal sets in $G$.

    $M$ is defined by filtering $G$ for those sets $A$ that contain no strict subset $B \in G$. Membership in $M$ immediately implies membership in $G$ via `Finset.mem_filter.mp`.

    lines 6–8

    uses Finset.mem_filter.mp

      classical
      let M : Finset (Finset α) := G.filter (fun A => ∀ B ∈ G, ¬ B ⊂ A)
      have hMsub : M ⊆ G := fun A hA => (Finset.mem_filter.mp hA).1
  2. Base case of induction on cardinality: no set in $G$ can have size at most 0.

    To prove that every set in $G$ contains a minimal member, we set up an induction on an upper bound $n$ on set cardinality. When $n = 0$, any $A \in G$ with $|A| \le 0$ must satisfy $|A| = 0$ by `Nat.le_zero.mp` and hence $A = \emptyset$ by `Finset.card_eq_zero.mp`. But every member of $G$ is nonempty by hypothesis `hne`, which contradicts `Finset.not_nonempty_empty`.

    lines 9–20

    uses Nat.le_zero.mp, Finset.card_eq_zero.mp, Finset.not_nonempty_empty

      have hex_min : ∀ A ∈ G, ∃ B ∈ M, B ⊆ A := by
        have key : ∀ n, ∀ A, A.card ≤ n → A ∈ G → ∃ B ∈ M, B ⊆ A := by
          intro n
          induction n with
          | zero =>
            intro A hcard hA
            exfalso
            have h0 : A.card = 0 := Nat.le_zero.mp hcard
            have hempty : A = ∅ := Finset.card_eq_zero.mp h0
            have hneA : A.Nonempty := hne A hA
            rw [hempty] at hneA
            exact Finset.not_nonempty_empty hneA
  3. Induction step: any set $A \in G$ of cardinality at most $n + 1$ contains some minimal set in $M$.

    If $A \in M$, then $A$ contains itself by `Finset.Subset.refl`. Otherwise, $A \notin M$, which by `Finset.mem_filter.mpr` means $A$ is not minimal, so there is some $B \in G$ strictly contained in $A$. By `Finset.card_lt_card`, $|B| < |A| \le n + 1$, so $|B| \le n$ by linear arithmetic (`omega`). The induction hypothesis on $B$ gives a minimal set $B' \in M$ with $B' \subseteq B \subset A$.

    lines 21–35

    uses Finset.Subset.refl, Finset.mem_filter.mpr, Finset.card_lt_card

          | succ n ih =>
            intro A hcard hA
            by_cases hAM : A ∈ M
            · exact ⟨A, hAM, Finset.Subset.refl A⟩
            · have hnotmin : ¬ ∀ B ∈ G, ¬ B ⊂ A := by
                intro hc
                exact hAM (Finset.mem_filter.mpr ⟨hA, hc⟩)
              have hExists : ∃ B, B ∈ G ∧ B ⊂ A := by
                by_contra hc
                exact hnotmin (fun B hBG hBA => hc ⟨B, hBG, hBA⟩)
              obtain ⟨B, hBG, hBA⟩ := hExists
              have hlt : B.card < A.card := Finset.card_lt_card hBA
              have hle : B.card ≤ n := by omega
              obtain ⟨B', hB'M, hB'sub⟩ := ih B hle hBG
              exact ⟨B', hB'M, hB'sub.trans hBA.subset⟩
  4. Every set in $G$ contains a minimal member in $M$.

    Applying the inductive lemma `key` to any $A \in G$ with $n = |A|$ (using `le_rfl` for $|A| \le |A|$) yields a minimal set $B \in M$ with $B \subseteq A$.

    lines 36–37

    uses le_rfl

        intro A hA
        exact key A.card A le_rfl hA
  5. The minimal sets $M$ form an antichain, and therefore $|M| \le w$.

    Let $A, B \in M$ be distinct. If $A \subseteq B$, then since $A \ne B$, antisymmetry (`Finset.Subset.antisymm`) implies $A \subsetneq B$, contradicting the minimality of $B$ in $G$. By symmetry, $B \not\subseteq A$. Thus $M$ is an antichain contained in $G$, so the theorem's antichain-size hypothesis $h$ guarantees $|M| \le w$.

    lines 38–47

    uses Finset.mem_filter.mp, Finset.Subset.antisymm

      have hanti : ∀ A ∈ M, ∀ B ∈ M, A ≠ B → ¬ A ⊆ B ∧ ¬ B ⊆ A := by
        intro A hA B hB hAB
        obtain ⟨hAG, hAmin⟩ := Finset.mem_filter.mp hA
        obtain ⟨hBG, hBmin⟩ := Finset.mem_filter.mp hB
        constructor
        · intro hsub
          exact hBmin A hAG ⟨hsub, fun hBA' => hAB (Finset.Subset.antisymm hsub hBA')⟩
        · intro hsub
          exact hAmin B hBG ⟨hsub, fun hAB' => hAB (Finset.Subset.antisymm hAB' hsub)⟩
      have hMcard : M.card ≤ w := h M hMsub hanti
  6. Construct a candidate hitting set $S \subseteq \alpha$ of size at most $w$ by choosing one representative from each member of $M$.

    Because each set in $M \subseteq G$ is nonempty, `Classical.choose` and `Classical.choose_spec` pick an element $x(A) \in A$ for each $A \in M$. Defining $S$ as the image of $M$ under $x$, `Finset.card_image_le` and `Finset.card_attach` show that $|S| \le |M| \le w$.

    lines 48–55

    uses Classical.choose, Classical.choose_spec, Finset.card_image_le, Finset.card_attach

      let x : (A : Finset α) → A ∈ M → α := fun A hA => Classical.choose (hne A (hMsub hA))
      have hx_mem : ∀ (A : Finset α) (hA : A ∈ M), x A hA ∈ A :=
        fun A hA => Classical.choose_spec (hne A (hMsub hA))
      let S : Finset α := M.attach.image (fun p => x p.1 p.2)
      have hScard : S.card ≤ w := by
        calc S.card ≤ M.attach.card := Finset.card_image_le
          _ = M.card := Finset.card_attach
          _ ≤ w := hMcard
  7. The set $S$ intersects every set in $G$, which completes the proof.

    Given any $A \in G$, there exists a minimal set $B \in M$ such that $B \subseteq A$. The chosen representative $x(B)$ belongs to $B \subseteq A$ and also belongs to $S$ by `Finset.mem_image.mpr` and `Finset.mem_attach`. Therefore $x(B) \in A \cap S$ by `Finset.mem_inter.mpr`, confirming that $A \cap S$ is nonempty.

    lines 56–63

    uses Finset.mem_image.mpr, Finset.mem_attach, Finset.mem_inter.mpr

      refine ⟨S, hScard, ?_⟩
      intro A hA
      obtain ⟨B, hBM, hBA⟩ := hex_min A hA
      have hxmem : x B hBM ∈ B := hx_mem B hBM
      have hxS : x B hBM ∈ S := by
        apply Finset.mem_image.mpr
        exact ⟨⟨B, hBM⟩, Finset.mem_attach M ⟨B, hBM⟩, rfl⟩
      exact ⟨x B hBM, Finset.mem_inter.mpr ⟨hBA hxmem, hxS⟩⟩
Finset.mem_filter.mp
An element of a filtered finset `s.filter p` belongs to `s` and satisfies `p`.
Nat.le_zero.mp
If a natural number is at most 0, it is equal to 0.
Finset.card_eq_zero.mp
A finset with cardinality 0 is the empty set.
Finset.not_nonempty_empty
The empty finset has no elements (is not nonempty).
Finset.Subset.refl
Every set is a subset of itself.
Finset.mem_filter.mpr
If an element of `s` satisfies `p`, it belongs to `s.filter p`.
Finset.card_lt_card
A proper subset of a finite set has strictly smaller cardinality.
le_rfl
Every element is less than or equal to itself in a preorder.
Finset.Subset.antisymm
Two sets that are subsets of each other are equal.
Classical.choose
Given a proof that an element with a property exists, returns such an element.
Classical.choose_spec
The element returned by `Classical.choose` satisfies the given property.
Finset.card_image_le
The cardinality of the image of a finset under a function is at most the cardinality of the original finset.
Finset.card_attach
The finset of elements bundled with proofs of membership has the same cardinality as the underlying finset.
Finset.mem_attach
Every element bundled with its membership proof belongs to `s.attach`.
Finset.mem_image.mpr
If `a ∈ s` and `f a = b`, then `b ∈ s.image f`.
Finset.mem_inter.mpr
If `x ∈ A` and `x ∈ B`, then `x ∈ A ∩ B`.

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

/-- A family of nonempty finite sets with no antichain larger than w has a hitting set of size at most w, obtained by picking one element from each ⊆-minimal member. -/theorem exists_hitting_set_of_no_large_antichain (α : Type*) [Fintype α] [DecidableEq α]    (G : Finset (Finset α)) (w : ℕ) (hne : ∀ A ∈ G, A.Nonempty)    (h : ∀ H : Finset (Finset α), H ⊆ G → (∀ A ∈ H, ∀ B ∈ H, A ≠ B → ¬ A ⊆ B ∧ ¬ B ⊆ A) → H.card ≤ w) :    ∃ S : Finset α, S.card ≤ w ∧ ∀ A ∈ G, (A ∩ S).Nonempty := by  classical  let M : Finset (Finset α) := G.filter (fun A => ∀ B ∈ G, ¬ B ⊂ A)  have hMsub : M ⊆ G := fun A hA => (Finset.mem_filter.mp hA).1  have hex_min : ∀ A ∈ G, ∃ B ∈ M, B ⊆ A := by    have key : ∀ n, ∀ A, A.card ≤ n → A ∈ G → ∃ B ∈ M, B ⊆ A := by      intro n      induction n with      | zero =>        intro A hcard hA        exfalso        have h0 : A.card = 0 := Nat.le_zero.mp hcard        have hempty : A = ∅ := Finset.card_eq_zero.mp h0        have hneA : A.Nonempty := hne A hA        rw [hempty] at hneA        exact Finset.not_nonempty_empty hneA      | succ n ih =>        intro A hcard hA        by_cases hAM : A ∈ M        · exact ⟨A, hAM, Finset.Subset.refl A⟩        · have hnotmin : ¬ ∀ B ∈ G, ¬ B ⊂ A := by            intro hc            exact hAM (Finset.mem_filter.mpr ⟨hA, hc⟩)          have hExists : ∃ B, B ∈ G ∧ B ⊂ A := by            by_contra hc            exact hnotmin (fun B hBG hBA => hc ⟨B, hBG, hBA⟩)          obtain ⟨B, hBG, hBA⟩ := hExists          have hlt : B.card < A.card := Finset.card_lt_card hBA          have hle : B.card ≤ n := by omega          obtain ⟨B', hB'M, hB'sub⟩ := ih B hle hBG          exact ⟨B', hB'M, hB'sub.trans hBA.subset⟩    intro A hA    exact key A.card A le_rfl hA  have hanti : ∀ A ∈ M, ∀ B ∈ M, A ≠ B → ¬ A ⊆ B ∧ ¬ B ⊆ A := by    intro A hA B hB hAB    obtain ⟨hAG, hAmin⟩ := Finset.mem_filter.mp hA    obtain ⟨hBG, hBmin⟩ := Finset.mem_filter.mp hB    constructor    · intro hsub      exact hBmin A hAG ⟨hsub, fun hBA' => hAB (Finset.Subset.antisymm hsub hBA')⟩    · intro hsub      exact hAmin B hBG ⟨hsub, fun hAB' => hAB (Finset.Subset.antisymm hAB' hsub)⟩  have hMcard : M.card ≤ w := h M hMsub hanti  let x : (A : Finset α) → A ∈ M → α := fun A hA => Classical.choose (hne A (hMsub hA))  have hx_mem : ∀ (A : Finset α) (hA : A ∈ M), x A hA ∈ A :=    fun A hA => Classical.choose_spec (hne A (hMsub hA))  let S : Finset α := M.attach.image (fun p => x p.1 p.2)  have hScard : S.card ≤ w := by    calc S.card ≤ M.attach.card := Finset.card_image_le      _ = M.card := Finset.card_attach      _ ≤ w := hMcard  refine ⟨S, hScard, ?_⟩  intro A hA  obtain ⟨B, hBM, hBA⟩ := hex_min A hA  have hxmem : x B hBM ∈ B := hx_mem B hBM  have hxS : x B hBM ∈ S := by    apply Finset.mem_image.mpr    exact ⟨⟨B, hBM⟩, Finset.mem_attach M ⟨B, hBM⟩, rfl⟩  exact ⟨x B hBM, Finset.mem_inter.mpr ⟨hBA hxmem, hxS⟩⟩
See it in the graphDiscuss this resultChallenge it