tgreedy_rc_output_sanity
With cm = id, TGREEDY-RC on {12} can output 12.
Statement
theorem tgreedy_rc_output_sanity : tgreedy_rc_output id ({[1, 2]} : Finset (List ℕ)) [1, 2]- Source
- Sanity check of tgreedy_rc_output (arXiv:2611.16573)
- Verified
- 14 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 6
- tgreedy_rc_outputFor cm : Γ → Γ, S : Finset (List Γ) and t : List Γ, tgreedy_rc_output cm S t holds when there is T : Finset (List Γ) such that the state…
- mgreedy_rc_stepFor cm : Γ → Γ and states st = (S, T), st' : Finset (List Γ) × Finset (List Γ), mgreedy_rc_step cm st st' holds when, with V = S ∪…
- string_overlap_lenFor two lists x, y : List Γ over an arbitrary alphabet type Γ with decidable equality (strings are lists of letters, not Lean Strings),…
- greedy_rc_stepFor cm : Γ → Γ and S, S' : Finset (List Γ), greedy_rc_step cm S S' holds when S has more than one element and, with V = S ∪ rev_comp cm ''…
- rev_compThe reverse complement rc(s) of a string s = a_1…a_m under a complement map cm is cm(a_m)…cm(a_1).
- string_overlap_mergeFor two lists x, y : List Γ over an alphabet type Γ with decidable equality, the overlap merge ⟨x,y⟩ is the list consisting of the first…
The proof, explained
To show that TGREEDY-RC with cm = id on the singleton input {[1, 2]} can output [1, 2], we choose the intermediate set T = {[1, 2]}. The first phase (the modified greedy phase) moves [1, 2] from the working set to the frozen set in a single step, verified by decision procedure. The second phase (the standard greedy phase) requires zero steps, completing the proof by reflexivity.
Witness the intermediate set T = {[1, 2]} and reduce the first phase to a single transition of `mgreedy_rc_step`.
The definition of `tgreedy_rc_output` requires an intermediate set of strings `T` reachable from the initial state `({[1, 2]}, ∅)` in zero or more `mgreedy_rc_step` steps, such that the singleton `{t} = {[1, 2]}` is reachable from `T` in zero or more `greedy_rc_step` steps. We provide `T = {[1, 2]}`. For the first phase, we apply `Relation.ReflTransGen.single`, reducing the reachability goal to the single step `mgreedy_rc_step id ({[1, 2]}, ∅) (∅, {[1, 2]})`. Unfolding `mgreedy_rc_step` yields an existential statement about choosing a string to transfer from the active set to the completed set; Lean's `decide` evaluates the finite search over the singleton input set and confirms the transition holds.
uses
Relation.ReflTransGen.single⟨{[1, 2]}, Relation.ReflTransGen.single (by unfold mgreedy_rc_step; decide),The second phase requires zero steps because the intermediate set is already the desired singleton.
Since the intermediate set `T = {[1, 2]}` is already identical to the target singleton `{[1, 2]}`, the second phase `Relation.ReflTransGen (greedy_rc_step id) {[1, 2]} {[1, 2]}` holds immediately by reflexivity of the reflexive-transitive closure (`Relation.ReflTransGen.refl`).
uses
Relation.ReflTransGen.reflRelation.ReflTransGen.refl⟩
Relation.ReflTransGen.single- Every relation is contained in its reflexive-transitive closure: if `r a b`, then `ReflTransGen r a b`.
Relation.ReflTransGen.refl- Reflexivity of the reflexive-transitive closure: `ReflTransGen r a a` holds for any element `a`.
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 tgreedy_rc_output_sanity : tgreedy_rc_output id ({[1, 2]} : Finset (List ℕ)) [1, 2] := ⟨{[1, 2]}, Relation.ReflTransGen.single (by unfold mgreedy_rc_step; decide), Relation.ReflTransGen.refl⟩