Every tree-safe word with a fully open pair admits a tree-safe sink step
ProvedErdos195.exists_sink_append_safeA tree witness defines a strict total order on : for with , iff the -th binary digit of is exactly when . A finite word of integers is -safe if the sequence "letters of in order, then all remaining integers in -order" has no monotone 4-term arithmetic progression (positions are first occurrences); is tree-safe if it is -safe for some . For an in-order pair of ( before ) call its third term and its fourth term. An open path in is a family of in-order pairs , , , with for and no third term in . Its sink fourth term is a true-sink fourth term of if and every in-order pair of with has (condition C1 for appending ).
Theorem. Let be tree-safe and suppose has a fully open in-order pair (both and ). Then there is an open path , , in whose sink fourth term
is a true-sink fourth term of and such that is again tree-safe.
So a deadlock in which every sink step fails cannot occur: one closing step (appending the fourth term of the sink pair, which closes it) is always available. The proof takes to be the -least true-sink fourth term, which exists because there are finitely many and at least one by milestone #154, and applies the preceding milestone.
import Mathlib import Definitions.Def_Erdos195_tree
namespace Erdos195
theorem exists_sink_append_safe (T : List ℤ) (hS : ∃ θ : ℕ → ℤ → Bool, Safe (treeLt θ) T)
(a₀ b₀ : ℤ) (ha₀ : a₀ ∈ T) (hb₀ : b₀ ∈ T) (hi₀ : T.idxOf a₀ < T.idxOf b₀)
(ht₀ : 2 * b₀ - a₀ ∉ T) (hw₀ : 3 * b₀ - 2 * a₀ ∉ T) :
∃ (m : ℕ) (a b : ℕ → ℤ), 0 < m ∧
(∀ i < m, a i ∈ T) ∧ (∀ i < m, b i ∈ T) ∧ (∀ i < m, T.idxOf (a i) < T.idxOf (b i)) ∧
(∀ i, i + 1 < m → 3 * b i - 2 * a i = 2 * b (i + 1) - a (i + 1)) ∧
(∀ i < m, 2 * b i - a i ∉ T) ∧ 3 * b (m - 1) - 2 * a (m - 1) ∉ T ∧
(∀ x y : ℤ, x ∈ T → y ∈ T → T.idxOf x < T.idxOf y →
2 * y - x = 3 * b (m - 1) - 2 * a (m - 1) → 3 * y - 2 * x ∈ T) ∧
∃ θ' : ℕ → ℤ → Bool, Safe (treeLt θ') (T ++ [3 * b (m - 1) - 2 * a (m - 1)]) := by sorry
end Erdos195