- #1
cragar
- 2,552
- 3
Homework Statement
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 [itex] a \in A [/itex] 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 [itex] a \in A [/itex] To arrive at a contradiction, we will produce
a subset [itex] B \subseteq A [/itex] that is not equal to f(a) for
any [itex] a \in A [/itex]
[itex] B=\{a\in A:a\notin f(a)\} [/itex]
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.
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: