1
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ The natural numbers are not order complete, because $\mathbb N$ has no upper bound. $\endgroup$ Commented Feb 27, 2014 at 3:09
  • $\begingroup$ hahaha ok, I have to change the definition of order-complete. $\endgroup$
    – Chilote
    Commented Feb 27, 2014 at 3:19

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
7
  • $\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
    Commented Feb 27, 2014 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$ Commented Feb 27, 2014 at 7:17
  • $\begingroup$ But, can we say that every upper bounded set of natural numbers is definable? $\endgroup$
    – Chilote
    Commented Feb 27, 2014 at 16:43
  • $\begingroup$ Of course: It is finite. Since parameters are allowed, you can just list its elements. $\endgroup$ Commented Feb 27, 2014 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
    Commented Feb 27, 2014 at 18:36

You must log in to answer this question.

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