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 well-defined function. $h$ is onto since both $f$ and $g$ are. Since $f,g$ are one-to-one, and $B\cap D=\mathrm{\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 $\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 well-defined function. It is one-to-one 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 well-defined function. It is one-to-one: 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	2013-03-22 18:50:41
Last modified on	2013-03-22 18:50:41
Owner	CWoo (3771)
Last modified by	CWoo (3771)
Numerical id	6
Author	CWoo (3771)
Entry type	Derivation
Classification	msc 03-00