7
$\begingroup$

Having just finished "Meta Math!" (Chaitin), I came across an interesting observation on infinite sets that I hadn't seen before. If I'm correct (and please let me know if I'm not):

1] There are infinite sets that we are used to, like the whole numbers, integers, and rational numbers that, since they can be put in one-to-one correspondence with each other, have the same 'size' or cardinality, $\aleph_0$

2] The real numbers can not be put in correspondence with these sets. They are in fact a power set of the smaller sets, $| \mathbb{R} | = 2^{\aleph_0}$.

3] If the continuum hypothesis holds we get that $| \mathbb{R} |=\aleph_1$, ie. there is no intermediate infinity in between the cardinality of the set of the whole numbers versus that of the reals.

Now comes the part where I get a bit fuzzy. There are 'computable reals', numbers like $\pi$ that can be encoded in a finite length program. These computable reals must be of size $\aleph_0$ as well, since you can encode all of them with a Turing machince and match each code to an integer.

There are uncomputable reals, such as Chaitin's $\Omega$ which, although we can't write down all the digits, we can at least specify what the number means. Chaitin calls these numbers 'nameable', let's call them $\mathbb{A}$. He asserts that the probability that you'll pick one at random is zero. This implies (I think) that $|\mathbb{A}|=\aleph_0$, but it also implies that there is a mapping of the integers to the uncomputable, yet namable numbers!

What is the cardinality of numbers like $\Omega$?

  • 0
    @tomcuchta. This essentially boils down to the fact that truth is not definable (this is usually attributed to Tarski). For more information read http://en.wikipedia.org/wiki/Tarski%27s_undefinability_theorem or the link provided by Qiaochu in the comments below his answer.2011-07-25

2 Answers 2

11

I forgot what this term was called, but I remember now: the numbers you're looking for are called definable numbers. Instead of Turing machines, we use first-order formulas, of which there are countably many since the collection of all finite strings of symbols from a finite alphabet is countable (exercise).

  • 0
    @Qiaochu: Thanks for clarifying the intent of your answer, and also for linking to that well written MO answer!2011-07-17
9

Let me record an answer which is more naive than Qiaochu's and see how people like it.

To name a number one explicitly gives a finite string of characters (say from the set of keys on a standard typewriter, but clearly one can take any nonempty finite set as an alphabet without essential change) and implicitly has some mapping $D$ from the set of all finite strings of characters -- or possibly a proper subset -- into $\mathbb{R}$.

Now three things are clear:

I. For any fixed $D$, the set of $D$-nameable numbers is at most countably infinite, since it is the image of a subset of the set of all finite strings on a finite alphabet, which is countably infinite.

II. For any fixed $D$ you choose, I can name a number which you cannot. Of course you can interpret this simply as saying that the D-nameable numbers are countable whereas $\mathbb{R}$ is uncountable, but this is true in more "explicit" ways. For instance, a diagonalization argument allows me to do this in a uniform manner across all $D$ without making any "choices": I don't need any particular insight about your $D$ to give a perfectly definite answer (of course my answer will use and thus depend on the $D$ you've given me!). Suppose for instance that your $D$ is computable: that is, you give me a computer program $P_D$ which upon inputting a finite string $s$ in the domain of $D$ and a positive integer $n$ outputs the first $n$ decimal digits of $D(s)$. Then I can easily write a computer program which upon being inputted $P_D$ and a positive integer $n$ computes the first $n$ decimal digits of a certain non $D$-nameable number.

III. If we are allowed to vary $D$ with complete freedom then any real number $\alpha$ is $D$-definable for some $D$, e.g. for $D_{\alpha}$, the function which maps any string of characters to $\alpha$.

Problems arise when we assume that the usual descriptions of numbers and sets using the English language give rise to a well-defined $D$, for instance Berry's Paradox.