# First-order Peano Axioms and order-completeness of $\mathbb{N}$

Definition: An ordered set is order-complete if any nonempty subset with an upper bound, has a lowest upper bound or supremo.

Notation: We denote the system of first-order Peano Axioms (along with axioms for addition and multiplication) by PA1.

1.- Can we express the order-completeness of $\mathbb{N}$ using first-order logic? How does it look?

2.- Can we prove that natural numbers are order-complete using PA1 or it has to be considered as an axiom?

• The natural numbers are not order complete, because $\mathbb N$ has no upper bound. – Andrés E. Caicedo Feb 27 '14 at 3:09
• hahaha ok, I have to change the definition of order-complete. – Chilote Feb 27 '14 at 3:19

By compactness, first order $\mathsf{PA}$ is not enough to describe the least upper bound property. This follows from the existence of non-standard models of $\mathsf{PA}$, which is an obvious consequence of compactness (let $c$ be a new constant symbol, and consider the result of adding to $\mathsf{PA}$ the axioms "$c>\underline n$" for all $n$). Now, any non-standard model has an initial segment isomorphic to $\mathbb N$. This segment has no supremum. Because if $a$ is larger than all the standard integers, then so is $a-1$. What you have is that any definable set with an upper bound has a supremum, since for each definable set, the corresponding statement is an easy consequence of an appropriate instance of (first-order) induction.
By the way, this gives us the nice and very useful property of overspill in non-standard models: Given a non-standard model $\mathcal N$, if $\phi(x)$ is a first order property (perhaps with parameters from $\mathcal N$), and $\phi(n)$ holds in $\mathcal N$ for infinitely many standard integers, then it holds of some non-standard integers as well. Otherwise, there would be a first $m$ such that $\phi(k)$ fails for all $k\ge m$, and this $m$ would be a supremum of the standard part.
• In that case, why is the following attempt incorrect? For every formula $P(x)$ in the language consider the formula $Q(x):=(\forall n)(P(n)\to n\leq x)$. The least upper bound property can be defined as the following scheme: $$(\exists n_0)P(n_0)\to(\exists k)(\forall n)(Q(k)\& Q(n)\to k\leq n)$$ For every formula $P(x)$. – Chilote Feb 27 '14 at 7:12