Domain coverage and ranked coalescence imply finite reachability
ProvedNewMathDiscovery.RankedCoalescence.covered_ranked_coalescence_sounddynamical-systemsformal-verificationsodelin-newmathwell-foundedness
Let be types, a transition, a terminal state, a decoding map, a rank, and a relation on . Let be a relation with , , and . Assume:
- .
- The pullback relation is well founded.
- Every configuration with admits some edge .
- Every such edge satisfies and .
- For every , there is with .
Here denotes -fold iteration, with the identity. Then
This is an abstract soundness theorem for a supplied ranked coalescence certificate. Progress and rank decrease are assumed for all configurations, while entry coverage is only needed for the selected domain. It does not construct a certificate for Collatz or prove universal Collatz termination.
Preamble
import Std import Init.Grind.Ordered.Module import Definitions.Def_NewMathDiscovery_RankedCoalescenceSound
Formal statement
theorem NewMathDiscovery.RankedCoalescence.covered_ranked_coalescence_sound
{α C W : Type}
(f : α → α)
(one : α)
(decode : C → α)
(rank : C → W)
(lt : W → W → Prop)
(edge : C → Nat → Nat → C → Prop)
(Entry : C → Prop)
(Domain : α → Prop)
(hfix : f one = one)
(hwf : WellFounded (fun c' c => lt (rank c') (rank c)))
(hprogress : ∀ c, decode c ≠ one → ∃ a b c', edge c a b c')
(hexact : ∀ {c a b c'}, edge c a b c' →
iterate f a (decode c) = iterate f b (decode c'))
(hdecrease : ∀ {c a b c'}, edge c a b c' →
lt (rank c') (rank c))
(hcoverage : ∀ x, Domain x → ∃ c, Entry c ∧ decode c = x) :
∀ x, Domain x → Reaches f one x := by sorry
Source