AFTD Auto-Formalizing Theoretical Domains

not_greedy_fraction_le_of_blocking_ge

theoremverifiedoriginal

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.

  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.

    lines 5–6

      classical
      intro h
  2. The 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`.

    lines 7–11

    uses Finset.subset_empty.mp

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

    lines 12–22

    uses List.find?_eq_none

      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]
  4. 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.

    lines 23–33

    uses List.foldl_cons

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

    lines 34–39

    uses Nat.zero_le

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

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