Chap.3 :

Relations,fonctions,bons ordres

Définition 1 : Une relation est un ensemble R don't tous les éléments sont des paires ordonnées.
R étant une relation,on définit

Remarque 1 : On a clairement
et on peut définir

Définition 2 : f est une fonction ssi f est une relation et

Notations :
signifie :
(1) f est une fonction
(2) dom(f)=A
(3)
,on note f(x) l'unique
est la restriction de f à C.

Définition 3 : f est une injection ssi est une fonction.
f est une surjection ssi Im(f)=B
f est une bijection ssi f est à la fois une injection et une surjection.

Définition 4 : Un «ordre total strict» est une paire ordonnée (A,R),où A est un ensemble et R une relation,vérifiant les propriétés suivantes :
(1) R est transitive sur A :

(2) On a la trichotomie suivante :

(3) R est irréflexive :

Remarque 2 : L'irréflexivité prouve que,dans la propriété (2),le ou est exclusif.

Remarque 3 : Soit une relation d'ordre total sur A,au sens habituel du terme,c'est-à-dire au sens défini dans le Chap0.
Alors,la relation R définie sur A par xRy ssi est un ordre total strict.
Réciproquement,si (A,R) est un ordre total strict,alors la relation définie sur A par ssi xRy ou x=y est une relation d'ordre total.

Définition 5 : Soient A et B 2 ensembles,R et S 2 relations.
On dit que ssi il existe une bijection telle que

f est appelé un isomorphisme de (A,R) sur (B,S).

Définition 6 : R est un bon ordre (wellordering) sur A,ou (A,R) est bien ordonné,ssi (A,R) est un ordre total strict et toute partie non vide de A possède un élément R-minimal.

Notation : (A,R) bien ordonné,soit

C'est la «section commençante ouverte» délimitée supérieurement par x.

Lemme de rigidité du bon ordre : Si (A,R) est bien ordonné,alors
[Un ensemble bien ordonné n'est pas isomorphe à l'une de ses sections commençantes propres.
Démonstration : Raisonnons par l'absurde
Soit un isomorphisme,et soit
On a ,donc nécessairement
i.e.
donc B a un plus petit élément,soit y.
On a donc
Mais et y est le plus petit élément de B,donc yRx ou y=x

,on a f(x)Rx
donc
donc f(f(x))=f(x)
avec
ce qui contredit l'injectivité de f.

Si yRx,comme f est une bijection :

On a [sinon f(y)=y],donc tRy ou yRt

Remarque 4 : On ne peut pas avoir f(t)=t
car alors on aurait f(f(t))=f(t)
f(y)=y exclu

mézalor forcément yRt
donc f(y)Rf(t) [car f isomorphisme]
i.e. f(y)Ry
donc
i.e. f(f(y))=f(y) avec ,ce qui contredit l'injectivité de f.

Commentaires : Ce lemme de rigidité du bon ordre prouve la «richesse» de la structure d'ensemble bien ordonné.
En effet,si on pose ssi il existe une bijection de A sur B,alors l'ensembles des nombres complexes algébriques sur Q etc.
Bref,il existe beaucoup d'ensembles qui sont «équipotents» à d'autres ensembles beaucoup plus petits.
Ce genre de «désagréments» ne peut plus se produire dès l'instant qu'on impose aux ensembles en question d'être couplés avec une structure de bon ordre.

Lemme 2 : Si (A,R) et (B,S) sont 2 ensembles bien ordonnés isomorphes,alors l'isomorphisme entre eux est unique.
Démonstration : Soient f et g 2 isomorphismes différents
Soit

Soit y le plus petit élément de C
On a donc
mais et g bijective,donc f(y)=g(y')
,car sinon f(y)=g(y)
donc,soit yRy',soit y'Ry

donc f(y')=g(y')
i.e. f(y')=f(y) avec ,ce qui contredit l'injectivité de f.

En intervertissant les rôles de f et g on démontre de même que f(y)Sg(y),ce qui est absurde car S est un ordre total strict.

Nous allons voir maintenant que 2 ensembles bien ordonnés sont forcément comparables.

Théorème fondamental : Soient (A,R) et (B,S) 2 ensembles bien ordonnés.
Alors l'un,et un seul,de ces 3 phénomènes a lieu :



[2 ensembles bien ordonnés non isomorphes sont tels que l'un est isomorphe à une section commençante de l'autre].

Démonstration : Soit

en effet,,
donc en particulier .
Cela prouve que dom(f) est une section commençante de A.
de même,Im(f) est une section commençante de B.
et donc

Soit x' le plus petit élément de A \
Soit y'  le plus petit élément de B \
Il est clair que
donc contradiction.

Remarque 5 : Il est clair que la relation entre ensembles bien ordonnée est réflexive,symétrique et transitive.
Par ailleurs,le fait que 2 ensembles bien ordonnés soient toujours comparables nous donne envie de «hiérarchiser» les classes d'équivalence de bons ordres,en posant ssi (A,R) est isomorphe à une section commençante de (B,S).La classe d'équivalence mesurerait en quelque sorte la «longueur» de l'ensemble bien ordonné,et le lemme de rigidité du bon ordre prouverait que 2 ensembles bien ordonnés ayant la même «longueur» sont isomorphes.
Malheureusement,la «classe» ou la «famille» de tous les ensembles bien ordonnés qui sont isomorphes à (A,R) ne constitue pas un ensemble,on ne peut donc pas parler de «Classe d'équivalence de bons ordres».
D'où la nécessité,parmi tous les ensembles bien ordonnés isomorphes entre eux,d'en sélectionner un qui possède des propriétés bien particulières.C'est ainsi que nous allons être amenés à définir la notion d'ordinal.