# 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. 1.

$A\sim A$. The identity function  is the bijection from $A$ to $A$.

2. 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. 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. 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

 $h(x)=\left\{\begin{array}[]{ll}f(x)\quad\mbox{ if }x\in A,\\ g(x)\quad\mbox{ if }x\in C.\end{array}\right.$

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. 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. 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. 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. 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. 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 $\varphi_{B}:A\to 2$ by

 $\varphi_{B}(x)=\left\{\begin{array}[]{ll}1\quad\mbox{ if }x\in B,\\ 0\quad\mbox{ otherwise}.\end{array}\right.$

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=\{x\in A\mid f(x)=1\}$, 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$.

Title properties of bijections PropertiesOfBijections 2013-03-22 18:50:41 2013-03-22 18:50:41 CWoo (3771) CWoo (3771) 6 CWoo (3771) Derivation msc 03-00