6:15 PM

Let's look at some examples of countable sets. Along the way, we'll develop some rules for countable sets in general.

By definition, a set X is countable if there exists a one-to-one, onto function from that set to the natural numbers. This means that countable sets are infinite. This also means that all countable sets are the same size, but the concept of size is misleading when it comes to countable sets.

For example, take the set of even positive numbers. If x is a member of this set, f(x)=x/2 is a function that maps to the natural numbers and is both one-to-one and onto. Therefore, the even numbers are countable, and the set of even numbers is the same size as the set of natural numbers.

The fact that both sets are the same size is somewhat counterintuitive. If we start listing off even numbers, the list begins 2, 4, 6, …. But the list of natural numbers begins 1, 2, 3, 4, 5, 6, …. In general, for any number n, there are n natural numbers less than or equal to n, but there are only n/2 even numbers less than or equal to n. At first glance, it looks like there are twice as many natural numbers as even numbers, so even though both sets are infinite, the natural numbers are twice as big.

This thinking would be valid for finite sets, but the fact that the sets are infinite causes this reasoning to go wrong. A better way of thinking about the problem is that for any number n, the number of points in the first n members of the set is always n. For example, the first 5 even numbers are 2, 4, 6, 8, and 10, and the first 5 natural numbers are 1, 2, 3, 4, and 5. Both sets have 5 members. Since both sets are infinite, we can count off through both sets like this, and the number of members of each set will always be the same.

Essentially, we add members, one at a time, to each set, and the members we add are specified by the function showing the relationship between the sets. We will never repeat numbers in either list (this is because the function is one-to-one), and we will eventually get to every member of each set (this is because the function is onto).

The striking thing here is that the even numbers are a proper subset of the natural numbers. (A proper subset is a subset which is not equal to the original set.) One property of infinite sets is that they have proper subsets which have the same cardinality as the set itself. This cannot happen for finite sets. Any proper subset of a finite set is (obviously) smaller than the original set.

Taking this a step further, we can prove that any infinite subset of a countable set is countable. All finite sets are smaller than all infinite sets. There may be infinite sets which are larger than countable sets (we'll come back to this later), but there are no infinite sets smaller than countable.

This has a useful implication. If we have an infinite set, and a one-to-one function from that set to the natural numbers, that function does not have to be onto in order to prove that the infinite set is countable. If it is one-to-one and the set is infinite, the range of the function is an infinite subset of the natural numbers. As a result of this theorem, the subset of the natural numbers is countable. The function is both one-to-one and onto that countable subset, and therefore the original infinite set is countable. When trying to prove that a set is countable, it may be easier to define a one-to-one function than a function that is both one-to-one and onto, and as long as the set is infinite, just being one-to-one is good enough to show that it is countable.

The topic this time was showing that infinite sets which look smaller than the natural numbers in fact have the same cardinality as the natural numbers. Next time we will look at sets which look larger than the natural numbers.

0 comments