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

  • 10
    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...2011-07-17
  • 6
    By the way, it is not true that every set of real numbers of measure zero is countable. For example, the Cantor set (http://en.wikipedia.org/wiki/Cantor_set) has measure zero but is not countable.2011-07-17
  • 0
    @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?2011-07-17
  • 0
    What leads you to think that "the probability that you'll pick one [a nameable number] at random is zero" implies that $|\mathbb{A}| = \aleph_0$?2011-07-17
  • 0
    @amWhy given Qiaochu's example of the Cantor set, I don't think that $|\mathbb{A}|=\aleph_0$ immediately follows anymore! However, I can see only three possible outcomes, 1] $|\mathbb{A}|=|\mathbb{R}|$ which seems unlikely since they aren't dense. 2] $|\mathbb{N}| < |\mathbb{A}| < |\mathbb{R}|$ which violates the CM. 3] $|\mathbb{A}| = \aleph_0$ as the only option left.2011-07-17
  • 0
    @Hooked: Qiaochu's answer shows why $|A|=\aleph _0$, but note that $\mathbb{Q}$ is countable and dense in $\mathbb{R}$, so density is not an argument. There are many countable, noncomputable sets. Most are undefinable-again the definitions are countable, but the subsets of $\mathbb{N}$ are not.2011-07-17
  • 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$).2011-07-17
  • 1
    Why should this collection even form a set? How do we know that it is meaningful to speak of its cardinality?2011-07-17
  • 0
    Let me ask this: does Chaitin give a precise definition of a **nameable number** in his book?2011-07-17
  • 0
    @ccc The set $\mathbb{A}$ exists because the function that maps the "names" of a nameable real to the real it actually names is a function from a known (countable) set (the set of names) to a known set (the real numbers). So by the Axiom of Replacement, $\mathbb{A}$ is a set.2011-07-25
  • 0
    @tomcuchta. You are not applying Replacement correctly. First, the collection of names is in the meta-universe, not the set-theoretic universe under consideration. Second, even if you manage to somehow encode the names in the universe in a faithful way, the "map" which sends a name to the real it names is not first-order definable, so Replacement does not grant anything. You have to be very careful dealing with notions as circular as "definable" (or "nameable," whatever that actually means) or you run into contradictions quickly.2011-07-25
  • 0
    @ccc Why isn't that function first order definable even if we have a faithful encoding? Set theory can't see that it's an encoding? If not, then how did we know what the encodings encode in the first place?2011-07-25
  • 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
    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: http://en.wikipedia.org/wiki/Skolem%27s_paradox2011-07-17
  • 0
    @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.2011-07-17
  • 0
    @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?2011-07-17
  • 0
    @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 http://en.wikipedia.org/wiki/Berry_paradox.2011-07-17
  • 0
    @Pete: If you haven't yet, I strongly suggest you read up on Skolem's paradox. It is related to this very issue of determining whether things are countable when moving between various universes of set theory (or in this case, between a universe and the metatheory).2011-07-17
  • 0
    @ccc: I am familiar with Skolem's paradox, and I see what you are getting at...but at the moment I do not want to consider answers that involve models of ZFC set theory. (Maybe this is really necessary and I'm just evading the issue; we'll see...) So I recorded a much more naive answer of my own.2011-07-17
  • 0
    @ccc: I am only talking about external countability, not internal countability.2011-07-17
  • 1
    @Pete: these issues were extensively discussed in one of JDH's MO answers if you're interested: http://mathoverflow.net/questions/44102/is-the-analysis-as-taught-in-universities-in-fact-the-analysis-of-definable-numbe/44129#441292011-07-17
  • 0
    @Qiaochu: thanks, that is indeed helpful. Do you think one needs to give such a set-theoretically fraught answer though?2011-07-17
  • 0
    @Pete: well, I think it is worth saying when a statement not internally provable in ZFC, if only so a student does not get tripped up later on by precisely the issues JDH discusses.2011-07-17
  • 0
    Hmm. What I am saying is that if your definition of "nameable number" leads to such a complicated answer, maybe we should check whether that's actually the intended definition?2011-07-17
  • 0
    @Pete: well, I suppose there are potentially many ways to interpret "what is the cardinality of numbers like $\Omega$?" But I'm out of ideas myself.2011-07-17
  • 0
    @Qiaochu: Thanks for clarifying the intent of your answer, and also for linking to that well written MO answer!2011-07-17
8

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.