Prove that a function is not surjective Let $A$ be any (possibly infinite) set. Argue by contradiction to show that there is no surjection from $A \to \{0,1\}^A$ 
By contradiction I'm assuming that for every element $b \in \{0,1\}^A$, there exists at least one element $a$ in $A$ such that $f(a)=b$. But how can I now claim that $f$ is not surjective? 
 A: Hint: you can think of elements of $\{0, 1\}^A$ as subsets of $A$, so $f$ sends each element of $A$ to a set of elements from $A$.
So before worrying too much about surjectivity, you can ponder more 'natural' questions like:
'Wouldn't it be cute if every $a$ is an element of its "own" set $f(a)$?'
'Is this even possible?'
'What about $f$s where NO $a$ is an element of $f(a)$.'
'Ok, now that I cannot choose $f$ myself, but are given one by the assumption, it seems that we are facing a situation where some $a$'s are elements of their own $f(a)$ and others are not. Can we tell the two types of elements of A apart?'
'What would the set of all $a \in A$ with one of these two properties look like?'
Etc, etc, etc. At some point you will have enough feeling for the situation to derive the desired contradiction.
A: Notice that $\left\{0,1\right\}^A\cong \mathcal{P}(A)$. Indeed, given a subset of $A$, you can consider the sequence $(s_a)_{a\in A}$ such that $s_a=1$ if and only if $a\in A$. Conversely each such sequence determines a subset of $A$.
So your question reduces to is there a surjection from $A$ to $\mathcal{P}(A)$, which is impossible. 
In case you wonder why the latter statement is true: Suppose $f:A\rightarrow\mathcal{P}(A)$ is a function. Define $B=\left\{a\in A\mid a\notin f(a)\right\}$. Clearly $B\in \mathcal{P}(A)$. Now you can easily show that there is no $a$ such that $f(a)=B$ by considering two cases: $a\in B$ and $a\notin B$.
A: Suppose $f\colon A\to \{0,1\}^A$ is a map. Consider $\varphi\colon A\to\{0,1\}$ defined by
$$
\varphi(x)=\begin{cases}
0 & \text{if $f(x)(x)=1$} \\[4px]
1 & \text{if $f(x)(x)=0$}
\end{cases}
$$
Note that $f(x)$ is a map $A\to\{0,1\}$, which we can evaluate at $x$.
In particular, for every $x\in A$, $\varphi(x)\ne f(x)(x)$, so there exists no $x\in A$ with $f(x)=\varphi$. Therefore $f$ is not surjective.
