Sorry if my question is not constructive. This theme is very interesting for me and I really want to understand it. All written below don't claim as serious argument for any fact. It just shows my understanding of the theme (as you can see I don't understand it well).

Let's look at $\mathbb{Z}$ and $\mathbb{Q}$. They are both infinite and countable but we can differ them using this fact: $\mathbb{Q}$ is dense (unlike $\mathbb{Z}$). I'm trying to understand the difference between countable and uncountable sets in the same way, by finding any property which is true for one and false for other.
Let's look at $\mathbb{Q}$ and $\mathbb{R}$. What property can I get? Dense? There are both dense. Containing irrational numbers? Well, but the set of algebraic numbers also contains some of them, even all roots, but it's countable.
Yes, Cantor's diagonal argument gives us a simple example of uncountable set. But there I have same question: what are the properties which are true for the set of infinite sequences of 0 and 1 and false, for example, for $\mathbb{N}$? Or, if we interpret the infinite sequence of 0 and 1 as a binary fraction, we can compare real numbers from [0; 1] with algebraic ones.

I can't understand how it can two different infinities exist.

What finally confused me is Zermelo's Well-ordering theorem which says that we can rearrange elements in any (even in more than uncountable) set such that it will become well-ordered. Because of this every element will have next to it. It means that even $\mathbb{R}$ will not be dense but will stay still uncountable. How is it possible? (I know that there are used Ordinal numbers)

  • 7
    $\begingroup$ From a set theoretic point of view that's all you can say: one is countable and the other is not. When you say the rational are dense you're considering they live inside the real numbers, under a specific topology, so it is not really relevant to your argument. $\endgroup$ – Pedro Tamaroff Sep 5 '16 at 23:53
  • 1
    $\begingroup$ @PedroTamaroff, I know that it is not really relevant but I'm trying to understand the theme using any example. Does it exist another example which is more suitable for this? $\endgroup$ – Pavel Sep 5 '16 at 23:58
  • 3
    $\begingroup$ The problem is that not only is denseness not relevant, but it obscures the main point. The question is merely whether there exists two infinite sets $X,Y$ having the property that there is no bijection $f : X \to Y$. There does exist a bijection between $\mathbb{Z}$ and $\mathbb{Q}$, so that does not address the question. What the diagonal argument shows is that there is no bijection between $\mathbb{Z}$ and $\mathbb{R}$, end of story. $\endgroup$ – Lee Mosher Sep 6 '16 at 0:01
  • 1
    $\begingroup$ You need to study topology and then perhaps descriptive set theory, your question's answer is quite long, almost uncountable. (Not really almost uncountable, definitely countable.) $\endgroup$ – JKEG Sep 6 '16 at 0:09
  • 1
    $\begingroup$ One property that holds is true for $\mathbb{Q}$ but not for $\mathbb{R}$ is that $\mathbb{Q}$ is not a connected topological space while $\mathbb{R}$ is. $\endgroup$ – user 170039 Sep 6 '16 at 3:23

Let me address your question about $\mathbb{Q}$ versus $\mathbb{R}$. There is indeed a feature which guarantees uncountability! Specifically, completeness. It's a good exercise to show that any countable metric space containing $\mathbb{Q}$ is not complete.

In fact, I think this will make the uncountability of the reals a lot clearer for you. Remember that one consequence of $\mathbb{R}$ being a complete metric space is that whenever I have a decreasing sequence of nonempty closed and bounded sets $C_1\supseteq C_2\supseteq C_3\supseteq . . .$, their intersection $\bigcap C_i$ is nonempty! This can be used to give a proof of the uncountability of $\mathbb{R}$ which looks very different from the diagonal argument (although I'd argue that they are of the same substance ultimately), and in fact preceded it. Basically, given a sequence $r_i$ of reals, build a decreasing sequence $C_i$ of nonempty closed intervals such that $r_i\not \in C_i$; then let $s$ be any real in $\bigcap C_i$. We can't have $s=r_i$ for any $i$!

Why does this proof fail for $\mathbb{Q}$? Well, since $\mathbb{Q}$ isn't complete, the intersection of a decreasing sequence of nonempty closed and bounded sets can be empty. So we can build the $C_i$s, but we're not guaranteed an $s$ at the end. I think this will make the distinction between $\mathbb{Q}$ and $\mathbb{R}$ much clearer.

Note that completeness is about sets, or rather sequences - a space is complete if every Cauchy sequence converges. Meanwhile, density is about elements - "$\forall x_0<x_1\exists y(x_0<y<x_1)$" only involves talking about individual elements. In a precise sense (see the Lowenheim-Skolem theorem), conditions that only talk about elements can't distinguish the countable from the uncountable. So this is a very good template for what distinguishes naturally-occuring uncountable structures from their countable relatives.

A couple final comments:

  • A caveat: the slogan "completeness guarantees uncountability," while often helpful, is technically wrong. E.g. $\mathbb{N}$ with the usual metric is complete (exercise) but countable. It is true that any complete compact and infinite metric space, or complete metric space with no isolated points, is uncountable; but this isn't as snappy.

  • Conversely, uncountability does not guarantee completeness! We can "rearrange" the reals (that is, look at a different metric on $\mathbb{R}$) to get something which is not complete. One way to do this is to make $\mathbb{R}$ "look like" uncountably many copies of the (countable, incomplete) metric space $(0, 1)\cap\mathbb{Q}$ of rationals between $0$ and $1$ (where points in two different copies are distance $2$ away from each other; it's a good exercise to check that this is indeed a metric space). Bottom line: Uncountability is fundamentally not a geometric property, although it can interact with geometric concepts like completeness etc. Ultimately it has to be understood in its own (set-theoretic) terms.

  • You mention at the end of your question that you find being able to well-order $\mathbb{R}$ very confusing. This is normal (or at least, I share(d) it). First of all, it's worth pointing out that results in descriptive set theory show that any well-ordering of $\mathbb{R}$ would have to be extremely complicated, so you're not missing something obvious. Secondly, I suspect that your problem is with uncountable ordinals in general, as much as with $\mathbb{R}$. To that end I think this is a good exercise: let $S$ be a set of countable well-orderings such that each countable well-ordering is order-isomorphic to exactly one element of $S$. (A snappier way to say this: "let $S$ be the set of countable ordinals.") Show that $S$ is itself well-ordered under the relation "is longer than," and that $S$ is uncountable. Congratulations - you've just constructed an uncountable ordinal, namely $\omega_1$!

  • $\begingroup$ +1. Re: "since $\mathbb{Q}$ isn't complete, the intersection of a decreasing sequence of nonempty closed and bounded sets can be empty": For a concrete example: such a sequence is $[3,4], [3.1,3.2], [3.14,3.15], [3.141,3.142], [3.1415,3.1416], [3.14159,3.14160], \dots$; in the reals, the intersection is $\{ \pi \}$, but in the rationals, the intersection is the empty set. $\endgroup$ – ruakh Sep 6 '16 at 5:11

Here is one example of using countability in practice. The number of languages over an alphabet $\Sigma$ is uncountable. While the number of languages represented by regular expressions over $\Sigma$ is countable. That proves that there are languages (in fact uncountably many) which can not be represented by regular expressions.

  • 2
    $\begingroup$ This example would have a bit more "punch" if you changed from "regular languages" to "recursive languages" or even "recursively enumerable languages". So to put it another way (in a special case), there exist real numbers such that no computer program can list its decimal digits. $\endgroup$ – Daniel Schepler Sep 6 '16 at 5:14

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.