**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*

_{1}is

**bigger**than the set

*S*

_{2}if and only if:

- A subset of
*S*_{1}can be put into one-to-one correspondence with*S*_{2}, and *S*_{2}cannot be put into one-to-one correspondence with*S*_{1}.

**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 ofSince each singleton {a} is a subset ofS}.

*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 ∈orf(a)

a ∉Define the setf(a).

*T*to be the set of all elements in

*S*that map under

*f*to a set not containing themselves:

SinceT= { a | a ∈Sand a ∉f(a)}

*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

Now consider whether or notf(b) =T.

b ∈Suppose true. But, by the definition ofT.

*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:

(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_{0}= { N, P(N), P(P(N)), ..., P^{n}(N), ...}

One can even imagine constructing a power set of all these difference size infinite sets in this sequence of sequences of sets:U_{1}= {U_{0}, P(U_{0}), P(P(U_{0})), ..., P^{n}(U_{0}), ...}.

P( {The definitions of infinite sets need not stop here.U_{0},U_{1},U_{2}), ...} )

**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

## 2 comments:

My route into this was chapter 9 of Ian Stewart's

Concepts of Modern Mathematics25 years ago (and then 10 years old). I loved the delayed reporting until chapter 20 of Cohen's 1963 theorem on whether the cardinality of the set of real numbers is the next caridnal after cardinality of the set of natural numbers.(I must re-read the book.)

I don't know Ian Stewart. Cosma, however, recommends Stewart's

Does God Play Dice?. He further says: "Dis-recommended: James Gleick,Chaos: The Making of a New Science(Yes, I'm completely serious about dis-recommending this. Get hold of Ian Stewart's book above, instead.)" I find this quite surprising.Post a Comment