exists_hitting_set_of_no_large_antichain
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$.
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`.
uses
Finset.mem_filter.mpclassical 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
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`.
uses
Nat.le_zero.mp,Finset.card_eq_zero.mp,Finset.not_nonempty_emptyhave 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
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$.
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⟩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$.
uses
le_rflintro A hA exact key A.card A le_rfl hA
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$.
uses
Finset.mem_filter.mp,Finset.Subset.antisymmhave 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
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$.
uses
Classical.choose,Classical.choose_spec,Finset.card_image_le,Finset.card_attachlet 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
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.
uses
Finset.mem_image.mpr,Finset.mem_attach,Finset.mem_inter.mprrefine ⟨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`.
- In line 33, `omega` closes the arithmetic goal `B.card ≤ n` from `B.card < A.card` and `A.card ≤ n + 1` automatically using Presburger linear arithmetic.
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.
/-- 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⟩⟩