Countability
A set, which should be thought of simply as a collection of objects, is called countable if it either consists of a finite number of objects or if the objects can be put in one to one correspondence with the integers. Two sets are defined to be of the same cardinality if the elements of one set can be mapped in a one to one fashion onto the elements of the second set. Thus infinite sets that are countable have the same cardinality as the integers. As a simple example, consider the set of even integers. Naively one might think that the set of even integers is somehow smaller than the set of all integers. However consider the function f(n) = n/2. This function exhibits a one-to-one mapping of the even integers onto all integers, proving that the set of even integers is countable. In a similar fashion it can be shown that any subset of a countable set is countable.
Not all infinite sets have the same cardinality. The set of real numbers for instance is strictly larger than the set of integers and hence the reals are uncountable. One can prove this fact by contradiction. First assume that one could assign to every real nurmber an integer in a one-to-one fashion. Now construct a real number whose ith digit is one plus the ith digit of the real number assigned the integer i. This real number has been constructed to be different from every real number that has already been assigned an integer and hence is not in correspondence with any integer.
The assumption is then violated proving that the reals are uncountable.
A natural question to ask is what other sets besides the integers and their subsets are countable. Consider the rationals. Again one may naively think that there are more rationals than integers, but fewer rationals than reals. Surprisingly enough the rationals are countable. Imagine arranging the rationals in two dimensional table T[p,q] with p and q integers. One can think of the contents of table location T[p,q] as the rational p/q. Now the entries of the table can be numbered diagonally. This diagonal numbering scheme for the entries places the rationals in one to one correspondence with the integers. This proof can be generalized to show that a finite cartesian product of countable sets is countable. However it is not true that a countable product of countable sets is countable. But a countable union of countable sets is countable. Also, although any subset of a countable set is countable, the set of all subsets of a countable set is not. Clearly when sets become infinite, our naïve intuition about the relative size of infinite sets is not always correct. In this situation the set theoretic notion of cardinality is an important way to think about the size of infinite sets and the notion of countability captures the idea that an infinite set has the same size as the set of integers.
This is the complete article, containing 494 words
(approx. 2 pages at 300 words per page).
