AFTD Auto-Formalizing Theoretical Domains

relation_reaches_terminal_of_nat_rank_descent

theoremverified

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

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.

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

    lines 6–8

    uses le_rfl

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

    lines 9–16

    uses Relation.ReflTransGen.refl

      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
  3. 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$.

    lines 17–23

    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

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