Infinities Of Infinities

1.0 Introduction

This is mathematics, not economics. It is meant to be an introduction to how abstract mathematicians can be.

2.0 Some Definitions for Set Theory

Two sets are the same size if and only if they can be put into a one-to-one correspondence with each other.

A set S₁ is bigger than the set S₂ if and only if:

• A subset of S₁ can be put into one-to-one correspondence with S₂, and
• S₂ cannot be put into one-to-one correspondence with S₁.

A set is countably infinite if and only if it can be put into one-to-one correspondence with the set of natural numbers N = {0, 1, 2, ...}. (The integers and the rational numbers are both countably infinite.)

The power set P(S) formed from the set S is the set of all subsets of S. For example, the power set for the set {a, b} contains four elements:

P( {a,b} ) = {S | S ⊂ {a, b}.} = { ∅, {a}, {b}, {a, b} }

3.0 A Theorem

Theorem For all sets S, the power set P(S) is bigger than the set S.

Proof: First, show that a subset of P(S) can be put into one-to-one correspondence with S. Consider the set of singletons:

{ {a} | a is an element of S }.

Since each singleton {a} is a subset of S, the set of all singletons is a subset of P(S). And the set of all singletons maps one-to-one to S.

Next, show, by a proof by contradiction, that P(S) cannot be put into one-to-one correspondence with S. Suppose that there exists a one-to-one function f that maps S into P(S).

Notice that, for all a ∈ S, f(a) is a subset of S. For any given a in S, either

a ∈ f(a)

or

a ∉ f(a).

Define the set T to be the set of all elements in S that map under f to a set not containing themselves:

T = { a | a ∈ S and a ∉ f(a)}

Since f is one-to-one and T is a (possibly empty) subset of S, there exists, by hypothesis, an element b in S such that

f(b) = T.

Now consider whether or not

b ∈ T.

Suppose true. But, by the definition of T as the set of elements of S that are not elements of the subset of S that they map to, b cannot be in f(b), that is, T. But, if b is not in f(b), by the definition of T, b must be in T. So either way yields a contradiction. Thus, no such b can exist.

So I have shown that there does not exist an element b in S that maps under f to T. Yet T is in P(S). Thus, f cannot be one-to-one. Which was to be demonstrated.

4.0 Applying the Theorem to the Set of Natural Numbers

An interesting property of the above proof is that it applies to both finite sets and infinite sets. So start with N, the set of natural numbers. N contains an infinite number of elements. But, by the theorem, P(N), the set of all subsets of the natural numbers, is a set containing a bigger infinity. One can go on to form a set of infinite sets, each with a bigger size infinity:

U₀ = { N, P(N), P(P(N)), ..., Pⁿ(N), ...}

(Under the Zermelo Frankel axioms for set theory, the elements of a set do not need to all be of the same "type".) One can repeat the process of forming a sequence of power sets:

U₁ = { U₀, P(U₀), P(P(U₀)), ..., Pⁿ(U₀), ...}.

One can even imagine constructing a power set of all these difference size infinite sets in this sequence of sequences of sets:

P( { U₀, U₁, U₂), ...} )

The definitions of infinite sets need not stop here.

4.0 Conclusion
I don't find the above hard to follow if I think of it as merely a matter of syntactic manipulation of symbols. Do I have a clear idea of these infinities of different size infinities after every point in this sequence of definitions? Does anybody? This is not so clear to me.

Reference

• Paul R. Halmos (1960) Naive Set Theory, Springer Verlag