On 5 Mar 2009, at 15:23, Daniel Fischer wrote:
Just to flesh this up a bit:
let f : P(N) -> R be given by f(M) = sum [2*3^(-k) | k <- M ] f is easily seen to be injective.
define g : (0,1) -> P(N) by let x = sum [a_k*2^(-k) | k in N (\{0}), a_k in {0,1}, infinitely many a_k = 1] and then g(x) = {k | a_k = 1}
again clearly g is an injection. Now the Cantor-Bernstein theorem asserts there is a bijection between the two sets.
I think one just defines an equivalence relation of elements mapped to each other by a finite number of iterations of f o g and g o f. The equivalence classes are then at most countable. So one can set up a bijection on each equivalence class: easy for at most countable sets. Then paste it together. The axiom of choice probably implicit here. Hans Aberg