Re: CANTOR's theorem

In article <1116420225.347414.260910@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
mueckenh@xxxxxxxxxxxxxxxxx wrote:

> It is a matter of taste, it seems. Therefore let us avoid the whole
> problem. Map N --> P(N)\T_f. If you can prove that this mapping is not
> surjective, we now that N --> P(N) is not surjective either. If you
> cannot prove non-surjectivity, then there is no valid proof of
> non-surjectivity for N --> P(N), (and we can assume that it is
> surjective, because such a great mathematician never fails).
>
> Is this a fair trade?
>
> PS: Best would be, however, you could prove non-surjectivity of N -->
> P(N)\N.
>
> Regards, WM

Notationally, A\B usually means set difference, the set of elements that
are members of set A but not members of set B, so your notations should
properly be P(N)\{T_f} or P(N)\{N}

For any given f:N -> P(N), let T_f = {n e N : n ~e f(n)}
where N = {1,2,3,...} is the set of (positive) naturals

Since T_f is never in the image of f, we can always form the restricted
function f: N -> p(N) \ {T_f}, with no ambiguity about the meaning og f.

We can also construct g :(P(N) \ {T_f}) -> P(N) by
g(T_f) = f(1),
g(f(n)) = f(n+1) for each n e N,
g(s) = S otherwise.
This is clearly a surjection, and if f is a bijection, so is g.

Let h be the composite function h = gof defined by
h : N -> P(N) : n -> g(f(n)).

Clearly h is surjective if and only if f is surjective.

But T_h = {n e N : n ~e h(n)} is not in the image of h, so that h and f
are never surjective.

QED.

Given f: n -> P(N)/ {N}, a similar argument shows that mapping not
surjective.

QED.

And as I rate only patzer quality as a mathematician and can still so
quickly and easily prove it not surjective, we can conclude that it is
never surjective.
.

Quantcast