9.2: Finite Sets

In the previous section, we used the phrase “finite set" without formally defining it. Let’s be a bit more precise. The following shorthand comes in handy.

Definition 9.17. For each \(n\in \mathbb{N}\), define \([n]:= \{1,2,\ldots,n\}\).

For example, \([5]=\{1,2,3,4,5\}\). Notice that our notation looks just like the notation we used for equivalence classes. However, despite the similar notation, these concepts are unrelated. We will have to rely on context to keep them straight.

The next definition should coincide with your intuition about what it means for a set to be finite.

Definition 9.18. A set \(A\) is finite if \(A=\emptyset\) or \(card(A)=card([n])\) for some \(n\in\mathbb{N}\). If \(A=\emptyset\), then we say that \(A\) has cardinality 0 and if \(card(A)=card([n])\), then we say that \(A\) has cardinality \(n\).

Let’s prove a few results about finite sets. When proving the following theorems, do not forget to consider the empty set.

Theorem 9.19. If \(A\) is finite and \(card(A)=card(B)\), then \(B\) is finite.

Theorem 9.20. If \(A\) has cardinality \(n\in\mathbb{N}\cup\{0\}\) and \(x\notin A\), then \(A\cup\{x\}\) is finite and has cardinality \(n+1\).

Consider using induction when proving the next theorem.

Theorem 9.21. For every \(n\in\mathbb{N}\), every subset of \([n]\) is finite.

Theorem 9.20 shows that adding a single element to a finite set increases the cardinality by 1. As you would expect, removing one element from a finite set decreases the cardinality by 1.

Theorem 9.22. If \(A\) has cardinality \(n\in\mathbb{N}\), then for all \(x\in A\), \(A\setminus \{x\}\) is finite and has cardinality \(n-1\).

The next result tells us that the cardinality of a proper subset of a finite set is never the same as the cardinality of the original set. It turns out that this theorem does not hold for infinite sets.

Theorem 9.23. Every subset of a finite set is finite. In particular, if \(A\) is a finite set, then \(card(B)<card(A)\) for all proper subsets \(B\) of \(A\).

Induction is a sensible approach to proving the next two theorems.

Theorem 9.24. If \(A_1,A_2,\ldots, A_k\) is a finite collection of finite sets, then \(\displaystyle \bigcup_{i=1}^k A_i\) is finite.

The next theorem, called the Pigeonhole Principle, is surprisingly useful. It puts restrictions on when we may have an injective function. The name of the theorem is inspired by the following idea: If \(n\) pigeons wish to roost in a house with \(k\) pigeonholes and \(n>k\), then it must be the case that at least one hole contains more than one pigeon. Note that 2 is the smallest value of \(n\) that makes sense in the hypothesis below.

Theorem 9.25. If \(n,k\in\mathbb{N}\) and \(f:[n]\to [k]\) with \(n>k\), then \(f\) is not injective.