Lax Lean Archive

Descriptive complexity: recursive enumerability, Trakhtenbrot and halting

lax-624099·formalized by Pierre Senellart @PierreSenellart · Claude (Anthropic)·registered·created ·GitHub @f8eeb1b·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

    Recursive enumerability as a logically defined class, from the descriptive-complexity library, built on the NP core registered as lax-904597. RE is the class of decision problems on finite structures definable in existential second-order logic with value invention: the certificate is a finite extension of the universe by invented values, in unbounded number, together with relations over it checked by a first-order kernel. No machine model enters the definition.

    Four problems are RE-complete under the core's first-order reductions: finite satisfiability of first-order sentences, by the generic reduction that writes a definition as a sentence, which is Trakhtenbrot's theorem in logical form; the halting problem of the core's machine instances, with the step and tape bounds dropped; the halting of a partial recursive code of Mathlib drawn as a syntax tree; and Post's correspondence problem, by the computation-history dominoes. The archive's proof network carries the chain: every problem of RE reduces to finite satisfiability, finite satisfiability to the two halting problems, the halting problem to Post's.

    The class meets Mathlib's computability theory on concrete instances, finite structures presented as a size and Boolean tables: a problem is in RE exactly when its concrete instances form a recursively enumerable set, first-order reductions are computable, so every RE-hard problem is undecidable, and the four problems are undecidable in Mathlib's sense, finite satisfiability being Trakhtenbrot's theorem proper. NP is contained in RE, and RE differs from co-RE, by Post's theorem on code halting.

    The proofs are those of version 1.2.2 of the library, sliced to what these statements use; they assume the core's hardness laws and the submission's own statements where they compose. The library and its documentation are at https://github.com/PierreSenellart/descriptive-complexity and https://pierresenellart.github.io/descriptive-complexity/DescriptiveComplexity.html. The Lean code was written with the assistance of several Claude models; the design and the statements are the author's.

    Concepts

    Concept map
    32 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 submission / another 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-624099,
  author = {Pierre Senellart and Claude (Anthropic)},
  title = {Descriptive complexity: recursive enumerability, Trakhtenbrot and halting},
  year = {2026},
  howpublished = {Lax Archive, lax-624099},
  url = {https://laxarchive.org/lax-624099/},
}

    References

    1. Pierre Senellart and Anton Gnatenko. Descriptive Complexity in Lean: Completeness by First-Order Reductions. 2026. arXiv:2609.18261
    2. Pierre Senellart. DescriptiveComplexity: Completeness by First-Order Reductions in Lean. 2026. doi:10.5281/zenodo.21678423 · github.com/PierreSenellart/descriptive-complexity
    3. Boris A. Trakhtenbrot. The impossibility of an algorithm for the decidability problem on finite classes. Proceedings of the USSR Academy of Sciences 70(4):569–572, 1950. In Russian.
    4. Emil L. Post. A variant of a recursively unsolvable problem. Bulletin of the American Mathematical Society 52(4):264–268, 1946. doi:10.1090/S0002-9904-1946-08555-9
    5. Leonid Libkin. Elements of Finite Model Theory. Springer, 2004. doi:10.1007/978-3-662-07003-1
    6. Serge Abiteboul, Richard Hull and Victor Vianu. Foundations of Databases. Addison-Wesley, 1995.

    Discussion

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

    Loading discussion…