Fixed-node fourth-term cascade: no tree-safe word on
ProvedErdos195.cascade_set_not_tree_safeA tree witness is a function on the nodes , , of the binary tree of residues. For distinct integers with , put iff (two's-complement digits). A finite word of integers is -safe if the sequence "the letters of in order, then all remaining integers in -order" contains no monotone -term arithmetic progression. Let (so and ) and . No word beginning with , containing , all of whose letters lie in
is -safe for any tree witness . The pair forces the value and the pair forces the value at the same node , and closing by its fourth term creates : an infinite fourth-term cascade at a fixed node, so no depth-type potential can make that repair rule terminate (Erdős Problem 195, tree-witness approach).
Formalization note: treeLt θ is from Definitions.Def_Erdos195_tree; Safe, bitOne are from Definitions.Def_Erdos195_defs. "Begins with" is the list prefix relation <+:; positions in a word are List.idxOf. The statement quantifies over every witness θ, so it holds in particular for all ε-orders.
import Mathlib import Definitions.Def_Erdos195_tree
namespace Erdos195
theorem cascade_set_not_tree_safe (m : ℕ) (θ : ℕ → ℤ → Bool) (Q : List ℤ)
(hpre : [0, 1, -1] <+: Q) (hw : 2 * (3 : ℤ) ^ (m + 1) - 1 ∈ Q)
(hset : ∀ x ∈ Q, (x = -1 ∨ x = 0 ∨ x = 1 ∨ x = 2 ∨ x = 3) ∨
∃ j ≤ m, x = 2 * (3 : ℤ) ^ (j + 1) - 1) :
¬ Safe (treeLt θ) Q := by sorry
end Erdos195