Let $A,B,C,D$ be sets. We write $A\sim B$ when there is a bijection from $A$ to $B$ . Below are some properties of bijections.

1. $A\sim A$ . The identity function is the bijection from $A$ to $A$ .
2. If $A\sim B$ , then $B\sim A$ . If $f:A\to B$ is a bijection, then its inverse function $f^{-1}:B\to A$ is also a bijection.
3. If $A\sim B$ , $B\sim C$ , then $A\sim C$ . If $f:A\to B$ and $g:B\to C$ are bijections, so is the composition $g\circ f:A\to C$ .
4. If $A\sim B$ , $C\sim D$ , and $A\cap C=B\cap D=\varnothing$ , then $A\cup B\sim C\cup D$ .
   Proof. If $f:A\to B$ and $g:C\to D$ are bijections, so is $h:A\cup C\to B\cup D$ , defined by

   

   Since $A\cap C=\varnothing$ , $h$ is a well-defined function. $h$ is onto since both $f$ and $g$ are. Since $f,g$ are one-to-one, and $B\cap D=\varnothing$ , $h$ is also one-to-one.
5. If $A\sim B$ , $C\sim D$ , then $A\times C\sim B\times D$ . If $f:A\to B$ and $g:C\to D$ are bijections, so is $h:A\times C\to B\times D$ , given by $h(x,y)=(f(x),g(y))$ .
6. $A\times B\sim B\times A$ . The function $f:A\times B\to B\times A$ given by $f(x,y)=(y,x)$ is a bijection.
7. If $A\sim B$ and $C\sim D$ , then $A^C\sim B^D$ .
   Proof. Suppose $\phi:A\to B$ and $\sigma:C\to D$ are bijections. Define $F:A^C\to B^D$ as follows: for any function $f:A\to C$ , let $F(f)= \sigma \circ f \circ \phi^{-1}: B\to D$ . $F$ is a well-defined function. It is one-to-one because $\sigma$ and $\phi$ are bijections (hence are cancellable). For any $g:B\to D$ , it is easy to see that $F(\sigma^{-1} \circ g \circ \phi)=g$ , so that $F$ is onto. Therefore $F$ is a bijection from $A^C$ to $B^D$ .
8. Continuing from property 8, using the bijection $F$ , we have $\operatorname{Mono}(A,B)\sim \operatorname{Mono}(C,D)$ , $\operatorname{Epi}(A,B)\sim \operatorname{Epi}(C,D)$ , and $\operatorname{Iso}(A,B)\sim \operatorname{Iso}(C,D)$ , where $\operatorname{Mono}(A,B)$ , $\operatorname{Epi}(A,B)$ , and $\operatorname{Iso}(A,B)$ are the sets of injections, surjections, and bijections from $A$ to $B$ .
9. $P(A)\sim 2^A$ , where $P(A)$ is the powerset of $A$ , and $2^A$ is the set of all functions from $A$ to $2=\lbrace 0,1\rbrace$ .
   Proof. For every $B\subseteq A$ , define $\varphi_B:A \to 2$ by

   

   Then $\varphi: P(A)\to 2^A$ , defined by $\varphi(B)=\varphi_B$ is a well-defined function. It is one-to-one: if $\varphi_B=\varphi_C$ for $B,C\subseteq A$ , then $x\in B$ iff $x\in C$ , so $B=C$ . It is onto: suppose $f:A\to 2$ , then by setting $B=\lbrace x\in A\mid f(x)=1\rbrace$ , we see that $\varphi_B=f$ . As a result, $\varphi$ is a bijection.

Remark. As a result of property 9, we sometimes denote $2^A$ the powerset of $A$ .