# Why do we need the axiom of completeness? Why won't Cantor's diagonalization work without it?

Okay so for my upcoming test I need to "be able to explain at least one result that would not hold if the axiom of completeness were not accepted"

My teacher suggested that I could try to explain why Cantor's diagonalization method won't work without the axiom of completeness, but I'm not really sure why it wouldn't work?

EDIT: If you can think of any easier examples I could explain for my test, that be great as well!

-
I assume you are referring to the "complete ordered field" axiomatization of the real numbers. The rational numbers satisfy all of the other axioms, so contrasting the rational numbers to the real numbers should help you figure things out. – Hurkyl Nov 4 '12 at 0:24
If this is a real analysis class, then I would rather highlight the importance of completeness in proving the intermediate value theorem. – Zhen Lin Nov 4 '12 at 0:43
Suppose you go through the diagonal argument and the number you find that is not on the list is $\pi-3$. Without completeness, we could say that is not a real number. – Ross Millikan Nov 4 '12 at 1:21

In Cantor's diagonalization argument, you assume (for a contradiction) that you can make a list $(x_1,x_2,x_3,\ldots)$ of all real numbers (let's say between $0$ and $1$ inclusive). We then construct a new number $y = .d_1 d_2 d_3 \ldots$ which differs from $x_1$ in the first digit, differs from $x_2$ in the second digit, and so on. We now say, aha, I have found a number in $[0,1]$ which is not on our list!

But wait, is $y$ really a number? Without completeness, we don't know that the infinite series $$y = \sum_{i=1}^{\infty} \frac{d_i}{10^i}$$ converges! And if that series does not converge, then we have failed to show that our list was incomplete.

-

That’s a rather strange suggestion on the part of your teacher, since there are much more straightforward examples, but it can be made to work. The version of the diagonalization that I think you have in mind argument constructs a non-terminating decimal that differs from each row from the diagonal entry in that row. In order to conclude that this decimal actually represents a real number not in your list, you must first show that it represents a real number. Let’s say that the decimal expansion looks like this: $0.d_1d_2d_3\ldots~$. We understand this to mean $\sum_{k\ge 1}\frac{d_k}{10^k}$, but that infinite series is really an abbreviation for

$$\lim_{n\to\infty}\sum_{k=1}^n\frac{d_k}{10^k}\;,\tag{1}$$

if it exists. Let $$s_n=\sum_{k=1}^n\frac{d_k}{10^k}\;,$$ the $n$-th partial sum; it’s these partial sums are all rational, and it’s easy enough to show that $s_1\le s_2\le s_3\le\ldots~$, but how do you know that the limit in $(1)$ exists? In other words, what guarantees that this $0.d_1d_2d_3\dots$, the one that disagrees with the diagonal in every row, actually represents a real number at all?

-
but how does the axiom of completeness tell us that "the number we create that's not on the list" converges? I know the axiom of completeness says that any subset of the Reals that is bounded above has a unique supremum. Obviously all the numbers on our list have an upper bound of 1, and due to the axiom of c. they all have a unique supremum. I get that, and Im going to assume this would apply to the new number we create as well. However how does the axiom of completness tell us that the new number we create coverges/is a real number? – MathMajor Nov 4 '12 at 0:46
Series converge. Numbers are just numbers. – Hurkyl Nov 4 '12 at 0:47
@MathMajor: First, numbers don’t converge; sequences do. You have the set $\{s_n:n\in\Bbb Z^+\}\subseteq\Bbb R$, and it’s bounded above by $1$, so it has a supremum. That supremum is in fact the limit in $(1)$, because the $s_k$ are non-decreasing. If you didn’t have completeness, $\{s_n:n\in\Bbb Z^+\}$ might not have a supremum, and then the limit in $(1)$ wouldn’t exist: your diagonalization process wouldn’t have produced anything more than a meaningless string of digits. – Brian M. Scott Nov 4 '12 at 0:49
ahhh I think I understand now! So basically the axiom of c. guarantees that the limit(when n approaches infinity) of the series we create(for the number that's not on the list) exists, i.e it guarantees the series converges and is thus a real number. Thanks Brian.. you said there were a lot more straightforward examples I could use instead of cantors diagonilization method? Do you think you could give me another example? Id greatly appreciate it.. Im just thinking it might take a bit of time for me to explain this particular example on a test. – MathMajor Nov 4 '12 at 0:58
@MathMajor: Yes, exactly: it guarantees the existence of the limit. For the other, how about the assertion that every non-negative real number has a non-negative square root? You know that it’s not true without completeness, since $2$ has no square root in the rationals; what makes it work in the reals? HINT: Given $x\ge 0$, consider the set $\{y\in\Bbb R:y\ge 0\text{ and }y^2\le x\}$. – Brian M. Scott Nov 4 '12 at 1:06