1. Mar 7, 2012

### cragar

Im trying to understand this proof by Cantor.
For every set $X, |X|<|P(x)|$
Proof. Let f be a function from X into P(x)
the set $Y=(x \in X: x \notin f(x) )$
is not in the range of f:
if $z \in X$ where such that f(z)=Y, then $z \in Y$
if and only if $z \notin Y$, a contradiction. Thus f is not
a function of X onto P(x).
Hence |P(x)|≠|X|, the function
f(x)={x} is a one-to-one function of X into P(x) and so
|X|≤|P(x)|. it follows that
|X|<|P(x)|.
I dont understand why z cant be in Y and f(z).
I guess thats because they defined it that way.
Is it because we want to find a one-to-one function from
the set to the power set, and because we want it to be one-to-one
we want to map every x to a unique element in the power set we don't want x to get mapped to itself. Is that the reason. And do we need z to be in Y and f(z) for it to be onto.

2. Mar 7, 2012

### tiny-tim

yes
but x can't get mapped to itself … x and f(x) are in different spaces

3. Mar 7, 2012

### cragar

so if x got mapped to itself, it wouldn't be onto.

4. Mar 7, 2012

### micromass

We CAN'T map x to itself. Since x is not an element of P(X).

5. Mar 7, 2012

### Number Nine

The element x is not in P(X).
P(X) contains the set containing x (that is, it contains {x}), but it does not contain x itself. Remember that the power is the set of subsets of X.

6. Mar 7, 2012

### cragar

this might be a dumb question, but maybe we didn't do a very good job of defining our funtion from the set to the powerset. why cant x be in P(x)

7. Mar 7, 2012

### Number Nine

The elements of P(X) are subsets, not elements, of X. P(X) contains {x}, but not x itself.

8. Mar 7, 2012

### micromass

A simple example will help you. Take X={1,2,3}, then P(X)=\{∅,{1},{2},{3},{1,2},{2,3},{1,3},{1,2,3}}. As you see, 1 is not an element of P(X). But {1} is an element of P(X).

9. Mar 7, 2012

### cragar

ok thanks for the responses, it makes more sense now.