How Can You Prove the Completeness of $\mathbb{N}$?

Question

I am trying to self-study real analysis and I am finding it difficult to prove some statements even when I have intuition for it. One exercise in my book asks:

Prove that $\mathbb{N}$ is complete.

So I have intuition for the proof. My thinking is that if I have nonepty $A \subseteq \mathbb{N}$, where $A$ has an upper bound, then it should also have a maximum which is its supremum. That would imply that $\sup(A) \in A$, which would then also imply that $\sup(A) \in \mathbb{N}$ since $A \subseteq \mathbb{N}$. Then if my reasoning is correct, this would then show that $\mathbb{N}$ is complete. However I cannot figure out how to prove that a if $A \subseteq \mathbb{N}$ has an upper bound, it has a maximal element. How can one prove this statement? Also, are there other ways to show that $\mathbb{N}$ is complete?

Answer 1

My first thought is to try showing any Cauchy sequence converges. But the Cauchy sequences are eventually constant. Hence they converge.

Answer 2

Suppose $A \subset \Bbb{N}$ is bounded by $M$, then $|A| < M$, and $A$ is a finite set. Every finite set has a maximum. (Sort the elements; this is a finite process for a finite set.)

(There are straightforward modifications if your version of bounded uses nonstrict inequality or your version of the natural numbers does not include $0$.)

A direct construction using well ordering is...

For each $a \in A$, define $f(a)$ to be the interval $[a,\infty) \subset \Bbb{N}$. Then $$ F = \bigcap_{a \in A} f(a) $$ is a subset of $\Bbb{N}$. Since $A$ is bounded, by $M \in \Bbb{N}$, $M \in f(a)$ for all $a \in A$. This shows $F$ is nonempty, so by well-ordering, $F$ has a least member, $m$. Observe that $m$ is in $f(a)$ for each $a$, so $a \leq m$. We have only to show $m$ is in $A$ to show that $m$ is the maximum element of $A$.

Suppose $m \not\in A$. Since $m \in f(a)$ for each $a \in A$, $a +1 \leq m$. But then $m-1 \in f(a)$ for every $a \in A$, so the minimum of $F$ would be no greater than $m-1$, leading to a contradiction.

Answer 3

There are several different notions of “completeness”. From the context of your tags, it seems you mean Dedekind completeness (i.e. every upper-bounded set has a least upper bound). If you mean metric completeness, Chris Custer’s answer has you covered.

You could prove $\mathbb{N}$ is (Dedekind) complete from the well-ordering of $\mathbb{N}$. Let $$S = \{n \in \mathbb{N} : (\forall a \in A)(a \leq n)\} ,$$ i.e. $S$ is the set of all upper bounds on $A$. By the well-ordering of $\mathbb{N}$, the set has a minimum, which would be a least upper bound.

Alternatively, you could do a proof by induction. Assume for contradiction that $A$ has no least upper bound. Let $U$ be some upper bound. Define a sequence $f(n)$ by setting $f(1) = U$, and recursively choosing $f(n + 1)$ to be some upper bound that’s less than $f(n)$, which exists because no least upper bound exists. Then $f(n) \leq U - (n - 2)$, but this means that $f(U + 3) \leq -1$, which is impossible. Thus a contradiction.