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.
Thanks.
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
existence.
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
themselves.
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:
0--------omega
1--------0
2--------1
3--------2
...
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.
Bruno
http://iridia.ulb.ac.be/~marchal/
--~--~---------~--~----~------------~-------~--~----~
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.domain.name.hidden
To unsubscribe from this group, send email to everything-list-unsubscribe.domain.name.hidden
For more options, visit this group at
http://groups.google.com/group/everything-list?hl=en
-~----------~----~----~----~------~----~------~--~---
Received on Tue Nov 20 2007 - 05:59:58 PST