relation_reaches_terminal_of_nat_rank_ascent
Let P and Term be predicates and R a relation on a type α, with r : α → ℕ. If every non-terminal P-state X has a P-successor Y (that is, R X Y) with r Y < r X, then every P-state X starts a finite R-chain X → ⋯ → Q whose last element Q is terminal.
Statement
theorem relation_reaches_terminal_of_nat_rank_ascent {α : Type*} (P Term : α → Prop) (R : α → α → Prop) (r : α → ℕ) (h : ∀ X, P X → ¬ Term X → ∃ Y, P Y ∧ r Y < r X ∧ R X Y) : ∀ X, P X → ∃ Q, Term Q ∧ Relation.ReflTransGen R X Q
- Source
- step towards op223_poset_connectivity
- Verified
- 19 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 1
- nonsustainable_star_connectivity_of_ascent_stepIf every non-sustainable tree on Fin n (n ≥ 2) that is not a star has a non-sustainable generalized-tree-shift successor with strictly…
The proof, explained
The proof proceeds by mathematical induction on an upper bound k ∈ ℕ on the rank r(X). In the base case k = 0, either X is already terminal (so an empty path reaches it), or X must have a successor with strictly smaller rank, which is impossible for non-negative integers. In the inductive step, if X is not terminal, the hypothesis provides a successor Y with r(Y) < r(X) ≤ k + 1, giving r(Y) ≤ k; the induction hypothesis then yields a path from Y to a terminal state Q, and prepending the initial step X → Y completes the reachability chain from X to Q.
It suffices to prove that for all k ∈ ℕ, any state X with r(X) ≤ k and P(X) reaches some terminal state Q via R.
We strengthen the target by introducing an explicit upper bound k on the rank r(X). If this bounded statement holds for all k, then for any given state X with P(X), choosing k = r(X) (using r(X) ≤ r(X) via le_rfl) immediately establishes the theorem.
uses
le_rflsuffices H : ∀ k, ∀ X, r X ≤ k → P X → ∃ Q, Term Q ∧ Relation.ReflTransGen R X Q by intro X hX exact H (r X) X le_rfl hX
The base case k = 0 holds: any state X satisfying P(X) with r(X) ≤ 0 reaches a terminal state.
We proceed by induction on k. For k = 0, we have r(X) ≤ 0, so r(X) = 0. We case-split on whether X is already terminal. If it is, X reaches itself in zero steps by reflexivity (Relation.ReflTransGen.refl). If X is not terminal, hypothesis h provides a successor Y with r(Y) < r(X) ≤ 0, which is impossible for natural numbers; omega detects this arithmetic contradiction and closes the branch.
uses
Relation.ReflTransGen.reflintro k induction k with | zero => intro X hk hX by_cases hT : Term X · exact ⟨X, hT, Relation.ReflTransGen.refl⟩ · obtain ⟨Y, -, hlt, -⟩ := h X hX hT omega
The inductive step holds: if every state with rank at most k reaches a terminal state, the same holds for states with rank at most k + 1.
Assume the induction hypothesis for k, and consider a state X with P(X) and r(X) ≤ k + 1. If X is terminal, reflexivity (Relation.ReflTransGen.refl) finishes the proof with Q = X. If X is not terminal, hypothesis h yields an R-successor Y satisfying P(Y) with r(Y) < r(X). Since r(Y) < r(X) ≤ k + 1, integer arithmetic (omega) gives r(Y) ≤ k. Applying the induction hypothesis to Y produces a terminal state Q reachable from Y in zero or more R-steps. Prepending the step R(X, Y) via Relation.ReflTransGen.head yields a complete path from X to Q.
uses
Relation.ReflTransGen.refl,Relation.ReflTransGen.head| succ k ih => intro X hk hX by_cases hT : Term X · exact ⟨X, hT, Relation.ReflTransGen.refl⟩ · obtain ⟨Y, hPY, hlt, hR⟩ := h X hX hT obtain ⟨Q, hTQ, hstep⟩ := ih Y (by omega) hPY exact ⟨Q, hTQ, Relation.ReflTransGen.head hR hstep⟩
le_rfl- Every element in a preorder is less than or equal to itself (a ≤ a).
Relation.ReflTransGen.refl- The reflexive-transitive closure of a relation is reflexive: every element reaches itself in zero steps.
Relation.ReflTransGen.head- If a relates to b and b reaches c in zero or more steps, then a reaches c in zero or more steps.
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.
/-- Ascent from a state to a terminal state through a ℕ-valued rank: a non-terminal P-state always has an R-successor of strictly smaller rank. -/theorem relation_reaches_terminal_of_nat_rank_ascent {α : Type*} (P Term : α → Prop) (R : α → α → Prop) (r : α → ℕ) (h : ∀ X, P X → ¬ Term X → ∃ Y, P Y ∧ r Y < r X ∧ R X Y) : ∀ X, P X → ∃ Q, Term Q ∧ Relation.ReflTransGen R X Q := by suffices H : ∀ k, ∀ X, r X ≤ k → P X → ∃ Q, Term Q ∧ Relation.ReflTransGen R X Q by intro X hX exact H (r X) X le_rfl hX intro k induction k with | zero => intro X hk hX by_cases hT : Term X · exact ⟨X, hT, Relation.ReflTransGen.refl⟩ · obtain ⟨Y, -, hlt, -⟩ := h X hX hT omega | succ k ih => intro X hk hX by_cases hT : Term X · exact ⟨X, hT, Relation.ReflTransGen.refl⟩ · obtain ⟨Y, hPY, hlt, hR⟩ := h X hX hT obtain ⟨Q, hTQ, hstep⟩ := ih Y (by omega) hPY exact ⟨Q, hTQ, Relation.ReflTransGen.head hR hstep⟩