not_greedy_fraction_le_of_blocking_ge
The statement greedy_fraction_le_of_blocking_ge is false: The statement is false as written; a machine-checked refutation is provided.
Counterexample: take P := fun t => t = ∅ (so P holds only on the empty family), ℓ = 1, p = 0.
* P is hereditary: P ∅ holds, and if s ⊆ t with P t (i.e. t = ∅) then s = ∅, so P s.
* The hypothesis hβ : p ≤ segment_blocking_number P 1 is 0 ≤ _, hence trivial — in fact the set {p' | ∃ L S, L.card = 1 ∧ P L ∧ ...} is empty (L.card = 1 with L = ∅ is impossible), so the supremum is 0 and the hypothesis carries no information at all.
* But greedyMatching P pts = (∅, pts) for EVERY list pts: greedyStep only inserts s(u,v) when P (insert s(u,v) M) holds, i.e. when insert s(u,v) M = ∅, which is never true since that finset is nonempty. Hence (greedyMatching P pts).1.card = 0 for all pts, and the required conclusion (greedyMatching P pts).1.card = 1 is unsatisfiable.
So the conclusion ∃ pts, ... ∧ (greedyMatching P pts).1.card = ℓ fails.
Two root causes of the falsity (both worth fixing in any restatement):
(1) p ≤ segment_blocking_number P ℓ says nothing when the defining set of cardinalities is empty (or, more generally, when p = 0): the recorded proof plan implicitly assumed a genuine witness family L with card ℓ satisfying P that blocks p points, which the hypothesis does not supply.
(2) Even with p ≥ 1 and a nonempty witness set the statement fails, because degenerate pairs s(x,x) are legitimate members of a P-satisfying blocking family, while greedy on a duplicate-free list can never insert a pair with equal endpoints: u is taken from the unmatched (hence already seen, distinct) list and v is the new point. Concretely P := fun t => t ⊆ {s(((0:ℝ),(0:ℝ)),((0:ℝ),(0:ℝ)))} is hereditary, L := {s((0,0),(0,0))} has card 1, and it blocks every finite point set S with endpoints ∪ S in general position, so segment_blocking_number P 1 is unbounded; yet (greedyMatching P pts).1.card = 0 for every nodup pts, so no ℓ = 1 witness list exists.
Verified in Lean: the negation ¬ (∀ (P) (hP) (ℓ p), p ≤ segment_blocking_number P ℓ → ∃ pts, pts.Nodup ∧ points_in_general_position ↑pts.toFinset ∧ (greedyMatching P pts).1.card = ℓ ∧ ...) compiles with no sorry and only the standard axioms.
Statement
theorem not_greedy_fraction_le_of_blocking_ge : ¬ (∀ (P : Finset (Sym2 (ℝ × ℝ)) → Prop) (hP : IsHereditarySegmentProperty P) (ℓ p : ℕ) (hβ : p ≤ segment_blocking_number P ℓ), ∃ pts : List (ℝ × ℝ), pts.Nodup ∧ points_in_general_position (pts.toFinset : Set (ℝ × ℝ)) ∧ (greedyMatching P pts).1.card = ℓ ∧ (2 * (ℓ : ℝ)) / (pts.length : ℝ) ≤ (2 * (ℓ : ℝ)) / (2 * (ℓ : ℝ) + (p : ℝ)))
- Related work
- refutes `greedy_fraction_le_of_blocking_ge`
- Verified
- 22 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- IsHereditarySegmentPropertyA predicate P on finite sets of unordered pairs in Sym2 (ℝ × ℝ) is a hereditary segment property if P holds on the empty finset and for…
- greedyMatchingGiven a predicate P : Finset (Sym2 (ℝ × ℝ)) → Prop and an input list of points pts : List (ℝ × ℝ), greedyMatching folds greedyStep P…
- points_in_general_positionA set S of points in the real plane ℝ × ℝ is in general position if for all pairwise distinct points p₁, p₂, p₃ in S, the three-element…
- segment_blocking_numberFor a predicate P on finite sets of unordered pairs in Sym2 (ℝ × ℝ) and an integer ℓ, the blocking number segment_blocking_number P ℓ is…
- greedyStepGiven a predicate P : Finset (Sym2 (ℝ × ℝ)) → Prop, a state (M, U) consisting of a finite set of matched unordered pairs M : Finset (Sym2…
The proof, explained
The proof refutes the universal claim by contradiction using an explicit counterexample. It chooses the property P(t) := (t = ∅), which is hereditary because any subset of the empty set is empty, and sets ℓ = 1 and p = 0. The condition 0 ≤ segment_blocking_number P 1 holds trivially, so the theorem would guarantee a point list whose greedy matching has cardinality 1. However, because adding any segment produces a nonempty set, P can never accept any candidate edge; an induction shows that the greedy matching on any list is ∅ (cardinality 0), which contradicts the existence of a matching of size 1.
Assume for contradiction that the statement holds universally.
We introduce the assumed universal statement `h` to derive `False`. Classical logic is enabled for non-constructive reasoning.
classical intro hThe property P(t) ↔ t = ∅ is a hereditary segment property.
By definition, a segment property is hereditary if it holds for the empty set and is preserved under taking subsets. The empty set satisfies ∅ = ∅. If a ⊆ b and b = ∅, then a ⊆ ∅, so a = ∅ by `Finset.subset_empty.mp`.
uses
Finset.subset_empty.mphave hP : IsHereditarySegmentProperty (fun t : Finset (Sym2 (ℝ × ℝ)) => t = ∅) := by refine ⟨rfl, ?_⟩ intro a b hab hb rw [hb] at hab exact Finset.subset_empty.mp hab
If no point in the unmatched list can form an accepted segment with a new point v, greedyStep leaves the matching unchanged and appends v.
The greedy step searches the unmatched list U for an element x such that P(M ∪ {s(x, v)}) holds. By `List.find?_eq_none`, because the predicate is false for every x ∈ U, the search returns `none`. Consequently, greedyStep does not augment M and appends v to the unmatched list U.
uses
List.find?_eq_nonehave step : ∀ (P : Finset (Sym2 (ℝ × ℝ)) → Prop) (M : Finset (Sym2 (ℝ × ℝ))) (U : List (ℝ × ℝ)) (v : ℝ × ℝ), (∀ x ∈ U, decide (P (insert s(x, v) M)) = false) → greedyStep P (M, U) v = (M, U ++ [v]) := by intro P M U v hh have hfind : List.find? (fun x => decide (P (insert s(x, v) M))) U = none := by rw [List.find?_eq_none] intro x hx rw [hh x hx] simp simp only [greedyStep] rw [hfind]
For P(t) ↔ t = ∅, running greedy matching on any list of points from an empty matching leaves the matching empty and leaves all points unmatched.
We proceed by induction on the list `pts`. If `pts` is empty, no steps are taken. For a list `v :: rest`, `List.foldl_cons` unwraps the step on v. For any x ∈ U, {s(x, v)} ≠ ∅, so P({s(x, v)}) is false; our previous lemma shows that the state becomes (∅, U ++ [v]). The induction hypothesis on `rest` then completes the step.
uses
List.foldl_conshave key : ∀ (pts U : List (ℝ × ℝ)), List.foldl (greedyStep (fun t : Finset (Sym2 (ℝ × ℝ)) => t = ∅)) (∅, U) pts = (∅, U ++ pts) := by intro pts induction pts with | nil => intro U; simp | cons v rest ih => intro U rw [List.foldl_cons] rw [step (fun t : Finset (Sym2 (ℝ × ℝ)) => t = ∅) ∅ U v (fun x hx => by simp)] simpa using ih (U ++ [v])
Specializing the assumed statement to P, ℓ = 1, and p = 0 produces a contradiction.
We instantiate the assumed statement `h` with P := (· = ∅), ℓ := 1, and p := 0. The hypothesis 0 ≤ segment_blocking_number P 1 holds trivially by `Nat.zero_le`. This yields a point list `pts` whose greedy matching has size 1. However, our inductive lemma proves that the greedy matching on `pts` is ∅, which has cardinality 0. The equality 0 = 1 is impossible, closing the proof.
uses
Nat.zero_lehave h1 := h (fun t : Finset (Sym2 (ℝ × ℝ)) => t = ∅) hP 1 0 (Nat.zero_le _) obtain ⟨pts, hnodup, hgen, hcard, hratio⟩ := h1 have hkey := key pts [] simp only [greedyMatching] at hcard rw [hkey] at hcard simp at hcard
Finset.subset_empty.mp- Any finite set that is a subset of the empty set must itself be the empty set.
List.find?_eq_none- A linear search `List.find?` over a list returns `none` if and only if the test predicate evaluates to false on every element of the list.
List.foldl_cons- Folding a function `f` left over `a :: l` with initial accumulator `b` equals folding `f` over `l` with updated accumulator `f b a`.
Nat.zero_le- Zero is less than or equal to any natural number.
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.
theorem not_greedy_fraction_le_of_blocking_ge : ¬ (∀ (P : Finset (Sym2 (ℝ × ℝ)) → Prop) (hP : IsHereditarySegmentProperty P) (ℓ p : ℕ) (hβ : p ≤ segment_blocking_number P ℓ), ∃ pts : List (ℝ × ℝ), pts.Nodup ∧ points_in_general_position (pts.toFinset : Set (ℝ × ℝ)) ∧ (greedyMatching P pts).1.card = ℓ ∧ (2 * (ℓ : ℝ)) / (pts.length : ℝ) ≤ (2 * (ℓ : ℝ)) / (2 * (ℓ : ℝ) + (p : ℝ))) := by classical intro h have hP : IsHereditarySegmentProperty (fun t : Finset (Sym2 (ℝ × ℝ)) => t = ∅) := by refine ⟨rfl, ?_⟩ intro a b hab hb rw [hb] at hab exact Finset.subset_empty.mp hab have step : ∀ (P : Finset (Sym2 (ℝ × ℝ)) → Prop) (M : Finset (Sym2 (ℝ × ℝ))) (U : List (ℝ × ℝ)) (v : ℝ × ℝ), (∀ x ∈ U, decide (P (insert s(x, v) M)) = false) → greedyStep P (M, U) v = (M, U ++ [v]) := by intro P M U v hh have hfind : List.find? (fun x => decide (P (insert s(x, v) M))) U = none := by rw [List.find?_eq_none] intro x hx rw [hh x hx] simp simp only [greedyStep] rw [hfind] have key : ∀ (pts U : List (ℝ × ℝ)), List.foldl (greedyStep (fun t : Finset (Sym2 (ℝ × ℝ)) => t = ∅)) (∅, U) pts = (∅, U ++ pts) := by intro pts induction pts with | nil => intro U; simp | cons v rest ih => intro U rw [List.foldl_cons] rw [step (fun t : Finset (Sym2 (ℝ × ℝ)) => t = ∅) ∅ U v (fun x hx => by simp)] simpa using ih (U ++ [v]) have h1 := h (fun t : Finset (Sym2 (ℝ × ℝ)) => t = ∅) hP 1 0 (Nat.zero_le _) obtain ⟨pts, hnodup, hgen, hcard, hratio⟩ := h1 have hkey := key pts [] simp only [greedyMatching] at hcard rw [hkey] at hcard simp at hcard