Proof of Theorem 1.16, root test (corrected: alternating evaluation) — deciding at the root
ProvedCoDecompFO.root_evaluationco-decompositionsfirst-order-logicmodel-checkingp2o-correctedp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1parameterized-complexity
For every structure , every map and every matrix on ,
where is alternating evaluation: says at level that all hypotheses in satisfy , and at a higher level that for every and every personality in some pair has .
Taking and gives the root test, and needs only the table at .
Differences from the source:
- correction: accept when there is a supported hypothetical all of whose leaf hypotheses satisfy the quantifier-free part of φ → alternating evaluation of the one full-strategy table; reason: the corrected table has one entry per node, and the printed test on that entry rejects true sentences: the full strategy has losing responses, as on the two-bag instance of Observation 5.79
- generalization: the root bag with the projection from the partial limit → any structure G with any map π to any set; reason: the root is the case G = G[r], π = π_r
Preamble
import Mathlib import Definitions.Def_CoDecompFO_HTh set_option autoImplicit false
Formal statement
namespace CoDecompFO
open FirstOrder
/-- **The root test**, corrected to alternating evaluation (Bumpus et al., arXiv:2611.04658, held file
sha256 d550d7af…, proof of Theorem 1.16, p.41): "Finally, at the root we apply Lemma 5.78 and accept when
there is a supported hypothetical all of whose leaf hypotheses satisfy the quantifier-free part of φ."
For every structure `G` and every map `π : G → P`, `G ⊨ ∀x₁∃y₁ ⋯ ∀x_ℓ∃y_ℓ ψ` iff the projection of the
full strategy's induced hypothetical passes alternating evaluation.
**Formalization Note** The corrected table holds one hypothetical per node (Observation 5.79), so the
printed test on that entry would ask all leaves to satisfy `ψ`, and the full strategy has losing
responses. Alternating evaluation replaces it. The map `π` need not be surjective. -/
theorem root_evaluation {σ : Sig} (G P : Type) [σ.lang.Structure G] (π : G → P) (ℓ : ℕ)
(ψ : σ.lang.BoundedFormula Empty (2 * ℓ)) (hψ : IsMatrix ψ) :
AltSat (G := G) ψ ℓ [] ↔ eval ψ ℓ (push π ℓ (ind σ (2 * ℓ) ℓ (Strat.full G ℓ) [])) := by sorry
end CoDecompFO
Source
Bumpus, Gomes, Larios-Jones, Turner, Co-Decompositions and FO Model Checking, arXiv:2611.04658 (held file sha256 d550d7af…), proof of Theorem 1.16, p.41
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.