AFTD Auto-Formalizing Theoretical Domains

tgreedy_rc_output_sanity

theoremverified

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.

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

    line 2

    uses Relation.ReflTransGen.single

      ⟨{[1, 2]}, Relation.ReflTransGen.single (by unfold mgreedy_rc_step; decide),
  2. 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`).

    line 3

    uses Relation.ReflTransGen.refl

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

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