Lax Lean Archive

While this submission is a draft, it cannot be used by other submissions.

Environment v4.30.0. The archive's epoch is v4.33.0; only submissions in v4.30.0 can cite this work.

Fagin’s theorem

lax-678846·formalized by Szymon Toruńczyk @szymtor · Codex 6·created ·GitHub @ce4e972·Lean v4.30.0 · mathlib c5ea00351c28

Loading review…

Community review

Flags

Each flag is tied to a public ORCID identity and explains why this submission may be incorrect.

No flags have been submitted.

    Community review

    Flag this submission

    State precisely what appears incorrect. This explanation will be public under your ORCID name.

    Abstract

    This submission formalizes Fagin’s theorem: an isomorphism-invariant property of finite relational structures is definable in existential second-order logic if and only if its binary encoding language belongs to NP.

    The logic has no built-in order. NP is defined by polynomially bounded binary certificates checked by a concrete deterministic polynomial-time Turing machine. Empty universes and nullary relations are included.

    Both directions reuse the Immerman–Vardi formalization. To obtain an existential second-order definition, the proof guesses certificate relations and an order, simulates the concrete polynomial verifier, and replaces its least fixed point by exact iteration tables checked by first-order formulas. It then projects the certificate relations and removes the auxiliary order. In the other direction, a concrete polynomial-time verifier decodes the guessed relation tables and runs the existing first-order evaluator.

    Concepts

    Concept map
    6 concepts
    100%
    Proven claimDefinitionThis submissionOther submissionA → B: B builds on A

    Proofs

    Proof networkview on GitHub

    100%
    assumptions conclusionProven claimStatement 1, 2, … of a claim with several statementsClaim from this submissionProof — open large view for details
    Proof list

    Lean sources for these proofs: proofs/ on GitHub

    Proof code is not displayed; the archive records each proof's checked relationship between claims.

    Related submissions

    Submission map

    100%
    This submissionOther submissionA → B: B's concepts build on A

    Cite this

    This is only the formalizers. The authors of the formalized results may be different (see References).

    @misc{lax-678846,
  author = {Szymon Toruńczyk and Codex 6},
  title = {Fagin’s theorem},
  year = {2026},
  howpublished = {Lax Archive, lax-678846},
  url = {https://laxarchive.org/lax-678846/},
  note = {draft},
}

    References

    1. Ronald Fagin. Generalized first-order spectra and polynomial-time recognizable sets. In Complexity of Computation 7:43–73, 1974. ronfagin.com/papers
    2. Leonid Libkin. Elements of Finite Model Theory. Springer, 2004. doi:10.1007/978-3-662-07003-1 · homepages.inf.ed.ac.uk/libkin/fmt/fmt.pdf

    Discussion

    Ask a question or add context. Endorsements and structured flags are kept in the review panel above.

    Loading discussion…