properties of bijections
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=\mathrm{\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
$$h(x)=\{\begin{array}{cc}f(x)\hspace{1em}\text{if}x\in A,\hfill & \\ g(x)\hspace{1em}\text{if}x\in C.\hfill & \end{array}$$ Since $A\cap C=\mathrm{\varnothing}$, $h$ is a welldefined function. $h$ is onto since both $f$ and $g$ are. Since $f,g$ are onetoone, and $B\cap D=\mathrm{\varnothing}$, $h$ is also onetoone. ∎

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 $\varphi :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 {\varphi}^{1}:B\to D$. $F$ is a welldefined function. It is onetoone because $\sigma $ and $\varphi $ are bijections (hence are cancellable). For any $g:B\to D$, it is easy to see that $F({\sigma}^{1}\circ g\circ \varphi )=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 $\mathrm{Mono}(A,B)\sim \mathrm{Mono}(C,D)$, $\mathrm{Epi}(A,B)\sim \mathrm{Epi}(C,D)$, and $\mathrm{Iso}(A,B)\sim \mathrm{Iso}(C,D)$, where $\mathrm{Mono}(A,B)$, $\mathrm{Epi}(A,B)$, and $\mathrm{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=\{0,1\}$.
Proof.
For every $B\subseteq A$, define ${\phi}_{B}:A\to 2$ by
$${\phi}_{B}(x)=\{\begin{array}{cc}1\hspace{1em}\text{if}x\in B,\hfill & \\ 0\hspace{1em}\text{otherwise}.\hfill & \end{array}$$ Then $\phi :P(A)\to {2}^{A}$, defined by $\phi (B)={\phi}_{B}$ is a welldefined function. It is onetoone: if ${\phi}_{B}={\phi}_{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=\{x\in A\mid f(x)=1\}$, we see that ${\phi}_{B}=f$. As a result, $\phi $ is a bijection. ∎
Remark. As a result of property 9, we sometimes denote ${2}^{A}$ the powerset of $A$.
Title  properties of bijections 

Canonical name  PropertiesOfBijections 
Date of creation  20130322 18:50:41 
Last modified on  20130322 18:50:41 
Owner  CWoo (3771) 
Last modified by  CWoo (3771) 
Numerical id  6 
Author  CWoo (3771) 
Entry type  Derivation 
Classification  msc 0300 