Acyclic initial continuation demands do not guarantee safe extension
ProvedErdos195.acyclic_demands_do_not_ensure_extensionLet . For any finite word and relation on the integers, form the relation that puts the letters of first in their order of first occurrence, puts them before every integer missing from , and uses between missing integers. Write when this completion relation contains no nonconstant four-term arithmetic progression in increasing relation order.
For integers , define the initial continuation-demand relation by requiring that are both missing from and that there are letters appearing in this order in with and . Such a demand means that any safe prefix extension containing must contain earlier.
Then:
- holds, where is the constantly false tail relation.
- The directed graph has no nonempty directed cycle.
- For every relation and finite word extending as a prefix, implies .
Thus safety for the empty tail relation together with acyclicity of the initial continuation demands is insufficient to guarantee extension to a prescribed integer. The conclusion has no bound on additional letters or their sizes and does not assume that is a total order. It is a finite obstruction to this proposed extension invariant, not a resolution of Erdős Problem 195.
import Mathlib import Definitions.Def_Erdos195_defs
namespace Erdos195
theorem acyclic_demands_do_not_ensure_extension :
let P : List ℤ := [0, 3, 2, 11, 10]
let D : ℤ → ℤ → Prop := fun c d =>
c ∉ P ∧ d ∉ P ∧ ∃ a ∈ P, ∃ b ∈ P,
P.idxOf a < P.idxOf b ∧ c = 2 * b - a ∧ d = 3 * b - 2 * a
Erdos195.Safe (fun _ _ => False) P ∧
(∀ c : ℤ, ¬ Relation.TransGen D c c) ∧
∀ (R : ℤ → ℤ → Prop) (Q : List ℤ),
P <+: Q → Erdos195.Safe R Q → (4 : ℤ) ∉ Q := by
sorry
end Erdos195