An Introduction to Proof via Inquiry-Based Learning

In the previous section, we explored finite sets. Now, let’s tinker with infinite sets.

Let’s see if we can utilize this definition to prove that the set of natural numbers is infinite. For sake of a contradiction, assume otherwise. Then there exists \(n\in\mathbb{N}\) such that \(\card([n])=\card(\mathbb{N})\text{,}\) which implies that there exists a bijection \(f:[n]\to \mathbb{N}\text{.}\) What can you say about the number \(m\coloneqq \max(f(1),f(2),\ldots,f(n))+1\text{?}\)

The next theorem is analogous to Theorem 9.19, but for infinite sets. To prove this theorem, try a proof by contradiction. You should end up composing two bijections, say \(f:A\to B\) and \(g:B\to [n]\) for some \(n\in\mathbb{N}\text{.}\) As we shall see later, the converse of this theorem is not true in general.

Notice that Definition 9.26 tells us what infinite sets are not, but it doesn’t really tell us what they are. In light of Theorem 9.27, one way of thinking about infinite sets is as follows. Suppose \(A\) is some nonempty set. Let’s select a random element from \(A\) and set it aside. We will call this element the “first” element. Then we select one of the remaining elements and set is aside, as well. This is the “second” element. Imagine we continue this way, choosing a “third” element, and “fourth” element, etc. If the set is infinite, we should never run out of elements to select. Otherwise, we would create a bijection with \([n]\) for some \(n\in\mathbb{N}\text{.}\)

The next problem, sometimes referred to as the Hilbert Hotel, named after the German mathematician David Hilbert

¹

en.wikipedia.org/wiki/David_Hilbert

(1862–1942), illustrates another way of thinking about infinite sets.

The previous problem verifies that there exists a proper subset of the natural numbers that is in bijection with the natural numbers themselves. We also witnessed this in Parts (a) and (b) of Problem 9.29. Notice that Theorem 9.23 forbids this type of behavior for finite sets. It turns out that this phenomenon is true for all infinite sets. The next theorem verifies that that the two viewpoints of infinite sets discussed above are valid. To prove this theorem, we need to prove that the three statements are equivalent. One possible approach is to prove (i) if and only if (ii) and (ii) if and only if (iii). For (i) implies (ii), construct \(f\) recursively. For (ii) implies (i), try a proof by contradiction. For (ii) implies (iii), let \(B=A\setminus \{f(1),f(2),\ldots\}\) and show that \(A\) can be put in bijection with \(B\cup\{f(2),f(3),\ldots\}\text{.}\) Lastly, for (iii) implies (ii), suppose \(g:A\to C\) is a bijection for some proper subset \(C\) of \(A\text{.}\) Let \(a\in A\setminus C\text{.}\) Define \(f:\mathbb{N}\to A\) via \(f(n)=g^n(a)\text{,}\) where \(g^n\) means compose \(g\) with itself \(n\) times.

It is worth mentioning that for the previous theorem, (iii) implies (i) follows immediately from the contrapositive of Theorem 9.23. When proving (i) implies (ii) in the previous theorem, did you apply the Axiom of Choice? If so, where?