I sum up, a little bit, and then I go quickly, just to provide some  
motivation for the sequel.

We have seen the notion of set. We have seen examples of finite sets  
and infinite sets.

For example the sets

A = {0, 1, 2},

B = {2, 3}

are finite.

The set N = {0, 1, 2, 3, ...} is infinite.

We can make the union of sets, and their intersection:

A union B = {x such-that x is in A OR x is in B} = {0, 1, 2, 3}

A intersection B = {x such-that x is in A AND x (the same x) is in B}  
= {2}. 2 is the only x being both in A and B.


We have seen the notion of subset. X is a subset of Y, if each time  
that x is in X, x is also in Y.

And we have seen the notion of powerset of a set. The powerset is the  
set of all subset of a set.

Example: the powerset of {2, 3} is the set {{ }, {2}, {3}, {2, 3}}.


In particular we have seen that the number of element of the powerset  
of a set with n elements is 2^n.

Example: {2, 3} has two elements, and the powerset of {2, 3}, i.e.   
{{ }, {2}, {3}, {2, 3}} has 2^2 = 4 elements. OK?

We have seen the notion of function from a set A to a set B.

It is just a set of couples (x, y) with x in A and y in B. x is  
supposed to be any elements of A, and y some element of B.

To be a function, a set of couples has to verify the *functional  
condition* that no x is send to two or more different y. This is  
because we want y be depending on x. Think about the function which  
describes how the temperature  evolves with respect to time: an  
instant t cannot be "send" on two different temperature.

Let A = {1, 2} and B = {a, b, c}

F1 = {(1, a), (2, a)}

F2 = {(1, c}, (2, a)}

F1 and F2 are functions.

But the following are not:

G1 = {(1, a), (2, b}, (2, c)}  because 2 is send on two different  

G2 = {(1, a), (2, b), (1, b)} because 1 is send on two different  


We have then consider the set of all functions from A to B, written  
B^A, and seen that this number is equal to
card(B) ^card(A)  where card(A) is the number of elements of A.    A  
is supposed to be a finite set, and later we will see how Cantor will  
generalize the notion of cardinal for infinite sets.

We have then studied the notion of bijection.

A function from A to B is a bijection from A to B when it is both

- ONE-ONE  two different elements of A are send to two different  
elements of B

- ONTO, this means that all elements of B are in the range of the  
function, i.e. for any y in B there is some couple (x, y) in the  

Example: F from {a, b} to {1, 2} with F = {(a, 1}, (b, 2)} is a  
bijection, but G = {(a, 1), (b, 1)} is not because G is not ONTO, nor  


We have seen that if A and B are two finite sets, then we have

A and B have the same number of element if and only if there exists a  
bijection from A to B.


Now I can give you the very ingenious idea from Cantor. Cantor will  
say that two INFINITE sets have the same cardinality if and only if  
there exists a bijection between them.

This leads to some surprises.

Let N = {0, 1, 2, 3, ...} be the usual set of all natural numbers.  
This is obviously an infinite set, all right?
Let 2N = {0, 2, 4, 6, ....} be the set of even numbers. This is  
obviously a subset of N OK?, and actually an infinite subset of N.

Now consider the function from N to 2N which send each n on 2*n. This  
function is one-one. Indeed if n is different from m, 2*n is different  
from 2*m. OK?
And that function, from N to 2N is onto. Indeed any element of 2N, has  
the shape 2*n for some n, and (n, 2*n) belongs to the function.

In extension the bijection is {(0, 0), (1, 2), (2, 4), (3, 6), (4, 8),  
(5, 10), (6, 12), ...}

So here we have the peculiar fact that a bijection can exist between a  
set and some of its proper subset. (A subset of A is a proper subset  
of A if it is different of A).

The first who discovered this is GALILEE. But, alas, he missed Cantor  
discovery. Like Gauss later, such behavior was for them an argument to  
abandon the study of infinite sets. They behave too much weirdly for  


At first sight we could think that all infinite sets have the same  
cardinality. After all those sets are infinite, how could an infinite   
set have a bigger cardinality than another infinite set? This is the  
second surprise, and the main discovery of Cantor: the fact that there  
are some infinite sets B such that there is no bijection between N and  

Cantor will indeed show that there is no bijection between N and N^N,  
nor between N and 2^N. We will study this.

Cantor will prove a general theorem, know as Cantor theorem, which  
asserts that for ANY set A, there are no bijection between A and the  
powerset of A.
The powerset operation leads to a ladder of "bigger infinities".  I  
will come back with some detail later.

Some surprises were BAD surprises. Conceptual problems which Cantor  
will "hide" in its desk, to treat them later. The so-called paradoxes  
of "naïve set theory". The root of what has been called the crisis in  

For example, we could naively consider the set of all sets. Often  
called the universal set, or Universe (of sets). Surely no set can be  
bigger that this one? But by Cantor theorem the powerset of the  
universe has to be bigger than the universe. So there is a problem.

And the naïve conception of sets will lead to many other problems.  
Torgny Tholerus has mentioned some other problems, if you remember.

So what?

Mainly three approaches have been proposed to solve those conceptual  

1) The most liberal one, suggested by Hilbert, who was fond of Cantor  
theory. He said that no one will drive us away from Cantor Paradise.  
He suggested to build a formal system capable of talking about sets,  
and capable of proving the main theorem of Cantor, but free of the  
paradoxes. This will lead to the modern axiomatic trend in  
mathematics. Hilbert asked for the proof of the consistency of such  
formal theories, and this will be shown just impossible, by Gödel.  
Despite this, most mathematicians have followed this path, explicitly  
or implicitly. In most axiomatic set theories, the axiom will prevent,  
for example, the existence of a universal set or universe. To be sure,  
some highly non standard axiomatic set theory allows a Universal set  
to exist, for example Quine new foundations (cf some post by Brian and  

2) The least liberal one, suggested by Brouwer (the main opponent to  
Cantor and Hilbert). To abandon classical logic, and "set realism".  
This consists in abandoning the law of the excluded middle (p or ~p)  
in mathematics, and this will lead to intuitionist mathematics and  
philosophy, which is a form of mathematical solipsism.

3) Intermediate solutions. One will consist in searching a weaker  
notion of function, capable of satisfying both the intuitionist and  
the classical mathematicians. This will lead mathematicians to the  
notion of computable functions, and when Cantor reasoning is applied  
again, this will lead to the (mathematical) notion of universal  
machine. In my opinion: this is the biggest discovery ever done by  
humanity. And both UDA and AUDA are just non sensical without that  
discovery (and this explains why I insist on this). Note that from  
empirical data, we can guess that "nature" has done that discovery and  
has exploited it again, and again, and again, and again ....

            * * *

Exercise: if you have not yet done them, or understand them, please  
take some time to just think about those questions. I have to solve  
them properly to proceed. You may try to read Brent's correct answer  
to some of those questions.

Show that there is a bijection between the following sets:

N and 2N, 3N, 4N, 5N, ....     (nN = the set of multiple of n).

N and Z    (Z = all integers, that is postive and negative integers, Z  
= {... -3, -2, -1, 0, 1, 2, 3, ...}

N and Q  (Q = the reduced fractions, or the decimal periodics)

N and NxN

N and NxNxN.

The powerset of A (finite set) and the set of functions from A to {0, 1}

The powerset of N and the set of functions from N to {0, 1}.

The powerset of N and the real numbers.  (real numbers = finite of  
infinite decimals).

*                                    *

Take it easy, and enjoy if you have the time and taste,



You received this message because you are subscribed to the Google Groups 
"Everything List" group.
To post to this group, send email to everything-list@googlegroups.com
To unsubscribe from this group, send email to 
For more options, visit this group at 

Reply via email to