0
$\begingroup$

My question is stated in bold text.

This question pertains to the following formulation of Peano's axioms used to formalize an introduction of the natural numbers (beginning with 1) consisting of successions of vertical strokes drawn on paper in horizontal rows.

  • I. $1$ is a number.
  • II. To every number $a$ there corresponds a unique number $a^{\prime},$ called its successor.
  • III. If $a^{\prime}=b^{\prime},$ then $a=b.$
  • IV. $a^{\prime}\ne1$ for every number $a.$

  • V. Let $A\left(x\right)$ be a proposition containing the variable $x.$ If $A\left(1\right)$ holds and if $A\left(n^{\prime}\right)$ follows from $A\left(n\right)$ for every number $n,$ then $A\left(x\right)$ holds for every number $x.$

Are these axioms sufficient to determine the natural numbers $\mathbb{N}\equiv\left\{ 1,2,3,\dots\right\} ?$ Or is it necessary to add a further requirement that a number must inherit its membership in $\mathbb{N}$ from $1?$

For example, it seems that the set $\mathcal{N}=\mathbb{N}\cup\left\{ h\vert i\in\mathbb{Z}\land h=i+\frac{1}{2}\right\} $ is consistent with these axioms, with $a^{\prime}\equiv a+1,$ in the standard sense.

I propose that the following statement would fulfill such a requirement: The set of natural numbers contains the number $1$ as well as every number reached successively beginning with $1,$ with succession conforming to Peano's axioms as stated.

That avoids explicit reference to a "successor function", which would require additional definitions. Nonetheless, any such requirement stated in addition to Peano's axioms seems to presuppose ordering. Terms such as beginning with, repeated application, successively, inherited from, etc., appeal to our a priori notions of ordering. So I'm left wondering to what extent our subsequent theorems pertaining to ordering are actually derived results.

$\endgroup$
  • $\begingroup$ The original Peano's formulation of V is second-order : "for every property (or set) of numbers" and not "for every formula (of the Language)". $\endgroup$ – Mauro ALLEGRANZA Mar 11 at 14:04
  • $\begingroup$ There is a footnote in the text: "Thus $A\left(n\right)$ is the proposition that is formed when $x$ is replaced by $n$. Strictly speaking, $A\left(n\right)$ is a propositional form." $\endgroup$ – Steven Thomas Hatton Mar 11 at 14:09
  • $\begingroup$ I copied the actual axioms verbatim from the book. In another section the (different) authors state explicitly that they are confining their arithmetic to expression of first order logic. There is no indication in the section from which I am quoting that the authors intend their discussion to involve second order logic. $\endgroup$ – Steven Thomas Hatton Mar 11 at 14:36
  • 1
    $\begingroup$ Ok, thanks. See Non-standard model of arithmetic : "a non-standard model of arithmetic is a model of (first-order) Peano arithmetic that contains non-standard numbers. There are several methods that can be used to prove the existence of non-standard models of arithmetic." $\endgroup$ – Mauro ALLEGRANZA Mar 11 at 14:52
  • $\begingroup$ From the reference given in your user profile, and from the passage of text you have quoted, it seems you are referring to H. Behnke et al. (eds.), Fundamentals of Mathematics, Volume I: Foundations of Mathematics/The Real Number System and Algebra (MIT Press 1974). $\endgroup$ – Calum Gilhooley Mar 11 at 15:15
3
$\begingroup$

Yes, the (first-order) theory PA is not sufficient for characterizing $\mathbb{N}$ up to isomorphism.

In fact, no first-order theory can do the job for any infinite structure at all! This is a consequence of the compactness theorem:

  • Suppose $\mathcal{A}$ is an infinite structure in a language $\Sigma$ and $\Gamma$ is a set of sentences true in $\mathcal{A}$.

  • Fix a cardinal $\kappa>\vert\Gamma\vert$, and let $\Sigma^*$ be the language gotten by adding $\kappa$-new constant symbols $\{c_\eta:\eta<\kappa\}$ to $\Sigma$.

  • Let $\Gamma^*=\Gamma\cup\{c_\eta\not=c_\theta:\eta<\theta<\kappa\}$.

  • By the compactness theorem, $\Gamma^*$ has a model - any finite subset of $\Gamma^*$ can only mention finitely many of the new constants, so an appropriate expansion of $\mathcal{A}$ will do the job.

  • But any model of $\Gamma^*$ has cardinality $\ge\kappa$ - hence can't be $\mathcal{A}$ itself. But the reduct of such a model to the original language $\Sigma$ is a model of $\Gamma$, so there are $\Sigma$-structures satisfying $\Gamma$ which aren't (isomorphic to) $\mathcal{A}$.

(Note that the original formulation of PA was as a second-order theory; second-order logic can indeed capture $\mathbb{N}$ up to isomorphism.)

$\endgroup$
  • $\begingroup$ Since foundational mathematics is not my primary interest, it will be a while before I can attempt to understand why second order logic is necessary and sufficient to determine the natural numbers using Peano's Axioms. I hadn't realized there was a problem until I tried to show every number $\ne1$ is a successor. It's why I found the ordering theorems difficult. That axioms, as stated aren't sufficient to prove that given a number $n,$ I can "count backwards" to arrive at $1$. I have to wonder if the people who down-vote and close-vote my questions have ever gone through this exercise. $\endgroup$ – Steven Thomas Hatton Mar 14 at 10:48
  • $\begingroup$ I may have been too hasty in accepting this answer. Though your proposition is likely correct as a general statement about Peano's axioms; I believe the present formulation can easily be defended from my onjection. All that is necessary is the proposition that $x$ appears in a given succession beginning with $1$. It is true for $x=1$. If it is true for $x=n$ then it is clearly true for $x=n^\prime$. $\endgroup$ – Steven Thomas Hatton Mar 27 at 18:14
  • $\begingroup$ @StevenHatton " All that is necessary is the proposition that 𝑥 appears in a given succession beginning with 1" Great - that's still not first-order. There's no way around the necessity of something beyond first-order logic for truly pinning down $\mathbb{N}$. $\endgroup$ – Noah Schweber Mar 27 at 19:07
-2
$\begingroup$

The answer is no. It is fairly easy to show that the axioms as stated are sufficient to characterize the natural numbers.

Proof of the following theorem suffices: $\forall_n\left[ n=1\lor \exists_m n=m^\prime\right].$ This is shown as follows: $P\left[1\right]$ is given, and $P\left[n\right]\implies P\left[n^\prime\right]$ is axiomatic.

But this really isn't the entire proposition which I wanted to demonstrate.

A more complete statement such as: every number is either $1$ or succeeds $1$ does appear to require second order logic. By $n$ succeeds $1$, I mean that the number $n$ is either $1^\prime$, or is the successor of a number which succeeds $1$.

$$S\left[x\right]\text{:=}\left(x=1'\lor \exists _y\left[S\left[y\right]\land x=y'\right]\right).$$

The proposition that $n$ is either $1$ or $n$ succeeds $1$ is now:

$$P\left[x\right]\text{:=}\left(x=1\lor S\left[x\right]\right).$$

The inclusion of the existential quantifier in $S$ raises this to logic of the second order.

Part of the reason for my confusion is that the authors of BBFSK seem to take the existence of the natural numbers as a-priori. This is especially true the in first chapter where they omit the first two of Peano's axioms in their second-order logic statement of them.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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