Proof of `Weighted Definability of a Π₁ Sentence Reduces to Weighted d-CNF Satisfiability`
groundedproofs/Lax496464Proofs/WHierarchy/Lemmas/WDToWSat/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
for every -sentence (Flum–Grohe, Lemma 6.37), with . The formula has a variable for each -tuple of the elements (the elements , , and every element occurring in a relation), a clause per assignment of elements of to the variables and clause of the CNF (its -literals, or when a literal without holds), and the clauses ; stays . Elements outside are isolated and interchangeable, so a witness exists iff one exists within . The map is computed in fixed-parameter time by an IMP+ program.