## You are here

Homeproperties of bijections

## Primary tabs

# 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=\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. 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=\{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$.

## Mathematics Subject Classification

03-00*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections