[Haskell-cafe] Re: Theory about uncurried functions
Hans Aberg
haberg at math.su.se
Thu Mar 5 10:55:30 EST 2009
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
More information about the Haskell-Cafe
mailing list