Lax Lean Archive

The Immerman–Vardi theorem

lax-751879·formalized by Szymon Toruńczyk @szymtor · GPT 6·registered·created ·GitHub @9fa0990·Lean v4.33.0 epoch · mathlib db584cd6d46c

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 proves the Immerman–Vardi theorem: on finite linearly ordered relational structures, a query is definable in first-order logic with least fixed points if and only if it is decidable in deterministic polynomial time. The statement covers queries of every fixed arity, including Boolean queries.

    The concepts specify finite ordered structures, syntactically positive fixed-point formulas and their semantics, an explicit dense binary encoding, and polynomial time using mathlib's finite Turing machines. Empty universes and nullary relations are included.

    Both computational directions are proved. A concrete Turing-machine decoder and relation-table evaluator decide each fixed FO(LFP) query in polynomial time. Conversely, a finite positive rule system represents the initialized, polynomially bounded computation of an arbitrary finite multi-stack Turing machine. Its least fixed point is proved equal to the encoded computation; an accepting-output formula defines the query on sufficiently large domains, and finite diagrams handle the remaining domains.

    The proofs include the fixed-point laws, positivity and monotonicity, encoding injectivity, and the simulation and runtime arguments. The main theorems use only Lean's standard background axioms, with no unproved simulation assumptions.

    This is a Lean 4.33 port of the original Lean 4.30 draft.

    Concepts

    Concept map
    8 concepts; 4 descendants hidden
    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-751879,
  author = {Szymon Toruńczyk and GPT 6},
  title = {The Immerman–Vardi theorem},
  year = {2026},
  howpublished = {Lax Archive, lax-751879},
  url = {https://laxarchive.org/lax-751879/},
}

    References

    1. 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
    2. Neil Immerman. Relational Queries Computable in Polynomial Time. Information and Control 68(1–3):86–104, 1986. doi:10.1016/S0019-9958(86)80029-8 · people.cs.umass.edu/~immerman/pub/query.pdf
    3. Moshe Y. Vardi. The Complexity of Relational Query Languages. In Proceedings of the Fourteenth Annual ACM Symposium on Theory of Computing 137–146, 1982. doi:10.1145/800070.802186 · cs.rice.edu/~vardi/papers/stoc82.pdf

    Discussion

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

    Loading discussion…