Let $E$ a set and $f:E\rightarrow P(E)$ any function. If $$A=\{a\in E:a\notin f(a)\}$$ Prove that $A$ has no preimage under $f$.
Asked
Active
Viewed 174 times
2
-
Try the proof by contradiction but I do not quite understand what the set A – Roiner Segura Cubero Mar 17 '13 at 03:16
-
1This gives a proof of Cantor's theorem: there exists no surjection $A\to P(A)$. – Pedro Mar 17 '13 at 03:29
2 Answers
1
Assume there is $x \in E$ such that $f(x) = A$. Then either $x \in f(x) = A$, but then $x \notin A$, or $x \notin f(x) = A$, but then $x \in A$. So you get a contradiction.
beauby
- 753
1
Suppose $\exists a\in E$, $f(a)=A$. Then, is $a\in f(a)$?
If $a\in f(a)$, that means $a\notin A$, contradicts to $f\in f(a)=A$.
If $a\notin f(a)$, that means $a\in A$.
Thus, such $a$ does not exists i.e. $f(a)$ has no preimage.
NECing
- 4,095