The set of all (infinite) sequences of digits in any finite alphabet (e.g. 0 to 9) is only countably large
Actually, the set of all infinite sequences of digits in any finite alphabet with two or more symbols is uncountable—this can be shown via a diagonalization argument. I suspect you meant to say that the set of all finite sequences of digits is countably large.
I thought I might be able to get around that limit by permitting infinite repeating sequences of digits—but it turns out that that’s equivalent to introducing a single new symbol to the notation (with the further restriction that it can only be used not more than once per number), and therefore the set of infinite repeating sequences is also countable; thus, in order to represent all real numbers, it remains insufficient.
Yup. Just for fun, some other ways to see that there are only countably many repeating sequences:
A countable union of finite sets is countable. For any m,n there are only finitely many sequences that repeat everything from place m to place n.
(Actually, a countable union of countable sets is countable but we don’t need that here.)
A repeating sequence can be generated by a computer program. There are only countably many computer programs, so there are only countably many repeating sequences.
(So there are only countably many real numbers that can be completely and explicitly specified by a computer program. They include, e.g., all the rational numbers; all the numbers that satisfy algebraic equations with integer coefficients; things like e, pi, gamma, etc.; every number that is explicitly considered in any mathematics textbook, with a few exceptions for things like Chaitin’s Ω. These are the “computable numbers”; they form e.g. an algebraically closed field. But I don’t think I know of any actual useful or interesting applications.)
Take your repeating sequence and just treat it as the decimal expansion of a number. That number is always rational. There are only countably many rational numbers.
A repeating sequence can be generated by a computer program. There are only countably many computer programs, so there are only countably many repeating sequences.
That’s an interesting point. A computer program is itself a finite number of symbols chosen from a finite list (with certain restrictions that further reduce the number of programs that make sense).
The same can be said for the English language. In fact, the same can be said for any language that can be translated into English, or into any other language that has a finite alphabet.
And I don’t know how a language with an infinite alphabet would work, but if it can be explained in English, then that implies that it can be translated to English.
This therefore implies that there must exist numbers which cannot be precisely specified at all.
I was going to say “Congratulations, you just proved the halting theorem.”—but actually I think the paradox you’re gesturing at fails to “work” for shallower reasons (e.g., the reals not being well-ordered—trivially not by the usual ordering, and less trivially not by anything computable, because it’s consistent with ZF for there to be no well-ordering of the reals).
And among these, there is the smallest undefinable number.
There isn’t. The collection of positive, undefinable numbers is bounded below by zero, but doesn’t actually have a smallest element (due to the reals not being well-ordered).
Actually, a countable union of countable sets is countable
Technical note: strictly this requires the Axiom of Choice, or at least some weaker version of it. For each of your countable sets, there is at least one way of counting it; but to count the whole lot you need to pick one way of counting each set. This is exactly the kind of thing that can fail to happen without Choice. You don’t need “very much” Choice; e.g., the axiom of choice for countable collections is enough; but it turns out that the axiom of choice for countable collections of countable sets is not enough.
Actually, the set of all infinite sequences of digits in any finite alphabet with two or more symbols is uncountable—this can be shown via a diagonalization argument. I suspect you meant to say that the set of all finite sequences of digits is countably large.
Yes, that’s right. Thanks!
I thought I might be able to get around that limit by permitting infinite repeating sequences of digits—but it turns out that that’s equivalent to introducing a single new symbol to the notation (with the further restriction that it can only be used not more than once per number), and therefore the set of infinite repeating sequences is also countable; thus, in order to represent all real numbers, it remains insufficient.
Yup. Just for fun, some other ways to see that there are only countably many repeating sequences:
A countable union of finite sets is countable. For any m,n there are only finitely many sequences that repeat everything from place m to place n.
(Actually, a countable union of countable sets is countable but we don’t need that here.)
A repeating sequence can be generated by a computer program. There are only countably many computer programs, so there are only countably many repeating sequences.
(So there are only countably many real numbers that can be completely and explicitly specified by a computer program. They include, e.g., all the rational numbers; all the numbers that satisfy algebraic equations with integer coefficients; things like e, pi, gamma, etc.; every number that is explicitly considered in any mathematics textbook, with a few exceptions for things like Chaitin’s Ω. These are the “computable numbers”; they form e.g. an algebraically closed field. But I don’t think I know of any actual useful or interesting applications.)
Take your repeating sequence and just treat it as the decimal expansion of a number. That number is always rational. There are only countably many rational numbers.
That’s an interesting point. A computer program is itself a finite number of symbols chosen from a finite list (with certain restrictions that further reduce the number of programs that make sense).
The same can be said for the English language. In fact, the same can be said for any language that can be translated into English, or into any other language that has a finite alphabet.
And I don’t know how a language with an infinite alphabet would work, but if it can be explained in English, then that implies that it can be translated to English.
This therefore implies that there must exist numbers which cannot be precisely specified at all.
Almost all of them! But, y’know, I can’t tell you what any of them are :-).
And among these, there is the smallest undefinable number.
I was going to say “Congratulations, you just proved the halting theorem.”—but actually I think the paradox you’re gesturing at fails to “work” for shallower reasons (e.g., the reals not being well-ordered—trivially not by the usual ordering, and less trivially not by anything computable, because it’s consistent with ZF for there to be no well-ordering of the reals).
There isn’t. The collection of positive, undefinable numbers is bounded below by zero, but doesn’t actually have a smallest element (due to the reals not being well-ordered).
If you mean the smallest undefinable positive number, then isn’t that epsilon?
Technical note: strictly this requires the Axiom of Choice, or at least some weaker version of it. For each of your countable sets, there is at least one way of counting it; but to count the whole lot you need to pick one way of counting each set. This is exactly the kind of thing that can fail to happen without Choice. You don’t need “very much” Choice; e.g., the axiom of choice for countable collections is enough; but it turns out that the axiom of choice for countable collections of countable sets is not enough.