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