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
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
