2
$\begingroup$

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.)

$\endgroup$
7
  • 3
    $\begingroup$ Not only $\sqrt{2}$, also the number $0.101001000100001...$ or $0.12345678910111213...$ have finite information. It is true, however, that all numbers defined with finite information are countable, in some sense, check en.wikipedia.org/wiki/Definable_real_number $\endgroup$
    – MathBug
    Jan 28 at 12:59
  • $\begingroup$ It is not exactly clear to me what your question is, but it does make me think of Cantor's Diagonalisation argument when used to prove that there are uncountably many real numbers/or sequences whose elements are the digits $0$ or $1.$ $\endgroup$ Jan 28 at 15:06
  • 1
    $\begingroup$ @MathBug makes sense. So my statement should be instead that, because not every real number can be expressed using finite information, the set of real numbers is not countable? $\endgroup$ Jan 28 at 16:52
  • $\begingroup$ I think you should look into computability theory. $\endgroup$ Jan 28 at 17:00
  • $\begingroup$ @user19642323 If we know that the set of real numbers is not countable, and that the set of numbers that can be defined with finite information is countable, then we can conclude from these two things that there are some real numbers that cannot be defined with finite information. Also proving these two things is doable. Going in the other direction, as you propose: first proving that there are some real numbers that can not be defined with finite information and from there concluding that the set of real numbers must be uncountable are both harder. (ctd in next comment) $\endgroup$
    – Vincent
    Jan 28 at 17:19

2 Answers 2

3
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Thank you, this is a good answer. $\endgroup$ Jan 29 at 14:40
  • $\begingroup$ ...Somewhat disliked using the word "size" for cardinality. $\endgroup$
    – Anixx
    Feb 7 at 19:33
3
$\begingroup$

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 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$ 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.)
$\endgroup$
1
  • $\begingroup$ Aaah this is great! $\endgroup$
    – Vincent
    Feb 7 at 11:08

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .