30
$\begingroup$

By "formal analogies" between the metamathematics of $\mathsf{ZFC}$/set theory and $\mathsf{PA}$(=Peano Arithmetic)/first order arithmetic, I mean facts such as the following:

  • We are considering a first-order theory ($\mathsf{ZFC}$ or $\mathsf{PA}$) motivated as a first-order approximation to a second-order theory (second-order $\mathsf{ZFC}^2$ or $\mathsf{PA}^2$) which is "more or less" categorical; because of this, some axioms (the separation and replacement axioms on the one hand, the induction axiom on the other) have to be stated as axiom schemes in the first-order theory.

  • There is an interesting hierarchy of formulæ, $\Sigma_n$ or $\Pi_n$, based on alternations of quantifiers (viz.: the arithmetic hierarchy vs. the Lévy hierarchy); at the lowest ($\Delta_0$) level of this hierarchy are formulæ with only "bounded" quantifiers.

  • There is a uniform truth predicate for any (concrete) given level of the hierarchy, which is built upon some kind of absoluteness of $\Delta_0$ formulæ. As a related fact, the infinite axiom schemes are naturally stratified along the hierarchy (they can be cut off at the $\Sigma_n$ level and stated as a single formula for each concrete $n$).

  • There is a reflection theorem which ensures that any finite set of true statements (or one bounded in the hierarchy of formulæ) is consistent. In particular, the full theory proves the consistency of the subtheory with the axiom schemes cut off at the $\Sigma_n$ level: that is, the theory ($\mathsf{ZFC}$ or $\mathsf{PA}$) is reflexive. In fact, it is even essentially reflexive (every consistent extension is reflexive).

  • There is a conservative two-kinded extension (Gödel-Bernays on the set theoretical side, $\mathsf{ACA}_0$ on the arithmetical side) which is obtained by allowing formation of classes but only with a comprehension scheme for such classes that does not involve quantifying over classes; remarkably, this conservative two-kinded extension is finitely axiomatizable. There is also a standard strictly stronger two-kinded extension (Morse-Kelley on the set-theoretical side, second-order arithmetic $\mathsf{Z}_2$ seen as a first-order theory on the arithmetical side).

(I hope I didn't mess things up too much, but all of these facts are standard and can be found in standard textbooks such as Jech's Set Theory for the set-theoretical side and Hájek and Pudlák's Metamathematics of First-Order Arithmetic plus Simpson's Subsystems of Second-Order Arithmetic for the arithmetical side.)

I'm sure many more examples can be found. Maybe I should also nod to the similarity between proof theory of extensions of $\mathsf{PA}$ by analysing ordinal notations made by collapsing recursively large ordinals, and large cardinal extensions of $\mathsf{ZFC}$ — or maybe not.

Yet as striking as this analogy seems, nobody seems to comment upon it as far as I know. (At the very least, this seems pedagogically regrettable: I'm sure all of the above statements would be more memorable to students if the analogous statements were made explicit.)

So: is there some deeper truth to be found behind this parallelism? (Or are all my sample facts just aspects of a single phenomenon? Or is this just a red herring?) Might it make sense to bring $\mathsf{ZFC}$ and $\mathsf{PA}$ under an umbrella metatheory so that the above facts can be proved in a common formalism? At the very least, is there a textbook I missed where the analogy is played out in some detail?

And perhaps more thought provokingly: can one give an example of a completely different kind of theory that is just as similar to $\mathsf{ZFC}$ and $\mathsf{PA}$ as they are to each other?

(I'm of course aware that are also huge differences between $\mathsf{ZFC}$ and $\mathsf{PA}$; but I would tend to say that they make the similarities all the more striking.)

$\endgroup$
  • 3
    $\begingroup$ The part about axiom schemata is a red herring, IMO: there is always a way to build a conservative extension to the theory with only finitely many axioms. One fact that might help understanding the analogy is the following fact: ZF+negation of infinity is equivalent to PA, in the sense that each is interpretable in the other and the interpretations are inverse to each other. $\endgroup$ – cody Dec 29 '15 at 21:55
  • 1
    $\begingroup$ Perhaps this is too glib, but several of these similarities seem to stem from the fact that both systems were, in part, set up to provide a formalism for the foundations of (a lot of) mathematics, in a hierarchical (as opposed to a structuralist) way. Truth, reflection, and hierarchy seem to emerge rather naturally from such a project. $\endgroup$ – Timothy Chow Dec 30 '15 at 2:57
  • $\begingroup$ Gro-Tsen, does Ed Nelson's IST qualify? $\endgroup$ – Mikhail Katz Dec 30 '15 at 17:35
23
$\begingroup$

A significant amount of the parallelism can be explained by the bi-interpretabiity of $PA$ with $ZF^{-\infty}$ ("finite set theory"), which is the theory obtained from $ZF$ by replacing the axiom of infinity by its negation, and adding the sentence asserting that every set has a transitive closure. For more detail and references, see my joint paper with Schmerl and Visser entitled $\omega$-Models of Finite Set Theory here.

But that is only part of the story since the parallelism between arithmetic and set theory is deep and mysterious. I can even say that my career as a logician has been greatly shaped by comparing and contrasting the metamathematics of arithmetic and set theory.

My 1998-paper Analogues of MacDowell-Specker Theorem for Set Theory, available here, gives a synopsis of the similarities and differences between $PA$ (equivalently: $ZF^{-\infty}$) and $ZF$ through the lens of model theory.

Added in the third edit: Here is a relevant quote from the above paper:

The axiom of infinity is of course only the first step in the progression of ever bolder large cardinal axioms. As we shall see below, the negation of the axiom of infinity endows $ZF^{-\infty}$ with a model theoretic behavior that $ZF$ can only imitate with the help of additional axioms asserting the existence of large cardinals. This is partially explainable by noting that the negation of the axiom of infinity in finite set theory itself can be viewed as a large cardinal axiom, not positing the existence of a large set - indeed denying it - but attributing a large cardinal character to the universe itself. Of course the axioms of power set and replacement give a ”strong inaccessibility” character to the class of ordinals which allows models of $ZF$ to share some of the model theoretic properties of $ZF^{-\infty}$.

Added in the second edit: In this 2009-presentation I describe a scheme $\Lambda$ (named in honor of Azriel Levy) consisting of set-theoretic sentences of the form "there is an $n$-reflective, $n$-Mahlo cardinal" which has the surprising property that:

$ZFC + \Lambda$ is the weakest extension of $ZFC$ whose model-theoretic behavior matches that of $PA$, in several surprising respects. So $PA$ is used here as a guide to find an improvement of $ZFC$.

Most, but not all of the results in the presentation have appeared in print.

$\endgroup$
  • $\begingroup$ @Prof. Enayat: Since Robinson arithmetic $Q$ can also be formulated in finite $ZF$, does $Q$+"Second-order Mathematical Induction " imply some form of the Axiom of Infinity? $\endgroup$ – Thomas Benjamin Dec 30 '15 at 16:19
  • 2
    $\begingroup$ @Thomas Benjamin: when mathematical induction is added to $Q$ (within second order logic), we obtain full second order arithmetic, which is a categorical theory in second order logic, whose only model up to isomorphism is bi-interpretable with the structure $(H(\omega_1), \in)$, which of course is a model of axiom of infinity, more specifically, it is a model of all the axioms of ZFC except the power set axiom. However, most people think of second order logic as a reformulation of set theory, so the fact that we get a model of the Axiom of Infinity is not surprising. $\endgroup$ – Ali Enayat Dec 30 '15 at 16:42
  • $\begingroup$ @Prof. Enayat: Is there a difference then between second-order $PA$ and full second-order arithmetic? (Sorry for seeming obtuse....) $\endgroup$ – Thomas Benjamin Dec 30 '15 at 22:24
  • 1
    $\begingroup$ @Thomas Benjamin: in my usage, full second order arithmetic is formulated in second order logic, whereas what is commonly referred to as second arithmetic by many logicians, is a first order theory $Z_2$ (e.g., in Simpson' s comprehensive textbook on the subject). It is well-known that $Z_2$ can interpret the theory obtained by deleting the power-set axiom from $ZF$ and adding the sentence "every set is finite or countable". The details are in Simpson' s book. $\endgroup$ – Ali Enayat Dec 31 '15 at 8:35

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.