An Introduction to Proof via Inquiry-Based Learning

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.

For example, \([5]=\{1,2,3,4,5\}\text{.}\) 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.

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

Consider using induction when proving the next theorem.

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.

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.

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

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\text{,}\) 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.