Comparing The Sizes of Infinite Sets

Melody Laycock
Math 300

Abstract

This article shows how to compare the sizes of infinite sets. Using the method of diagonalization, we show that a set cannot be put into one-to-one correspondence with its power set and that the real numbers between 0 and 1 are uncountable.

1  Introduction

For finite sets it is easy to tell whether two sets are the same size. We count the elements in each and compare the results. Infinite sets cannot be compared in this way. We need to make a new definition of when two sets are the same size. To do this we need some terms about functions. A function f is one-to-one if f(a) = f(b) implies a = b. A function f is onto if for every element y of the range, there exists an element x such that f(x) = y.

One way of looking at counting the elements in a finite set is to say we are building a function from the set to a subset of the natural numbers. So we know {a, b, c, d} has four elements because we can build a function f: {a, b, c, d} ® {1,2, 3, 4} which is one-to-one and onto. One example of such a function is f(a) = 1, f(b) = 2,f(c) = 4, and f(d) = 3. The function f is called a one-to-one correspondence between the two sets. In a similar way, we can build a one-to-one correspondence g: {q, s, r, t}® {a,b,c,d}, so we say {a, b, c, d} and {q, r, s,t} have the same size. This method works for infinite sets as well since it no longer involves counting the elements.

We say two sets S and T are the ßame size" if we can build a function f:S® T that is one-to-one and onto. For example the natural numbers and the even numbers are the same size since the function f(x) = 2x is one-to-one and maps the natural numbers onto the even numbers. Next we will apply this to power sets.

2  A set and its power set

The power set of a set S (denoted P(S)) is the set of all subsets of S. We know that given a set S = {a, b, c} the power set of S is P(S) = { {}, {a}, {b}, {c}, {a,b}, {a,c}, {b,c}, {a,b,c}}. It seems logical that a set and its power set cannot be put into one-to-one correspondence. Each element of S corresponds to an element of the power set: a® {a}, b® {b}, c® {c} and there are other elements of the power set left over. This, however is not a proof that they are different sizes. We have an example of a function which is not onto, but that does not mean that no such function can exist. To understand the difference, consider the natural numbers (N) and the negative integers (Z-). We can build a function f: N ® Z- which is not one-to-one and onto, specifically f(x) = -2x. This function has the natural numbers as domain and the negative integers as its codomain, but misses some of them (-1 for example) so it is not onto. Using the function f(x) = -x however, we see that the two sets can be put into one-to-one correspondence.

If we restrict our attention to finite sets we can prove that if a set S has size n, then its power set P(S) has size 2n. We denote the size of S as |S|. For our example set |S| = 3 and |P(S)| = 8 = 23. This style of proof cannot be extended to infinite sets because we cannot find the number n which represents the size of the infinite set. That means we need another approach. We will use a method of proof called diagonalization. It involves assuming that an onto function exists and building an element of the target set which cannot be an output of the function.

Let S be a non-empty set. Assume that there exists a function f : S® P(S) such that f is one-to-one and onto. Inputs to the function f are elements of S and the outputs are elements of P(S). An element of P(S) is a subset of S, so for any a Î S, f(a) is a subset of S. This means that either a Î f(a) or a Ï f(a). Let E = { a Î S| a Ï f(a) } . For example if f(a) = {a,b} then a Ï E and if f(b) = {c} then b Î E. Since E Ì S , we know that E Î P(S). So since f is onto there exists an e such that f(e) = E. Now consider whether e Î E. If e Î E, then by the definition of E, e Ï f(e). But f(e) = E so e Ï E which is a contradiction. If e Ï E then e Ï f(e) and so e Î E by the definition of E. This is also a contradiction. This shows that our assumption that there is a one-to-one and onto function from S to P(S) is false.

We have shown that a set S and its power set P(S) cannot be the same size. In fact, the diagonalization argument shows that the power set is bigger since it has extra elements not covered by the attempted correspondence. The name diagonalization is related to the proof that the real numbers (0,1) cannot be put into one-to-one correspondence with the natural numbers.

3  Natural Numbers vs. Real numbers

If an infinite set can be put into one-to-one correspondence with the natural numbers (N) it is called a countable set. Otherwise it is uncountable. The real numbers are uncountable. In fact, we can show that there are more real numbers between 0 and 1 than there are natural numbers. This is done with a diagonalization argument.

We want to show that there is no one-to-one and onto function mapping N ® (0,1). (The open interval from 0 to 1 is denoted (0,1). Assume that f is such a function. We can list the outputs of f by input. One example of a possible f might be:

f(1)
=
0.800 ...
f(2)
=
0.222 ...
f(3)
=
0.3110 ...
:
Each of these is an infinite decimal f(n) = 0.dn1dn2dn3 ... We build a new decimal based on the diagonal d11d22d33 .... Let D = 0.x1x2x3... where
xi = ì
í
î
0
if
dii = 1,
1
if
dii ¹ 1
So for our example function f, D = 0.110 .... We know D is a real number between 0 and 1 so if f is onto, there is some n so that f(n) = D. We know that n ¹ 1 since the first digit of f(1) is different from D by construction. In fact n cannot be any natural number. We see this as follows. We know that the nth digit of f(n) is dnn and the nth digit of D is xi. If dnn = 1 then xn = 0 from the definition of xi, so they are not equal. Also if dnn ¹ 1 then by definition xn = 1 and again they are not equal. Thus, for any n, f(n) and D are different in the nth decimal place. This contradicts the existence of an n such that f(n) = D. Since we have reached a contradiction, our assumption that a one-to-one correspondence exists between N and (0,1) is false. We have shown that the interval (0,1) cannot be put into one-to-one correspondence with the natural numbers and is therefore uncountable.

4  Conclusion

Using the concept of one-to-one correspondence we can compare the sizes of infinite sets. To show that two sets are the same size we simply need to demonstrate a one-to-one and onto function between the two. If, however, we need to prove that two sets are not the same size, we have to prove that there does not exist a function between the sets that is one-to-one and onto. One way of doing this is through diagonalization. We demonstrated this method in two examples. In both we use a specific form of a proof by contradiction. The RAA hypothesis is that a one-to-one correspondence exists. We construct an element in the target set which is not in the image of the function. We see this when we get a result of the form A Þ ~ A and ~ A Þ A. Thus the function fails to be onto after all. Diagonalization is not a very obvious way of proving things, but it is important. One application of this proof method is in computer science where it is used to prove the undecidability of the halting problem [1]. This is the proof that there are problems that a computer cannot solve.

References

[1]
Michael Sipser, Introduction to the Theory of Computation, PWS Publishing Co., Boston, 1997.

File translated from TEX by TTH, version 1.96.
On 30 Apr 1999, 16:13.