Cours-M1-0708

Informations

• Publié par: Nishur
• Nombre de lectures: 18
• Langue: Français

Extrait

Premiµere partie
Th¶eorie des ensembles
16
Chapitre 1
Ensembles ordonn¶es, ordinaux
Ce chapitre est consacr¶e µa l’¶etude des propri¶et¶es fondamentales des ordinaux. Les ordinaux
nesonten fait quedes ensemblesmunisd’une certainerelationd’ordre.Pourtantcettestructure
sisimplesu–tpourleuraccorderlestatutd’unit¶edemesuredelatailled’unensemble.Ainsi,les
ordinauxofirentuneg¶en¶eralisationnaturelledesnombresnaturels.Commechaqueg¶en¶eralisation
leur ¶etude n¶ecessite plus de soin en raison des complications suppl¶ementaires qui sont invisibles
au niveau des nombres naturels.
1.1 Ordinaux
D¶eflnition 1.1.1 Soit E un ensemble muni d’une relation binaire R. Voici quelques propri¶et¶es
bien connues dont une telle relation peut jouir :
R R est dite r¶e exive si aRa pour tout a2E.
AR R est dite antir¶e exive si pour tout a2E, a Ra.
2S R est dite sym¶etrique si pour toute paire (a;b)2E , aRb et bRa.
2AntiS R est antisym¶etrique si pour toute paire (a;b)2E , aRb et bRa implique a=b.
2AS R est asym¶etrique si pour toute paire (a;b)2E , il n’est pas le cas que aRb et bRa.
T R est transitive si pour tous a;b;c2E, aRb et bRc implique que aRc.
D¶eflnition 1.1.2 Soit E un ensemble muni d’une relation R binaire.
1. La relation binaire R sur E sera dite relation d’ordre si R est R, AntiS et T.
22. SiR est une relation d’ordre, elle est dite totale ou lin¶eaire si pour toute paire (a;b)2E ,
soit a=b, soit aRb, soit bRa.
3. Si R est une relation d’ordre, elle est dite stricte si elle est AR, AS et T.
4. Un ensemble ordonn¶e est dit bien ordonn¶e si chacune de ses parties non vides a un plus
petit ¶el¶ement. L’ordre d’un ensemble bien ordonn¶e est dit un bon ordre.
La paire (E;R) est, ouµ E est un ensemble ordonn¶e, est un exemple de l’une des notions les
plusimportantesdececours,celled’unestructure,uneentit¶eform¶eeparunensemblesous-jacent
muni ¶eventuellement des relations et des fonctions et muni toujours de la relation d’¶egalit¶e.
Nous avons fait certaines d¶eflnitions. Les exemples de relations d’ordre sont bien connus.
D¶emontrons donc quelques lemmes pour compl¶eter le paysage math¶ematique de nos premiers
pas.
Lemme 1.1.3 Soit (E;<) un bon ordre. Alors l’application identit¶e est le seul automorphisme
de (E;<). En d’autres termes, c’est une structure dont le groupe d’automorphismes est trivial,
une structure rigide.
Preuve. Un automorphisme f de la structure (E;<) est une bijection telle que x < y si et
seulement si f(x) < f(y). L’automorphisme f n’est pas l’identit¶e alors si et seulement si D =
36
6
6
6
6
¶4 CHAPITRE 1. ENSEMBLES ORDONNES, ORDINAUX
¡1fx 2 Ejf(x) = xg = ;. L’ensemble D est le support de f, et bien sur^ celui de f aussi. Soit
¡1alors x 2 D le plus petit ¶el¶ement de D. Si f(x) < x alors x = f (f(x)) = f(x), absurde.
¡1 ¡1 ¡1 ¡1Alors f(x) > x. Or ceci ¶equivaut µa x = f (f(x)) > f (x). Donc f(f (x)) = f (x), Or
¡1x=f(f (x)) aussi, absurde.⁄
On d¶eflnit un isomorphisme entre deux structures ordonn¶ees de fa»con analogue µa la notion
d’automorphisme d’un ensemble ordonn¶e, une bijection qui pr¶eserve la structure.
Lemme 1.1.4 Soient (E;<) et (F;`) deux ensembles bien ordonn¶es. Si ces deux structures
sont isomorphes, il existe un seul isomorphisme entre les deux.
Preuve. Ce r¶esultat d¶ecoule du lemme 1.1.3 puisque si f et g sont deux isomorphismes de
¡1(E;<) vers (F;`) alors fg est un automorphisme de (E;<).⁄
Lemme 1.1.5 Si (E;<) est un ensemble strictement bien ordonn¶e. Si a 2 E alors (E;<) et
fb2Ejb<ag ne sont pas isomorphes.
Preuve. Supposons par l’absurde qu’un isomorphisme f existe. Alors f(a) = a puisque a 62
fb2Ejb<ag. Doncfx2Ejf(x)=xg=;. On peut raisonner comme dans la preuve du lemme
1.1.3.⁄
Exemple 1.1.1 Soit(E;2)unensemblemunidelarelationd’appartenanceusuelle.Supposons
que pour tout fi2E, fi soit un sous-ensemble de E. Voici un exemple :
ff;g;ff;ggg :
Notonsquenotreexemplen’existeraitpassionn’¶etaitpasassur¶edel’existencede;.Rassurons-
nous :
Axiome d’existence : Il existe un ensemble sans ¶el¶ements. Dans le \langage" de notre struc-
ture ordonn¶ee, on peut formellement exprimer cet ¶enonc¶e : 9x8y(y62x).
La relation 2 d¶eflnit dans l’ensemble E une relation d’ordre. Motiv¶e par ce constat, nous
introduisons une notion importante :
D¶eflnition 1.1.6 Un ensemble E est dit transitif si la relation2 y d¶eflnit une relation d’ordre,
en d’autres terms si pour tout x2E, x‰E (tout ¶el¶ement de E en est une partie).
Soulignons que cette relation d’ordre n’est pas n¶ecessairement lin¶eaire. Voici un ensemble
transitif qui n’est pourtant pas totalement ordonn¶e :
f;;f;g;ff;ggg :
D¶eflnition 1.1.7 Un ensemble est un ordinal s’il est strictement et bien ordonn¶e par la relation
d’appartenance.
Exemple 1.1.2 La motivation pour la notion d’ordinal est de trouver des exemples canoniques
de bons ordres qui g¶en¶eralisent nombres naturels :
0 ;
1 f;g
2 f;;f;gg
3 f;;f;g;f;;f;ggg
...6
1.1. ORDINAUX 5
Axiome de l’inflni : Il existe un ensemble inductif. Plus formellement,
9x(02x^8y((y2x)!S(y)2x)) :
La lettre S est utilis¶ee pour noter l’op¶eration successeur sur les ensembles :
Si x est un ensemble, alors S(x)=x[fxg :
Le nouvel axiome est su–sant pour continuer :
! =f0;1;2;3;:::g
S(!)=!+1=![f!g
!+2;:::
!:2=!+!
!:3;!:4;:::
2! =!:!
...
Nous pouvons proc¶eder µa d¶emontrer certaines propri¶et¶es de base des ordinaux. Mais puisque
nous avons d¶ej a pris l’habitude des axiomes, pourquoi ne pas en introduire un autre. D’ailleurs
ce nouvel axiome, certains raisonnements manqueraient de rigueur dans ce qui suit tant cet
axiomeestnaturel.Enfait,nousintroduironsunsch¶emad’axiomespuisquepourtoutepropri¶et¶e,
l’axiome a un ¶enonc¶e particulier.
Nous venons d’utiliser un autre mot dangeureusement naturel, µa savoir \propri¶et¶e". C’est
une notion qu’on pourrait rendre rigoureuse dµes maintenant en ayant recours aux notions de la
th¶eorie des modµeles telles que les langages, les formules du premier ordre, etc. Nous pr¶ef¶erons
attendreavantlapartieconsacr¶eeµalath¶eoriedesmodµelesdececoursavantd’atteindreceniveau
de rigueur et nous nous contentons de dire qu’une propri¶et¶e dans ce contexte est une propri¶et¶e
math¶ematique sur des ensembles qui s’exprime en quantiflant les variables et les joignant soit
par des symboliques logiques, soit par2, soit par = (\une propri¶et¶e d¶eflnissable").
Sch¶ema d’Axiome de Compr¶ehension : Soit P(x) une propri¶et¶e. Pour tout ensemble A, il
existe un ensemble B tel que x2B si et seulement si x2A et P(x) est vraie.
Ce sch¶ema d’axiome, si naturel soit-il, est crucial pour ¶eviter les paradoxes du type \l’ensemble
de tous les ensembles".
Lemme 1.1.8 Si fi et fl sont deux ordinaux tels que fi‰fl et que fi=fl alors fi2fl.
Preuve. Soient fi et fl comme dans l’¶enonc¶e. On note ° le plus petit ¶el¶ement de l’ensemble
fl¡fi par rapport µa l’ordre d¶eflni sur fl par2. Ceci est consistant puisque fl est par hypothµese
un ordinal. Il su–ra de montrer que ° =fi.
Notons que fl ¶etant un ordinal, tout¶el¶ement de ° appartient µa fl. Alors un¶el¶ement – tel que
–2°¡fi contredirait le choix minimal de °. Ainsi, °µfi.
Si – 2 fi, alors comme fl est totalement ordonn¶e par l’appartenance, soit – 2 °, soit – = °,
soit ° 2 –. La deuxiµeme possibilit¶e est exclue puisque par hypothµese ° 62 fi. Il en est de m^eme
pour la troisiµeme puisque par hypothµese fi est un ordinal, donc transitivement ordonn¶e par
l’appartenance et que nous supposons °62fi. Ainsi, fiµ°.⁄
Lemme 1.1.9 Si fi et fl sont deux ordinaux, il en est de m^eme pour leurs intersections.
Preuve. La v¶eriflcation des propri¶et¶es de bon ordre strict ¶etant laiss¶ee aux bons soins des
lecteurs, v¶eriflons que 2 est transitif. Or, fi et fl sont transitivement ordonn¶es par 2. Donc, si
°2fi\fl, alors °‰fi\fl.⁄6
6
6
¶6 CHAPITRE 1. ENSEMBLES ORDONNES, ORDINAUX
Notation 1.1.10 Si fi et fl sont des ordinaux, alors sauf mention contraire, fi < fl et fl < fi
auront le m^eme sens q ue fi2fl et fl2fi respectivement.
Proposition 1.1.11
1. Si fi et fl sont deux ordinaux alors fi<fl ou fi=fl ou fl <fi.
2. Soit E un ensemble d’ordinaux. Alors E est bien ordonn¶e par <.
3. Si fi est un ordinal alors il en est de m^eme pour S(fi). Il n’existe pas d’ordinal entre fi et
S(fi).
4. Il n’existe pas d’ensemble de tous les ordinaux.
Preuve. (1) D’aprµes le lemme 1.1.9, fi\fl est un ordinal. Alors, le lemme 1.1.8 montre que si
fi\fl = fi et que fi\fl = fl alors fi\fl 2 fi et que fi\fl 2 fl. Alors fi\fl 2 fi\fl. Or ceci est
impossible en raison de l’asym&#