5
$\begingroup$

I think this needs to be clarified, so it would be helpful to see an answer to this somewhere.

I've seen the following terms:

  1. Peano arithmetic.
  2. Second-order arithmetic.
  3. Second-order Peano arithmetic.

Can anyone make a clear explanation of the difference between the three terms and what they mean?

My understanding is that (1) and (2) are theories in first-order logic and (3) is a theory in second-order logic. In particular, second-order arithmetic is a first-order theory, and it's NOT the same as second-order Peano arithmetic. Is this true?

What are the axioms for each theory? How do they differ?

$\endgroup$

1 Answer 1

4
$\begingroup$

Yes, your understanding is basically right.

In more detail:


The term "Peano arithmetic" is used variously by different communities to refer to either first or second order Peano arithmetic (I'll denote the latter by "$\mathsf{PA}_1$" and "$\mathsf{PA}_2$" respectively). Within the modern mathematical logic community, "Peano arithmetic" almost exclusively refers to $\mathsf{PA}_1$; however, in older texts and among philosophers and historians of mathematics, it often refers to $\mathsf{PA}_2$.

The theory $\mathsf{PA}_1$ is usually formulated in the language $\{0,1,+,\times,<\}$ or something similar; roughly speaking, the only crucial point is that we have both addition and multiplication (arithmetic with only addition, for example, is quite a different matter). The axioms of $\mathsf{PA}_1$ consist of:

  • the discrete positive ordered semiring axioms (often denoted "$\mathsf{P}^-$"); and

  • the full first-order induction scheme.

Weakening the induction scheme to apply to only certain first-order formulas results in subtheories of $\mathsf{PA}_1$; e.g. $\mathsf{I\Sigma_{17}}$ is the fragment of $\mathsf{PA_1}$ consisting of $\mathsf{P}^-$ together with induciton for $\Sigma_{17}$ formulas.

Meanwhile, $\mathsf{PA}_2$ is usually formulated in the much smaller language $\{0,\mathsf{succ}\}$ with a very sparse set of axioms ... followed by the full second-order induction axiom. Again, there is some flexibility in the details but the power of the underlying logic is such that it ultimately doesn't matter.

(As an aside, if we build a direct analogue of $\mathsf{PA_1}$ with second-order logic replacing first-order logic in the setup of the induction scheme we get something appropriately equivalent to $\mathsf{PA}_2$; see here.)


"Second-order arithmetic" meanwhile refers to the two-sorted, first-order theory $\mathsf{Z_2}$. The two sorts are generally called "numbers" and "sets," and the axiom of extensionality (which is part of $\mathsf{Z_2}$) ensures that we can WLOG restrict attention to models whose sets sort literally consists of subsets of the numbers sort and whose elementhood relation is actual elementhood. The language of $\mathsf{Z_2}$ consists of the language of $\mathsf{PA}_1$ on the numbers sort, and the new binary relation "$\in$" connecting the numbers and sets sorts. Its axioms consist of:

  • $\mathsf{P}^-$ for the numbers sort,

  • extensionality for the sets sort, and

  • the full induction and comprehension schemes.

Whereas the interesting subtheories of $\mathsf{PA}_1$ essentially arise from restricting the induction scheme, $\mathsf{Z_2}$ is "two-dimensional:" we get interseting subtheories by restricting either the induction or comprehension schemes.


For further reading about $\mathsf{PA}_1$ and $\mathsf{Z_2}$, and their interesting subtheories specifically, I strongly recommend Hajek/Pudlak and Simpson respectively. See also my recommendations here and here.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .