Hi Mirek,

## Advertising

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 [EMAIL PROTECTED] To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/everything-list?hl=en -~----------~----~----~----~------~----~------~--~---