Proof of `Positive Σ₁ Model Checking Reduces to Binary Relations`
groundedproofs/Lax496464Proofs/WHierarchy/Lemmas/Incidence/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
The incidence structure: the universe gets one new element per tuple (in the order the word lists them), unary symbols hold the new elements of the tuples of , binary symbols connect entry of a tuple to its element. Each atom becomes for a fresh , bound in front with the other quantifiers. The map is computed by one IMP+ program in cubic time; the new formula is at most six times as large.