Infinite Sets

by George E. Hrabovsky, President, MAST

Where We Have Been

We have been continuing our focus on the foundations of mathematics. We have discussed the basic ideas of set theory and logic, proof techniques, quantifiers, and have begun to develop the number system. We have laid the groundwork for discussing the real numbers by exploring sequences. Last column we discussed functions and relations.

Where Will We Go in This Column

In this column we will discuss the concept and some ramifications of infinite sets.

Cardinals of Power Sets

Recall from the column. "Setting up for the Future," that the set of all subsets is called the power set. Recall too that the power set of any set of n elements will have elements. It seems as though the cardinal number of a set is less than the cardinal number of the power set. Thus for the set A we have,

Assume we are dealing with the empty set , then and . Clearly, in this case, . If A is finite with n elements, we have,

On the other hand, if A is infinite we need to look at this carefully. We can be sure that,

because the cardinal number of A is equal to the cardinal number of the set of singleton subsets of A.
Suppose that

Then there has to be some function,

such that, given two elements x, y of A,

An additional requirement is that

If this is the case, and are distinct subsets of A. Then, given the subset B of A, there is a unique element y of A such that . We can define B as,

Now, since y is an element of A and , then we have to ask where y is? It must either be in B or in A\B. This is an absurd situation, this implies that

an absurd result, and

$y ∈ A \ B ==> y ∉ f(y) = B ==> y ∈ B,$

another absurd result. The only possible conclusion is that there is no element y of A such that , thus

The only remaining possibility is that

This is valid for any non-empty set.

Aleph-Null

The last section makes an implication that given an infinite set A we can form an infinite sequence of sets,

This sequence is increasing and composed of infinite cardinal numbers. This being the case it seems reasonable to think that there might be a smallest infinite cardinal. It turns out that there is such a cardinal, we call it aleph-null.
Given an infinite set A we choose an element . We choose a subset $A _ 1 = A \ {x _ 1}$ . We next choose and $A _ 2 = A _ 1 \ {x _ 2} = A \ {x _ 1, x _ 2}$ . We can continue this process endlessly since A is infinite till we get ${x _ 1, x _ 2, x _ 3, ..., x _ n}$ . We next get from $A _ n = A \ {x _ 1, x _ 2, x _ 3, ..., x _ n}$ . If we define $A _ 0 = {x _ 1, x _ 2, x _ 3, ...}$ . This inductively leads us to the conclusion that