Skip to main content

Chapter 4 Bijective Proof

Each problem below defines two finite sets, \(X\) and \(Y\text{.}\) Create a bijective proof to show that \(|X|=|Y|\text{.}\) You must define a bijection \(f : X \rightarrow Y\) between the two sets, and then either (1) show \(f\) is both injective and surjective, or (2) define a function \(g: Y \rightarrow X\) and show that \(f\) and \(g\) are inverse functions.

Exercises Practice Problems

1. Binary Words and Subsets.

For a given positive integer \(n\)

  • Let \(X\) be the collection of binary sequences \(x=x_1x_2 \cdots x_n\) of length \(n\) where each \(x_i \in \{0,1\}\text{.}\)

  • Let \(Y = {\mathcal{P}}([n])\) be the power set of \([n]\text{,}\) which is the set of all subsets of \([n]\text{.}\)

Solution.

Define the mapping \(f: X \rightarrow Y\) as follows. For a bit string \(x_1 x_2 \cdots x_n\) where each \(x_i \in \{ 0,1 \}\text{,}\) we define

\begin{equation*} f(x_1 x_2 \cdots x_n) = \{ k \mid x_k = 1 \}. \end{equation*}

This is a function that selects element \(k\) if and only if \(x_k=1\text{.}\)

  • Well defined. The output of function \(f\) is a subset of \([n]\text{.}\)

  • Injective. Let \(x = x_1 x_2 \cdots x_n\) and \(w = w_1 w_2 \cdots w_n\) be distinct binary words. This means that there is some \(k\) such that \(x_k \neq w_k\text{.}\) Without loss of generality, we can assume that \(x_k=0\) and \(w_k=1\text{.}\) Let \(A = f(x)\) and \(B = f(w)\text{.}\) Then \(k \notin A\) while \(k \in B\text{.}\) So \(A \neq B\text{.}\)

  • Surjective. Given a subset \(S \subset [ n]\text{,}\) define the word \(x=x_1 x_2 \cdots x_n\) where \(x_k = 1\) if and only if \(k \in S\text{.}\) Then \(f(x)=S\text{.}\)

Instead of proving injective and surjective, we can show that \(f\) is invertible by defining its inverse function. Here is what that would look like. Define \(g: Y \rightarrow X\) as

\begin{equation*} g(S) = x_1 x_2 \cdots x_n \mbox{where} x_k = \left\{ \begin{array}{cc} 1 & \mbox{if } k \in S, \\ 0 & \mbox{if } k \notin S. \\ \end{array} \right. \end{equation*}

We have \(g \circ f(x) = x\) for every binary word \(x\text{,}\) and \(f \circ g(S) = S\) for every subset \(S\text{.}\)

2. \(k\)-sets and \((n-k)\)-sets.

For given positive integers \(0 \leq k \leq n\text{,}\)

  • Let \(X\) be the collection of \(k\)-subsets of \([n]\text{,}\) and

  • Let \(Y\) be the collection of \((n-k)\)-subsets of \([n]\text{.}\)

(The \(k\)-subsets of \([n]\) are all the subsets of size \(k\)). Solution.

This time, we will create a function \(f: X \rightarrow Y\) and then show that it is well defined, injective and surjective. Consider the function

\begin{equation*} f(S) = \overline{S} \end{equation*}

that makes a \(k\)-set to its complement.

  • This function is well defined, since the complement of a \(k\)-set is an \((n-k)\)-set.

  • The function is one-to-one. Suppose that \(S \neq T\text{.}\) This means that either (1) there is an element \(k \in S\) such that \(k \notin T\text{,}\) or there is an element \(k \in T\) such that \(k \notin S\text{.}\) The names of the sets don't matter, so we'll assume the first case holds. It is clear that \(k \notin \overline{S} = f(S)\) and \(k \in \overline{T} = f(T)\text{.}\) Therefore \(f(S) \neq f(T)\text{.}\)

  • The function is onto. Consider any \((n-k)\)-set \(T\text{.}\) Then the set \(\overline{T}\) is a \(k\)-set, and \(f(\overline{T}) = T\text{.}\)

Alternatively, we can prove that \(f\) is invertible. In fact, the function \(f\) is its own inverse function!

\begin{equation*} f \circ f(S) = f(\overline{S}) =S. \end{equation*}

This proof is much faster than proving that \(f\) is bijective. But that's because we know a lot about set complements (and \(f\) is its own inverse!). There will be cases where proving injective and surjective is easier to explain than constructing an inverse function.

3. Lattice Paths and Subsets.

Let \(r,s\) be nonnegative integers.

  • Let \(X\) be the set of lattice paths from \((0,0)\) to \((r,s)\text{.}\) These paths start at \((0,0)\) and join integer points via steps of unit length, moving rightward or upward.

  • Let \(Y\) be the set of all \(r\)-subsets of \([r+s]\text{.}\)

Here is a lattice path from \((0,0)\) to \((6,4)\text{.}\)

Solution.

Let \(L\) be a lattice path from \((0,0)\) to \((r,s)\text{.}\) Define

\begin{equation*} f(L) = \{ k \mid \mbox{the } k\mbox{th step is a rightward step} \}. \end{equation*}

There are \(r\) such steps, \(f(L)\) is an \(r\)-set chosen from \([r+s]\text{.}\) The inverse of \(f\) is the function \(g: Y \rightarrow X\) which takes an \(r\)-set \(S\) to the lattice path \(L\) whose rightward steps occur at the indices contained in \(S\text{.}\) I leave the details to you.

4. Even Subsets and Odd Subsets.

For any positive integer \(n\text{,}\) we can partition the power set \(\cP([n])\) into two sets: the set \(\cE_n\) of even-sized subsets and the set \(\cO_n\) of odd-sized subsets.

In this problem, you will show that \(| \cE_n | = | \cO_n | \) via a bijective proof. Since \(| \cP([n])| = 2^n\text{,}\) this means that \(| \cE_n | = | \cO_n | = 2^{n-1}\text{.}\)

  1. We start with a proof that only works when \(n=2k+1\) is odd.

    1. List all the subsets of \([3]\text{.}\) Solution.

      \begin{equation*} \emptyset, \{1 \}, \{2\}, \{ 3 \}, \{1, 2\} , \{ 1,3 \} , \{2,3\}, \{1,2,3 \} \end{equation*}

    2. Pair each set with its complement. What do you notice? Solution.

      \begin{equation*} \emptyset, \{ 1,2, 3\} \qquad \{1 \} , \{2,3\} \qquad \{2 \} , \{1,3\} \qquad \{3 \} , \{1,2\} \end{equation*}

      Every odd set pairs with an even set.

    3. Now give a bijective proof that when \(n\) is odd, \(| \cE_n | = | \cO_n | \text{.}\) Solution.

      Consider the mapping \(f: \cE_n \rightarrow \cO_n\) given by \(f(S) = \overline{S}\text{.}\)

      When \(n\) is odd, an even set of size \(2\ell\) maps to a set of size \(2(k -\ell) + 1\text{,}\) which is an odd set. So the function is well defined. This function is invertible: just take the complement again.

  2. Now we consider the case where \(n\) is even.

    1. List all the subsets of \([4]\text{.}\) Solution.

      \begin{equation*} \begin{array}{c} \emptyset, \{1 \}, \{2\}, \{ 3 \}, \{ 4 \}, \{1, 2\} , \{ 1,3 \} , \{1,4\}, \\ \{2,3\}, \{2,4\}, \{3,4\}, \{1,2,3 \}, \{1,2,4 \}, , \{1,3,4 \}, \{2,3,4 \}, \{ 1,2,3,4\} \end{array} \end{equation*}

    2. Pair each set with its complement. Why doesn't this lead to a proof of the result? Solution.

      \begin{equation*} \begin{array}{c} \emptyset, \{1 ,2, 3, 4\} \qquad \{1 \}, \{2,3,4 \} \qquad \{2\}, \{1,3,4 \} \qquad \{ 3 \}, \{1,2,4 \} \\ \{ 4 \}, \{1,2,3 \} \qquad \{1, 2\} , \{ 3,4 \} \qquad \{1,3\}, \{2,4\} \qquad \{ 1, 4 \} , \{ 2, 3 \} \\ \end{array} \end{equation*}

      This time, sets are paired with another set of the same parity (even, even) or (odd, odd)

  3. We now give a bijective proof that works for both even and odd \(n\text{.}\) Consider the following mapping \(f : \cE_n \rightarrow \cO_n\text{.}\) For \(S \in \cP([n])\text{,}\) we define

    \begin{equation*} f(S) = \left\{ \begin{array}{cl} S \backslash \{ 1 \} & \mbox{if } 1 \in S, \\ S \cup \{ 1 \} & \mbox{if } 1 \notin S. \end{array} \right. \end{equation*}

    1. Explain why \(f: \cE_n \rightarrow \cO_n\) is well defined, meaning that an even set is always mapped to an odd set. Solution.

      We start with an even set. We either add one element or remove one element. The resulting set is odd. So this function really does map an element of \(\cE_n\) to an element of \(\cO_n\text{.}\)

    2. Now prove that \(f\) is a bijection. Solution.

      The inverse function \(g: \cO_n \rightarrow \cE_n\) is defined in the same way: we either add or remove the element 1. It is straight-forward to see that \(g \circ f = I_{\cE_n}\) and that \(f \circ g = I_{\cO_n}\text{.}\)