Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$?

share|improve this question
8  
Surely the cardinality of the nameable numbers is at most the cardinality of the names. And what's in a name? A finite collection of symbols from a finite alphabet... –  Qiaochu Yuan Jul 17 '11 at 3:06
6  
By the way, it is not true that every set of real numbers of measure zero is countable. For example, the Cantor set (en.wikipedia.org/wiki/Cantor_set) has measure zero but is not countable. –  Qiaochu Yuan Jul 17 '11 at 3:08
    
@Qiaochu and that's percisely what I fail to understand. I see how we can encode the computable numbers via a Turing machine, but $\Omega$ can't be computed by a Turing machine, it would require something ... more powerful? And with these more powerful machines, can we match all their codes to an integer? If so, what does it look like? –  Hooked Jul 17 '11 at 3:14
2  
@Hooked: Not only is $\mathbb{Q}$ countable and dense in $\mathbb{R}$, but if $C$ is the ternary Cantor set mentioned by Qiaochu, $|C|=|\mathbb{R}|$, and $C$ is nowhere dense in $\mathbb{R}$ (meaning that every open interval of real numbers contains numbers not in $C$). –  Brian M. Scott Jul 17 '11 at 4:42
1  
Why should this collection even form a set? How do we know that it is meaningful to speak of its cardinality? –  user83827 Jul 17 '11 at 6:54
show 8 more comments

2 Answers

up vote 11 down vote accepted

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

share|improve this answer
    
This argument seems a bit fishy to me; am I missing some details? It looks like you're using a metamathematical enumeration of formulas to conclude that your particular universe of set theory thinks a certain collection (which may not even be a set as far as I can tell) is countable. It reminds me of Skolem's paradox: en.wikipedia.org/wiki/Skolem%27s_paradox –  user83827 Jul 17 '11 at 7:09
    
@Pete: Comprehension only applies when there is a first-order definition of whatever property you're considering. Suppose we had a f.o. formula $\phi$ such that $\phi(x)$ iff $x$ is definable. Then every element of $\omega_1$ would be definable (if not, "the least element which is not definable" would be a definition of a non-definable element!), which seems to contradict the apparent argument that only countably many things can be definable. –  user83827 Jul 17 '11 at 7:45
    
@Qiaochu: I found your "countably many names" argument in the comments to be simpler and more general. The linked wikipedia article uses some serious set theory (and it says "assuming the definable numbers form a set", which confuses me just as in ccc's comment: maybe I am missing something here) and it mentions that there are in a sense nameable numbers which are not definable, e.g. using a diagonalization argument. But it's clear that there are only countably many things that we can uniquely specify by name, because there are only countably many names. Why not just leave it at that? –  Pete L. Clark Jul 17 '11 at 7:49
    
@ccc: I take your point, thanks. As in my last comment, a less explicitly set-theoretic approach seems best. Moreover, upon further thought I agree that there are some potential paradoxes here, e.g. as in en.wikipedia.org/wiki/Berry_paradox. –  Pete L. Clark Jul 17 '11 at 7:57
1  
@Pete: these issues were extensively discussed in one of JDH's MO answers if you're interested: mathoverflow.net/questions/44102/… –  Qiaochu Yuan Jul 17 '11 at 13:50
show 8 more comments

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.