Proof of `Σ₁ Model Checking over Binary Relations Reduces to Clique`

groundedproofs/Lax496464Proofs/WHierarchy/Lemmas/BinaryToClique/Final.lean · lax-496464

What this proof establishes

Assuming the claims on the left, the claim on the right holds — checked by the archive's pipeline. Proof code is not displayed here.

Read the Lean proof on GitHub

Description

p−MC(Σ1[2])≤fptp−Cliquep-MC(Σ₁[2]) ≤fpt p-Clique (Flum–Grohe, Lemma 6.14). For an instance (A,∃xˉψ)(A, ∃x̄ ψ), list the qq atoms of ψψ and their two variables (2q2q rows); for every truth valuation cc of the atoms under which ψψ holds, the vertices (c,e,r)(c, e, r) — a candidate value ee for the variable of row rr — are joined when their rows differ, rows of one variable carry one value, and the two rows of an atom carry values that give the atom the truth value cc assigns it. A 2q2q-clique is exactly a satisfying assignment. The candidates are the entries of the word inside the universe and the first ∣x∣+2q|x| + 2q elements (isolated elements are interchangeable), so the graph has at most 2q⋅4∣x∣⋅2q2^q · 4|x| · 2q vertices; the new parameter is 2q≤2∣φ∣2q ≤ 2|φ|.