[Haskell-cafe] Re: Theory about uncurried functions

[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.

   Hans Aberg