Apply Cantor’s diagonal argument to the list of describable numbers, and one arrives at a description of a number which is not describable. A paradox? Not at all. Merely proof that higher orders of description exist. That is, some numbers are metagrammatical. They can be described and computed to arbitrary precision, but necessarily the description is meta to whatever grammar one begins with. This is delightful!
Details: We call a number describable if it can be described by a finite expression, with a specified alphabet and a specified grammar, which decides how to compute the number from the description if it is grammatical, and discards expressions which are not grammatical (i.e., we are using ”grammar” to mean both what is admissible as a description, and given an admissible description, what is the protocol to compute the number which is described). For example, consider the set
With this set we can describe every rational number, since we can write a rational number as an expression using just these 5 characters. (If we are careful we can get rid of the parentheses). The grammar throws out nonsensical expressions like , and computes the others. Allowing iterative operators (e.g., ), quantifiers (), a countable number of variable (), et cetera, we get descriptions of algebraic numbers and a lot of common transcendental numbers. Still, even with a countable alphabet we can enumerate the number of finite strings of characters, so that the set of describable numbers is countable. This is not too surprising, but if you have never thought about it, it is worth pondering. This set of numbers is a field, for example, and not a trivial example either! Indeed (almost) all numbers that are useful at all are describable. Of course, picking one at random (with equal distribution) is impossible, so probabilists, among others, demand the existence of indescribable numbers.
Let us make a list of all descriptions on the left hand side of our paper, and on the right we will make the corresponding list of numbers, written in binary (which frequently do not terminate, but that’s allowed). Now we’ll construct a number, , that can be computed but is not on our list. Let have as its th diadic (“diadic” is like “digit” but for base two and not base ten) a 0 if the th description has a 1 in its th diadic, and a 1 if the th description has a 0 in its th diadic. That is, go down the diagonal of the list of numbers and make the number which has switched each diadic in the diagonal. Have we not described ? But it cannot be on our list, since it differs from every number on our list in at least one diadic.
The point is we can never nest a description of a grammar within the grammar itself, although we can nest one grammar inside another. If we could nest a grammar inside itself, we could, in grammar , write the description
the th diadic of this number is the opposite (base 2) of the th diadic of the th description in ,
and we would have produced the paradoxical situation of having a number which both is and is not on a countable list.
More specifically, let some huge be the number in an ordering of , so that the th description is the one in the above blockquote, and let it correspond to the real number , which it describes. If such a description can be written, it must be written in a finite number of characters, and so there must be some such number . Now we ask what is the first diadic in ? No problem, our grammar just asks itself what the st diadic in the first description is, and adds 1 (mod 2) to it, next it asks what the nd diadic in the second description is, and adds 1 (mod 2) to it. Eventually it gets to and it asks itself about the th description, but the th description requires it make a list of the first descriptions to get to the th diadic in that number, so the grammar tries to reference itself, and in doing so must reference itself again, in a nested infinite recursive loop. So forget about the fact that the grammar is paradoxically trying to switch one of its own diadics. Forget the paradox that the number is both on and not on the countable list. The first problem is that the grammar goes into an infinite recursion.
In fact, lets go back and do the same thing except instead of switching the th diadic of the th describable number, we use the th diadic of the th describable number as the th diadic in our number, say . Can you think of a more agreeable number to have on our list? could be any of the countable numbers on our list. Suppose it is the th number. What does it have for its th diadic? Well, either 0 or 1, since this number must merely be equal to itself. But then is not describable, since its description does not produce a unique value!
This is, essentially, how one approaches the Berry Paradox. In short,
definable in this system
is just never a logical definition (or clause thereof) in that system.
However, once we agree on what a definition or a description is, then these examples tell us that there are deterministically producible, unambiguously definable, finitely expressible numbers and strings which can only be expressed with a grammar meta to the one first chosen.
What a delight!