6
$\begingroup$

If Peano axioms uniquely determine the natural numbers, doesn't this mean that Peano axioms are categorical and hence complete?

If above is true, how is it explained by Goedel's incompleteness theorem?

$\endgroup$
2
  • 4
    $\begingroup$ First-order Peano arithmetic is not categorical, because it replaces the second-order induction axiom with a first-order axiom schema that is weaker. $\endgroup$ May 15, 2017 at 12:19
  • 4
    $\begingroup$ And second-order Peano artihmetic is not (proof-theoretically) complete, since second-order logic does not possess a complete proof system. $\endgroup$
    – Nagase
    May 15, 2017 at 12:27

2 Answers 2

11
$\begingroup$

It depends what you mean by "Peano axioms".

M.Winter's answer assumes you mean the first-order Peano axioms. By the compactness theorem, no infinite structure can ever be captured up to isomorphism by a first-order theory, and no countable rigid structure (like $\mathbb{N}$) can ever be captured up to isomorphism amongst countable structures by a first-order theory. Moreover, by Godel's incompleteness theorem, PA isn't even complete: there are sentences which are true in some models of PA and false in others.

So first-order PA does a very bad job of capturing PA. The second-order axioms, meanwhile, are categorical: $\mathbb{N}$ is their only model (up to isomorphism). However, working in second-order logic has drawbacks: the semantics for second-order logic depend highly on set theory, to the point that there is a second-order sentence which is a validity if and only if the Continuum Hypothesis is true, and second-order logic has no complete and sound proof system. Of course, if we embrace set theory then things get somewhat better: any model $M$ of the first-order(!) theory ZFC contains a unique up-to-internal-isomorphism structure which it thinks is a model of the second-order Peano axioms. However, different models can disagree about what exactly these axioms entail, so this ultimately just pushes back the question to the incompleteness of the theory ZFC (and also is really a thinly-veiled transformation of second-order PA into something embedded in a first-order theory, so dodging the really deep second-order questions). Ultimately there's no escaping the logical commitments needed for second-order logic to work properly in this context.

So the version of the PA axioms which do capture $\mathbb{N}$, do so by invoking a very messy logical framework.

$\endgroup$
5
$\begingroup$

The Peano axioms do not pin down the natural numbers uniquely (see this amazing answer to some silimar question of mine).

As you said, there is Gödel's incompleteness theorem which prevents this from happening. Each approach to pin down the natural numbers must fail in one of these points:

  • You will have other models, so called non-standard natural numbers that also satisfy your axioms. Your axiom system is too weak to tell you which model you are currently talking about. This happens in the first-order Peano axioms.
  • If your axioms determine the natural numbers uniquely, then there is still no way to prove all truths about them, because we have no way to perform these proves. Our prove techniques are just to weak. This is seen as worse than not pinning down $\Bbb N$. This happens in the second-order Peano axioms.
  • The axioms you desire are not computably enumerable, i.e. there is no procedure to write them down. There is indeed an axiom system that describes $\mathbb N$ uniquely, but there is no algorithm in the world to give it to you or write it out completely (or in a closed form). This happens in the theory $\mathrm{Th}(\Bbb N)$ of all true sentences of $\Bbb N$.
  • Absurdely but possible, your proof system is chosen so unfavorable that it can prove all truths about $\Bbb N$, but also some wrong theorems about it. Very undesirable. Such a system is called not sound.

You can see this as the incapability of our finite axioms and prove systems (in the end, our finite human nature) to talk about infinite structures of some specific expressive power. We would need infinitely many space and/or time to talk about them uniquely.

$\endgroup$

You must log in to answer this question.

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