greedyMatching_nil
For every predicate P : Finset (Sym2 (ℝ × ℝ)) → Prop on finite sets of unordered pairs of points in ℝ × ℝ, greedyMatching P [] equals the pair (∅, []).
Statement
theorem greedyMatching_nil (P : Finset (Sym2 (ℝ × ℝ)) → Prop) : greedyMatching P [] = (∅, [])
- Source
- arXiv:2610.23130, Section 1
- Verified
- 22 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- greedyMatchingGiven a predicate P : Finset (Sym2 (ℝ × ℝ)) → Prop and an input list of points pts : List (ℝ × ℝ), greedyMatching folds greedyStep P…
- Used by 1
- greedy_matching_fraction_ge_of_blocking_leLet P be a hereditary segment property. If β_P(ℓ) ≤ p (formalized by segment_blocking_bound_le P ℓ p), then on every duplicate-free list…
Read back from the Lean
For every predicate $P$ on finite sets of unordered pairs of points in $\mathbb{R}^2$ (Finset (Sym2 (ℝ × ℝ)) → Prop), the greedy matching procedure greedyMatching P applied to the empty list of points returns (∅, []) (the empty set of edges and the empty list of points).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The greedy matching algorithm is defined as a left fold (`foldl`) over the input list of points, starting from the base state `(∅, [])`. When the input sequence is empty, the fold performs no steps and immediately returns the initial state `(∅, [])`. The simplifier unfolds the definition of `greedyMatching` and evaluates the fold on the empty list.
greedyMatching P [] = (∅, [])
Unfolding the definition of `greedyMatching` expresses the term as `[].foldl (greedyStep P) (∅, [])`. Folding over the empty list performs zero iterations and returns the initial accumulator `(∅, [])`, which closes the goal.
uses
greedyMatchingsimp [greedyMatching]
greedyMatching- the greedy matching algorithm on a list of points, defined as a left fold of `greedyStep P` over the list starting from the initial state `(∅, [])`
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.
/-- Greedy matching on the empty sequence produces an empty matching and empty unmatched list. -/theorem greedyMatching_nil (P : Finset (Sym2 (ℝ × ℝ)) → Prop) : greedyMatching P [] = (∅, []) := by simp [greedyMatching]