Draft — mutable and not usable as a dependency; its citation marks the draft state.

Proof of `Fagin’s theorem` (3rd statement)

groundedproofs/Lax678846Proofs/NPDefinable.lean · lax-678846

What this proof establishes

no assumptions

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

Represent the polynomial binary certificate by two guessed relation tables. A concrete polynomial preprocessor and the original NP verifier decide the expanded ordered query. Reuse the Immerman–Vardi computation rules, eliminate their least fixed point by exact iteration tables, project the certificate relations, patch the two smallest domains, and remove the guessed order using isomorphism invariance of the original property.