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

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?

• There is a difference between infinite sequences and arbitrarily long finite sequences. In particular $\aleph_0^{\aleph_0} = \mathfrak{c}$ (the exponent is infinite), but $\bigcup_{i \in \mathbb{N}}\aleph_0^i = \aleph_0$ (the exponent is finite). – dtldarek Jan 28 '14 at 20:03
• That is not a listing of the reals because it fails to list the number $\frac 13$. – MJD Jan 28 '14 at 20:16
• @MJD That number is most certainly bound to $8$. – user2939875 Jan 28 '14 at 20:23
• Did you say that in the question? Or was I just supposed to guess? Your post seems to suggest that at the time you wrote it, you thought that $\{0,1, \ldots, 7, ., -\}^\ast$ would exhaust the rationals. – MJD Jan 28 '14 at 20:29

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 surective. There will always be some reals left over that you're not representing.

• What I'm not understanding is how these missing representations actually manifest when all notions are inextricably bound to the limitations of syntax. – user2939875 Jan 28 '14 at 20:11
• @user2939875: I don't understand what you mean by "inextricably bound to the limitations of syntax". Since $\Sigma^*$ is countable, there is a surjection $f:\mathbb N\to \Sigma^*$. If you have any representation scheme $g:\Sigma^*\to\mathbb R$, form the composition $g\circ f:\mathbb N\to\Sigma^*$, and apply Cantor's theorem (for example, with the diagonal proof). This produces a real number $x$ that is not hit by $g\circ f$ -- and since $f$ hits all of $\Sigma^*$, we can conclude that $g$ doesn't hit $x$ either. Therefore your $g$ does not represent all of $\mathbb R$. – Henning Makholm Jan 28 '14 at 20:17
• In fact, the statement that 'all notions are inextricably bound to the limitations of syntax' is at the crux of the problem; the reals are so deep and mysterious that not only can we not list them all, we can't compute them all; the number of programs is also countable and so the number of numbers computed by them must be countable as well. This implies that there are uncomputable reals, reals that we can't possibly give a proper description of. (Arguably, the fact that we don't even 'know' how many reals there are - the continuum hypothesis - arises because of this unknowability.) – Steven Stadnicki Feb 27 '14 at 16:23

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.