9.1: Finite Sets

Last updated
Save as PDF

Page ID: 7086

$Sundstrom.jpg$
Ted Sundstrom
Professors (Mathematics) at Grand Valley State University
Publisher: ScholarWorks @Grand Valley State University

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $ $ \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} $$\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$ $\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$

Preview Activity $\PageIndex{1}$: Equivalent Sets, Part 1

Let $A$ and $B$ be sets and let $f$ be a function from $A$ to $B$. ($f: A \to B$). Carefully complete each of the following using appropriate quantifiers: (If necessary, review the material in Section 6.3.)
1. The function $f$ is an injection provided that...
2. The function $f$ is not an injection provided that...
3. The function $f$ is a surjection provided that...
4. The function $f$ is not a surjection provided that...
5. The function $f$ is a bijection provided that...

Definitions: equivalent Sets and one-to-one correspondence

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$. In this case, we write $A \thickapprox B$.
When $A \thickapprox B$, 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$.

Note: When $A$ is not equivalent to $B$, we write $A \not\thickapprox B$.

For each of the following, use the definition of equivalent sets to determine if the first set is equivalent to the second set.
1. $A = \{1, 2, 3\}$ and $B = \{a, b, c\}$
2. $C= \{1, 2\}$ and $B = \{a, b, c\}$
3. $X = \{1, 2, 3, ..., 10\}$ and $Y = \{57, 58, 59, ..., 66\}$
Let $D^{+}$ be the set of all odd natural numbers. Prove that the function $f: \mathbb{N} \to D^{+}$ defined by $f(x) = 2x - 1$, for all $x \in \mathbb{N}$, is a bijection and hence that $N \thickapprox D^{+}$.
Let $\mathbb{R}^{+}$ be the set of all positive real numbers. Prove that the function $g: \mathbb{R} \to \mathbb{R}^{+}$ defined by $g(x) = e^{x}$, for all $x \in \mathbb{R}$ is a bijection and hence, that $\mathbb{R} \thickapprox \mathbb{R}^{+}$.

Preview Activity $\PageIndex{2}$: Equivalent Sets, Part 2

Review Theorem 6.20 in Section 6.4, Theorem 6.26 in Section 6.5, and Exercise (9) in Section 6.5.
Prove each part of the following theorem.

Theorem 9.1.

Let $A$, $B$, and $C$ be sets.

For each set $A$, $A \thickapprox A$.
For all sets $A$ and $B$, if $A \thickapprox B$, then $B \thickapprox A$.
For all sets $A$, $B$ and $C$, if $A \thickapprox B$ and $B \thickapprox C$, then $A \thickapprox C$.

Equivalent Sets

In Preview Activity $\PageIndex{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 Preview Activity $\PageIndex{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$. In this case, our elements would be the sets $A$, $B$, and $C$, and these would then have to 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$, $B$, 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 \thickapprox B$, 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 in Preview Activity $\PageIndex{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.

Let $A = \{1, 2, 3, ..., 99, 100\}$ and let $B = \{351, 352, 353, ..., 449, 450\}$. Define $f: A \to B$ by $f(x) = x + 350$, for each $x$ in $A$. Prove that $f$ is a bijection from the set $A$ to the set $B$ and hence, $A \thickapprox B$.
Let $E$ be the set of all even integers and let $D$ be the set of all odd integers.
Prove that $E \thickapprox D$ by proving that $F: E \to D$, where $F(x) = x + 1$, for all $x \in E$, is a bijection.
Let (0, 1) be the open interval of real numbers between 0 and 1. Similarly, if $b \in \mathbb{R}$ with $b > 0$, let $0, b$ be the open interval of real numbers between 0 and $b$.
Prove that the function $f: (0, 1) \to (0, b)$ by $f(x) = bx$, for all $x \in (0, 1)$, is a bijection and hence $(0, 1) \thickapprox (0, b)$.

Answer: Add texts here. Do not delete this text first.

In Part (3) of Progress Check 9.2, notice that if $b > 1$, then (0, 1) is a proper subset of (0, $b$) and $(0, 1) \thickapprox (0, b)$. Also, in Part (3) of Preview Activity $\PageIndex{1}$, we proved that the set $D$ of all odd natural numbers is equivalent to $\mathbb{N}$, and we know that $D$ is a proper subset of $\mathbb{N}$.

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.

Finite Sets

In Section 5.1, we defined the cardinality of a finite set $A$, denoted by card($A$), to be the number of elements in the set $A$. 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}$, we define $\mathbb{N}_k$ to be the set of all natural numbers between 1 and $k$, inclusive. That is,

$\mathbb{N}_k = \{1, 2, ..., k\}$.

We will use the concept of equivalent sets introduced in Preview Activity $\PageIndex{1}$ to define a finite set.

Definition: finite and infinite sets

A set $A$ is a finite set provided that $A = \emptyset$ or there exists a natural number $k$ such that $A \thickapprox \mathbb{N}_k$.
A set is an infinite set provided that it is not a finite set.
If $A \thickapprox \mathbb{N}_k$, we say that the set $A$ has cardinality $k$ (or cardinal number $k$), and we write card($A$) $= k$.

In addition, we say that the empty set has cardinality 0 (or cardinal number 0), and we write $\text{card}(\emptyset) = 0$.

Notice that by this definition, the empty set is a finite set. In addition, for each $k \in \mathbb{N}$, 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$.

Theorem 9.3

Any set equivalent to a finite nonempty set $A$ is a finite set and has the same cardinality as $A$.

Proof: Suppose that $A$ is a finite nonempty set, $B$ is a set, and $A \thickapprox B$. Since $A$ is a finite set, there exists a $k \in \mathbb{N}$ such that $A \thickapprox \mathbb{N}_k$. We also have assumed that $A \thickapprox B$ and so by part (b) of Theorem 9.1 (in Preview Activity $\PageIndex{2}$), we can conclude that $B \thickapprox A$. Since $A \thickapprox \mathbb{N}_k$, we can use part (c) of Theorem 9.1 to conclude that $B \thickapprox \mathbb{N}_k$. Thus, $B$ is finite and has the same cardinality as $A$.

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$, then $A \cup \{x\}$ is a finite set and $\text{card}(A \cup \{x\}) = \text{card}(A) + 1$.

Proof

Let $A$ is a finite set and assume that $\text{card}(A) = k$, where $k = 0$ or $k \in \mathbb{N}$. Assume $x \notin A$.

If $A = \emptyset$, then $\text{card}(A) = 0$ and $A \cup \{x\} = \{x\}$, which is equivalent to $\mathbb{N}_1$. Thus, $A \cup \{x\}$ is a finite set with cardinality 1, which equals card($A$) + 1.

If $A \ne \emptyset$, then $A \thickapprox \mathbb{N}_k$, for some $k \in \mathbb{N}$. This means that $\text{card}(A) = k$, and there exists a bijection $f: A \to \mathbb{N}_k$. We will now use this bijection to define a function $g: A \cup \{x\} \to \mathbb{N}_{k + 1}$ and then prove that the function $g$ is a bijection. We define $g: A \cup \{x\} \to \mathbb{N}_{k + 1}$ as follows: For each $t \in A \cup \{x\}$,

$g(t) = \begin{cases} f(t) & \text{ if \(t \in A$} \\ k + 1 & \text{ if $t = x$.} \end{cases}\)

To prove that $g$ is an injection, we let $x_1, x_2 \in A \cup \{x\}$ and assume $x_1 \ne x_2$.

If $x_1, x_2 \in A$, then since $f$ is a bijection, $f(x_1) \ne f(x_2)$, and this implies that $g(x_1) \ne g(x_2)$.
If $x_1 = x$, then since $x_2 \ne x_1$, we conclude that $x_2 \ne x$ and hence $x_2 \in A$. So $g(x_1) = k + 1$, and since $f(x_2) \in \mathbb{N}_k$ and $g(x_2) = f(x_2)$, we can conclude that $g(x_1) \ne g(x_2)$.

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 \{x\} \thickapprox \mathbb{N}_{k + 1}$, and

$\text{card}(A \cup \{x\}) = k + 1$.

Since $\text{card}(A) = k$, we have proved that $\text{card}(A \cup \{x\}) = \text{card}(A) + 1$.

Lemma 9.5

For each natural number $m$, if $A \subseteq \mathbb{N}_{m}$, then $A$ is a finite set and $\text{card}(A) \le m$.

Proof

We will use a proof using induction on $m$. For each $m \in \mathbb{N}$, let $P(m)$ be, "If $A \subseteq \mathbb{N}_{m}$, then $A$ is finite and $\text{card}(A) \le m$".

We first prove that $P(1)$ is true. If $A \subseteq \mathbb{N}_1$, then $A = \emptyset$ or $A = \{1\}$, both of which are finite and have cardinality less than or equal to the cardinality of $\mathbb{N}_1$. 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$, then $B$ is a finite set and $\text{card}(B) \le k$. We need to prove that $P(k + 1)$ is true.

So assume that $A$ is a subset of $\mathbb{N}_{k + 1}$. Then $A - \{k + 1\}$ is a subset of $\mathbb{N}_{k}$. Since $P(k)$ is true, $A - \{k + 1\}$ is a finite set and

$\text{card}(A - \{k + 1\}) \le k$.

There are two cases to consider: Either $k + 1 \in A$ or $k + 1 \notin A$.

If $k + 1 \notin A$, then $A = A - \{k + 1\}$. Hence, $A$ is finite and

$\text{card}(A) \le k < k + 1$.

If $k + 1 \in A$, then $A = (A - \{k + 1\}) \cup \{k + 1\}$. Hence, by Lemma 9.4, $A$ is a finite set and

$\text{card}(A) = \text{card}(A - \{k + 1\}$ + 1\).

Since $\text{card}(A - \{k + 1\}) \le k$, we can conclude that $\text{card}(A) \le k + 1$.

This means that we have proved the inductive step. Hence, by mathematical induction, for each $m \in \mathbb{N}$, if $A \subset \mathbb{N}_{m}$, then $A$ is finite and $\text{card}(A) \le m$.

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$, then $A$ is a finite set and $\text{card}(A) \le \text{card}(S)$.

Proof

Let $S$ be a finite set and assume that $A$ is a subset of $S$. If $A = \emptyset$, then $A$ is a finite set and $\text{card}(A) \le \text{card}(S)$. So we assume that $A \ne \emptyset$.

Since S is finite, there exists a bijection $f : S \to \mathbb{N}_k$ for some $k \in \mathbb{N}$. In this case, $\text{card}(S) = k$. We need to show that $A$ is equivalent to a finite set. To do this, we define $g : A \to f(A)$ by

$g(x) = f(x)$ for each $x \in A$.

Since $f$ is an injection, we conclude that $g$ is an injection. Now let $y \in f(A)$. Then there exists an $a \in A$ such that $f(a) = y$. But by the definition of $g$, this means that $g(a) = y$, and hence $g$ is a surjection. This proves that $g$ is a bijection.

Hence, we have proved that $A \thickapprox f(A)$. Since $f(A)$ is a subset of $\mathbb{N}_k$, we use Lemma 9.5 to conclude that $f(A)$ is finite and $\text{card}(f(A)) \le k$. In addition, by Theorem 9.3, $A$ is a finite set and $\text{card}(A) = \text{card}(f(A))$. This proves that $A$ is a finite set and $\text{card}(A) \le \text{card}(S)$.

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$, then $A - \{x\}$ is a finite set and $\text{card}(A - \{x\}) = \text{card} (A) - 1$

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$. Since $A$ is a proper subset of $B$, there exists an element $x$ in $B - A$. This means that $A$ is a subset of $B - \{x\}$. Hence, by Theorem 9.6,

$\text{card}(A) \le \text{card}(B - \{x\}).$

Also, by Corollary 9.7

$\text{card}(B - \{x\}) = \text{card}(B) - 1.$

Hence, we may conclude that $\text{card}(A) \le \text{card}(B) - 1$ and that

$\text{card}(A) < \text{card}(B).$

Theorem 9.3 implies that $B \not\thickapprox A$. This proves that a finite set is not equivalent to any of its proper subsets.

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$, 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$. We can then define a function $f : 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)$, then any function $f : A \to B$ is not an injection.

Proof

Let $A$ and $B$ be finite sets. We will prove the contrapositive o the theorem, which is, if there exists a function $f : A \to B$ that is an injection, then $\text{card}(A) \le \text{card}(B)$.

So assume that $f : A \to B$ is an injection. As in Theorem 9.6, we define a function $g: A \to f(A)$ by

$g(x) = f(x)$ for each $x \in A$.

As we saw in Theorem 9.6, the function $g$ is a bijection. But then $A \thickapprox f(A)$ and $f(A) \subseteq B$. Hence,

$\text{card}(A) = \text{card}(f(x))$ and $\text{card}f((A)) \le \text{card}(B)$.

Hence, $\text{card}f((A)) \le \text{card}(B)$, and this proves the contrapositive. Hence, if $\text{card}(A) > \text{card}(B)$, then any function $f : 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 9.1

Prove that the function $g : A \cup \{x\} \to \mathbb{N}_{k + 1}$ in Lemma 9.4 is a surjection.
Let $A$ be a subset of some universal set $U$. Prove that if $x \in U$, then $A \times \{x\} \thickapprox A$.
Let $E^{+}$ be the set of all even natural numbers. Prove that $\mathbb{N} \thickapprox E^{+}$.
Prove Corollary 9.7.
If $A$ is a finite set and $x \in A$, then $A - \{x\}$ is a finite set and $\text{card}(A - \{x\}) = \text{card} (A) - 1$
Hint: One approch is to use the fact that $A = (A - \{x\}) \cup \{x\}$.
Let $A$ and $B$ be sets. Prove that

(a) If $A$ is a finite set, then $A \cap B$ is a finite set.
(b) If $A \cup B$ is a finite set, then $A$ and $B$ are finite set.
(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.
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.
Prove the following proposiitons:

(a) If $A$, $B$, $C$, and $D$ are sets with $A \thickapprox B$ and $C \thickapprox D$, then $A \times C \thickapprox B \times D$.
(b) If $A$, $B$, $C$, and $D$ are sets with $A \thickapprox B$ and $C \thickapprox D$ and if $A$ and $C$ are disjoint and $B$ and $D$ are disjoint, then $A \cup C \thickapprox B \cup D$.

Hint: Since $A \thickapprox B$ and $C \thickapprox D$, there exist bijections $f: A \to B$ and $g: C \to D$. To prove that $A \times C \thickapprox B \times D$, prove that $h: A \times C \to B \times D$ is a bijection, where $h(a, c) = (f(a), g(c))$, for all $(a, c) \in A \times C$.
If $A \cap C = \emptyset$ and $B \cap D = \emptyset$, then to prove that $A \cup C \thickapprox B \cup D$, prove that the following function is a bijection: $k: A \cup C \to B \cup D$, where
\[k(x) = \begin{cases} f(x) & \text{ if $t \in A$} \\ g(x) & \text{ if $x \in C$.} \end{cases}\]
Let $A = \{a, b, c\}$.

(a) Construct a function $f: \mathbb{N}_5 \to A$ such that $f$ is a surjection.
(b) Use the function $f$ to construct a function $g: A \to \mathbb{N}_5$ so that $f \circ g = I_A$, where $I_A$ is the identity function on the set $A$. Is the function $g$ an injection? Explain.
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$ asfollows:
For each $x \in A$, $g(x) = j$, where $j$ is the least natural number in $f^{-1}(\{x\})$.
Prove that $f \circ g = I_A$, where $I_A$ is the identity function on the set $A$ and prove that $g$ is an injection.
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.
Hint: Since $B$ is finite, there exists a natural number $m$ such that $\mathbb{N}_m \thickapprox B$. This means there exists a bijection $k: \mathbb{N}_m \to B$. Now let $h = k \circ g$, where $g$ is the function constructed in Exercise (9).

Explorations and Activities
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 = \{3, 5, 11, 17, 21, 24, 26, 29\}$. Notice that
\[\begin{array} {rcr} {\{3, 21, 24, 26\} \subseteq A} &\text{and} & {3 + 21 + 24 + 26 = 74} \\ {\{3, 5, 11, 26, 29\} \subseteq A} &\text{and} & {3 + 5 + 11 + 26 + 29 = 74} \end{array}\]
Use this information to find two disjoint subsets of $A$ whose elements have the same sum.
(b) Let $B = \{3, 5, 9, 12, 15, 18, 21, 24\}$. Find two disjoint subsets of $B$ whose elements have the same sum. Note: By convention, if $T = \{a\}$, where $a \in \mathbb{N}$, then the sum of the elements in $T$ is equal to $a$.
(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: \mathcal{P}(C) \to \mathbb{N}_M$ so that for each $X \in \mathcal{P}$, $f(X)$ is equal to the sum of the elements in $X$.
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 part (11(c)iii) are not disjoint, use the idea presented in part (11a) 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.

Answer: Add texts here. Do not delete this text first.