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.
2026-04-09 05:47:21.1775713641
On
On
On
On
On
On
What does it mean for a set to be countably infinite?
725 Views Asked by Bumbble Comm https://math.techqa.club/user/bumbble-comm/detail At
7
There are 7 best solutions below
0
On
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.
4
On
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.
1
On
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.
5
On
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.
0
On
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.
0
On
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.
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.