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.

Read the Lean proof on GitHub

Description

The incidence structure: the universe gets one new element per tuple (in the order the word lists them), unary symbols PiP_i hold the new elements of the tuples of RiR_i, binary symbols ElE_l connect entry ll of a tuple to its element. Each atom Riy0…yk−1R_i y_0 … y_{k-1} becomes E0y0z∧…∧Ek−1yk−1z∧PizE_0 y_0 z ∧ … ∧ E_{k-1} y_{k-1} z ∧ P_i z for a fresh zz, 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.