# What does it mean for a set to be countably infinite?

Why distinguish between countable and uncountable? What advantages does this property have? I haven't studied much set theory but I am writing about the set of algebraic vs transcendental numbers and found one is countable whereas the other is not. So this led me to ask these questions. Thanks for any guidance.

• If you can achieve a bijection of the members of the sets to $\Bbb N$, the the set will be called countable, and moreover ,if it is infinite, then it is countably infinite. So, the set $\Bbb Q$ is countable in spite of being infinite. – user249332 Nov 24 '15 at 20:31

As mentioned above, countably infinite formally means a bijection (one to one and onto mapping) to the naturals exists, but I wanted to offer a personal response to "Why distinguish between countably infinite and uncountably infinite?"

Well, we don't always distinguish between the two. For example if you were answering a question in elementary linear algebra regarding the number of solutions to a homogeneous equation, Ax = 0, where the system had a free variable it is unlikely a professor would insist you specify if it had countably or uncountably many solutions. Infinite solutions would suffice. However in other contexts it is relevant to make clear. The difference between a discrete random variable and a continuous random variable in probability is one example of such a circumstance.

In general, part of what we do in pure mathematics is search for truth and Cantor was able to prove that different infinite cardinalities (size of sets) existed, which was actually rather controversial at first. So regardless of why we make clear a distinction, the bottom line is there is a distinction, it is proven! When we choose to be pedantic about specifying the distinction is just a matter of context.

A fun question (that may be too elementary for you) that I like to ask my algebra students is:

Which contains more numbers, $$\text{all of the natural numbers, }\mathbb{N} = \{1, 2, 3, ...\}, \text{ or the interval } [.1, .2] \text{ on } \mathbb{R}?$$

Lastly, if the answers here are interesting to you I recommend Cantors Theorem, Cantors Diagonal Argument, and The Continuum Hypothesis as further topics of reading.

One especially useful application is to give very easy proofs of existence of objects that can otherwise be much harder to construct. To take your example, here is the shortest and easiest proof that transcendental numbers exist: the reals are uncountably many, but the algebraic numbers are countable, so there must be reals that are not algebraic. Before Cantor introduced the idea of countable and uncountable infinities, the existence of transcendental numbers was much harder to prove.

Another example of a similar non-constructive proof is the proof that there are uncomputable functions from $\mathbb{N}$ to $\{0,1\}$ (for instance): there are uncountably many such functions, and only countably many computer programs (because each program is just a finite string of symbols), so there must be some function which is not computed by any program. This is not terribly formal as I wrote it: you actually need to specify a precise model of computation and use that to define "program". But the point is, whatever reasonable model of computation you specify, the proof sketch above can be easily adapted to it.

I think one surprising consequence is that we tend to think of transcendental numbers like $\pi$ and $e$ as being incredibly rare. (After all, how many can you name?) However, all but countably-many real numbers are transcendental. It is the algebraic numbers that are rare. In fact, the algebraic numbers account for precisely $0\%$ of the real numbers.

You can get a little stranger with this idea. Fix a finite alphabet and call a number describable if you can describe it with finitely-many characters. My favorite alphabet is the one consisting of every English word, mathematical symbol, and computer language. The set of numbers describable by this alphabet is only countable, so I am capable of describing precisely $0\%$ of the real numbers that exist.

• I have some slides on countability and uncountability. Maybe they will be useful. – Austin Mohr Nov 24 '15 at 20:50
• Something I used to wonder about when I was young (early 1970s) is whether there are countably many different infinities or uncountably many different infinities. Pretty much all of the popular expositions did what you did on p. 75 of your slides, which was to say that the number of infinities is infinite, but do so in such a way that the reader might suspect there are only countably many. (Yes, I now know there are uncountably many different infinities.) – Dave L. Renfro Nov 24 '15 at 21:18
• @DaveL.Renfro Indeed, there are proper-class many different infinities! Is that the proper term? Proper-class many? – Akiva Weinberger Nov 24 '15 at 21:45
• yes you can say that and anyone who understands it won't object. It's more common to say they are a proper class. – DanielWainfleet Nov 24 '15 at 22:04

The motivation for destinguishing between countable and uncountable sets, I think, is telling whether infinite sets are 'of the same size'. A countable set has an injection with the natural number and is therefore in a sense 'of the same size' as the natural numbers. The uncountable sets are the sets not having this property and are therefore 'bigger'. Some books however use bijection instead of injection.

• I think this answer goes partway toward identifying a motivation, but it leaves open the question, "Why do we care if infinite sets are the same size?" Of what use is that distinction? Ultimately, there isn't one simple answer to that question, I think, so much as there are a variety of reasons. Prince M's example of probability distributions is one. We have to confront infinity in different ways in different situations, and in a sense, we classify infinities by how we deal with them. – Brian Tung Nov 24 '15 at 21:48

Infinite has caused lots of troubles in the history of mathematics. This concept often leds to paradoxes, like Hilbert's paradox of the Grand Hotel. This is even used to define infitine sets as those that can be put into a one-to-one correspondence with a strict subset (Dedekind infinite).

$\mathbb{N}$ is the first most natural infinite set. It defines what countable can be: not quite finite, but letting you feel you could exhaust it given an infinite duration, you can iterate. A lot of sets are countable, i.e. in bijection with $\mathbb{N}$: $\mathbb{Z}$, $\mathbb{Q}$, the set $\mathbb{A}$ (or $\overline{\mathbb{Q}}$) of algebraic numbers. Those sets can index other objects, like series.

Some sets cannot be put in correspondence with $\mathbb{N}$, as shown by Cantor's diagonal argument; $\mathbb{R}$ is an example, transcendentals $\mathbb{T}$ too.

Loosely speaking, some branches of mathematics (intuitionism or constructivism) have chosen logical tools that remain somehow closer to intuition or construction. While they easily use countable forms of axioms or properties, they refrain using uncountable ones. One typical debate is around the axioms of choice, or one of its weaker form, the axiom of countable choice. Indeed, using the classical axiom of choice can lead to some counter-intuitive geometry, like the Banach-Tarski paradox, that can turn one ball in two balls of the same size. One can also construct weird looking Hamel bases, considering $\mathbb{R}$ as a vector space over $\mathbb{Q}$ .

So with different infinites (countable or not), come different powers and paradoxes, some of them more or less acceptable, see also The axiom of choice: Intiution and Paradox or The axiom of choice is wrong.

• Once we have shown that the set of algebraic numbers is countable and the reals are not, the existence of transcendentals is proven without having to give a single explicit example. – DanielWainfleet Nov 24 '15 at 22:09
• Not the most constructive way, isn't? – Laurent Duval Nov 24 '15 at 22:31
• Proving that a particular number is not algebraic can be very hard.Liouville showed that a certain set of numbers is transcendental, and Cantor came along and showed that almost all of them are. Euclid's proof that there's no largest prime isn't so constructive.You can use Ghandi's recursive construction, which only takes about $2^{25}$ operations to find the least prime greater than 100. (Not efficient!) – DanielWainfleet Nov 24 '15 at 22:47
• True. I am not taking sides here – Laurent Duval Nov 24 '15 at 22:49
• @user254665: Actually, that proof can be easily turned into a constructive example. Just enumerate all algebraic numbers represented by the roots of polynomials over the rationals (obviously possible, say by length-lexicographical ordering of the exact representation) and for each algebraic number compute it to sufficient precision and make sure the next digit of the number you're constructing differs by at least $2$ at that position. This gives an explicit program that computes the digits of some transcendental number. But if you want an uncomputable transcendental number, then too bad! – user21820 Nov 25 '15 at 6:06

From a compuatability point of view, a set being countably infinite means that searching for an element in that set is now semi-decidable. That is, if the element is in that set, you can search in a way that you will eventually find it. (You may search forever if that element is not in that set).

Basically, because a countably infinite set has a bijection with the natural numbers, you can apply that bijection and iterate through its elements in the ordering induced by that bijection.

A similar thing cannot be done, however, for uncountably-infinte sets.

In computability theory, problems are usually modeled as languages, which are effectively subsets of $\mathbb{N}$. But it is very hard, in general, to algorithmically search for a language, or to answer the question "does there exist a language with property X", because there are uncountably many languages.

Incedentally, this is also why there are uncomputable functions. There are countably-many general-recursive functions, but uncountably many functions.

Formally, a set $S$ is countably infinite if there is a bijection between $S$ and the natural numbers $\mathbb N$. What this means is that one can assign each element of $S$ to an element of $\mathbb N$, allowing one (in theory) to list all of the numbers. Uncountable sets (for example, $\mathbb R$) cannot be listed. If a subset of $\mathbb R$ is countable, it can be interpreted as that nearly all real numbers do not belong to the set.