This is very strange. I’ve looked through all the books that I’ve read recently and cannot find it, even after exhausting the indices of each. I can even remember that the definition took a full page, was printed on the right hand page, was more than likely in a book printed by Dover, was in the first half of the book, involved defining a relation, R, inputting 2 to a certain function made “diagonalization” drop out, and for every natural number another proof method was obtained. I’m also pretty sure that this was due to Quine in some of his work on paradoxes (I’m sure you are aware, a lot of paradoxes are related to diagonalization).
However, there doesn’t seem to be a single mention of this on the Internet!
Remember: the result only shows that the Continuum Hypothesis cannot be proved or disproved from a particular system of axioms*. Just because a set “actually exists” in some Platonic sense, doesn’t mean you can describe it and prove its existence in the language of that particular formal system, and even if you could, it certainly doesn’t mean you could prove that it was larger than countable and smaller than uncountable in that particular formal system.
Consider the so-called “field axioms”: These state that there are operations + and * on numbers, each of which is associative, commutative, and has an identity element (denoted 0 and 1 respectively; we also use 2 to denote 1 + 1, 3 to denote 1 + 1 + 1, etc.). Furthermore, * distributes over + [i.e., x * (y + z) = x*y + x*z]. And, every number has an inverse with respect to + (we use - to denote “+ the inverse of”), and every number not equal to 0 has an inverse with respect to * (we use / to denote “* the inverse of”). Finally, we demand that 0 not be equal to 1.
Great. This is a fine formal system in which we can prove many things (e.g., we can show that there exists a square root of 9, that the number of roots of x^2 + 3x + 8 is even, that 0 * x = 0 for all x, etc.). But, there are also very simple things which this system does not prove one way or another; for example, we can ask if 2 has a square root (or if -1 has a square root, or if x^2 + 3x + 8 has any roots).
How do I know this system doesn’t answer these questions one way or another? Well, it can’t prove that these numbers exist, since the rationals satisfy all these axioms but have no such roots. But it can’t prove that these numbers don’t exist, either, since the complex numbers satisfy all these axioms and do have such roots. The field axioms underspecify; there are certain questions which they do not resolve, even questions about what kinds of numbers exist, because they are compatible with all kinds of different structures, not all of whom agree about these questions.
The situation with the Continuum Hypothesis is the same (assuming, as always, that ZFC is consistent): the ZFC axioms of set theory underspecify; they are compatible with structures in which there is a cardinality inbetween |N| and 2^|N|, and they are also compatible with structures in which there is not.
*: Well, the CH independence result isn’t really intrinsically about just ZFC, per se; there’s a whole class of axiom systems with the right properties to make the argument go through, but the point is the same.
If your formal system and your intended model (i.e., your notion of what the language of your formal system is actually talking about) are compatible in the right way, then this sort of thing works out in particular situations; for example, suppose your hypothesis is “There is an integer/string/whatever having property P” (with the intended model, of course, being the standard integers/strings/whatever that we know and love). Suppose also that P is such a simple property as to be semidecidable [by which I mean, any number/string which actually has property P in the intended model can be proved, within your formal system, to do so; for example, P might be the property of being a palindrome, or being the sum of two primes, or of being the source code of a program that eventually halts].
In that case, proving the hypothesis unprovable will indeed be the same as proving it false, by the obvious reasoning (this fact gets called fancy names like “The Sigma_1-completeness of formal arithmetic”). So if we could prove that “There is an even number > 2 which is not the sum of two primes” was unprovable, we would have automatically proved it false. But we need all those extra assumptions above to make the argument go through; it doesn’t automatically hold of anything and everything.
For example, if my hypothesis is “There is a number which is larger than all twin primes”, the kind of reasoning above doesn’t automatically hold; it’s perfectly well plausible that such a number exists, yet, all the same, that our particular formal system isn’t capable of proving that it has this property. If I were to hand you such an upper-bound, and say “Can’t you see? Isn’t it immediately obvious that all twin primes are below this?”, you would probably shake your head and say “Uh, no. It’s not obvious. I’m not sure how I would prove such a thing.” Merely satisfying a property doesn’t generally ensure that a proof of such can be find.
Well, pedantically speaking, it all depends on what we take to be our language of definition. If we take it to be a programming language in the natural way, then all definable numbers are automatically computable; if we take it to have constants referring to each real number, then the set of definable numbers is automatically uncountable. But presumably, you’re both taking it to be something like “(an idealizedly unambiguous version of) English” or “the language of ZFC”, in which case, sure. [Though definability in “(an idealizedly unambiguous version of) English” is troublingly tricky; is not the diagonalization argument which produces an “undefinable” number itself definable? It is a point of some great gnashing of teeth…]
Whoops, we need slightly more than the field axioms to prove that the number of roots of x^2 + 3x + 8 is even. We also need the fact that 23 is not equal to 0, which doesn’t actually follow from those axioms. I hang my head in shame (but this is, again, a fine example of independence)…
No, it is not itself a definition, not unless you first produce the complete list, in order, of numbers you’re diagonalizing across.
And I’m content to restrict “definitions” to strings of finite length drawn from a finite alphabet, myself. I don’t make any qualms about what alphabet you use, though. Even the English language is fine, so long as you realize that not all strings in the English language specify any number at all (and you can’t even tell in general which ones do specify a number). But the set of numbers specifiable in English is certainly isomorphic to a subset of the set of all strings in English, and the set of all strings in English is countable, so the set of numbers specifiable in English is therefore also countable.
What I mean is, does the English string “The binary sequence whose k-th bit is the opposite of the k-th bit of the binary sequence defined by the k-th English string which defines a binary sequence” define a binary sequence? It would certainly appear to; after all, it is the description we use to establish the existence of an non-English-definable binary sequence. But then, paradox…
Presumably, the start of the way out is in “(and you can’t even tell in general which ones do specify a number)”, but exactly how this helps is not clear; are we willing to say “the k-th English string which defines a binary sequence” is not well defined? If so, then we may avoid paradox, but our method of avoiding it involves rejecting the diagonalization argument as establishing the existence of a non-English-definable binary sequence as well.
Well, perhaps scratch that last sentence, and replace it with:
If so, then we may avoid paradox, by considering the English strings which define such-and-such to have a bijection with the natural numbers, but no definable one. But is it not odd to say of “the k-th string which defines a binary sequence” that it is definable? I mean, one string serving superplausibly as a definition of it is staring us right in the face…
What this amounts to, of course, is that the property of defining, in English, a binary sequence must be taken as not definable in English. But, again, it sure looks definable; it sure looks like we’ve employed a phrase that refers clearly to it.
I’m perfectly fine with that, since I wasn’t using a diagonalization argument to establish the existence of such a sequence in the first place. It’s simple enough to prove that the set of English-definable binary sequences is countable, and it’s also simple enough (using a separate proof) to show that the total number of binary sequences is uncountable. Put those two together, and you’ve nonconstructively proven the existence of non-English-definable binary sequences (in fact, a great many of them).
The paradox transfers over; the diagonalization argument you use to establish that {binary sequenes} has no bijection with {natural numbers} translates, when composed with the (presumably English-definable) bijection between {natural numbers} and {English strings defining binary sequences}, into the same thing as a direct diagonalization argument on {English strings defining maps from English strings to bits}. Which has all the above mentioned paradoxical difficulties.
I make no claims to be able to define that bijection, either. I can define a bijection between all English strings and the natural numbers, thus proving that the set of English strings is countable. And the set of English strings defining binary sequences is clearly a subset of the set of all English strings, right? And since any subset of a countable set is also countable, that shows that the set of English strings defining binary sequences is countable.
Sure, you may not explicitly claim it, but it is implicitly present in the argument for your claim that every subset of a countable set is itself countable (though it depends on what you mean by this; see below). Specifically, it sure looks like such a bijection can be defined, simply by sending the number n to the n-th English string which defines a binary sequence.
My point is, whatever your particular explicit claims are, formal discussion of definability in English (or any other ordinary language) has shown itself to be tricky and fraught with paradox, because of issues like “The binary sequence whose k-th bit is the opposite of the k-th bit in the sequence defined by the k-th English phrase defining a binary sequence”, “The smallest integer not English-definable in under 200 characters”, “The property of being an English phrase which does not define a property of English phrases which it itself satisfies”, and so forth. Because of this, I am not comfortable with making nontrivial claims about the concept of English-definability as though its appropriate analysis in this regard was a matter of settled mathematical fact; I think disclaimers are generally warranted.
When you say “countable”, do you mean “in bijection with the natural numbers” (call this A-countable) or “in bijection with a subset of the natural numbers [i.e., injects into the natural numbers]” (call this B-countable) or “is the image of a partial function on the natural numbers [i.e., there is a partial surjection from the natural numbers to]” (call this C-countable) or what?
[Section on nuances of A-, B-, and C-countability removed; I think I’ll just wait for you to say which one you meant]
Let’s put it another way. The following is the argument for the existence of bit-sequences not definable in English (depending on precisely what “countable” is taken to mean, some slight changes in the exact wording of the following may need to be made; regardless, this, as I understand it, is the basic framework of the proof):
The uncountability of bit-sequences is shown by establishing that every countable set of bit-sequences is missing at least one; the proof of this proceeds by explicitly defining, from any map witnessing the countability of a set of bit-sequences, a specific bit-sequence not in that set.
The proof that the range of any partial function on a countable set is itself countable proceeds by explicitly defining, from the partial function and a map witnessing the countability of the set of potential arguments, a map witnessing the countability of the range.
The proof of the countability of English strings proceeds by explicitly defining a map witnessing the countability of English strings.
Composing these three, we have a proof that the range of any partial function from English strings to bit-sequences is missing at least one; this proof proceeds by explicitly defining, from the partial function, a specific bit-sequence not in its range. [That is to say, this proof works by defining a function MissedOne such that, for every partial function j from English strings to bit-sequences, MissedOne(j) is a bit-sequence not in the range of j.]
As an instance of this, consider the partial function Interp which sends English strings to the bit-sequences they define; our proof establishes that MissedOne(Interp) is not in Interp’s range, and thus a bit-sequence which is not English-definable.
But, being English-speaking mathematicians, our definition of MissedOne is carried out in English; if Interp is English-definable as well, then so is MissedOne(Interp), yielding a contradiction.
But surely Interp is English-definable…?..!
Does this make the troublesome aspect of the argument clearer?
I think I mean B-countable… I certainly don’t mean A-countable, since by that definition, finite sets are not countable, and I’m not certain I understand C, since it looks to me to be equivalent to B.
Possibly the point where we’re differing is that I do not require an English construction to be meaningful in order to be valid: For instance, “The smallest integer not English-definable in under 200 characters” is a validly-constructed English noun phrase, but is nonetheless meaningless, and certainly doesn’t define any number. For a less mathematical example, something like “The rock’s aspirations are mauve, and taste like gravity.” is a valid but meaningless English sentence.
And I’ve never encountered “witnessing” as a mathematical term… What does that mean? And are we allowed to do it in GQ?
I know the Continuum Hypothesis says that the cardinality of the real numbers equals aleph-1, and that this is neither provable nor disprovable under the ZFC axioms. I also know that if you use the Axiom of Constructibility, you can prove CH and the Greater Continuum Hypothesis as well, where 2^aleph-n = aleph-(n+1).
(For those of you not familiar with this, the cardinality of the natural numbers is aleph-0, and the cardinality of the real numbers is 2^aleph-0. That means the set of real numbers is the same size as the set of all subsets of the natural numbers.)
My questions are:
What sets are provable as having cardinality aleph-1, and why can’t these sets be compared to the continuum in ZFC?
Why do most set theorists dislike the Axiom of Constructibility, which neatly resolves that pesky problem?
How can we prove that the set of real numbers is the same size as the set of all subsets of the natural numbers? I suppose it has to do with the fact that you can write a real number as an infinite decimal expansion, which is composed of concatenated natural numbers. But how do you prove the bijection?
The set of countable ordinals has cardinality aleph_1. ZFC proves that this set has cardinality <= 2^(aleph_0); it just doesn’t settle whether it’s < or =. “Why”? Because, given any model V of ZFC, we can construct a new model where the answer goes either way; by restricting ourselves to its predicative/constructible sets, we obtain the model L, which has aleph_1 = the continuum. Alternatively, by using forcing, we can augment V with a large number of “random reals” to obtain a new model which has the continuum much larger than aleph_1. Thus, if ZFC is consistent, it cannot prove the result to go either way.
Because it’s a principle of parsimony and set theorists prefer principles of plenitude (cf. set theorists’ embrace of large cardinal axioms, etc.). One might also say there is no compelling intuition in favor of this axiom holding of “the actual set-theoretic universe” (though the quoted bit does, of course, have its Platonic overtones); it’s easy to resolve questions by adopting axioms with no compelling motivation in themselves. The trick is to resolve questions starting from principles that are more clearly true.
