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.
Description
(Flum–Grohe, Lemma 6.14). For an instance , list the atoms of and their two variables ( rows); for every truth valuation of the atoms under which holds, the vertices — a candidate value for the variable of row — 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 assigns it. A -clique is exactly a satisfying assignment. The candidates are the entries of the word inside the universe and the first elements (isolated elements are interchangeable), so the graph has at most vertices; the new parameter is .