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$?
Answer
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).
No comments:
Post a Comment