Grab some collection of objects and count it. How does that work?
Let's say we want to count the (living) former Presidents of the United States in this photograph:
We're so good at counting that we'd probably just glance and say "5". But if we were three or four years old, we'd probably have to count more carefully, which means doing something like placing our index finger on Obama and pronouncing "one", shifting the index finger to W. Bush and pronouncing "two", shifting the index finger to Clinton and pronouncing "three", shifting it to H. W. Bush and pronouncing "four", and finally shifting to Carter and pronouncing "five".
In other words, we would construct the following explicit bijection:
Definition. We call the set A finite if either A is empty, or there is some and a bijection . The number is called the cardinality of A. The cardinality of the empty set is defined to be 0.
We've been dealing with finite sets our whole lives, and much of set theory is inspired by them. We'll take the time to record some important facts, which may seem obvious but are worth noting.
Theorem. If is finite and there is a surjection , then is finite.
Proof. We'll start with a lemma:
Lemma. If there is a surjection , then there is an injection .
Proof. Since is a surjection, for each , there is some with . Pick one of them and call it .
We claim is an injection. .
So now we have an injection from to a finite set. Further, there is some bijection . Then is an injection. But every function is a surjection onto its range, so is bijective with a subset of , hence must be finite.
Corollary. If is finite and there is an injection , then is finite.
Corollary. Any subset of a finite set is finite.
Proof. If and is finite, consider the function given by . This is an injection, so the previous corollary applies..
Definition. We call a proper subset of if but ; that is, if every element of is an element of , but there is some element of which is not an element of .
Theorem. If is finite, then is not equivalent to any of its proper subsets.
Proof. Suppose not. Then there is some finite set and a proper subset of with . So there is some with .
Now let be the bijection which shows that is finite, and arrange so that . Then the range of is a subset of . But then would be equivalent to a subset of , which is absurd. .
Perhaps the most surprising part of this theorem is that we have the assumption `` is finite". You might think that there's no way a set could be equivalent to the set you get after you remove an element. But! Infinite sets are kind of weird; or at least we aren't used to dealing with them so our intuitions are sometimes wrong.
Definition. We call a set infinite if it is not finite.
Theorem. If is equivalent to one of its proper subsets, then is infinite.
Proof. This is the contrapositive of the last theorem.
This theorem (though you might think its hypothesis never applies) turns out to be a very useful way to prove that a particular set is infinite.
Theorem. is infinite.
Proof. Consider the function . This is a function from to . Notice that there is a function given by , which has
so that serves as an inverse to . Therefore is a bijection, and so .
We can also give another proof, which is how most proofs that something is infinite go. Since infinite just means not finite, we challenge the reader to try and tell us how many elements the infinite set has. Then we show we can always defeat them, by finding an element they left out of their count.
Another proof that is infinite.
Suppose had finitely many elements, say of them. Then there would be a bijection .
Let . Then is strictly greater than any of the . Therefore . so is not onto. This contradiction establishes the theorem. .
The following proof of this type is the oldest recorded reductio ad absurdum.
Theorem. (Euclid, ca. 300 BCE) There are infinitely many prime numbers.
Proof. Suppose there were finitely many prime numbers, say of them. List them all: . Consider the numbers
Now we know that has at least one prime factor; call that factor . Observe that could not be 2, because is even, so is odd. Further, could not be 3, because is a multiple of 3, so has remainder 1 when we divide by 3. Proceeding in this way, we find that cannot be any of the prime numbers we listed.
So we have found a prime that was not on our list, which we supposed to be complete. This contradiction establishes the theorem..
We can also show that a set is infinite by finding an infinite subset:
Theorem. If and is infinite, then is infinite.
Proof. Assume . We will show that if is infinite, then is infinite. The contrapositive of this claim is: If is finite, then is finite, which we already showed.
E.g. is infinite.
Actually this can be souped up:
Theorem. If is infinite and there is an injection , then is infinite.
E.g. is infinite.
Proof. Consider the function given by .
If , then , so . This shows that is an injection, so the above theorem shows that is infinite.
is in fact the smallest infinite set, in the following sense:
Theorem. Any infinite set has a subset which is equivalent to .
Proof. Let be an infinite set. We'll show, by induction, that we can pick a distinct element for each .
For the base case, pick . Note that is not empty (otherwise would have had only one element to begin with).
For the inductive step, suppose we've picked distinct elements of already. Then is not empty (otherwise would have only elements), so there is some which is distinct from .
Mathematical induction allows us to continue this way to define for any , thus building a bijection . .