1. Dec 24, 2012

### cragar

1. The problem statement, all variables and given/known data
Given any set A, there does not exist a function f:A→P(A)
It wants us to do a proof by contradiction and assume there is an onto function.
For each element $a \in A$ f(a) is a particular subset
of A. The assumption that f is onto means that every subset of A appears as f(a)
for some $a \in A$ To arrive at a contradiction, we will produce
a subset $B \subseteq A$ that is not equal to f(a) for
any $a \in A$
$B=\{a\in A:a\notin f(a)\}$
If f is onto then it must be the case that B=f(a') for some a' in A.
the contradiction arises when we consider if a' is an element of B.
First show that the case that a' is in B leads to a contradiction.
Now finish the argument by showing that the case a' is not in B
is equally unacceptable.
3. The attempt at a solution
If a' is in B then a' is in A
and if f is onto then f(a') is in B
if f(a') is in B then f(a') is some a
in A but this is a contradiction
because we assumed that a was not in f(a).
If a' is not in B then it is not in A and therefore
it is not in anything.
Am I headed the right direction?

Last edited: Dec 24, 2012
2. Dec 24, 2012

### pasmith

This is somewhat confused.

Given $f$, $B$ consists of exactly those elements $a \in A$ which are not members of their image, $f(a) \subset A$. However there could be other elements of A which are members of their image.

The point is that if $f$ is onto, then by definition $B \subset A$ must be the image of some $a' \in A$, so that $f(a') = B$. Note that, by assumption, $a' \in A$. Whether $a' \in B$ is another question.

So what happens if $a' \in B$? That would mean that $a'$ is not a member of its image. But its image is B. This is a contradiction.

Now you need to show that a similar contradiction arises if you assume $a' \notin B$.

3. Dec 24, 2012

### cragar

is image f(a)=a

4. Dec 24, 2012

### haruspex

a' was chosen to be in A.
a' was chosen such that f(a')=B. It cannot be "in B".
a is an element of A; f(a) is a subset of A. They cannot be equal.
Start again at "If a' is in B then " and use the definition of B to deduce something about a'.