An alternative way of looking at countable/uncountable infinities

Question

Consider the decimal expansion of a rational number. This will either terminate, or repeat forever a finite number of its final digits. Thus, any rational number can be expressed with a finite amount of information.

The decimal expansion of an irrational number on the other hand neither terminates nor repeats, and so cannot be expressed in a finite amount of information.

Is this related to the distinction between countable and uncountable infinities? My reasoning is that if it a single irrational number takes a countably infinite amount of information to write in decimal form, then the set of all irrational numbers must be 'doubly' infinite, that is uncountable. On the other hand, a single rational number takes a finite amount of information to write (as does a natural number), so the set of rationals is countably infinite.

A problem I can see is that it can be argued that some irrational numbers can in fact be expressed in a finite amount of information (e.g. $\sqrt{2}$). But I can't help but feel there is some link here. (Forgive me if this is all a bit imprecise, I'm not a mathematician.)

Answer 1

What you are suggesting is very similar to some existing ideas, including computable numbers and constructable numbers, or more generally definable numbers. In fact, "expressed in some finite amount of information" is not a terrible way to informally describe a definable number. The hard part is working out what kind of language you can use to define your numbers. There's a classic paradox about the set of positive integers that can be expressed in less than, say, twenty words, but then "the smallest positive integer that cannot be expressed in less than twenty words" clearly belongs to that set.

If we're more rigorous, and constrain ourselves to using formal languages to identify our sets of definable numbers, then we do discover the result you're discussing, but we usually approach it from the opposite direction. Which is to say - we start from the knowledge that the set of all real numbers is uncountable (thanks to, for example, Cantor's diagonalisation argument), and since we can show that any set of definable numbers is at most countably infinite, we know that the set of undefinable numbers must still be uncountably infinite because if you remove any countably infinite set from an uncountably infinite one you don't reduce its size.

This also means that it doesn't matter how hard you try to expand your language - if we find a way to construct numbers outside of any given set of definable numbers, and append that construction onto the language, we still only capture a countably infinite set and so there will be more numbers out there that can't be captured.

Answer 2

There are lots of subtleties involved in what constitutes definable (by finite amount of information). For example, one might be tempted to say the following: an element $a$ of some structure $\mathcal{M}$ is definable iff there exists a (first-order, parameter-free) formula $\varphi(x)$ s.t. $\mathcal{M} \models \varphi(x)$ iff $x = a$. But under this definition it actually could be the case that all real numbers (in fact, every mathematical object whatsoever) are definable. See, for example, https://arxiv.org/abs/1105.4597 . This does not contradict the countability arguments because the proof that the set of real numbers is uncountable is carried out within the model of ZFC, while the argument that the set of definable real numbers is countable is carried out within the metatheory. So, while the set of real numbers within the said model $\mathcal{M}$ (of ZFC) can be put in bijection with the set of natural numbers, this bijection is simply not contained in $\mathcal{M}$ itself, so it does not contradict the theorem that the set of real numbers are uncountable, proved in $\mathcal{M}$.

The idea behind this is actually not that complicated. Assuming $\mathrm{V} = \mathrm{HOD}$, there exists a definable well-ordering of the universe. So this allows us to pick, in a definable way (by choosing the least element in a fixed definable well-ordering of the universe), an element $x$ that satisfies $\exists x \varphi(x)$ for any such formula that is true in $\mathrm{V}$. Running through the proof of downward Lowenheim-Skolem using this fact then gives the required model. (The precise details are in the paper I cited above.) Assuming the existence of a definable well-ordering of the universe and that every natural number in the universe is definable (which is probably not trivial - the universe could contain plenty of non-standard natural numbers) also completes the argument of @Vincent in the comments. If one can prove that a (definable - otherwise the remainder doesn’t make much sense) set $A$ is countable in $\mathcal{M}$, i.e., there is a bijection between $\mathbb{N}$ and $A$ within $\mathcal{M}$, then we can define any element of $A$ by choosing the least bijection $A \to \mathbb{N}$ according to the well-ordering of the universe, and then use the induced definable numbering of $A$ and the fact that all elements of $\mathbb{N}$ are assumed definable to define elements of $A$, showing that any set that’s countable in-universe must have all its elements definable, in this scenario.

But then again, as the example with all objects being definable show, you cannot actually go back - all elements of a set are definable only imply it is countable looking from outside, not necessarily in-universe. To summarize, you have the following:

1. If you can prove (necessarily outside the universe) that all elements of a set $A$ are definable, then $A$ must be countable looking from outside the universe. But it could be uncountable in-universe;
2. Under some assumptions (the existence of a definable well-ordering of the universe and all natural numbers are definable), you can prove (again necessarily outside the universe), if (a definable) $A$ is countable within universe, then all elements of $A$ are definable. However, you can’t prove this if you only know $A$ is countable from outside the universe. (This follows from downward Lowenheim-Skolem and the assumption that there exists a universe in which some elements are not definable.)