linear_book_forces_center
In a finite linear family of sets all containing a fixed point, every transversal smaller than the family contains that point.
Statement
theorem linear_book_forces_center {α : Type*} [DecidableEq α] (H : Finset (Finset α)) (b : α) (C : Finset α) (hb : ∀ A ∈ H, b ∈ A) (hl : ∀ A ∈ H, ∀ B ∈ H, A ≠ B → (A ∩ B).card ≤ 1) (hh : ∀ A ∈ H, ¬Disjoint A C) (hc : C.card < H.card) : b ∈ C
- Source
- Related sunflower and triangle-kernel reductions: https://link.springer.com/article/10.1007/s00453-022-00986-0 and https://arxiv.org/abs/2308.16515. This is a structural helper for the triangle packing-cover campaign, with no claim of novelty.
- Verified
- 04 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 2
- linear_family_high_degree_neighborhood_obstructionIn a finite linear family, if B has more than q points and each point of B lies in more than q members, every set hitting all members that…
- linear_family_bounded_transversal_kernelGiven a finite linear set family, a transversal B, a subfamily P, and a cover budget q, retain P and at most q+1 sets through each point…
The proof, explained
The proof argues by contradiction: if the common point b were not in C, we could define an injection from the family H into C by selecting a point f(A) ∈ A ∩ C for each A ∈ H. If two distinct sets A and B produced the same point, then both b and f(A) would belong to A ∩ B; but since the family is linear, |A ∩ B| ≤ 1, forcing b = f(A) ∈ C, a contradiction. The injection then implies |H| ≤ |C|, contradicting |C| < |H|.
Assume for contradiction that b ∉ C.
We invoke classical logic and proceed by contradiction, assuming that the common point b does not belong to the transversal C.
classical by_contra hnThere exists a selection function f such that for every A ∈ H, f(A) ∈ A and f(A) ∈ C.
Since C is a transversal of H, every set A ∈ H has non-empty intersection with C (Finset.not_disjoint_iff.mp). Using Classical.choose, we define f(A) to be an element chosen from A ∩ C whenever A ∈ H (and b otherwise). By Classical.choose_spec, this choice satisfies f(A) ∈ A and f(A) ∈ C.
uses
Classical.choose,Classical.choose_spec,Finset.not_disjoint_iff.mplet f (A : Finset α) : α := if hA : A ∈ H then Classical.choose (Finset.not_disjoint_iff.mp (hh A hA)) else b have hf : ∀ A ∈ H, f A ∈ A ∧ f A ∈ C := by intro A hA simpa [f, hA] using Classical.choose_spec (Finset.not_disjoint_iff.mp (hh A hA))
|H| ≤ |C|.
By Finset.card_le_card_of_injOn, |H| ≤ |C| follows if f maps H into C and is injective on H. The mapping condition holds because f(A) ∈ C for all A ∈ H. For injectivity, assume for contradiction that distinct sets A, B ∈ H have f(A) = f(B). By linearity, |A ∩ B| ≤ 1, so any two elements in A ∩ B are identical (Finset.card_le_one_iff.mp). But b ∈ A ∩ B because b belongs to every set in H, and f(A) ∈ A ∩ B because f(A) ∈ A and f(A) = f(B) ∈ B (both via Finset.mem_inter.mpr). Hence b = f(A). But f(A) ∈ C, which forces b ∈ C, contradicting the assumption b ∉ C. Thus f is injective on H, establishing |H| ≤ |C|.
uses
Finset.card_le_card_of_injOn,Finset.card_le_one_iff.mp,Finset.mem_inter.mprhave hcard : H.card ≤ C.card := by apply Finset.card_le_card_of_injOn f · intro A hA exact (hf A hA).2 · intro A hA B hB hab by_contra hne have hu : ∀ {a b : α}, a ∈ A ∩ B → b ∈ A ∩ B → a = b := Finset.card_le_one_iff.mp (hl A hA B hB hne) have hbi : b ∈ A ∩ B := Finset.mem_inter.mpr ⟨hb A hA, hb B hB⟩ have hfi : f A ∈ A ∩ B := Finset.mem_inter.mpr ⟨(hf A hA).1, by rw [hab]; exact (hf B hB).1⟩ have heq : b = f A := hu hbi hfi apply hn rw [heq] exact (hf A hA).2
Contradiction.
The inequality |H| ≤ |C| directly contradicts the hypothesis |C| < |H|. Linear integer arithmetic (omega) closes the goal.
omega
Classical.choose- Given a proof that an element satisfying a predicate exists, returns such an element.
Classical.choose_spec- The element returned by Classical.choose satisfies the given predicate.
Finset.not_disjoint_iff.mp- Two finite sets are not disjoint if and only if there is an element belonging to both.
Finset.card_le_card_of_injOn- If a function maps a finite set s into a finite set t and is injective on s, then |s| ≤ |t|.
Finset.card_le_one_iff.mp- A finite set has cardinality at most 1 if and only if any two of its elements are equal.
Finset.mem_inter.mpr- If an element belongs to both set s₁ and set s₂, then it belongs to their intersection s₁ ∩ s₂.
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.
open Finsetset_option maxHeartbeats 1000000theorem linear_book_forces_center {α : Type*} [DecidableEq α] (H : Finset (Finset α)) (b : α) (C : Finset α) (hb : ∀ A ∈ H, b ∈ A) (hl : ∀ A ∈ H, ∀ B ∈ H, A ≠ B → (A ∩ B).card ≤ 1) (hh : ∀ A ∈ H, ¬Disjoint A C) (hc : C.card < H.card) : b ∈ C := by classical by_contra hn let f (A : Finset α) : α := if hA : A ∈ H then Classical.choose (Finset.not_disjoint_iff.mp (hh A hA)) else b have hf : ∀ A ∈ H, f A ∈ A ∧ f A ∈ C := by intro A hA simpa [f, hA] using Classical.choose_spec (Finset.not_disjoint_iff.mp (hh A hA)) have hcard : H.card ≤ C.card := by apply Finset.card_le_card_of_injOn f · intro A hA exact (hf A hA).2 · intro A hA B hB hab by_contra hne have hu : ∀ {a b : α}, a ∈ A ∩ B → b ∈ A ∩ B → a = b := Finset.card_le_one_iff.mp (hl A hA B hB hne) have hbi : b ∈ A ∩ B := Finset.mem_inter.mpr ⟨hb A hA, hb B hB⟩ have hfi : f A ∈ A ∩ B := Finset.mem_inter.mpr ⟨(hf A hA).1, by rw [hab]; exact (hf B hB).1⟩ have heq : b = f A := hu hbi hfi apply hn rw [heq] exact (hf A hA).2 omega