# Using Gödel Numbering to Represent Sets of Real Numbers

Recently, I was looking at Gödel numbering, and I was wondering, is it possible to represent, as a single real number, a set of real numbers. When dealing with only rational numbers, it would be easy enough to encode a number as {numerator,denominator,2 (negative) or 3 (positive)} However, for real numbers, this obviously won't work. Many irrational numbers can be represented as $\sqrt{x}$ and thus can be represented using their lexical representation. However, what about real numbers which we can't lexically name (if any exist)? Will a unique number still be generated if numbers are raised to those powers?

Thanks, Maz

-

It depends on what you are looking for. I can easily code two real numbers using just one, for example I can code the real numbers $a_n\cdots a_0.a_{-1}a_{-2}\cdots,b_m\cdots b_0.b_{-1}b_{-2}\cdots$ (where each $a_i,b_i$ is a base 10 digit and we assume $n\geq m$) as the real number $$a_n\cdots a_mb_ma_{n-1}b_{n-1}\cdots a_0b_0.a_{-1}b_{-1}a_{-2}b_{-2}\cdots$$ and by repeating this code any finite number of real numbers as a single real number. In fact, I could code countably infinitely many real numbers as a single real number. For real numbers between $0$ and $1$ I could do so by putting the $i^{th}$ digit (e.g. in $0.00a_{-3}00\cdots$ the 3rd digit would be $a_{-3}$) of the $j^{th}$ number at the $p_j^i$-th place, where $p_j$ is the $j^{th}$ prime number. It is easy to extend such a scheme to arbitrary countable sets of real numbers by simply keeping track of sign and the finite number of digits in each before the decimal place.

However, there is no method that will allow you to encode all uncountable sets of real numbers as a real number, because such an algorithm would be an injection from the set of uncountable subsets of the reals (which has cardinality $2^\mathfrak{c}$) to the set of real numbers (which has cardinality $\mathfrak c$), and no such injection exists.

-
Why won't a lexical encoding work? –  Maz Feb 25 '12 at 5:10
@Maz To encode any uncountable set of reals as a single real number? –  Alex Becker Feb 25 '12 at 5:13
To encode a single real, as long as we can describe it with letters or symbols, can't we assign each one of those a natural number, and then we have a set of natural numbers representing an irrational number. I suppose the bigger question is: are there irrational numbers that we can't define? –  Maz Feb 25 '12 at 5:20
@Maz The fact that any such method of encoding fails indeed implies that there are real numbers we cannot define. This is a very good observation! In fact, the set of definable numbers is countable (i.e. the same size as the set of natural numbers) and thus is a tiny subset of the real numbers. So we can define very few real numbers! –  Alex Becker Feb 25 '12 at 5:38
@Alex: Be careful! You're treading into a veritable minefield of technical logical issues with that statement. It's far safer to leave it at that the fact isn't an injective set function from the reals to the naturals. –  Hurkyl Feb 25 '12 at 12:00