display | more...

So you understand enough set theory to know that for every set there exists a larger set, or at least you know how Georg Cantor's diagonal argument proves that the set of real numbers is "larger" than the set of integers. Perhaps you've progressed enough into the history of set theory to know that c = 20 and how the whole controversy over the Continuum hypothesis (i.e. 1 =? ℵc) led to a civil war in mathematics and eventually the popular 1980 book Gödel, Escher, Bach: An Eternal Golden Braid.

So you know that the power set of the integers can be mapped to the reals; you just haven't seen the construction yet.

The following is not perfect (i.e. it is not actually a one-to-one-correspondence (aka "bijection") but it is sufficient to demonstrate the concept (i.e. it is surjective) and has the added benefit of being intuitive.

We need to associate each set of integers M with a real number R. Consider the function IN(i, M) = { 0, if i ∉ M or 1, if i ∈ M }. Define RE(M) = Limn→∞ Σi=1..n 2-i*IN(i,M).

Too mathy? Well, think of the set M as the set of which digits are 1's in the binary representation of RE(M). For example, if we pick the set of all even integers:

```
M = { 2, 4, 6, 8, 10, ...... }

i:             1      2      3      4      5        6       7        8 ...
IN(i,M):       0      1      0      1      0        1       0        1 ...
2-i:         1/2    1/4    1/8   1/16   1/32     1/64   1/128    1/256 ...
(decimal)
partial sum:   0    .25    .25  .3125  .3125  .328125 .328125 .3320125 ...

```

If you work out the geometric series you'll find that as i->∞ the final sum RE(M) approaches 0.33333... or 1/3. The binary representation of 1/3 is 0.0101010101.... In our mapping, then, the set of all even integers corrsponds to 1/3.

Every real number has a binary representation, and so every real number between 0 and 1 has a set of positive integers associated with it. What's more, RE is a function on the power set of positive integers, since there is only one RE(M) for each M.

(I'm sure you're clever enough to figure out a way to work in the negative integers. And to expand the interval [0, 1] to the entire set of reals (think: RE2(M)=tan(π(RE(M)-0.5)) ). The point is, we've mapped a class of sets containing members from a countable set onto an uncountable set.)

It should also be clear now where the expression c = 20 comes from: Elementhood has two possible values; there are 2n sequences of n binary digits and thus 20 sequences of 0 digts, which we know yields c values due to our function.

But as stated earlier, the operation isn't a one-to-one corespondence. As it turns out, a large set of real numbers has exactly two sets of integers corresponding to it, resulting from the binary equivalent to 0.99999....=1.

Consider a finite set F of positive integers. Let MAX(F) be the largest integer in F. When we create a digit a string from F there are 1's and 0's up until the MAX(F)-th digit, which is a 1, and all succeeding digits are 0's. Let's define F's "evil twin" G = { i | (i > MAX(F)) v (i < MAX(F) & i ∈ F) }. That is, produce G from F by removing MAX(F) and adding all integers greater than MAX(F). When we create a digit string from G, we switch the last 1 in F to a 0 and all of the succeeding 0's into 1's. The trouble is, RE(F) = RE(G)! For example:

```
F = { 1, 3, 4, 5, 7, 8 }
G = { 1, 3, 4, 5, 7, 9, 10, 11, 12, 13, ... }

```

If we construct a binary digit string from F we get 0.10111011000... If we construct a binary string from G we get 0.10111010111... But these both sum to 0.73046875! The numbers that result from finite sets and their evil twins are known as dyadic rationals, and we need to handle them carefully.

This isn't much of a problem, for the function is surjective, and lurking within every surjection is a bijection waiting to get out***. In our case, we simply ignore all finite sets and keep their "evil twin"s to represent the dyadic rationals. The resulting function, between the set of all infinite sets of integers and all reals, is a one-to-one correspondence, albeit not a continuous one. Waving away a dense countable set would probably give Kronecker something to fulminate about, but we'd have lost him anyway since we're fooling around with infinite sets.

Our adjustment of the function's domain has a fortunate side effect, helping to optimize Turing machines for their original purpose, distinguishing computable numbers from uncomputable numbers. The finite sets of integers can be put into a one-to-one correposndence with the halting sequences produced by Turing machines with two symbols. Since each dyadic rational can also be represented by an "evil twin" sequence (which is non-halting), and there is a simple Turing machine for every such sequence, computable numbers are still computable even if we ignore all of the halting machines! (Other computable numbers are unaffected since they are represented by non-halting machines.)

***This statement is made solely for the purposes of humor! It is equivalent to the Axiom of Choice, but not necessary for constructing this one-to-one-correspondence. See this for an explanation.