What is the point of countable vs. uncountable sets?

Question

I understand how to use these concepts and how to prove certain sets are countable or uncountable. However I don't get the point of it. What difference does it make whether a set is countable? People say that Cantor's proof that the real numbers are uncountable is a milestone of mathematics. Having read through the proof, I'm still struggling to understand what these ideas are important.

Answer 1

One important application is this: Consider the set of functions that take an integer argument and return an integer result. It's not hard to show that this set is uncountable. Now consider the set of computer programs. This set is countable. Therefore there are uncomputable functions—in fact most functions cannot be computed.

This is a pretty common type of argument in some contexts.

Answer 2

One very important (in my opinion) application of countability:

Often associated with a physical system is some function $f:\mathbb R^n\to \mathbb R^m$. It could be the acceleration experienced by a planet, the voltage in a circuit, whatever. We want to study the behavior of these functions, and we find that at some points the behavior is good, but at others the behavior is very bad. In particular, we have a nice mathematical model for the good points, which allows us to perform computations easily, but this model breaks down at the bad ones. To apply this model, we need a "generic" point to be a good point, in the sense that if you choose a random point it will be good with probability $1$. One common way to show this is to show that there are only countably many bad points. Formally, this uses the fact that the Lebesgue measure of any countable set is $0$.

Edit: A concrete example of this arises in my own area of interest, billiards. Consider a billiard ball bouncing around inside a polygon. The ball behaves in a very predictable manner when it strikes an edge (the angle of incidence is equal to the angle of reflection) but it's behavior is ill-defined when it strikes a corner. Luckily, starting from any fixed point there are only countably many different directions the ball could travel in which eventually strike a corner, so for the most part this possibility can be ignored.

Answer 3

One application is probability and measure theory.

If you have met infinite sums, then you may know that we often want probability to be countably additive. What does that mean? If $\{A_n\mid n\in\Bbb N\}$ is a countable collection of pairwise independent events, then $P(\bigcup A_n)=\sum P(A_n)$. That is to say, the probability that one of these will happen is the sum of probabilities.

The reason this is useful is that despite the fact that in "real world situations" there are only finitely many events we can talk and measure, sometimes we don't know how many exactly, and working with infinitely many makes it easier. Therefore countable additivity is a useful and important property.

But here's a catch. If $X$ is countable then there is no countable additive probability such that $P(X)=1$ and $P(\{x\})=0$ for every $x\in X$. This is because if $X$ is countable we can write it as $X=\{x_n\mid n\in\Bbb N\}$ and then we have $$1=P(X)=P\left(\bigcup_{n\in\Bbb N}\{x_n\}\right)=\sum_{n\in\Bbb N} P(\{x_n\})=\sum_{n\in\Bbb N} 0=0.$$

What all this have to do with your question? Well, easy. We often talk about a "uniform" probability over $[0,1]$ where every singleton has probability zero. If $[0,1]$ is countable, we can't do that.

Answer 4

One interesting fact that results in topology is that removing a countable set of points from the plane cannot disconnect the plane. This is because you have an uncountable number of slopes to pick from and a countable number of 'obstacles'.

If the plane were disconnected, then we would have an injective map from the set of slopes, $\mathbb{R}$, to the set of natural numbers, $\mathbb{N}$; absurd.

Answer 5

One application of different cardinalities: a quick way to tell that two sets are distinct.

Another: to build the constructable universe.

Answer 6

I think what you're missing here is the sheer extraordinariness of the existence of uncountable sets. The very notion that we can speak about sets which are uncountable is as big a leap as the notion that we can speak about infinitely small countable numbers, which the ancients (say Zeno) couldn't bring themselves to believe existed.

Answer 7

Here's an interesting fact that is due to Cantor's idea of uncountability:

Since $\mathbb{R}$ is uncountable, we can interpret this to mean that you can't list all the real numbers even if you tried (or were compelled to by some sadistic mathematician). You're probably thinking that this is obvious since $\mathbb{R}$ is infinite; but what I mean to say is that one cannot even write $\mathbb{R}$ in a "list-form", i.e., $\mathbb{R}=\{r_1,r_2,...\},$ where the ellipses loosely means that we know what each next term will be. This is shown by using Cantor's diagonalization argument. But what's more, one cannot even produce a "list-form" for any finite interval of $\mathbb{R}$! Just try listing all of the reals from $0$ to $1;$ Cantor guarantees you will fail. This is due to the uncountable nature of the reals.

So Cantor's ideas of uncountability and countability give us a precise way to think about just how manageable, or ridiculously out-of-hand, the size of an infinite set could be. That is, some sets can be listed, some cannot.

Additionally, You can use Cantor's "diagonalization argument" which I referred to above, to show that $\mathbb{Q}$ is countable (or "list-able", in the sense I mentioned above). This is pretty amazing considering that this very same method was previously used to show that a set ($\mathbb{R}$) is uncountable! That is the power of Cantor's ideas.

So its pretty neat stuff, eh?

Answer 8

I'd say that the milestone isn't just the set of real numbers is uncountable. From Cantor's proof it follows that

• There are different magnitudes of infinity. This is somewhat counter-intuitive at first sight, because we don't experience infinity around us so we tend to divide "amounts" into just finite and infinite.
• There are actually infinite number of magnitudes of infinity! For any set, its power set is strictly larger than the original set. This can be proved by a variant of Cantor's diagonal argument.
• It follows that there is no set $S$ of all sets - if it were, its power set would have to be its subset $P(S)\subseteq S$, but we know that $P(S)$ has strictly more elements than $S$.

These different "infinities" are called cardinal numbers or just cardinals and they're extensively studied in set theory.

Among different "infinities", the smallest one, the cardinality of $\mathbb{N}$, is very important for many aspects. If a set $M$ is countable (that is has the same cardinality as $\mathbb{N}$), we can assign a number to each its element, which means that "we can reach each of its element by a finite number of steps" using this assignment. Such an assignment also gives us well-ordering on $M$ - we order $M$ according to the natural numbers assigned to its elements. This allows us for example to prove that all its elements satisfy some property using mathematical induction. If a set is uncountable, it gets much more complicated - we need the axiom of choice to be able to find a well-order on the set, and then we need use transfinite induction.

Answer 9

Rather than answer countable vs uncountable specifically, I'll ramble on why Cantor's work could be considered important.

AFAIK, this was the very first time anyone had made an observation of that sort. It's big news in any subject when solid evidence appears contradicting what you thought was obviously true about a subject.

It also came during a time when there was a "crisis" in mathematics, and there was a feeling of urgency to study the foundations of the subject so that we could better understand what we're doing. And it was astonishing to find not a small crack in the foundations, but a large, gaping cavern waiting to be explored.

Mind you, this might be somewhat misleading. Cantor developed new techniques for approaching mathematics. That's the part that's really important; it's just the countable/uncountable distinction is the sensational piece of news that draws the attention.

Philosophers have mused for a long time on the "nature" of adjectives and descriptive words. For example, what is "blue"? Is 450 nanometer light? Is it the quality of things we've decided to call blue? Is it the collection of all blue things?

Cantor took this last idea, and made it an utterly precise mathematical notion today called "unrestricted comprehension". If you have some predicate $\Phi$ -- e.g. $\Phi(x)$ might mean "$x$ is an odd prime number", or it might mean "$x$ is either 2 or 3" -- then there is the set of all things that have property $\Phi$. In set-builder notation, Cantor says

$$ \{ x \mid \Phi(x) \} $$

is a set. And we know to reason with sets, and so he did. And this solved yet another historically muddled problem: the topic of infinity and the infinite. By approaching things this way, Cantor gives a clear, precise, and effective way of working with certain sorts of infinite things.

The discovery that the real numbers are uncountable demonstrates Cantor had discovered some genuinely new mathematics.

Answer 10

This is a very unimportant example, but it is very typical. Another user recently asked for an example of a subset of $\Bbb R^2$ that is closed under vector addition, but not under scalar multiplication.

I said:

Let $\{v_1, v_2, \ldots\}$ be any countable subset of $\Bbb R^2$ whose elements are not all 0. Then $$\left\{\sum_{i=1}^\infty z_iv_i \middle\lvert z_i\in \Bbb Z\right\}$$ is closed under addition.

How do we know that this set is not closed under scalar multiplication? There may be some other answer, but by far the easiest way to see this is to observe that this set is countable, but any set (other than {0}) that is closed under scalar multiplication must be uncountable.

Answer 11

It helps you make money:

Make a bet with someone that you pick a random number uniformly from the interval [0, 1]. If the number is rational, you give him \$1000, if it's irrational, you get the money. Or, if you want to play repeatedly, you can accept \$1 if it's irrational.

The point is that there are many more irrational numbers than rational ones, so you win (almost surely).

Answer 12

Sample a real number from $\mathbb{R}[0,1]$ as an infinite series of fair coin tosses. Then, each sample is not only a refinement, also the start of a new sample. The result being a rational may seem much less likely in the ergodic, but, sampling a rational sees sampling infinitely many copies of the terminus. Sampling an irrational (in this manner) sees infinitely many different, thus that the irrational is represented less, of the balance that the rationals and irrationals are each dense in the reals. It takes infinitely many fair coin tosses to sample a real number, that samples infinitely many, the sample is always plural.

Consider the function $\frac{n}{d}$ for naturals n,d with $0 \le n \le d$. As $d \to \infty$, $lim_{n\to d} f = 1$. Here $f$ ranges between zero and one and always includes zero and one. Also, the differences $f(n+1)-f(n)$ are constant (uniform). Then it is a CDF, uniform, with domain $\mathbb{N}$.

As that's in the countable it's a way to build notions of uniform probability from the natural integers, satisying various intuitions, and reasonably for application. The point of the uncountable here is to see there are various ways to see what would be facts about these systems.

Matters of the infinite are relevant to mathematics, in the pure for what it is and the applied for what it is and does.

In terms of the applied and for practical purposes for real analysis: additivity of measure is countable. And, much work is done in formalizing analysis in the constructible and countable.

It's good to know because other people believe it, to understand. But, except for its own sake, there aren't results solely due the uncountable. Results not of the uncountable are available via asymptotics, methods of exhaustion, and concrete mathematics. Here for example, point discontinuities can be discarded in solutions due their vanishing without appeal to their zero measure. And, the computable can be described in the countable constructible, the concrete mathematics is quite heavy. For example, given a wager whether a random integer is even or odd, the asymptotic density of even integers in integers is $\frac{1}{2}$, as an example of that the cardinalities of those two set being the same does not reflect their densities being different.

So, there is much intuition about the real numbers, not all satisifed with the uncountable. However, it is quite standard and in the general curriculum not knowing the general features as instructed and thus shared would be ignorant, regardless their eventual disposition or lack thereof.

The ideas are important as an example of a way to consider the mathematically infinite. It is important that their relevance is qualified, in their consideration.