4
$\begingroup$

There are several approaches in defining the real numbers axiomatically and suppose that we have some set of axioms $A$ which completely characterize rational numbers and which does not mention anything about some representation of rational numbers in any way (representation is here something like decimal representation or representation by continued fractions). Now let us add completeness axiom ($ca$) which states that "every nonempty set $S$ of real numbers which is bounded above has a least upper bound". If we join $ca$ to the set of axioms $A$ then $A$ along with the $ca$ should completely characterize the real numbers.

My question is:

Can we prove that $\mathbb R$ is uncountable by only using axioms from the set $A$ together with the axiom $ca$?

$\endgroup$
  • 2
    $\begingroup$ There are several answers at different levels of sophistication. To see what sort of answer you want: can you give an example of a set of axioms that, to your taste, "completely characterizes" the rational numbers? $\endgroup$ – Carl Mummert Dec 5 '15 at 19:51
  • 8
    $\begingroup$ Your question currently doesn't seem to make sense. The only way I can understand the sentence '... A which completely characterize rational numbers ....' is that the only the rational numbers satisfy A. This means adding $ca$ would mean the axioms are inconsistant (i.e. there is no model) $\endgroup$ – Nex Dec 5 '15 at 19:51
  • $\begingroup$ @CarlMummert Well, maybe I did write the question before I had the time to think on how to put my thoughts into words, all I wanted to know is if there is a way that only from the axioms for the real numbers we prove uncountability of the real numbers. And, when you raised another question, is there any set of axioms that "completely characterizes" the rational numbers? Because all the usual axioms for the rational numbers are also valid for the real numbers. $\endgroup$ – Farewell Dec 5 '15 at 19:58
  • 1
    $\begingroup$ @Ante Paladin: I am just trying to figure out the right level of technicality for an answer. Have you ever had a course in first-order logic? Do you know the Lowenheim-Skolem theorem? Unfortunately, although the question you asked is very natural, the answers can be very complicated. $\endgroup$ – Carl Mummert Dec 5 '15 at 20:00
  • 3
    $\begingroup$ Historically Cantor's first proof did not use decimals or the diagonal method. $\endgroup$ – DanielWainfleet Dec 5 '15 at 23:04
8
$\begingroup$

Since the phrasing of the question itself is a bit muddled, let me instead address the version of the question you stated in a comment:

all I wanted to know is if there is a way that only from the axioms for the real numbers we prove uncountability of the real numbers.

The answer is absolutely yes (assuming that by "axioms" you mean an axiomatic description of a structure in an ambient set theory, rather than some kind of self-contained first-order axiomatization). In particular, the real numbers can be completely axiomatized as a complete ordered field: that is, a field $\mathbb{R}$ together with a total ordering compatible with the field structure, such that any nonempty set $S\subset\mathbb{R}$ with an upper bound has a least upper bound.

Let me sketch a proof from these axioms that $\mathbb{R}$ is uncountable. Suppose $\mathbb{R}$ were countable, and $i:\mathbb{R}\to\mathbb{N}$ were an injection. We have elements $0,1\in\mathbb{R}$ with $0<1$. Moreover, the ordered field axioms imply that if $x,y\in\mathbb{R}$ satisfy $x<y$, then there exists an element $z\in\mathbb{R}$ such that $x<z<y$ (namely, $z=(x+y)/2)$. Now define an increasing sequence $(x_n)$ and a decreasing sequence $(y_n)$ such that $x_n<y_n$ for all $n$ by induction. Start with $x_0=0$ and $y_0=1$. Given $x_n$ and $y_n$ with $x_n<y_n$, consider the set of all $z\in\mathbb{R}$ such that $x_n<z<y_n$. This set is nonempty, and so it has a unique element $z$ which minimizes the value $i(z)$. Let $x_{n+1}$ be that value $z$. Similarly, there is a unique $w$ such that $x_{n+1}<w<y_n$ which minimizes the value $i(w)$ among all such $w$. Let $y_{n+1}=w$.

Having constructed these sequences, let $S=\{x_n\}_{n\in\mathbb{N}}$. This is a nonempty subset of $\mathbb{R}$, and it is bounded above (namely, by $y_n$ for any $n$). So there is some $r\in \mathbb{R}$ that is the least upper bound of the set $S$. Note that the numbers $y_n$ are all distinct, so the numbers $i(y_n)$ form an infinite subset of the natural numbers. In particular, there must be some $n$ such that $i(y_{n+1})>i(r)$. But I claim this is impossible. Indeed, $y_{n+1}$ was defined to be the element $w\in\mathbb{R}$ such that $x_{n+1}<w<y_n$ which minimized $i(w)$. But $r$ also satisfies $x_{n+1}<r<y_n$ ($r\geq x_{n+2}>x_{n+1}$ since $r$ is an upper bound of $S$, and $r\leq y_{n+1}<y_n$ since $r$ is the least upper bound of $S$ and $y_{n+1}$ is also an upper bound of $S$). Since $i(r)<i(y_{n+1})$, this contradicts our definition of $y_{n+1}$. This contradiction means that our injection $i$ cannot exist, i.e. $\mathbb{R}$ is uncountable.

For an alternate proof, you can define decimal expansions of real numbers from these axioms (though it takes a bit of work), and then do the usual diagonal argument.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ This is similar to but not the same as Cantor's first proof. Nice work. $\endgroup$ – DanielWainfleet Dec 5 '15 at 23:07
  • 1
    $\begingroup$ Oh, really? I was trying to reproduce his first proof but didn't remember exactly how it went, and this is what I came up with. :) $\endgroup$ – Eric Wofsey Dec 5 '15 at 23:08
  • $\begingroup$ (Approximately Cantor ) Given $f:N\to [0,1]$ with $f(0)=0$ and $f(1)=1$. Let $g(0)=0$ and $g(1)=1$. For $n\geq 1$ let $g(n+1)$ be the least $m>g(n)$ such that $f(m)$ lies between $f(g(n-1))$ and $f(g(n))$.Then $0=f(g(0))<f(g(2))<f(g(4))<....<f(g(5))<f(g(3))<f(g(1))=1$. Any $x\in [\sup_nf(g(2n)),\inf_nf(g(2n+1))]$ is not in $Im(f)$ so $f$ is not onto. $\endgroup$ – DanielWainfleet Dec 6 '15 at 3:10
  • $\begingroup$ Eric, you are mentioning in the proof that "there exists an element $z \in \mathbb R$ such that $x<z<y$ (namely, $z= \frac {(x+y)}{2}$". But in this way you are assuming that there exists number $\frac {1}{2}$ and the existence of such a number is not stated in the axioms, am I right? $\endgroup$ – Farewell Dec 6 '15 at 17:16
  • $\begingroup$ Right, it doesn't follow immediately from the axioms (I said I was only sketching the proof). To get $1/2$, you have to prove that $1+1\neq 0$ (this follows from the compatibility of the order with addition and the fact that $0<1$, so $0+0<1+1$), and then use the fact that you have a field to take the multiplicative inverse of $1+1$. Proving that $x<(x+y)/2<y$ then requires further use of the compatibility between the field structure and the order. $\endgroup$ – Eric Wofsey Dec 6 '15 at 17:58
3
$\begingroup$

This answer will be written assuming that you are coming from an amateur or undergraduate understanding of axioms, as is used in much of mathematics outside the study of mathematical logic. I will try not to say anything false, but I can't tell "the whole story" at this level. Please let me know in comments about areas of the answer that remain confusing.

I will call this common, informal reasoning "ordinary mathematics". It includes many informal principles for reasoning about mathematical objects and sets of mathematical objects. (In fact, many published mathematics papers outside mathematical logic work entirely in this informal system, so it is not just for amateurs and undergraduates.)

Characterizing the reals

In ordinary mathematics, there is a set of axioms that characterizes the rationals: they are the so-called field of fractions of the natural numbers. Of course, this doesn't "completely" characterize the rationals, because we still have to characterize the natural numbers. But I think this is good enough for the question at hand.

Now, given the rational numbers, there are ways to construct the real line axiomatically. One way is via Dedekind cuts, and in this context we can easily verify that the collection of Dedekind cuts of rationals satisfies the axiom of completeness and has the other properties we expect for the real line.

If we continue working in the same framework of ordinary mathematics, no additional axioms are needed to show that the reals are uncountable. We can prove many things about the reals using ordinary mathematical methods and the fact that the reals satisfy the axiom of completeness. For example, we can prove that there is no real number that is greater than every natural number (see below). We abbreviate that last fact by saying that the reals are an Archimedean field.

Many real analysis textbooks use only ordinary mathematical reasoning, along with the fact that the real numbers are a complete Archimedean ordered field, to prove all their results. One of these results is that the real numbers are uncountable. This can be proved in many ways, and I recommend picking up a good introductory textbook on real analysis to learn the details. I have used Understanding Analysis by Stephen Abbott, which I think is understandable and has a nice introduction to many properties of the reals.

Formalization

In mathematical logic, one thing that we do it to try to formalize the principles of "ordinary mathematics", to see what formal axioms are actually needed. The seeds of this project were planted as early as Euclid, but it fully blossomed from the late 1800s through the early 1900s. Indeed, most of the major issues were understood by 1940.

What we learned is that no "formal system of axioms", in the sense that you would naively expect, can fully characterize the natural numbers, the rationals, the reals, or any other particular infinite structure. It turns out, because of the "finite" nature of a formal proof, that formal proofs are simply incapable of fully capturing the nuances of infinite structures.

We can certainly write formal axioms that are true about the natural numbers, but these axioms will also be true of other stuctures, which we call "nonstandard" because they aren't the structure we really wanted to study. So the axioms won't characterize the naturals. For purpose of ordinary mathematics, though, we can ignore the nonstandard models, and know that whatever we prove in our formal systems really is true about the "standard" models we care about.

Now, you may ask, how can we characterize the rationals in ordinary mathematics, but not in any formal system? The answer is essentially that, in ordinary mathematics, we begin with the set of natural numbers as a given object. Similarly, we take other strucutres for granted, such as the powerset of the naturals. Relative to these starting objects, we can characterize the rationals, the reals, etc. In formal reasoning, we do not have these given structures to use as a reference, and there is no way to fully capture them with formal axioms.

P.S.

Here is the promised argument that the set of natural numbers is unbounded in the reals, using only the axiom of completeness and ordinary mathematical reasoning. If the naturals were a bounded set in the reals, they would have a least upper bound, which we can call $s$. Then there must be some natural number in the interval $(s-1, s)$, or else $s-1$ would be a smaller upper bound than $s$, which is impossible because $s$ is the smallest upper bound. But, if there is a natural number $n$ in the interval $(s-1,s)$, then $n+1$ is a natural number greater than $s$, which is impossible if $s$ is an upper bound for the naturals. Overall, we see that the natural numbers cannot be a bounded set.

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ In your third and fourth paragraphs, you're using the word "axiomatic" in a weird way that is inconsistent with ordinary (informal) mathematical usage. The way the term is usually used, "the field of fractions of the integers" (described explicitly as certain equivalence classes of ordered pairs) is emphatically not an axiomatization of the rationals but rather a particular construction satisfying an axiomatization. Similarly, Dedekind cuts in the rationals are not an axiomatic construction of the reals, at least the way mathematicians normally use the term. $\endgroup$ – Eric Wofsey Dec 5 '15 at 21:25
  • $\begingroup$ The only definition you stated which is actually "axiomatic" in the ordinary sense is "the real numbers are a complete Archimedean ordered field". $\endgroup$ – Eric Wofsey Dec 5 '15 at 21:25
  • $\begingroup$ @Eric Wofsey: indeed, being a "complete Archimedean ordered field" is a common axiomatization of the reals, but it is not as easy for me to state a common axiomatization of the rationals in the sense you mean. Of course, the notion of "field of fractions" can be defined by a universal property, apart from any specific construction of the field of fractions. Or, we could define the rationals as the smallest field of characteristic zero, but that is more complicated, and I would prefer to link back to the naturals for expository purposes. $\endgroup$ – Carl Mummert Dec 5 '15 at 22:43
  • $\begingroup$ I guess, if "the unique complete ordered field, up to isomorphism" is a characterization of the reals, then "the unique smallest field, up to isomorphism, which has the naturals as a subsemiring" should be the same kind of characterization of the rationals. $\endgroup$ – Carl Mummert Dec 5 '15 at 22:46

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.