Hi Mirek,

Le 19-nov.-07, à 20:14, Mirek Dobsicek a écrit :

> Hi Bruno,
> thank you for posting the solutions. Of course, I solved it by myself
> and it was a fine relaxing time to do the paper work trying to be
> rigorous, however, your solutions gave me additional insights, nice.
> I am on the board for the sequel.


I will explain soon (this "afternoon") how Cantor managed to show that 
some infinite set "have more elements" than the infinite set N,  in the 
sense that there will be no bijection from N to such set, despite 
obvious bijection between N and subset of such set.

I am sure most of you know that proof by diagonal. However, the goal 
will be to show later how a similar reasoning can put a serious doubt 
on the existence of universal machine, and on serious constraints such 
machine have to live with in case we continue to believe in their 

Before doing that, I want to explain briefly the difference between 
ordinal and cardinal. This explanation is not necessary for the sequel, 
but it could help.

I will also use the set representation of numbers and ordinals. So I 
will represent the number 0 by the empty set, and the number n by the 
set of numbers strictly little than n.

So 0 = { },  1 = {0} = {{}},   2 = {0, 1} = {{} {{}}},   3 = {0, 1, 2}, 
4 = {0, 1, 2, 3}, ...
then omega = N =  {0, 1, 2, 3 ...} is the least infinite ordinal. The 
advantage of such a representation is that "belongness" modelizes the 
strictly-lesser-than relation, and subsetness modelizes the 
lesser-than-or equal. I recall that A is a subset of B, if for all x, x 
belongs to A entails that x belongs to B. In particular for all set A x 
belongs to A entails x belongs to A, so all sets are subset of 

An ordinal is defined by being a linear well founded order. 
Well-foundness means that all subsets have a least element.

The finite ordinal are thus the natural numbers. They all have 
different cardinals. That is, two different natural numbers (= 
different finite ordinal) have different cardinality (different 
"number" of elements). Take 7 and 5, there is no bijection between 
them, for example.

So in the finite realm, ordinal and cardinal coincide.

But infinite ordinals can be different, and still have the same 
cardinality. I have given examples: You can put an infinity of linear 
well founded order on the set N = {0, 1, 2, 3, ...}.
The usual order give the ordinal omega = {0, 1, 2, 3, ...}. Now omega+1 
is the set of all ordinal strictly lesser than omega+1, with the 
convention above. This gives {0, 1, 2, 3, ... omega} = {0, 1, 2, 3, 4, 
....{0, 1, 2, 3, 4, ....}}. As an order, and thus as an ordinal, it is 
different than omega or N. But as a cardinal omega and omega+1 are 
identical, that means (by definition of cardinal) there is a bijection 
between omega and omega+1. Indeed, between  {0, 1, 2, 3, ... omega} and 
{0, 1, 2, 3, ...}, you can build the bijection:

n ------- n-1

All right?    "-----" represents a rope.

To sum up; finite ordinal and finite cardinal coincide. Concerning 
infinite "number" there are much ordinals than cardinals. In between 
two different infinite cardinal, there will be an infinity of ordinal. 
We have already seen that omega, omega+1, ... omega+omega, 
omega+omega+1, ....3.omega, ... 4.omega .... ....omega.omega ..... 
omega.omega.omega, .....omega^omega ..... are all different ordinals, 
but all have the same cardinality.

Don't worry, we will not use that.

Question: are there really two different infinite cardinals? That is, 
are there two infinite sets with different cardinality? That is, are 
there two different infinite sets A and B without any bijection in 
between ? The answer is yes, and that is what cantor has discovered by 
its diagonal construction, and that is the object of the next post. All 
what I did want to say here, is that automatically, in between A and B, 
there will be an infinite amount of different ordinals.



You received this message because you are subscribed to the Google Groups 
"Everything List" group.
To post to this group, send email to [EMAIL PROTECTED]
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at 

Reply via email to