If the Kleene star of countable sets is countable, how are the real numbers uncountable?

Question

The formal languages we use to represent number systems are interchangeable, which is why we don't hesitate to use different notations, e.g. hexadecimal, octal, binary, etc... to represent the reals. The addition, or removal, of characters to the underlying alphabet is irrelevant, as long as the interpretation remains consistent.

So why are we restricted from using the integers to represent real numbers?

For example, the octal language used to represent real numbers consists of the following alphabet: $\{0,1,2,3,4,5,6,7,.,-\}$. Clearly, we can replace the decimal point '$.$' and the minus sign '$-$' with $8$ and $9$ respectively. Thus a real number such as $-9.125_{10}$ or $-11.1_{8}$ becomes $91181$. This mapping also leaves us with an infinite number of meaningless symbols such as $888..$, $8989...$, or $999...$ which could be used to establish an entirely new language ($\{8,9\}^*$) that could be used to represent irrationals or whatever else you'd like.

Why doesn't this particular interpretation constitute an injective mapping?

How is this not a listing of the reals?

Answer 1

The Kleene star produces only finite sequences of the alphabet symbols. The elements in $\Sigma^*$ for some alphabet $\Sigma$ can be arbitrary long, but each of them is, individually, finite.

Because of this, there are not enough elements in $\Sigma^*$ to give every real number a representation.

You can select some irrational numbers to represent with your strings-that-don't-have-a-meaning-yet, of course -- getting an injective mapping from $\Sigma^*$ to $\mathbb R$ is no problem, but you can't make it surjective. There will always be some reals left over that you're not representing.

Answer 2

The short answer to the issue raised your question is this: $K^\ast$ is the set of finite sequences of elements of $K$. If $K$ is a finite set, then $K^\ast$ is countable, and Cantor's theorem tells us that the real numbers are not countable.

The mapping may be injective, but the real question is whether it is surjective: for any real number $r$, is there some sequence that is mapped to $r$. But there surely is not.

I began by asking how you plan to represent $\frac 13$, since the scheme you described, which is supposed to map rational numbers onto elements of $\{0, 1, \ldots 9\}^\ast$, does not succeed with $\frac13$, which is $0._825252525\ldots$ and does not receive a terminating base-8 representation, so does not correspond to a finite sequence of symbols in your system. You arbitrarily assigned $\frac13$ the representation 8.

But it's rather ingenuous to ask “How is this not a listing of the reals?” when you didn't actually explain how you plan to map $\{8, 9\}^\ast$ to the "irrationals or whatever", where "whatever" now apparently includes $\frac13$. If you had given a specific mapping, it would be possible to produce a real number that you missed; this is exactly what Cantor's theorem does. But in the absence of a particular mapping, all one can do is appeal to Cantor's theorem in general.

But these sequences are not members of $\{0,1\}^\ast$, because that is the set of finite sequences of zeroes and ones, and many real numbers are only represented by an infinite sequence. For example, $\frac13$ is $0._201010101\ldots$.

And indeed Cantor's theorem tells us that there is no system in which every real number has a finite representation.