We know that is the smallest infinite set; this makes a pretty good place to get started. But our ideas about size have to do just with bijections, so whatever we'd say about we could also say about any set which is equivalent to .
Definition. If , we call denumerable, and we call any bijection a denumeration of . We call countable if it is either finite or denumerable. Sometimes denumerable sets are called countably infinite.
E.g. is denumerable.
Theorem. Any subset of a denumerable set is countable.
Proof. Let be denumerable and . Assume that is not finite; we'll show that is denumerable.
Since is denumerable, there is a bijection . We'll construct a denumeration of using induction.
For the base case: by the Well-Ordering Principle, there is a least element of . By injectivity, this element is the image of a unique element of , call it . Observe that is not empty, so is not empty.
Suppose we've denumerated elements of so far, say . Since is not finite, is not empty. So is a nonempty subset of , hence by the Well-Ordering Principle has a least element. By injectivity, this element is the image of a unique , which is distinct from all the .
Proceeding in this way, we construct a bijection . Moreover, any will be one of the , since will occur in the list of values. So we have . .
Corollary. The following sets are equivalent to :
- The set of prime numbers.
- The set of even natural numbers.
- The set of odd natural numbers.
- The set of positive powers of 2.
- The set of positive powers of 3.
Proof. These are all infinite subsets of . Since they're not finite, they must be denumerable. .
Theorem. Any subset of a countable set is countable.
Theorem. If is countable and there is an injection , then is countable.
Theorem. If is countable and there is a surjection , then is countable.
One weird thing about denumerable sets -- actually any infinite set -- is that if you add a single element, the set doesn't get any larger.
Proof. The bijection is given by sending to . .
Okay, but what if we tried to add an entire additional copy of -- say, the negative numbers.
Proof. We'll give a bijection . Try
As an exercise, show that this function is a bijection. Actually, givetwo proofs: one by showing it is injective and surjective, and one by building the inverse function..
Notice that this is a bit weird: is the union of two disjoint sets, each of which is equivalent to . But it's no bigger than .
Theorem. If is denumerable and is denumerable, then is denumerable.
Proof. We'll show first that is denumerable.
We can represent as a grid of points in the plane:
and then denumerate them in any order we like, starting perhaps from the origin and snaking around like so:
It's clear that we'll eventually get all the dots numbered (so our denumeration is onto), and that dot will only get one number (so our denumeration is one-to-one).
Now let's go from this special case to the general case.
Lemma. If and , then .
Proof. This is homework..
To complete the proof: we know that and are denumerable, so we have and . So by the lemma . But we showed . So by transitivity of , we have . .
Theorem. If is countable and is countable, then is countable.
Proof. We have the cases when both sets are finite and both sets are denumerable. So we only need to handle the case when one set is finite and the other is denumerable. This is an exercise. .
Theorem. is denumerable.
Proof. By the theorem above, is countable. There is a surjection from to given by , so is countable. But we have an injection from to given by , so is infinite..