relation_reaches_terminal_of_nat_rank_descent
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-predecessor Y (that is, R Y X) with r Y < r X, then every P-state X is the top of a finite R-chain Q → ⋯ → X whose first element Q is terminal.
Statement
theorem relation_reaches_terminal_of_nat_rank_descent {α : Type*} (P Term : α → Prop) (R : α → α → Prop) (r : α → ℕ) (h : ∀ X, P X → ¬ Term X → ∃ Y, P Y ∧ r Y < r X ∧ R Y X) : ∀ X, P X → ∃ Q, Term Q ∧ Relation.ReflTransGen R Q X
- Source
- step towards op223_poset_connectivity
- Verified
- 19 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 1
- sustainable_path_connectivity_of_descent_stepIf every sustainable tree on Fin n (n ≥ 1) that is not a path has a sustainable generalized-tree-shift predecessor with strictly smaller…
The proof, explained
To show that every $P$-state reaches a terminal state, the goal is strengthened by introducing an explicit upper bound $k \in \mathbb{N}$ on the rank $r(X)$ and proceeding by mathematical induction on $k$. The original theorem follows by instantiating the bound with $k = r(X)$. At each induction stage, if a state is already terminal, it reaches itself in zero steps; otherwise, the rank-descent hypothesis provides a predecessor with strictly smaller rank, enabling an appeal to the induction hypothesis and extending the path by one step.
It suffices to show that for every $k \in \mathbb{N}$, any state $X$ satisfying $P(X)$ with $r(X) \le k$ is reachable from a terminal state via $R$.
Given any state $X$ satisfying $P(X)$, setting $k = r(X)$ satisfies the rank condition $r(X) \le k$ trivially by reflexivity of the order (`le_rfl`). Thus, establishing this bounded claim for all $k$ immediately proves the original theorem.
uses
le_rflsuffices H : ∀ k, ∀ X, r X ≤ k → P X → ∃ Q, Term Q ∧ Relation.ReflTransGen R Q X by intro X hX exact H (r X) X le_rfl hX
For $k = 0$, every state $X$ satisfying $P(X)$ with $r(X) \le 0$ is reachable from a terminal state.
We proceed by induction on $k$. In the base case $k = 0$, we case-split on whether $X$ is terminal: if it is, $X$ reaches itself in zero steps using `Relation.ReflTransGen.refl`. If $X$ is not terminal, the descent hypothesis yields a predecessor $Y$ with $r(Y) < r(X) \le 0$, which is impossible for natural numbers; linear arithmetic (`omega`) detects this 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
For the inductive step, if the property holds for all states of rank at most $k$, then every state $X$ satisfying $P(X)$ with $r(X) \le k + 1$ is also reachable from a terminal state.
Assuming the induction hypothesis for bound $k$, let $X$ satisfy $P(X)$ and $r(X) \le k + 1$. If $X$ is terminal, it reaches itself in zero steps by `Relation.ReflTransGen.refl`. If not, the descent hypothesis provides a predecessor $Y$ such that $P(Y)$, $R(Y, X)$, and $r(Y) < r(X)$. Since $r(Y) < r(X) \le k + 1$, linear arithmetic (`omega`) implies $r(Y) \le k$. We apply the induction hypothesis to $Y$ to obtain a terminal state $Q$ that reaches $Y$ via the reflexive transitive closure of $R$. Appending the final step $R(Y, X)$ via `Relation.ReflTransGen.tail` shows that $Q$ reaches $X$.
uses
Relation.ReflTransGen.refl,Relation.ReflTransGen.tail| 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.tail hstep hR⟩
le_rfl- Every element in a preorder is less than or equal to itself ($a \le a$).
Relation.ReflTransGen.refl- The reflexive transitive closure of a relation is reflexive: every element reaches itself in zero steps.
Relation.ReflTransGen.tail- A path in the reflexive transitive closure from $a$ to $b$ can be extended by a single step from $b$ to $c$ to form a path from $a$ to $c$.
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.
/-- Descent to a terminal state through a ℕ-valued rank: a non-terminal P-state always has an R-predecessor of strictly smaller rank. -/theorem relation_reaches_terminal_of_nat_rank_descent {α : Type*} (P Term : α → Prop) (R : α → α → Prop) (r : α → ℕ) (h : ∀ X, P X → ¬ Term X → ∃ Y, P Y ∧ r Y < r X ∧ R Y X) : ∀ X, P X → ∃ Q, Term Q ∧ Relation.ReflTransGen R Q X := by suffices H : ∀ k, ∀ X, r X ≤ k → P X → ∃ Q, Term Q ∧ Relation.ReflTransGen R Q X 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.tail hstep hR⟩