9.1: Definition and Basic Properties

Informally, the cardinality of a set is the number of elements that it contains. (This was mentioned in Notation \(3.2.14\).)

Exercise \(9.1.1\).

What is the cardinality of each of these sets? (You do not need to show your work or justify your answers.)

1. \(\#\{1,2,3,4\}=\)
2. \(\#\{\mathrm{a}, \mathrm{e}, \mathrm{i}, \mathrm{o}, \mathrm{u}\}=\)
3. \(\#\{\mathrm{a}, \mathrm{l}, \mathrm{b}, \mathrm{e}, \mathrm{r}, \mathrm{t}, \mathrm{a}\}=\)
4. \(\text { 4) } \# \varnothing=\)
5. \(\#\{\varnothing\}=\)
6. \(\#\{k \in\{1,2, \ldots, 10\} \mid k \neq 7\}=\)

An informal understanding of cardinality is not sufficient in advanced mathematics courses, so we need to study this idea more thoroughly.

Example \(9.1.2\).

The cardinality of \(\{a, b, c\}\) is 3. Children learn to verify this by counting: \[1(\text { for } \mathrm{a}), \quad 2(\text { for } \mathrm{b}), \quad 3(\text { for } \mathrm{c}) .\]

They are taught to assign exactly one number to each element of the set (and not skip any numbers as they count up). Mathematicians express this idea in a more sophisticated way: if we define a function \(f:\{\mathrm{a}, \mathrm{b}, \mathrm{c}\} \rightarrow\{1,2,3\}\) by \[f(\mathrm{a})=1, f(\mathrm{~b})=2, f(\mathrm{c})=3,\]

then \(f\) is a bijection.

In general, if a set \(A\) has \(n\) elements, then counting the elements one-by-one defines a bijection from \(A\) to \(\{1,2,3, \ldots, n\}\). This observation leads to the following official definition.

Definition \(9.1.3\).

1. Let \(A\) be a set and \(n\) be a natural number. We say that the cardinality of \(A\) is \(n\) (and write \(\# A = n\)) iff there is a bijection from \(A\) to \(\{1,2,3, \ldots, n\}\).
2. A set \(A\) is finite iff there is some \(n \in \mathbb{N}\), such that \(\# A = n\).
3. A set \(A\) is infinite iff it is not finite.

Remarks \(9.1.4\).

1. Not all sets are finite. For example, \(\mathbb{N}\) is infinite (see Exercise \(9.2.8(5)\)).
2. We will see in Theorem \(9.1.20\) that every subset of a finite set is finite.

Since the definition of \(\# A\) is based on bijections, every proof about cardinality will rely on facts about bijections.

Example \(9.1.5\).

Show \(\#\{1,2,3, \ldots, n\}=n\), for every \(n \in \mathbb{N}\).

Scratchwork. The definition of cardinality tells us that if \(A\) is any set, and we need to show \(\# A = n\), then we need to find a bijection from \(A\) to \(\{1,2,3, \ldots, n\}\). In this problem, we have \(A=\{1,2,3, \ldots, n\}\). Therefore, we need to find a bijection from \(\{1,2,3, \ldots, n\}\) to \(\{1,2,3, \ldots, n\}\). Thus, we need to find a bijection from a set to itself. Exercise \(6.6.9\) tells us that the identity map is such a function.

Solution

PROOF.

From Exercise \(6.6.9\), we know that the identity map \(I_{\{1,2, \ldots, n\}}\) is a bijection from \(\{1,2, \ldots, n\}\) to \(\{1,2, \ldots, n\}\), so \(\#\{1,2, \ldots, n\}=n\).

ALTERNATE PROOF.

Define \(f:\{1,2,3, \ldots, n\} \rightarrow\{1,2,3, \ldots, n\}\) by \(f(k) = k\).

We claim that \(f\) is a bijection. In other words, we claim that \(f\) is one-to-one and onto.

(one-to-one) Given \(i_{1}, i_{2} \in\{1,2,3, \ldots, n\}\), such that \(f(i_{1}) = f(i_{2})\), we have \(i_{1} = i_{2}\). So \(f\) is one-to-one.

(onto) Given \(j \in\{1,2,3, \ldots, n\}\), let \(i = j\). Then \(f(i) = i = j\). So \(f\) is onto.

Since \(f\) is both one-to-one and onto, it is a bijection. This completes the proof of the claim.

Therefore, there is a bijection (namely, \(f\)) from \(\{1,2,3, \ldots, n\}\) to \(\{1,2,3, \ldots, n\}\). Hence, \(\#\{1,2,3, \ldots, n\}=n\).

Remark \(9.1.6\).

Since the empty set has no elements, its cardinality should be 0. Although it may not be obvious, Definition \(9.1.3\) does agree with this observation. To verify this, it is important to realize that, for any \(n \in \mathbb{N}\), the notation \(\{1,2, \ldots, n\}\) is just another name for the set \(\{i \in \mathbb{N} \mid 1 \leq i \leq n\}\). In particular, if \(n = 0\), then \[\{1,2, \ldots, n\}=\{i \in \mathbb{N} \mid 1 \leq i \leq n\}=\{i \in \mathbb{N} \mid 1 \leq i \leq 0\}=\varnothing .\]

Therefore, letting \(n = 0\) in Example \(9.1.5\) tells us that \(\# \varnothing=0\), as expected.

The definition of \(\# A\) specifies that there is a bijection from \(A\) to \(\{1,2,3, \ldots, n\}\). The following exercise shows there is no harm if you choose to have the bijection go the other way.

Exercise \(9.1.7\).

Let \(A\) be a set. For \(n \in \mathbb{N}\), show \(\# A = n\) iff there is a bijection from \(\{1,2,3, \ldots, n\}\) to \(A\). [Hint: Use Exercise \(6.7.13(1)\).]

Bijections can be used to show that two sets have the same cardinality, without knowing how many elements they have.

Example \(9.1.8\).

In the society Married of Example \(6.6.2\) (where every man is married to a woman, and vice-versa), it is clear that there must be exactly the same number of men and women. (If there were more women than men, then either some woman would be unmarried, or more than one woman would have to be married to the same man. Similarly, if there were more men than women.) This is true, even though we have no idea how many women or men there are in the society. All we know is that however many women there are is exactly the same as the number of men.

This observation is formalized in the following proposition.

Proposition \(9.1.9\).

Suppose \(A\) and \(B\) are finite sets. Then \(\# A = \# B\) if and only if there is a bijection from \(A\) to \(B\).

Proof

\((\Rightarrow)\) Let \(n\) be the cardinality of \(A\). By definition, this means \[\text { there is a bijection } f: A \rightarrow\{1,2, \ldots, n\} \text {. }\]

By assumption, \(n\) is also the cardinality of \(B\), so \[\text { there is also a bijection } g: B \rightarrow\{1,2, \ldots, n\} \text {. }\]

The inverse of a bijection is a bijection (see Exercise \(6.7.13(1)\)), and the composition of bijections is a bijection (see Exercise \(6.8.12(1)\)), so \(g^{-1} \circ f\) is a bijection from \(A\) to \(B\).

\((\Leftarrow)\) We leave this as an exercise.

Exercise \(9.1.10\).

Prove Proposition \(9.1.9(\Leftarrow)\). [Hint: Use Exercise \(6.8.12(1)\).]

Exercise \(9.1.11\).

1. Show that if \(\# A_{1} = \# A_{2}\), then \(\# (A_{1} \times B) = \# (A_{2} \times B)\). [Hint: If \(f : A_{1} \rightarrow A_{2}\) is a bijection, define \(g : A_{1} \times B \rightarrow A_{2} \times B\) by \(g\left(a_{1}, b\right)=\left(f\left(a_{1}\right), b\right)\).]
2. Show that if \(\{a_{0}\}\) is any set with only one element, then \(\#\left(\left\{a_{0}\right\} \times B\right)=\# B\). [Hint: Define \(f: B \rightarrow\left\{a_{0}\right\} \times B\) by \(f(b)=\left(a_{0}, b\right)\).]
3. Suppose \(f : A \rightarrow B\) is one-to-one, and \(X \subset A\). Show \(\# f(X) = \# X\).

Example \(9.1.12\).

In elementary school, we learn that if Alice has \(m\) apples and Bob has \(n\) apples, then the sum \(m+n\) is the total number of apples that the two of them have. However, this simple example assumes that Alice and Bob are not sharing any of the apples; the set of Alice’s apples must be disjoint from the set of Bob’s apples.

The following result generalizes this example.

Theorem \(9.1.13\).

If \(A\) and \(B\) are disjoint finite sets, then \[\# (A \cup B) = \# A + \# B.

Proof

Let \(m = \# A\) and \(n = \# B\). Then there exist bijections \[f:\{1,2, \ldots, m\} \rightarrow A \quad \text { and } \quad g:\{1,2, \ldots, n\} \rightarrow B .\]

Define a function \(h:\{1,2, \ldots, m+n\} \rightarrow(A \cup B)) by \[h(k)=\left\{\begin{array}{cl}
f(k) & \text { if } k \leq m \\
g(k-m) & \text { if } k>m
\end{array}\right.\]

(Notice that if \(k \in\{1,2, \ldots, m+n\}\), and \(k > m\), then \(m + 1 \leq k \leq m + n\), so \(1 \leq k − m \leq n\); therefore, \(k − m\) is in the domain of \(g\), so the expression \(g(k − m)\) makes sense.)

To complete the proof, it suffices to show that \(h\) is a bijection; thus, we we need only show that \(h\) is one-to-one and onto.

(onto) Given \(y \in A \cup B\), we have either \(y \in A \text { or } y \in B\), and we consider these two possibilities as separate cases.

1. Suppose \(y \in A\). Since \(f\) is onto, there is some \(k \in\{1,2, \ldots, m\}\) with \(f(k) = y\). Then, because \(k \leq m\), we have \[h(k)=f(k)=y .\]
2. Suppose \(y \in B\). Since \(g\) is onto, there is some \(k \in\{1,2, \ldots, n\}\) with \(g(k) = y\). Then \(k+m \in\{1,2, \ldots, m+n\}\) and \(k + m > m\), so \[h(k+m)=g((k+m)-m)=\eta(k)=y .\]

Since \(y\) is an arbitrary element of \(A \cup B\), we conclude that \(h\) is onto.

(one-to-one) We leave this as an exercise.

Exercise \(9.1.14\).

Show that the function \(h\) defined in the proof of Proposition \(9.1.13\) is one-to-one.

Exercise \(9.1.15\).

Assume \(B\) is a finite set.

1. For all \(b \in B\), show that \(\#(B \backslash\{b\})=\# B-1\).
2. Show that if \(A \subset B\), then \(\# A \leq \# B. [Hint: \(\# B=\# A+\#(B \backslash A) \geq \# A\).]
3. Show that if \(A_{1}\) and \(A_{2}\) are disjoint subsets of \(B\), then \(\# A_{1}+\# A_{2} \leq \# B\).
4. (harder) Assume \(B \neq \varnothing\). Show that if \(S \subset \mathcal{P}(B)\), and no two elements of \(S\) are disjoint, then \(\# S \leq \frac{1}{2} \# \mathcal{P}(B)\).
   [Hint: You may assume (without proof) that \(\mathcal{P}(B)\) is finite. If \(X \in S\), then \(\bar{X} \notin S\).]
5. Show \(\# B = 0\) if and only if \(B=\varnothing\).

The following generalization of Proposition \(9.1.13\) applies to the union of any number of sets, not just two.

Exercise \(9.1.16\).

If \(A_{1}, A_{2}, \ldots, A_{n}\) are pairwise-disjoint finite sets, then \[\#\left(A_{1} \cup A_{2} \cup \cdots \cup A_{n}\right)=\# A_{1}+\# A_{2}+\cdots+\# A_{n} .\]

[Hint: Induct on \(n\), using Proposition \(9.1.13\) and Exercise \(4.5.7\).]

It was pointed out in Remark \(6.1.7\) that if \(A\) and \(B\) are finite sets, then \(\#(A \times B)=\# A \cdot \# B\). We can now prove this, after using Exercise \(9.1.16\) to solve the following exercise:

Exercise \(9.1.17\).

Suppose \(A_{1}, A_{2}, \ldots, A_{m}\) are pairwise-disjoint finite sets. Show that if \(A=A_{1} \cup \cdots \cup A_{m}\), then \[\#(A \times B)=\#\left(A_{1} \times B\right)+\#\left(A_{2} \times B\right)+\cdots+\#\left(A_{m} \times B\right) .\]

[Hint: The sets \(A_{i} \times B\) are pairwise-disjoint, and their union is \(A \times B\).]

Theorem \(9.1.18\).

For any finite sets \(A\) and \(B\), we have \[\#(A \times B)=\# A \cdot \# B.\]

Proof

Let \(m = \# A\). Then there is no harm in assuming \(A=\{1,2, \ldots, m\}\) (see Exercise \(9.1.11(1)\)). Therefore \[A=\{1\} \cup\{2\} \cup \cdots \cup\{m\},\]

and the sets \(\{1\},\{2\}, \cdots,\{m\}\) are pairwise-disjoint, so \[\begin{aligned}
\#(\Lambda \times B) &=\#(\{1\} \times B) \text { । } \#(\{2\} \times B)+\cdots \text { । } \#(\{m\} \times B) \\
&=\# B+\# B+\cdots+\# B \quad(m \text { summands }) \\
&=m \cdot \# B \\
&=\# A \cdot \# B .
\end{aligned}\]

(First Line: Exercise \(9.1.17\) Second Line: Exercise \(9.1.11(2)\))

Exercise \(9.1.19\).

Suppose \(A\) and \(B\) are finite sets, and \(m, n \in \mathbb{N}\). Prove:

1. If \(m \leq n\), then there exists a one-to-one function \(f:\{1,2, \ldots, m\} \rightarrow\{1,2, \ldots, n\}\).
2. If \(\# A \leq \# B\), then there exists a one-to-one function \(f: A \rightarrow B\). [Hint: Use the preceding exercise.]
3. If \(m \geq n > 0\), then there exists an onto function \(f:\{1,2, \ldots, m\} \rightarrow\{1,2, \ldots, n\}\).
4. If \(A\) and \(B\) are nonempty, and \(\# A \geq \# B\), then there exists an onto function \(f : A \rightarrow B\). [Hint: Use the preceding exercise.]

The converses of the exercises in \((9.1.19)\) are true, and important. They will be discussed in Section \(9.2\).

We end the section with a basic fact that may seem to be obvious (and was mentioned in Remark \(9.1.4(2)\)), but that would be difficult or impossible to prove without using induction.

Theorem \(9.1.20\).

Every subset of any finite set is finite.

Proof

Define \(P(n)\) to be the assertion \[\text { If } A \text { is any set with } \# A=n \text {, then every subset of } A \text { is finite. }\]

1. Base case. Assume \(n = 0\), and let \(B\) be any subset of \(A\). Now \(\# A = n = 0\), so \(A=\varnothing\). Since the only subset of the empty set is the empty set, we have \(B = \varnothing\). Hence \(\# B = 0\), so \(B\) is finite.
2. Induction step. Assume \(n \geq 1\), and that \(P(n − 1)\) is true, and let \(B\) be any subset of \(A\). We may assume \(B\) is a proper subset of \(A\). (Otherwise, we have \(B = A\), so \(\# B = \# A = n\), which means that \(B\) is finite.) Thus, there exists \(a \in A\), such that \(a \notin B\). Let \(A^{\prime}=A \backslash\{a\}\). Then \(\# A^{\prime} = n − 1\), so the induction hypothesis tells us that every subset of \(A^{\prime}\) is finite. Since \(B \subset A^{\prime}\), we conclude that \(B\) is finite.