Collatz descent principle: every eventually drops below
Opencollatz_descentLet denote the Collatz step map, for even and for odd . The descent principle asserts that every starting value larger than has a finite stopping time: for every there exists with
Equivalently, no orbit started above stays at or above its starting value forever.
This is the standard reformulation of the Collatz conjecture as a well-foundedness statement. It implies the conjecture: by strong induction on , the value reaches in zero steps, and for the descent principle produces a strictly smaller point of the orbit, which is still positive because positivity is preserved along orbits, so the induction hypothesis applies to it and the two segments of the orbit compose. Conversely the conjecture implies the descent principle, since an orbit that reaches from has passed below .
The advantage of this form is that it is local: it asks only for a bounded piece of each orbit rather than for the global behaviour, and it splits cleanly along residue classes modulo . The classes are settled by a single halving step and the class with by three steps, leaving as the open case.
Formalization Note. The index is not constrained to be positive because cannot witness the conclusion: is false.
import Mathlib import Definitions.Def_collatzStepMap
theorem collatz_descent (n : ℕ) (hn : 1 < n) : ∃ m : ℕ, collatzStep^[m] n < n := by sorry