An Introduction to Proof via Inquiry-Based Learning

Recall that if \(A=\emptyset\text{,}\) then we say that \(A\) has cardinality 0. Also, if \(\card(A)=\card([n])\) for \(n\in\mathbb{N}\text{,}\) then we say that \(A\) has cardinality \(n\text{.}\) We have a special way of describing sets that are in bijection with the natural numbers.

Notice if a set \(A\) has cardinality \(1,2,\ldots\text{,}\) or \(\aleph_0\text{,}\) we can label the elements in \(A\) as “first”, “second”, and so on. That is, we can “count” the elements in these situations. Certainly, if a set has cardinality 0, counting is not an issue. This idea leads to the following definition.

Utilize Theorem 9.31 or Corollary 9.33 when proving the next result.

For the next proof, consider the cases when \(A\) is finite versus infinite. The contrapositive of Corollary 9.32 should be useful for the case when \(A\) is finite.

Loosely speaking, the next theorem tells us that we can arrange all of the rational numbers then count them “first”, “second”, “third”, etc. Given the fact that between any two distinct rational numbers on the number line, there are an infinite number of other rational numbers (justified by taking repeated midpoints), this may seem counterintuitive.

Here is one possible approach for proving the next theorem. Make a table with column headings \(0, 1, -1, 2,-2,\ldots\) and row headings \(1,2,3,4,5,\ldots\text{.}\) If a column has heading \(m\) and a row has heading \(n\text{,}\) then the entry in the table corresponds to the fraction \(m/n\text{.}\) Find a way to zig-zag through the table making sure to hit every entry in the table (not including column and row headings) exactly once. This justifies that there is a bijection between \(\mathbb{N}\) and the entries in the table. Do you see why? But now notice that every rational number appears an infinite number of times in the table. Resolve this by appealing to Theorem 9.41.

We would like to prove a stronger result than the previous theorem. To do so, we need an intermediate result.

To handle the first case, use induction together with Theorem 9.45. The second case is substantially more challenging. First, use Theorem 9.46 to construct a collection \(\{B_n\}\) of pairwise disjoint sets whose union is equal to the union of the original collection. Since each \(B_n\) is a subset of one of the sets in the original collection and each of these sets is countable, each \(B_n\) is also countable by Theorem 9.41. This implies that for each \(n\text{,}\) we can write \(B_n=\{b_{n,1}, b_{n,2},b_{n,3},\ldots\}\text{,}\) where the set may be finite or infinite. From here, we outline two different approaches for continuing. One approach is to construct a bijection from \(\mathbb{N}\) to \(\bigcup_{n=1}^{\infty}B_n\) using Figure 9.2 as inspiration. One thing you will need to address is what to do when a set in the collection \(\{B_n\}\) is finite. For the second approach, define \(f:\bigcup_{n=1}^{\infty}B_n\to \mathbb{N}\) via \(f(b_{n,m})=2^n3^m\text{,}\) verify that this function is injective, and then appeal to Theorem 9.41. Try using both of these approaches when tackling the proof of the following theorem.

Did you use the Axiom of Choice when proving the previous theorem? If so, where?