§ 6. Finite Sets¶
Definition 6.1 : Finite Set
A set is said to be finite if there is a bijective correspondence of \(A\) with some section of the positive integers. That is, \(A\) is finite if it is empty or if there is a bijection
for some positive integer \(n\). In the former case, we say that \(A\) has cardinality 0; in the latter case, we say that \(A\) has cardinality \({n}\).
Lemma 6.1
Let \(n\) be a positive integer.
Let \(A\) be a set; let \(a_{0}\) be an element of \(A\).
Then there exists a bijective correspondence \(f\) of the set \(A\) with the set \(\{1, \ldots, n+1\}\) if and only if there exists a bijective correspondence \(g\) of the set \(A-\left\{a_{0}\right\}\) with the set \(\{1, \ldots, n\}\).
Proof
(\(\Rightarrow\))
First, let us assume that there is a bijective correspondence
We then define a function \(f: A \longrightarrow\{1, \ldots, n+1\}\) by setting
One checks at once that \(f\) is bijective.
(\(\Leftarrow\))
To prove the converse, assume there is a bijective correspondence
If \(f\) maps \(a_{0}\) to the number \(n+1\), things are especially easy; in that case, the restriction \(f \mid A-\left\{a_{0}\right\}\) is the desired bijective correspondence of \(A-\left\{a_{0}\right\}\) with \(\{1, \ldots, n\}\). Otherwise, let \(f\left(a_{0}\right)=m\), and let \(a_{1}\) be the point of \(A\) such that \(f\left(a_{1}\right)=n+1\). Then \(a_{1} \neq a_{0}\). Define a new function
by setting
Now we are back in the easy case; the restriction \(h \mid A-\left\{a_{0}\right\}\) is the desired bijection of \(A-\left\{a_{0}\right\}\) with \(\{1, \ldots, n\}\).
Theorem 6.2
Let \(A\) be a set; suppose that there exists a bijection \(f: A \rightarrow\{1, \ldots, n\}\) for some \(n \in \mathbb{Z}_{+}\).
Let \(B\) be a proper subset of \(A\).
Then there exists no bijection \(g: B \rightarrow\{1, \ldots, n\}\);
but (provided \(B \neq \varnothing\)) there does exist a bijection \(h: B \rightarrow\) \(\{1, \ldots, m\}\) for some \(m<n\).
Proof
The case in which \(B=\varnothing\) is trivial, for there cannot exist a bijection of the empty set \(B\) with the nonempty set \(\{1, \ldots, n\}\).
We prove the theorem "by induction." Let \(C\) be the subset of \(\mathbb{Z}_{+}\)consisting of those integers \(n\) for which the theorem holds. We shall show that \(C\) is inductive. From this we conclude that \(C=\mathbb{Z}_{+}\), so the theorem is true for all positive integers \(n\).
First we show the theorem is true for \(n=1\). In this case \(A\) consists of a single element \(\{a\}\), and its only proper subset \(B\) is the empty set.
Now assume that the theorem is true for \(n\); we prove it true for \(n+1\). Suppose that \(f: A \rightarrow\{1, \ldots, n+1\}\) is a bijection, and \(B\) is a nonempty proper subset of \(A\). Choose an element \(a_{0}\) of \(B\) and an element \(a_{1}\) of \(A-B\). We apply the Lemma 6.1 to conclude there is a bijection
Now \(B-\left\{a_{0}\right\}\) is a proper subset of \(A-\left\{a_{0}\right\}\), for \(a_{1}\) belongs to \(A-\left\{a_{0}\right\}\) and not to \(B-\left\{a_{0}\right\}\). Because the theorem has been assumed to hold for the integer \(n\), we conclude the following:
-
There exists no bijection \(h: B-\left\{a_{0}\right\} \rightarrow\{1, \ldots, n\}\).
-
Either \(B-\left\{a_{0}\right\}=\varnothing\), or there exists a bijection
Lemma 6.1, combined with (1), implies that there is no bijection of \(B\) with \(\{1, \ldots, n+1\}\).
This is the first half of what we wanted to proved.
To prove the second half, note that if \(B-\left\{a_{0}\right\}=\varnothing\), there is a bijection of \(B\) with the set \(\{1\}\); while if \(B-\left\{a_{0}\right\} \neq \varnothing\), we can apply Lemma 6.1, along with (2), to conclude that there is a bijection of \(B\) with \(\{1, \ldots, p+1\}\).
In either case, there is a bijection of \(B\) with \(\{1, \ldots, m\}\) for some \(m<n+1\), as desired.
The induction principle now shows that the theorem is true for all \(n \in \mathbb{Z}_{+}\).
Corollary 6.3
If \(A\) is finite, there is no bijection of \(A\) with a proper subset of itself.
Proof
Assume that \(B\) is a proper subset of \(A\) and that \(f: A \rightarrow B\) is a bijection. By assumption, there is a bijection \(g: A \rightarrow\{1, \ldots, n\}\) for some \(n\). The composite \(g \circ f^{-1}\) is then a bijection of \(B\) with \(\{1, \ldots, n\}\). This contradicts Theorem 6.2.
Corollary 6.4
\(\mathbb{Z}_{+}\) is not finite.
Proof
The function \(f: \mathbb{Z}_{+} \rightarrow \mathbb{Z}_{+}-\{1\}\) defined by \(f(n)=n+1\) is a bijection of \(\mathbb{Z}_{+}\)with a proper subset of itself. If \(\mathbb{Z}_{+}\) is finite, it is a contradiction to Corollary 6.3, so \(\mathbb{Z}_{+}\) is not finite.
Corollary 6.5
The cardinality of a finite set \(A\) is uniquely determined by \(A\).
Proof
Let \(m<n\). Suppose there are bijections
Then the composite
is a bijection of the finite set \(\{1, \ldots, n\}\) with a proper subset of itself, contradicting Corollary 6.3.
Corollary 6.6
If \(B\) is a subset of the finite set \(A\), then \(B\) is finite. If \(B\) is a proper subset of \(A\), then the cardinality of \(B\) is less than the cardinality of \(A\).
Corollary 6.7
Let \(B\) be a nonempty set. Then the following are equivalent:
-
\(B\) is finite.
-
There is a surjective function from a section of the positive integers onto \(B\).
-
There is an injective function from \(B\) into a section of the positive integers.
Proof
(1) \(\Longrightarrow\) (2).
Since \(B\) is nonempty, there is, for some \(n\), a bijective function \(f:\{1, \ldots, n\} \rightarrow B\).
(2) \(\Longrightarrow\) (3).
If \(f:\{1, \ldots, n\} \rightarrow B\) is surjective, define \(g: B \rightarrow\{1, \ldots, n\}\) by the equation
Because \(f\) is surjective, the set \(f^{-1}\{(b)\}\) is nonempty; then the well-ordering property of \(\mathbb{Z}_{+}\) tells us that \(g(b)\) is uniquely defined. The map \(g\) is injective, for if \(b \neq b^{\prime}\), then the sets \(f^{-1}(\{b\})\) and \(f^{-1}\left(\left\{b^{\prime}\right\}\right)\) are disjoint, so their smallest elements must be different.
(3) \(\Longrightarrow\) (1).
If \(g: B \rightarrow\{1, \ldots, n\}\) is injective, then changing the range of \(g\) gives a bijection of \(B\) with a subset of \(\{1, \ldots, n\}\).
It follows from the Corollary 6.6 that \(B\) is finite.
Corollary 6.8
Finite unions and finite cartesian products of finite sets are finite.
Proof
We first show that if \(A\) and \(B\) are finite, so is \(A \cup B\). The result is trivial if \(A\) or \(B\) is empty. Otherwise, there are bijections \(f:\{1, \ldots, m\} \rightarrow A\) and \(g\) : \(\{1, \ldots, n\} \rightarrow B\) for some choice of \(m\) and \(n\). Define a function \(h:\{1, \ldots, m+\) \(n\} \rightarrow A \cup B\) by setting \(h(i)=f(i)\) for \(i=1,2, \ldots, m\) and \(h(i)=g(i-m)\) for \(i=m+1, \ldots, m+n\). It is easy to check that \(h\) is surjective, and from Corollary 6.7 it follows that \(A \cup B\) is finite.
Now we show by induction that finiteness of the sets \(A_{1}, \ldots, A_{n}\) implies finiteness of their union. This result is trivial for \(n=1\). Assuming it true for \(n-1\), we note that \(A_{1} \cup \cdots \cup A_{n}\) is the union of the two finite sets \(A_{1} \cup \cdots \cup A_{n-1}\) and \(A_{n}\), so the result of the preceding paragraph applies.
Now we show that the cartesian product of two finite sets \(A\) and \(B\) is finite. Given \(a \in A\), the set \(\{a\} \times B\) is finite, being in bijective correspondence with \(B\). The set \(A \times B\) is the union of these sets; since there are only finitely many of them, \(A \times B\) is a finite union of finite sets and thus finite.
To prove that the product \(A_{1} \times \cdots \times A_{n}\) is finite if each \(A_{i}\) is finite, one proceeds by induction.