We can use cardinality to compare the size of different sets. Last time we discussed how to show that two sets have the same cardinality. This time we will look at three basic classes of cardinality. Sets can have finite cardinality, countable cardinality, or uncountable cardinality.

Finite cardinality is the most straightforward. Mathematically, take a set of natural numbers, such that the set includes every natural number less than or equal to some natural number k. Call this set J_{k}. For some set X, if we can define a one-to-one, onto function f which maps every member of J_{k} to every member of X, then J_{k}∼X and the cardinality of X is k. This is pretty much as simple as lining the members of X up in a row and counting them off. Finite sets are easy to understand and make intuitive sense.

My textbook (Principles of Mathematical Analysis, Third Edition, by Rudin) uses the word countable to mean countably infinite. On the one hand, this feels slightly misleading, since finite sets can obviously be counted. However, as I've been working with the concept, I think there are some good reasons for this, and I will use the same terminology to be consistent. A countable set is one which has a one-to-one, onto function mapping to the set of natural numbers. Since the natural numbers are infinite, countable sets are infinite. Infinity is deeply counter-intuitive, and the behavior of countable sets is therefore also deeply counter-intuitive. I plan to go into some detail on examples of countable sets, both to demonstrate that they defy expectations and in the hope that with enough examples, countable sets will start to make sense.

Finally, there are uncountable sets. These are sets which are infinite, but for which there does not exist a one-to-one, onto mapping to the natural numbers. Once countable sets start making sense, it may be reasonable to ask whether any sets are uncountable. We can demonstrate a way to contruct an uncountable set and prove that it's not countable, but we need to work on countable sets first.