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?

  • $\begingroup$ The natural numbers are not order complete, because $\mathbb N$ has no upper bound. $\endgroup$ – Andrés E. Caicedo Feb 27 '14 at 3:09
  • $\begingroup$ hahaha ok, I have to change the definition of order-complete. $\endgroup$ – 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.

| cite | improve this answer | |
  • $\begingroup$ 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)$. $\endgroup$ – Chilote Feb 27 '14 at 7:12
  • $\begingroup$ You are only obtaining the least upper bound property for definable sets. As I said, that's fine. But many sets are not definable. $\endgroup$ – Andrés E. Caicedo Feb 27 '14 at 7:17
  • $\begingroup$ But, can we say that every upper bounded set of natural numbers is definable? $\endgroup$ – Chilote Feb 27 '14 at 16:43
  • $\begingroup$ Of course: It is finite. Since parameters are allowed, you can just list its elements. $\endgroup$ – Andrés E. Caicedo Feb 27 '14 at 17:26
  • $\begingroup$ So then the scheme that I posted before is a correct description of the least upper bound property using PA. or not? $\endgroup$ – Chilote Feb 27 '14 at 18:36

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.