Boundedly axiomatizable theories meet (in)completeness

Ali Enayat^1
1 University of Gothenburg

Recently Albert Visser and I wrote a paper on the incompleteness of boundedly axiomatizable theories [1], which arose from a question posed by Steffen Lempp and Dino Rossegger in the context of calibrating the Borel complexity of the family of models of a given first order theory. The main result of our paper shows that any consistent extension of a sequential theory that is axiomatizable by a set of axioms of bounded complexity is incomplete. In the theorem “complexity” refers to the depth-of-quantifiers-alternation, which in the context of arithmetical theories that contain $\mathsf{I\Delta}_0+\mathsf{Exp}$, agrees with the usual $\Sigma_n$-complexity measure (in which $\Sigma_0$ corresponds to formulae all of whose quantifiers are bounded). This result has also had a number of offshoots, one of which is the ongoing work of Visser, Mateusz Lelyk, and myself on the construction of completions of the arithmetical theories ${\sf PA}^-$ and ${\sf IOpen}$ that, in contrast, lend themselves to axiomatizability by sentences of bounded complexity as measured by the $\Sigma_n$-complexity measure. This tutorial aims to provide an exposition of these recent developments.

References

[1] A. Enayat, A. Visser, Incompleteness of boundedly axiomatizable theories, arXiv:2311.14025 [math.LO], 2023

(Download the slides.)

 Overview