Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Show that: Let A be a set and let $P(A)$ be the set of all subsets of $A$. Then there is no surjection $f: A→P(A)$.

Here is what I thought:

if $A=\{a,b\}$ then it has only two elements where $P(A)=\{∅,\{a\},\{b\},\{a,b\}\}$ has 4 elements. Therefore $f:A→P(A)$ cannot be surjective. But I have some problems:

1) How is it possible that any $f$ function to take $\{a\}$ from set $A$ to $\{a,b\}$? Maybe because I am thinking mainly about functions with real values like $f(x)=2x$, I find it a little bit strange that a function to take an element of a set to another set which has more elements. Is it possible?

edit: Now I thought that if $f(x)$ is $\sqrt{x}$, then $f(4)=±2$ which means it took an element from a set to a set which has 2 elements. But still I find it kind of strange to denote $f(\{a\})=\{a,b,c,...\}$

2) How can I construct a explicit proof for this question?

Regards

share|improve this question

2 Answers 2

up vote 6 down vote accepted

Cantor's theorem states:

Suppose that $A$ is a set and $f\colon A\to\mathcal P(A)$ is any function, then $f$ is not surjective.

The proof is quite simple, and constructive!

Proof. Suppose that $f\colon A\to\mathcal P(A)$ is a function, we define $D=\{a\in A\mid a\notin f(a)\}$. This is a good definition, since $f(a)$ is a subset of $A$, and $a$ is an element of $A$, we can ask whether or not $a\in f(a)$. So $D$ is the set of those elements of $A$ which do not have this property.

Of course that $D\in\mathcal P(A)$ since it is clearly a subset of $A$. We will show that $f(a)\neq D$ for all $a\in A$.

  1. If $a\in D$, then $a\notin f(a)$. So $f(a)\neq D$, since $a\in D$ and $a\notin f(a)$.
  2. If $a\notin D$ then $a\in f(a)$. By the same argument, again $f(a)\neq D$.

Either way, $D\neq f(a)$ for all $a\in A$. Therefore $f$ is not surjective. $\square$


Note that for different functions we have different $D$'s. It is possible that $D=A$ (e.g. if $f(a)=\varnothing$ for all $a$), or it could be $\varnothing$ (e.g. if $f(a)=\{a\}$ for all $a$). However regardless to its value it will not be in the range of $f$.

share|improve this answer

Look up Cantor's Theorem. There are several versions of this theorem. The basic version is to the effect that there is no bijection between a set $A$ and its power set $P(A)$. One of the proofs goes by showing there is no surjection from $A$ to $P(A)$. What one does is to assume there is, so that for each $a$ there is a subset $f(a)$ in the power set. Then one defines a set $B$ by saying that $x$ is in $B$ if and only if $x$ is NOT in the set $f(x)$. Now you ask: Is $x$ in $B$? If it is, it isn't, and if it isn't then it is... either way you get a contradiction!

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.