6.6: Bijections

The best functions are both one-to-one and onto. These are called “bijections.”

Definition \(6.6.1\).

A function is a bijection iff it is both one-to-one and onto.

Example \(6.6.2\).

Consider a hypothetical country \(\text {Married}\), in which

• everyone is married (to only one person — there is no polygamy!), and
• every marriage is between a man and a woman (there are no same-sex marriages).

Let

• \(\text {Men}\) be the set of men in the country, and
• \(\text {Women}\) be the set of women in the country.

Then \(\text {wife}: \text { Men } \rightarrow \text { Women}\) is a bijection:

• Two different men cannot have the same wife, so we know that \(\text {wife}\) is one-to-one.
• Every woman is the wife of some man (because everyone is married), so \(\text {wife}\) is also onto.

Similarly, the function \(\text {husband}: \text { Women } \rightarrow \text { Men}\) is also a bijection.

Remark \(6.6.3\).

In the country \(\text {Married}\) described above, it is clear that the number of men is exactly equal to the number of women. (If there were more men than women, then not every man could have a wife; if there were more women than men, then not every women could have a husband.) This is an example of the following important principle that will be discussed in the later chapter on “cardinality”:

If there is a bijection from \(A\) to \(B\), then
the two sets \(A\) and \(B\) must have exactly the same number of elements.

Finding a bijection is the most common way to show two sets have the same number of elements.

Remarks \(6.6.4\).

1. You may recall that a one-to-one function can be called an “injection,” and an onto function can be called a “surjection.” The term “bijection” comes from having both of these two properties.
2. Some textbooks use the term “one-to-one correspondence” for a bijection, but we will avoid that terminology, because it is too easy to confuse with “one-to-one function,” which does not mean the same thing.

Remarks \(6.6.5\).

Showing that a function is a bijection requires two things: showing that the function is one-to-one, and showing that the function is onto. So a proof that a function is a bijection will (usually) have two parts:

1. Show that the function is one-to-one.
2. Show that the function is onto.

The two parts can come in either order: it is perfectly acceptable to first prove that the function is onto, and then prove that it is one-to-one.

Example \(6.6.6\).

Define \(f: \mathbb{R} \rightarrow \mathbb{R}\) by \(f(x) = 5x − 7\). Then \(f\) is a bijection.

Solution

It suffices to show that \(f\) is both one-to-one and onto.

(one-to-one) Given \(x_{1}, x_{2} \in \mathbb{R}\), such that \(f\left(x_{1}\right)=f\left(x_{2}\right)\), we have \[5 x_{1}+7=5 x_{2}+7 ,\]
so \[5 x_{1}=5 x_{2} ,\]
so \[x_{1}=x_{2} .\]
Therefore \(f\) is one-to-one.

(onto) Given \(y \in \mathbb{R}\), let \(x=(y+7) / 5\). Then \[f(x)=5 x-7=5\left(\frac{y+7}{5}\right)-7=(y+7)-7=y .\]
Therefore \(f\) is onto.

Since \(f\) is both one-to-one and onto, it is a bijection.

Exercise \(6.6.7\).

Each formula defines a function from \(\mathbb{R}\) to \(\mathbb{R}\). Show that the function is a bijection.

1. \(a(x) = 5x + 2\)
2. \(b(x) = 2x − 5\)
3. \(c(x) = 12x − 15\)
4. \(d(x) = −15x − 12\)
5. \(e(x) = x^{3}\)
6. \(f(x)=\sqrt[3]{x-4}\)

Notation \(6.6.8\).

For any set \(A\), define the identity map \(I_{A}: A \rightarrow A\) by \(I_{A}(a) = a\) for every \(a \in A\).

Exercise \(6.6.9\).

Let \(A\) be a set. Show that the identity map \(I_{A}\) is a bijection from \(A\) to \(A\).

Exercise \(\PageIndex{1}\)

Each formula defines a function from \(\mathbb{R}\) to \(\mathbb{R}\). Which of the functions are bijections? Show that your answers are correct.

1. \(a(x) = 7.\)
2. \(b(x) = 4x − 7.\)
3. \(c(x) = x^{2}.\)
4. \(d(r) = 3r + 2.\)
5. \(e(s) = 3|s| + 2.\)
6. \(f(t)=\sqrt{t^{2}+1}\)
7. \(g(u)=\sqrt[3]{u}-5 .\)

Example \(6.6.11\).

Define \(f : \mathbb{N} \times \mathbb{N} \rightarrow \mathbb{N}\) by \(f(m, n) = m^{2} + n\).

1. Show that \(f\) is onto.
2. Show that \(f\) is not one-to-one.

Solution

1. Given \(k \in \mathbb{N}\), let \(x = (0, k) \in \mathbb{N} \times \mathbb{N}\). Then \[f(x)=f(0, k)=0^{2}+k=k.\]
   Since \(k\) is an arbitrary element of \(\mathbb{N}\), we conclude that \(f\) is onto.
2. Let \(x_{1} = (1, 0)\) and \(x_{2} = (0, 1)\). Then \(x_{1} \neq x_{2}\), but \[f\left(x_{1}\right)=f(1,0)=1^{2}+0=1=0^{2}+1=f(0,1)=f\left(x_{2}\right) ,\]
   so \(f\) is not one-to-one.

Exercise \(6.6.12\).

Define \(g: \mathbb{Z} \times \mathbb{Z} \rightarrow \mathbb{Z} \times \mathbb{Z}\) by \(g(m, n) = (m + n, m − n)\).

1. Show that \(g\) is not onto. [Hint: \((m + n) + (m − n) = 2m\). Can this be odd?]
2. Show that \(g\) is one-to-one.

Preposition \(6.6.13\).

Suppose \(f: A \rightarrow B\). Show \(f\) is a bijection iff, for each \(b \in B\), there is a unique \(a \in A\), such that \(f(a) = b\). In other words, \(f\) is a bijection if and only if \[\forall b \in B, \exists ! a \in A,(f(a)=b) .\]

Proof

(\(\Rightarrow\)) Let \(b\) be an arbitrary element of \(B\). Since \(f\) is a bijection, it is onto, so there exists \(a \in A\), such that \(f(a) = b\). All that remains is to show that \(a\) is unique. To this end, let \(a^{\prime} \in A\), such that \(f(a^{\prime}) = b\). Then \[f\left(a^{\prime}\right)=b=f(a) .\]
Since \(f\) is a bijection, it is one-to-one, so we conclude that \(a^{\prime} = a\). Thus, \(a\) is unique.

(\(\Leftarrow\)) It suffices to show that \(f\) is both onto and one-to-one.
(onto) Given \(b \in B\), we are assuming that there is a (unique) element \(a\) of \(A\), such that \(f(a) = b\). Therefore \(f\) is onto.

(one-to-one) Given \(a_{1}, a_{2} \in A\), such that \(f(a_{1}) = f(a_{2})\), let \(b = f(a_{1})\). Then \(f(a_{1}) = b\) and \(f(a_{2}) = b\). From the uniqueness of the element \(a\) of \(A\), such that \(f(a) = b\), we conclude that \(a_{1} = a_{2}\). Since \(a_{1}\) and \(a_{2}\) are arbitrary elements of \(A\), such that \(f(a_{1}) = f(a_{2})\), this implies that \(f\) is one-to-one.

Remark \(6.6.14\).

Officially, \(\times\) is not associative, because \[(A \times B) \times C=\{((a, b), c) \mid a \in A, b \in B, c \in C\}\]
and \[A \times(B \times C)=\{(a,(b, c)) \mid a \in A, b \in B, c \in C\} .\]
are (usually) not the same sets: an element of \((A \times B) \times C\) must have an ordered pair \((a, b)\) as its first coordinate, whereas an element of \(A \times(B \times C)\) can have any element of \(A\) as its first coordinate.

Exercise \(6.6.15\).

Suppose \(A\), \(B\), and \(C\) are sets. Define \[f:(A \times B) \times C \rightarrow A \times(B \times C) \quad \text { by } \quad f((a, b), c)=(a,(b, c)) .\]

Show that \(f\) is a bijection.

Remark \(6.6.16\).

One can define the Cartesian product of more than two sets. For example, \[A \times B \times C=\{(a, b, c) \mid a \in A, b \in B, c \in C\} .\]
Although \(A \times B \times C\) is not the same as \((A \times B) \times C\) or \(A \times(B \times C)\), the difference between them can often be ignored in practice.