AFTD Auto-Formalizing Theoretical Domains

greedyMatching_nil

theoremverified

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

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.

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

    line 3

    uses greedyMatching

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

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