2
$\begingroup$

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

1 Answers 1

3

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.

  • 0
    @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.2012-02-25