First order theories stronger than PA

Question

I'm trying to learn basic logic, and it seems that Peano Arithmetic — a first order theory of the natural integers with $+$ and $\times$ symbols, is a common object of interest.

We could define (a priori) richer theories of arithmetic, for instance if we introduce the operation $x^y$ (exponentiation).

Also, we could add axioms for negative numbers and the $-$ symbol and define a theory of which $(\mathbb{Z}, +, -, \times)$ would be a model, for instance.

Wouldn't those two theories have theorems that are not theorems in Peano Arithmetic? If so, why is only Peano Arithmetic presented in all logic courses?

Answer 1

Usually by PA, we understand that we are including the induction axiom in the theory, as in the wiki page. If this is the case, you could define $+, \times$, exponential, all by induction, as can be see in the wiki. So adding exponential doesn't make it stronger.

A common motif is not use the induction axiom, as it is too strong. In this case we could work with the Robinson arithmetic (theory Q), which is as incomplete as PA. As commented, we can define exponentiation here also by the $\beta$-function.

But, because Peano arithmetic (or Q) is incomplete, there is a Gödel sentence there $G$ that the system can't prove or refute. So we could add $G$ to PA as an axiom. This system would be stronger than PA, because PA + G would proof G and PA alone could not proof it. But PA + G would also be incomplete, so we could add G', and so on. In this way we can get a infinite sequence of stronger theories.

We are still in the realm of same language theories. But in fact theories with different languages, as one with the $-$ sign could be compared with arithmetic, if we can define a sufficient amount of arithmetic there. The same happens with the ZFC axioms for set theory, which is incomplete. We can create symbols in ZFC that would act exactly as the ones in PA. Specifically: the set of finite ordinal numbers {0,1,2,...} (denoted $\omega$) can be defined in ZFC, and also the + and $\cdot$ operations. In ZFC you can prove that all of PA holds for the structure $(\omega,+,\cdot)$. We say that we've interpreted PA in ZFC.

In ZFC you can prove many things about PA (thus interpreted) that cannot be proven in PA. But this "PA in ZFC" is still incomplete: there are sentences of PA that cannot be decided one way or the other using ZFC.

So PA (or Q) is important because it can show that another systems that have it as subsystems are incomplete. And of course there are other interests besides incompleteness results.

Answer 2

We have to distinguish between superficially different theories, and theories that are "essentially different".

For example, you ask about adding exponentiation to PA. As noted in the comments, this does not essentially enrich PA, because exponentiation can be defined in PA. To be specific, there is a formula $\eta(x,y,z)$ in the language of PA (L(PA)) such that $$\eta(x,y,z) \Leftrightarrow x^y=z$$ (Finding such a formula $\eta$ is quite tricky!) That means that if L(PA+exp) stands for the augmented language, then any formula in L(PA+exp) can be translated in a mechnical fashion into a formula of L(PA). Furthermore, say PA+exp is PA augmented with the obvious axioms for exp. Then any theorem of PA+exp can be proved in translated form in PA.

The same essentially is true for $(\mathbb{Z},+,\cdot,<)$ vs. $(\mathbb{N},+,\cdot)$. The translation this time is more complicated, and can be done in various ways. One approach: represent integers by pairs of natural numbers, $(s,n)$, with $s=0$ or $1$, and $(s,n)$ stands for $n$ if $s=0$ and $-n$ if $s=1$. (This is clunky but it works.) Formulas of L(PA) and (let's call it) L($\pm$PA) can be translated back and forth, although the details are messy.

It's even true that the theory of $(\mathbb{Q},+,\cdot,>)$ is "essentially the same" as the theory of $(\mathbb{N},+,\cdot)$, in this "mutual translation" sense.

On the other hand, multiplication cannot be defined in Presberger arithmetic. So PrA is essentially different from PA.

PA can be translated into the language of set theory, say ZFC. Let $\omega=\{0,1,\ldots\}$, the set of finite ordinals. In ZFC there are formulas defining addition and multiplication for the elements of $\omega$. Also, ZFC can prove that $(\omega,+,\cdot)$ is a model of the PA axioms. Write $\theta^\text{ZFC}$ for a formula $\theta$ in L(PA) translated into L(ZFC). ZFC is stronger than PA in the following sense: if PA proves $\theta$, then ZFC proves $\theta^\text{ZFC}$, but there are formulas $\theta$ that cannot be proven or disproven in PA, where ZFC proves $\theta^\text{ZFC}$.

An example of such a formula is Con(PA), the consistency of PA. Using Gödel coding, this can be expressed as a sentence in L(PA), but by Gödel's second incompleteness theorem, cannot be proved in PA. However, since ZFC can prove that $\omega$ is a model of PA, it follows that ZFC can prove Con(PA).

However, this "L(PA) part of ZFC" is not complete. For example, Con(ZFC) can also be expressed as a formula of L(PA). But ZFC cannot prove this.

Why do logic textbooks use PA as an example and not, say, an axiom system for the integers? Partly tradition, and partly that while $\mathbb{Z}$ is algebraically nicer than $\mathbb{N}$, $\mathbb{N}$ is "neater" for most of what one wants to do in a logic course. (For example, the statement of the induction axioms.)