Am Donnerstag, 5. März 2009 16:55 schrieb Hans Aberg:
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.
Cantor-Bernstein doesn't require choice (may be different for intuitionists). http://en.wikipedia.org/wiki/Cantor-Bernstein_theorem
Hans Aberg
Cheers, Daniel