After two thousand years of confusion, at last some straight talk. What follows is not too difficult, although it does require a little reflection, some knowledge of sets, some logic, and functions. We hope you enjoy it.
The first time through, you should read this in order. Nevertheless, here is a menu with hyperlinks for convenient jumping:
Equipotent Sets
Without having even a single number you can tell if two groups of things have the same number of items. By pairing the objects in one group with those in the other group -- if there is nothing left over in either group, then we have the same number in each group.
If a dance is held for couples only, then there should be the same number of boys and girls at the dance. If people are seated around a table, no one is left standing, and there are no empty chairs; then the number of chairs equals the number of people. It is believed that in early societies herdsmen kept track of their cattle by pairing them with stones. In this way, without the use of an extensive number system, they could be sure they had not lost their 'sheep.'
Two sets A and B are equipotent if their elements can be paired, or put into a one-to-one correspondence. In terms of functions this means there is a one-to-one function from one set onto the other. Symbolically,
A ~ B Û $ f: A ® B, such that f is a one-to-one function.
Finite sets are equipotent if they have the same number of elements. Let A = {1, 2, 3, 4}, B = {, D, à, #} and C = {a, b, c}. Notice that A ~ B but not A ~ C since the elements of A and B can be paired (several ways) but not those of B and C.
Back to the menu
Infinite Sets
So far so good. Now what about infinite sets? Are there the same number of even whole numbers, as there are of all whole numbers -- or should there be only half as many even whole numbers?
After all, the even whole numbers can be paired with all whole numbers: just pair each number with one twice its size. Five is paired with ten, and eight with sixteen, etc. But the set of even whole numbers is a subset of the set of all whole numbers. Should a set have the same number of elements as a part of itself? Isn't the whole supposed to be greater than its parts?
Instead of seeing a contradiction in this situation, what Cantor did was to use it as a definition of an infinite set. If you have a collection of things, and you can pair the collection up with a collection consisting of a part of itself, then both collections are infinite.
Now we repeat the above in more mathematical terms. Let A be a proper subset of B. Is it possible that A ~ B? That is, can a set be paired with a proper subset of itself? Surprisingly, this is possible, but only for infinite sets -- a fact that can be used to define infinite sets.
Definition: A set A is Infinite if A ~ B where B Í A but B ¹ A, for some set B.
For example, the set of natural numbers N = {1, 2, 3, ... } can be paired with the set of even numbers E = {2, 4, 6, ... } by the function f(n) = 2n, which is one-to-one and onto E. For a second example we have g(x) = x / (1 + |x|) pairing R with the interval (-1, 1). Thus, R ~ (-1, 1), which shows that R is an infinite set.
Back to the menu
Denumerable Sets
It turns out that there are different sizes of infinite sets. We don't just have one, two, three, ... , infinity. Rather, the situation is more like: one, two, three, ... , infinityone, infinitytwo, infinitythree, .... The first of all the infinities is called denumerably infinite, or countably infinite. These are the infinite sets that can be counted with the whole numbers.
An infinite set S is denumerable if S ~ N. We have seen that E, the even numbers, is denumerable. Can you show that Z, the positive and negative integers, is denumerable? Surprisingly, even the set Q = { a / b | a, b Î Z Ù b ¹ 0 } is denumerable. We show only that Q+ is denumerable. Here is the pairing.
Notice that this pairing does not preserve the natural ordering of the rationals. Nevertheless, Q+ ~ N, so Q+ is denumerable. Can you show that Q is denumerable?
Nondenumerable Sets
The infinities higher than denumerable are lumpped together and called, quite naturally, nondenumerable infinities. The most familiar example of a nondenumerabe infinite set is the set of real numbers. (We ask you to show this below.) Even intervals of real numbers are nondenumerable. Again we see an example of having the same number (since a pairing is possible) of elements in a set and one of its proper subsets.
If a set is infinite and it cannot be paired with N, then it has a higher form of infinity; it is nondenumerable. Take (0, 1] for example. Suppose (for purposes of contradiction) that (0, 1] ~ N. Then there is a pairing of N and (0, 1]. Pick any such pairing, say
For reals like 0.5 which can also be represented by 0.4999... we have decided to use 0,4999.... Thus each ai,j Î {0, 1, 2, 3, ... , 9} and each decimal expansion has infinitly many nonzero entries. We get our contradiciton by finding an element of (0, 1] not on the above list. Pass down the diagonal a1,1, a2,2, a3,3, ... changing each entry to some other nonzero digit b1, b2, b3, .... All that is required is that ai,j ¹ bj, and bj ¹ 0 for each i Î N. The number
0.b1b2b3... Î (0, 1]
differs from each number on our list, since it differs from the first entry in the first place, the second entry in the second place, and so on. Thus N ~ (0, 1] is false since any pairing is subject to the above argument.
Back to the menu
Higher Infinities
Do you think that all nondenumerable sets are equipotent? The answer is no. Although it is not shown here
F = { f | f : R ® R and f is a function }
cannot be paired with R. In other words, there are more functions than there are real numbers. Actually, there are infinitely many different sizes of infinite sets. Mind boggling!
Back to the menu
