Not all infinite sets are the same. One way to distinguish between these sets is by asking if the set is countably infinite or not. In this way, we say that infinite sets are either countable or uncountable. We will consider several examples of infinite sets and determine which of these are uncountable.

## Countably Infinite

We begin by ruling out several examples of infinite sets. Many of the infinite sets that we would immediately think of are found to be countably infinite. This means that they can be put into a one-to-one correspondence with the natural numbers.

The natural numbers, integers, and rational numbers are all countably infinite. Any union or intersection of countably infinite sets is also countable. The Cartesian product of any number of countable sets is countable. Any subset of a countable set is also countable.

## Uncountable

The most common way that uncountable sets are introduced is in considering the interval (0, 1) of real numbers. From this fact, and the one-to-one function *f*( *x* ) = *bx* + *a*. it is a straightforward corollary to show that any interval (*a*, *b*) of real numbers is uncountably infinite.

The entire set of real numbers is also uncountable. One way to show this is to use the one-to-one tangent function *f* ( *x* ) = tan *x*. The domain of this function is the interval (-π/2, π/2), an uncountable set, and the range is the set of all real numbers.

## Other Uncountable Sets

The operations of basic set theory can be used to produce more examples of uncountably infinite sets:

- If
*A*is a subset of*B*and*A*is uncountable, then so is*B*. This provides a more straightforward proof that the entire set of real numbers is uncountable. - If
*A*is uncountable and*B*is any set, then the union*A*U*B*is also uncountable. - If
*A*is uncountable and*B*is any set, then the Cartesian product*A*x*B*is also uncountable. - If
*A*is infinite (even countably infinite) then the power set of*A*is uncountable.

Two other examples, which are related to one another are somewhat surprising. Not every subset of the real numbers is uncountably infinite (indeed, the rational numbers form a countable subset of the reals that is also dense). Certain subsets are uncountably infinite.

One of these uncountably infinite subsets involves certain types of decimal expansions. If we choose two numerals and form every possible decimal expansion with only these two digits, then the resulting infinite set is uncountable.

Another set is more complicated to construct and is also uncountable. Start with the closed interval [0,1]. Remove the middle third of this set, resulting in [0, 1/3] U [2/3, 1]. Now remove the middle third of each of the remaining pieces of the set. So (1/9, 2/9) and (7/9, 8/9) is removed. We continue in this fashion. The set of points that remain after all of these intervals are removed is not an interval, however, it is uncountably infinite. This set is called the Cantor Set.

There are infinitely many uncountable sets, but the above examples are some of the most commonly encountered sets.