Section 9.1 Finite Sets
Beginning Activity Beginning Activity 1: Equivalent Sets, Part 1
1.
Let \(A\) and \(B\) be sets and let \(f\) be a function from \(A\) to \(B\text{.}\) \(\left(f:A \to B \right)\text{.}\) Carefully complete each of the following using appropriate quantifiers: (If necessary, review the material in Section 6.3.)
(a)
The function \(f\) is an injection provided that \(\ldots \text{.}\)
(b)
The function \(f\) is not an injection provided that \(\ldots \text{.}\)
(c)
The function \(f\) is a surjection provided that \(\ldots \text{.}\)
(d)
The function \(f\) is not a surjection provided that \(\ldots \text{.}\)
(e)
The function \(f\) is a bijection provided that \(\ldots \text{.}\)
Definition.
Let \(A\) and \(B\) be sets. The set \(A\) is equivalent to the set \(B\) provided that there exists a bijection from the set \(A\) onto the set \(B\text{.}\) In this case, we write \(A \approx B\text{.}\) When \(A \approx B\text{,}\) we also say that the set \(A\) is in one-to-one correspondence with the set \(B\) and that the set \(A\) has the same cardinality as the set \(B\text{.}\)
Note: When \(A\) is not equivalent to \(B\text{,}\) we write \(A \not \approx B\text{.}\)
2.
For each of the following, use the definition of equivalent sets to determine if the first set is equivalent to the second set.
(a)
\(A = \left\{ 1, 2, 3 \right\}\) and \(B = \left\{ a, b, c \right\}\)
(b)
\(C = \left\{ 1, 2 \right\}\) and \(B = \left\{ a, b, c \right\}\)
(c)
\(X = \left\{ 1, 2, 3, \ldots, 10 \right\}\) and \(Y = \left\{ 57, 58, 59, \ldots, 66 \right\}\)
3.
Let \(D^+\) be the set of all odd natural numbers. Prove that the function \(f\x \mathbb{N} \to D^+\) defined by \(f \left( x \right) = 2x - 1\text{,}\) for all \(x \in \mathbb{N}\text{,}\) is a bijection and hence that \(\mathbb{N} \approx D^+\text{.}\)
4.
Let \(\R^+\) be the set of all positive real numbers. Prove that the function \(g\x \R \to \R^+\) defined by \(g (x ) = e^x\text{,}\) for all \(x \in \R\) is a bijection and hence, that \(\R \approx \R^+\text{.}\)
Beginning Activity Beginning Activity 2: Equivalent Sets, Part 2
1.
Review Theorem 6.29 in Section 6.4, Theorem 6.36 in Section 6.5, and Exercise 9 in Section 6.5.
2.
Prove each part of the following theorem.
Theorem 9.1.
Let \(A\text{,}\) \(B\text{,}\) and \(C\) be sets.
For each set \(A\text{,}\) \(A \approx A\text{.}\)
For all sets \(A\) and \(B\text{,}\) if \(A \approx B\text{,}\) then \(B \approx A\text{.}\)
For all sets \(A\text{,}\) \(B\text{,}\) and \(C\text{,}\) if \(A \approx B\) and \(B \approx C\text{,}\) then \(A \approx C\text{.}\)
Subsection Equivalent Sets
In Beginning Activity 1, we introduced the concept of equivalent sets. The motivation for this definition was to have a formal method for determining whether or not two sets “have the same number of elements.” This idea was described in terms of a one-to-one correspondence (a bijection) from one set onto the other set. This idea may seem simple for finite sets, but as we will see, this idea has surprising consequences when we deal with infinite sets. (We will soon provide precise definitions for finite and infinite sets.)
Technical Note: The three properties we proved in Theorem 9.1 in Beginning Activity 2 are very similar to the concepts of reflexive, symmetric, and transitive relations. However, we do not consider equivalence of sets to be an equivalence relation on a set \(U\) since an equivalence relation requires an underlying (universal) set \(U\text{.}\) In this case, our elements would be the sets \(A\text{,}\) \(B\text{,}\) and \(C\text{,}\) and these would then have to be subsets of some universal set \(W\) (elements of the power set of \(W\)). For equivalence of sets, we are not requiring that the sets \(A\text{,}\) \(B\text{,}\) and \(C\) be subsets of the same universal set. So we do not use the term relation in regards to the equivalence of sets. However, if \(A\) and \(B\) are sets and \(A \approx B\text{,}\) then we often say that \(A\) and \(B\) are equivalent sets.
Progress Check 9.2. Examples of Equivalent Sets.
We will use the definition of equivalent sets from Beginning Activity 1 in all parts of this progress check. It is no longer sufficient to say that two sets are equivalent by simply saying that the two sets have the same number of elements.
(a)
Let \(A = \left\{ 1, 2, 3, \ldots, 99, 100 \right\}\) and let \(B = \left\{ 351, 352, 353, \ldots, 449, 450 \right\}\text{.}\) Define \(f\x A \to B\) by \(f(x) = x + 350\text{,}\) for each \(x\) in \(A\text{.}\) Prove that \(f\) is a bijection from the set \(A\) to the set \(B\) and hence, \(A \approx B\text{.}\)
We first prove that \(f\x A \to B\) is an injection. So let \(x, y \in A\) and assume that \(f(x) = f(y)\text{.}\) Then \(x + 350 = y + 350\) and we can conclude that \(x = y\text{.}\) Hence, \(f\) is an injection. To prove that \(f\) is a surjection, let \(b \in B\text{.}\) Then \(351 \leq b \leq 450\) and hence, \(1 \leq b - 350 \leq 100\) and so \(b - 350 \in A\text{.}\) In addition, \(f(b - 350) = (b - 350) + 350 = b\text{.}\) This proves that \(f\) is a surjection. Hence, the function \(f\) is a bijection, and so, \(A \approx B\text{.}\)
(b)
Let \(E\) be the set of all even integers and let \(D\) be the set of all odd integers. Prove that \(E \approx D\) by proving that \(F\x E \to D\text{,}\) where \(F \left( x \right) = x + 1\text{,}\) for all \(x \in E\text{,}\) is a bijection.
If \(x\) and \(t\) are even integers and \(F ( x ) = F ( t )\text{,}\) then \(x + 1 = t + 1\) and, hence, \(x = t\text{.}\) Therefore, \(F\) is an injection. To prove that \(F\) is a surjection, let \(y \in D\text{.}\) This means that \(y\) is an odd integer and, hence, \(y - 1\) is an even integer. In addition,
Therefore, \(F\) is a surjection and hence, \(F\) is a bijection. We conclude that \(E \approx D\text{.}\)
(c)
Let \(\left( 0, 1 \right)\) be the open interval of real numbers between 0 and 1. Similarly, if \(b \in \mathbb{R}\) with \(b > 0\text{,}\) let \(\left( 0, b \right)\) be the open interval of real numbers between 0 and \(b\text{.}\) Prove that the function \(f\x \left( 0, 1 \right) \to \left( 0, b \right)\) by \(f \left( x \right) = bx\text{,}\) for all \(x \in \left( 0, 1 \right)\text{,}\) is a bijection and hence \(\left( 0, 1 \right) \approx \left( 0, b \right)\text{.}\)
Let \(x, t \in ( 0, 1 )\) and assume that \(f ( x ) = f ( t )\text{.}\) Then \(bx = bt\) and, hence, \(x = t\text{.}\) Therefore, \(f\) is an injection. To prove that \(f\) is a surjection, let \(y \in ( 0, b )\text{.}\) Since \(0 \lt y \lt b\text{,}\) we conclude that \(0 \lt \dfrac{y}{b} \lt 1\) and that
Therefore, \(f\) is a surjection and hence \(f\) is a bijection. Thus, \(( 0, 1 ) \approx ( 0, b )\text{.}\)
In Task 9.2.c of Progress Check 9.2, notice that if \(b > 1\text{,}\) then \(\left( 0, 1 \right)\) is a proper subset of \(\left( 0, b \right)\) and \(\left( 0, 1 \right) \approx \left( 0, b \right)\text{.}\)
Also, in Exercise 3 of Beginning Activity 1, we proved that the set \(D\) of all odd natural numbers is equivalent to \(\mathbb{N}\text{,}\) and we know that \(D\) is a proper subset of \(\mathbb{N}\text{.}\)
These results may seem a bit strange, but they are logical consequences of the definition of equivalent sets. Although we have not defined the terms yet, we will see that one thing that will distinguish an infinite set from a finite set is that an infinite set can be equivalent to one of its proper subsets, whereas a finite set cannot be equivalent to one of its proper subsets.
Subsection Finite Sets
In Section 5.1, we defined the cardinality of a finite set \(A\text{,}\) denoted by \(\card (A)\text{,}\) to be the number of elements in the set \(A\text{.}\) Now that we know about functions and bijections, we can define this concept more formally and more rigorously. First, for each \(k \in \mathbb{N}\text{,}\) we define \(\mathbb{N}_k\) to be the set of all natural numbers between 1 and \(k\text{,}\) inclusive. That is,
We will use the concept of equivalent sets introduced in Beginning Activity 1 to define a finite set.
Definition.
A set \(A\) is a finite set provided that \(A = \emptyset\) or there exists a natural number \(k\) such that \(A \approx \mathbb{N}_k\text{.}\) A set is an infinite set provided that it is not a finite set.
If \(A \approx \mathbb{N}_k\text{,}\) we say that the set \(A\) has cardinality \(\boldsymbol{k}\) (or cardinal number \(\boldsymbol{k}\)), and we write \(\text{ card} \left( A \right) = k\text{.}\) In addition, we say that the empty set has cardinality 0 (or cardinal number 0), and we write \(\text{ card} \left( \emptyset \right) = 0\text{.}\)
Notice that by this definition, the empty set is a finite set. In addition, for each \(k \in \mathbb{N}\text{,}\) the identity function on \(\mathbb{N}_k\) is a bijection and hence, by definition, the set \(\mathbb{N}_k\) is a finite set with cardinality \(k\text{.}\)
Theorem 9.3.
Any set equivalent to a finite nonempty set \(A\) is a finite set and has the same cardinality as \(A\text{.}\)
Proof.
Suppose that \(A\) is a finite nonempty set, \(B\) is a set, and \(A \approx B\text{.}\) Since \(A\) is a finite set, there exists a \(k \in \mathbb{N}\) such that \(A \approx \mathbb{N}_k\text{.}\) We also have assumed that \(A \approx B\) and so by Item 2.b of Theorem 9.1 (in Beginning Activity 2), we can conclude that \(B \approx A\text{.}\) Since \(A \approx \mathbb{N}_k\text{,}\) we can use Item 2.c of Theorem 9.1 to conclude that \(B \approx \mathbb{N}_k\text{.}\) Thus, \(B\) is finite and has the same cardinality as \(A\text{.}\)
It may seem that we have done a lot of work to prove an “obvious” result in Theorem 9.3. The same may be true of the remaining results in this section, which give further results about finite sets. One of the goals is to make sure that the concept of cardinality for a finite set corresponds to our intuitive notion of the number of elements in the set. Another important goal is to lay the groundwork for a more rigorous and mathematical treatment of infinite sets than we have encountered before. Along the way, we will see the mathematical distinction between finite and infinite sets.
The following two lemmas will be used to prove the theorem that states that every subset of a finite set is finite.
Lemma 9.4.
If \(A\) is a finite set and \(x \notin A\text{,}\) then \(A \cup \left\{ x \right\}\) is a finite set and \(\text{ card} \!\left( A \cup \left\{ x \right\} \right) = \text{ card} ( A ) + 1\text{.}\)
Proof.
Let \(A\) be a finite set and assume \(\text{ card} ( A ) = k\text{,}\) where \(k = 0\) or \(k \in \mathbb{N}\text{.}\) Assume \(x \notin A\text{.}\)
If \(A = \emptyset\text{,}\) then \(\text{ card} ( A ) = 0\) and \(A \cup \left\{ x \right\} = \left\{ x \right\}\text{,}\) which is equivalent to \(\mathbb{N}_1\text{.}\) Thus, \(A \cup \left\{ x \right\}\) is finite with cardinality 1, which equals \(\text{ card} ( A ) + 1\text{.}\)
If \(A \ne \emptyset\text{,}\) then \(A \approx \mathbb{N}_k\text{,}\) for some \(k \in \mathbb{N}\text{.}\) This means that \(\text{ card} ( A ) = k\text{,}\) and there exists a bijection \(f\x A \to \mathbb{N}_k\text{.}\) We will now use this bijection to define a function \(g\x A \cup \left\{ x \right\} \to \mathbb{N}_{k+1}\) and then prove that the function \(g\) is a bijection. We define \(g\x A \cup \left\{ x \right\} \to \mathbb{N}_{k+1}\) as follows: For each \(t \in A \cup \left\{ x \right\}\text{,}\)
To prove that \(g\) is an injection, we let \(x_1, x_2 \in A \cup \left\{ x \right\}\) and assume \(x_1 \ne x_2\text{.}\)
If \(x_1, x_2 \in A\text{,}\) then since \(f\) is a bijection, \(f( x_1 ) \ne f ( x_2 )\text{,}\) and this implies that \(g( x_1 ) \ne g( x_2 )\text{.}\)
If \(x_1 = x\text{,}\) then since \(x_2 \ne x_1\text{,}\) we conclude that \(x_2 \ne x\) and hence \(x_2 \in A\text{.}\) So \(g( x_1 ) = k + 1\text{,}\) and since \(f( x_2 ) \in \mathbb{N}_k\) and \(g( x_2 ) = f ( x_2 )\text{,}\) we can conclude that \(g( x_1 ) \ne g( x_2 )\text{.}\)
The case where \(x_2 = x\) is handled similarly to the previous case.
This proves that the function \(g\) is an injection. The proof that \(g\) is a surjection is Exercise 1. Since \(g\) is a bijection, we conclude that \(A \cup \left\{ x \right\} \approx \mathbb{N}_{k+1}\text{,}\) and
Since \(\text{ card} \left(A \right) = k\text{,}\) we have proved that \(\text{ card} \!\left(A \cup \left\{ x \right\} \right) = \text{ card} ( A ) + 1\text{.}\)
Lemma 9.5.
For each natural number \(m\text{,}\) if \(A \subseteq \mathbb{N}_m\text{,}\) then \(A\) is a finite set and \(\text{ card} \left( A \right) \leq m\text{.}\)
Proof.
We will use a proof using induction on \(m\text{.}\) For each \(m \in \mathbb{N}\text{,}\) let \(P( m )\) be, “If \(A \subseteq \mathbb{N}_m\text{,}\) then \(A\) is finite and \(\text{ card} ( A ) \leq m\text{.}\)”
We first prove that \(P( 1 )\) is true. If \(A \subseteq \mathbb{N}_1\text{,}\) then \(A = \emptyset\) or \(A = \left\{ 1 \right\}\text{,}\) both of which are finite and have cardinality less than or equal to the cardinality of \(\mathbb{N}_1\text{.}\) This proves that \(P( 1 )\) is true.
For the inductive step, let \(k \in \mathbb{N}\) and assume that \(P( k )\) is true. That is, assume that if \(B \subseteq \mathbb{N}_k\text{,}\) then \(B\) is a finite set and \(\text{ card} ( B ) \leq k\text{.}\) We need to prove that \(P( k+1 )\) is true.
So assume that \(A\) is a subset of \(\mathbb{N}_{k+1}\text{.}\) Then \(A - \left\{ k+1 \right\}\) is a subset of \(\mathbb{N}_k\text{.}\) Since \(P( k )\) is true, \(A - \left\{ k+1 \right\}\) is a finite set and
There are two cases to consider: Either \(k+1 \in A\) or \(k+1 \not \in A\text{.}\)
If \(k+1 \not \in A\text{,}\) then \(A = A - \left\{ k+1 \right\}\text{.}\) Hence, \(A\) is finite and
If \(k+1 \in A\text{,}\) then \(A = ( A - \left\{ k+1 \right\} ) \cup \left\{ k+1 \right\}\text{.}\) Hence, by Lemma 9.4, \(A\) is a finite set and
Since \(\text{ card} \!\left( A - \left\{ k+1 \right\} \right) \leq k\text{,}\) we can conclude that \(\text{ card} ( A ) \leq k + 1\text{.}\)
This means that we have proved the inductive step. Hence, by mathematical induction, for each \(m \in \mathbb{N}\text{,}\) if \(A \subseteq \mathbb{N}_m\text{,}\) then \(A\) is finite and \(\text{ card} ( A ) \leq m\text{.}\)
The preceding two lemmas were proved to aid in the proof of the following theorem.
Theorem 9.6.
If \(S\) is a finite set and \(A\) is a subset of \(S\text{,}\) then \(A\) is a finite set and \(\text{ card} ( A ) \leq \text{ card} ( S )\text{.}\)
Proof.
Let \(S\) be a finite set and assume that \(A\) is a subset of \(S\text{.}\) If \(A = \emptyset\text{,}\) then \(A\) is a finite set and \(\text{ card} ( A ) \leq \text{ card} ( S )\text{.}\) So we assume that \(A \ne \emptyset\text{.}\)
Since \(S\) is finite, there exists a bijection \(f\x S \to \mathbb{N}_k\) for some \(k \in \mathbb{N}\text{.}\) In this case, \(\text{ card} ( S ) = k\text{.}\) We need to show that \(A\) is equivalent to a finite set. To do this, we define \(g\x A \to f ( A )\) by \(g ( x ) = f ( x )\) for each \(x \in A\text{.}\) Since \(f\) is an injection, we conclude that \(g\) is an injection. Now let \(y \in f ( A )\text{.}\) Then there exists an \(a \in A\) such that \(f ( a ) = y\text{.}\) But by the definition of \(g\text{,}\) this means that \(g ( a ) = y\text{,}\) and hence \(g\) is a surjection. This proves that \(g\) is a bijection.
Hence, we have proved that \(A \approx f ( A )\text{.}\) Since \(f ( A )\) is a subset of \(\mathbb{N}_k\text{,}\) we use Lemma 9.5 to conclude that \(f ( A )\) is finite and \(\text{ card} ( f ( A ) ) \leq k\text{.}\) In addition, by Theorem 9.3, \(A\) is a finite set and \(\text{ card} ( A ) = \text{ card} ( f ( A ) )\text{.}\) This proves that \(A\) is a finite set and \(\text{ card} ( A ) \leq \text{ card} ( S )\text{.}\)
Lemma 9.4 implies that adding one element to a finite set increases its cardinality by 1. It is also true that removing one element from a finite nonempty set reduces the cardinality by 1. The proof of Corollary 9.7 is Exercise 4.
Corollary 9.7.
If \(A\) is a finite set and \(x \in A\text{,}\) then \(A - \left\{ x \right\}\) is a finite set and \(\text{ card} \!\left( A - \left\{ x \right\} \right) = \text{ card} ( A ) - 1\text{.}\)
The next corollary will be used in the next section to provide a mathematical distinction between finite and infinite sets.
Corollary 9.8.
A finite set is not equivalent to any of its proper subsets.
Proof.
Let \(B\) be a finite set and assume that \(A\) is a proper subset of \(B\text{.}\) Since \(A\) is a proper subset of \(B\text{,}\) there exists an element \(x\) in \(B - A\text{.}\) This means that \(A\) is a subset of \(B - \left\{ x \right\}\text{.}\) Hence, by Theorem 9.6,
Also, by Corollary 9.7
Hence, we may conclude that \(\text{ card} ( A ) \leq \text{ card} ( B ) - 1\) and that
Theorem 9.3 implies that \(B \not \approx A\text{.}\) This proves that a finite set is not equivalent to any of its proper subsets.
Subsection The Pigeonhole Principle
The last property of finite sets that we will consider in this section is often called the Pigeonhole Principle. The “pigeonhole” version of this property says, “If \(m\) pigeons go into \(r\) pigeonholes and \(m > r\text{,}\) then at least one pigeonhole has more than one pigeon.”
In this situation, we can think of the set of pigeons as being equivalent to a set \(P\) with cardinality \(m\) and the set of pigeonholes as being equivalent to a set \(H\) with cardinality \(r\text{.}\) We can then define a function \(f\x P \to H\) that maps each pigeon to its pigeonhole. The Pigeonhole Principle states that this function is not an injection. (It is not one-to-one since there are at least two pigeons “mapped” to the same pigeonhole.)
Theorem 9.9. The Pigeonhole Principle.
Let \(A\) and \(B\) be finite sets. If \(\text{ card} ( A ) > \text{ card} ( B )\text{,}\) then any function \(f\x A \to B\) is not an injection.
Proof.
Let \(A\) and \(B\) be finite sets. We will prove the contrapositive of the theorem, which is, if there exists a function \(f\x A \to B\) that is an injection, then \(\text{ card} ( A ) \leq \text{ card} ( B )\text{.}\)
So assume that \(f\x A \to B\) is an injection. As in Theorem 9.6, we define a function \(g\x A \to f ( A )\) by \(g ( x ) = f ( x )\) for each \(x \in A\text{.}\) As we saw in Theorem 9.6, the function \(g\) is a bijection. But then \(A \approx f ( A )\) and \(f ( A ) \subseteq B\text{.}\) Hence, \(\text{ card} ( A ) = \text{ card} \!\left( f ( A ) \right)\) and \(\text{ card} \!\left( f ( A ) \right) \leq \text{ card} ( B )\text{.}\) Hence, \(\text{ card} ( A ) \leq \text{ card} ( B )\text{,}\) and this proves the contrapositive. Hence, if \(\text{ card} ( A ) > \text{ card} ( B )\text{,}\) then any function \(f\x A \to B\) is not an injection.
The Pigeonhole Principle has many applications in the branch of mathematics called “combinatorics.” Some of these will be explored in the exercises.
Exercises Exercises
1.
Prove that the function \(g: A \cup \left\{ x \right\} \to \N_{k+1}\) in Lemma 9.4 is a surjection.
2.
Let \(A\) be a subset of some universal set \(U\text{.}\) Prove that if \(x \in U\text{,}\) then \(A \times \left\{ x \right\} \approx A\text{.}\)
One way to do this is to prove that the following function is a bijection: \(f\x A \times \left\{ x \right\} \to A\) by \(f ( a, x ) = a\text{,}\) for all \(( a, x ) \in A \times \left\{ x \right\}\text{.}\)
3.
Let \(E^+\) be the set of all even natural numbers. Prove that \(\mathbb{N} \approx E^+\text{.}\)
One way to prove that \(\N \approx E^+\) is to find a bijection from \(\N\) to \(E^+\text{.}\) One possibility is \(f: \mathbb{N} \to E^+\) by \(f \left( n \right) = 2n\) for all \(n \in \mathbb{N}\text{.}\) (We must prove that this is a bijection.)
4.
Prove Corollary 9.7.
If \(A\) is a finite set and \(x \in A\text{,}\) then \(A - \left\{ x \right\}\) is a finite set and \(\text{ card} ( A - \left\{ x \right\} ) = \text{ card} ( A ) - 1\text{.}\)
One approach is to use the fact that \(A = \left( A - \left\{ x \right\} \right) \cup \left\{x \right\}\text{.}\)
Notice that \(A = ( A - \left\{ x \right\} ) \cup \left\{x \right\}\text{.}\) Use Theorem 9.6 to conclude that \(A - \left\{ x \right\}\) is finite. Then use Lemma 9.4.
5.
Let \(A\) and \(B\) be sets. Prove that
(a)
If \(A\) is a finite set, then \(A \cap B\) is a finite set.
Since \(A \cap B \subseteq A\text{,}\) if \(A\) is finite, then Theorem 9.6 implies that \(A \cap B\) is finite.
(b)
If \(A \cup B\) is a finite set, then \(A\) and \(B\) are finite sets.
The sets \(A\) and \(B\) are subsets of \(A \cup B\text{.}\) So if \(A \cup B\) is finite, then \(A\) and \(B\) are finite.
(c)
If \(A \cap B\) is an infinite set, then \(A\) is an infinite set.
(d)
If \(A\) is an infinite set or \(B\) is an infinite set, then \(A \cup B\) is an infinite set.
6.
There are over 7 million people living in New York City. It is also known that the maximum number of hairs on a human head is less than 200,000. Use the Pigeonhole Principle to prove that there are at least two people in the city of New York with the same number of hairs on their heads.
7.
Prove the following propositions:
(a)
If \(A\text{,}\) \(B\text{,}\) \(C\text{,}\) and \(D\) are sets with \(A \approx B\) and \(C \approx D\text{,}\) then \(A \times C \approx B \times D\text{.}\)
Since \(A \approx B\) and \(C \approx D\text{,}\) there exist bijections \(f:A \to B\) and \(g:C \to D\text{.}\) To prove that \(A \times C \approx B \times D\text{,}\) prove that \(h:A \times C \to B \times D\) is a bijection, where \(h ( a, c ) = \left( f ( a ), g ( c ) \right)\text{,}\) for all \(( a, c ) \in A \times C\text{.}\)
Remember that two ordered pairs are equal if and only if their corresponding coordinates are equal. So if \(\left( a_1, c_1 \right) , \left( a_2, c_2 \right) \in A \times C\) and \(h \left( a_1, c_1 \right) = h \left( a_2, c_2 \right)\text{,}\) then \(\left( f \left( a_1 \right), g \left( c_1 \right) \right) = \left( f \left( a_2 \right), g \left( c_2 \right) \right)\text{.}\) We can then conclude that \(f \left( a_1 \right) = f \left( a_2 \right)\) and \(g \left( c_1 \right) = g \left( c_2 \right)\text{.}\) Since \(f\) and \(g\) are both injections, this means that \(a_1 = a_2\) and \(c_1 = c_2\) and therefore, \(\left( a_1, c_1 \right) = \left( a_2, c_2 \right)\text{.}\) This proves that \(f\) is an injection. Now let \(\left( b, d \right) \in B \times D\text{.}\) Since \(f\) and \(g\) are surjections, there exists \(a \in A\) and \(c \in C\) such that \(f \left( a \right) = b\) and \(g \left( c \right) = d\text{.}\) Therefore, \(h \left( a, c \right) = \left( b, d \right)\text{.}\) This proves that \(f\) is a surjection.
(b)
If \(A\text{,}\) \(B\text{,}\) \(C\text{,}\) and \(D\) are sets with \(A \approx B\) and \(C \approx D\) and if \(A\) and \(C\) are disjoint and \(B\) and \(D\) are disjoint, then \(A \cup C \approx B \cup D\text{.}\)
8.
Let \(A = \left\{ a, b, c \right\}\text{.}\)
(a)
Construct a function \(f:\mathbb{N}_5 \to A\) such that \(f\) is a surjection.
If we define the function \(f\) by \(f ( 1 ) = a\text{,}\) \(f ( 2 ) = b\text{,}\) \(f ( 3 ) = c\text{,}\) \(f ( 4 ) = a\text{,}\) and \(f ( 5 ) = b\text{,}\) then we can use \(g ( a ) = 1\text{,}\) \(g ( b ) = 2\text{,}\) and \(g ( 3 ) = c\text{.}\) The function \(g\) is an injection.
(b)
Use the function \(f\) to construct a function \(g:A \to \mathbb{N}_5\) so that \(f \circ g = I_A\text{,}\) where \(I_A\) is the identity function on the set \(A\text{.}\) Is the function \(g\) an injection? Explain.
9.
This exercise is a generalization of Exercise 8. Let \(m\) be a natural number, let \(A\) be a set, and assume that \(f:\mathbb{N}_m \to A\) is a surjection. Define \(g:A \to \mathbb{N}_m\) as follows:
For each \(x \in A\text{,}\) \(g ( x ) = j\text{,}\) where \(j\) is the least natural number in \(f^{-1} ( \left\{ x \right\} )\text{.}\)Prove that \(f \circ g = I_A\text{,}\) where \(I_A\) is the identity function on the set \(A\text{,}\) and prove that \(g\) is an injection.
10.
Let \(B\) be a finite, nonempty set and assume that \(f:B \to A\) is a surjection. Prove that there exists a function \(h:A \to B\) such that \(f \circ h = I_A\) and \(h\) is an injection.
Since \(B\) is finite, there exists a natural number \(m\) such that \(\mathbb{N}_m \approx B\text{.}\) This means there exists a bijection \(k:\mathbb{N}_m \to B\text{.}\) Now let \(h = k \circ g\text{,}\) where \(g\) is the function constructed in Exercise 9.
Activity 50. Using the Pigeonhole Principle.
For this activity, we will consider subsets of \(\mathbb{N}_{30}\) that contain eight elements.
(a)
One such set is \(A = \left\{ 3, 5, 11, 17, 21, 24, 26, 29 \right\}\text{.}\) Notice that
Use this information to find two disjoint subsets of \(A\) whose elements have the same sum.
(b)
Let \(B = \left\{ 3, 6, 9, 12, 15, 18, 21, 24 \right\}\text{.}\) Find two disjoint subsets of \(B\) whose elements have the same sum.
Note: By convention, if \(T = \left\{ a \right\}\text{,}\) where \(a \in \mathbb{N}\text{,}\) then the sum of the elements in \(T\) is equal to \(a\text{.}\)
(c)
Now let \(C\) be any subset of \(\mathbb{N}_{30}\) that contains eight elements.
(i)
How many subsets does \(C\) have?
(ii)
The sum of the elements of the empty set is 0. What is the maximum sum for any subset of \(\mathbb{N}_{30}\) that contains eight elements? Let \(M\) be this maximum sum.
(iii)
Now define a function \(f\x \mathcal{P} ( C ) \to \mathbb{N}_M\) so that for each \(X \in \mathcal{P} ( C )\text{,}\) \(f ( X )\) is equal to the sum of the elements in \(X\text{.}\) Use the Pigeonhole Principle to prove that there exist two subsets of \(C\) whose elements have the same sum.
(d)
If the two subsets in Task 50.c.iii are not disjoint, use the idea presented in Task 50.a to prove that there exist two disjoint subsets of \(C\) whose elements have the same sum.
(e)
Let \(S\) be a subset of \(\mathbb{N}_{99}\) that contains 10 elements. Use the Pigeonhole Principle to prove that there exist two disjoint subsets of \(S\) whose elements have the same sum.