Take the 2-minute tour ×

I have noticed a pattern. The set of integers is infinite. Therefore one at first would think it impossible to come up with a notation allowing the representation of all integers. This though becomes easy actually to get around. Simply allow larger integers to take up larger notation. Now look at the rational numbers. They are dense, so there are an infinite number of rational numbers between 0 and 1. Seemingly impossible, but not. By dividing two integers, you can come up with any rational numbers. Algebraic, and even all the computable numbers can be notated. Yet when you get to the real numbers, the great uncountable set, there is no finite notation to represent all the real numbers. Why is it that countable sets can be notated, but it seems that uncountable sets can not? Has this been studied before?

share|improve this question
Depending on your definition of notation, there are some countable sets that have no good notation. For example, the collection of all Turing machines that do not halt is a subset of the countable set of all Turing machines, but there is no way to enumerate them with a computer program, which would sort of be necessary for any good notation. –  Thomas Andrews Mar 27 '13 at 0:19
It is sort of a shame that the real numbers can not be detonated finitely. You know what I mean. –  PyRulez Mar 27 '13 at 0:22
You want to explode the real numbers? :) Yeah, you meant denotated. –  Thomas Andrews Mar 27 '13 at 0:24

4 Answers 4

up vote 2 down vote accepted

Let $\mathcal A$ be a finite alphabet. It can be the set of all familiar letters and digits or any other finite set you want. The set of all finite strings formed from this finite alphabet is countable. To show this, let $S_n$ be the set of all strings of length $n \in \Bbb N$ formed from this alphabet. Each such $S_n$ is finite. The set of all possible finite strings fromed from the alphabet $\mathcal A$ is then $\bigcup_{n=0}^\infty S_n$. This set is infinite. But it's the countable union of finite sets, so it's countable. On other hand, $\Bbb R$ is uncountable. Therefore, it's not possible to establish a bijection between the two sets.

share|improve this answer

Say you have a finite alphabet $A$ for denoting your sets. Your possible denotations are now given by the set $X$ of all finite-length tuples with entries in $A$. It is not hard to show that $X$ is countable. So there is no way to denote all the elements of an uncountable set in this way.

As a side note: This is exactly the way how to show that there are functions which cannot be computed: The set of all programs is countable (by the same argument), but the set of all functions is uncountable.

share|improve this answer
I was thinking of this, but for some reason it was not coming to me. –  PyRulez Mar 27 '13 at 0:15

Think about it - to "notate" a number, you must represent it using some fixed language. This language must have a set of "letters", an "alphabet". For instance, for rational numbers, we can "notate" a fraction using the "letters" {0,1,2,3,4,5,6,7,8,9,/}, with five restrictions - "0" cannot be the first symbol or the first symbol following a "/", "/" cannot be the first or last symbol or be followed by another "/".

In this "language", there are multiple "words" that mean the same thing. For instance, "2/2" means the same thing as "1/1", as does "6/2/3".

Now, all rational numbers can be expressed in at least one finite way in this language. But we can also associate these with integers by replacing each "letter" with a number, in this case in base 11. If we let "/" be equivalent to A (value 10 in base 11), then "1/1" = $1A1_{11}$ = 232. Meanwhile, the integer "232" gets mapped to $232_{11}$ = 277.

If we could "notate" uncountable numbers, then this would provide a method by which we could count them, and thus they would not be uncountable. Therefore, we cannot "notate" uncountable numbers.

share|improve this answer

Other people have answered why uncountable sets cannot be notated.

I'll just add that some countable sets cannot be "usefully" notated. So it depends on your definition of notation.

For example, the set of all Turing machines is countable. The set of Turing machines that do not halt is a subset, so is also countable. But there is no practical notation - that is, no programatic way - which allows for the enumeration of the set of non-halting Turing machines. A notation system is only as useful as it is computable, and there is no computable enumeration of this set.

share|improve this answer

Your Answer


