2.7. Relations binaires, ensembles ordonnés

Une relation binaire sur E est une relation RE×E. Notant x R y ⇔ (x,y) ∈ R et sous-entendant le domaine E des quantificateurs, elle sera dite
réflexive  ⇔  xx R x
antiréflexive  ⇔  x, ¬(x R x)
symétrique  ⇔   RtRR = tRR =R
antisymétrique  ⇔  x,y, (x R yy R x)⇒x=y
transitive  ⇔  x,y,z, (x R yy R z)⇒x R z

Pour toute relation binaire transitive R on note x R y R z ⇔ ((x R y)∧(y R z))⇒x R z.
Exemple. Soit AEE et R=fA Gr f. Alors
(IdEA) ⇒ R réflexive
(∀f,gA, gfA) ⇒ R transitive
(∀fA, f:EEf−1A) ⇒ R symétrique

Préordre. Un préordre R sur un ensemble E est une relation binaire réflexive et transitive sur E. De manière équivalente,
x,yEx R y ⇔R(x) ⊂R(y)
Preuve: ∀x,yExR(x) ⊂ R(y) ⇒ x R y ;
la transitivité s'énonce x R yR(x) ⊂R(y). ∎
Alors tR est aussi un préordre: x R y ⇔ R(y) ⊂ R(x).

Ensemble ordonné. Un ordre est un préordre antisymétrique. Un ensemble préordonné est un ensemble E avec un préordre choisi R. Un ensemble ordonné est un ensemble avec un ordre, généralement noté ≤.

Pour x, y dans un ensemble ordonné E, la formule xy peut se lire «x est inférieur à y» ou «y est supérieur à x». Les éléments x et y sont dits incomparables lorsque ¬(xyyx) (qui implique xy).

Tout sous-ensemble F d'un ensemble E avec un ordre (resp. un préordre) RE×E, est également ordonné (resp. préordonné) par sa restriction R∩(F×F) (qui est un ordre, resp. préordre, sur F)

Ordre strict. C'est une relation binaire transitive et antiréflexive; et donc aussi antisymétrique.

Les ordres stricts < correspondent bijectivement aux ordres ≤ par
x < y ⇔ (xyxy).
La correspondance inverse est définie par xy ⇔ (x < yx = y).

Ordre total. Un ordre total sur un ensemble E est un ordre R sur E sans paire d'éléments incomparables: ∀x,yE, xyyx, autrement dit RtR = E×E.

Définitions équivalentes:
Un ordre strict associé à un ordre total, appelé un ordre total strict, est toute relation transitive < sur E telle que
x,yE, x < y ⇎ (y < xx=y)
ou de manière équivalente ∀x,yE, x=y ⇎ (y < xx < y)).

Fonctions croissantes, décroissantes, strictement croissantes

Entre deux ensembles ordonnés E et F, une fonction f : EF sera dite :
- croissante ssi ∀x,yE, xyf(x) ≤ f(y)
- décroissante ssi ∀x,yE, xyf(y) ≤ f(x)
- strictement croissante ssi ∀x,yE, xy ⇔ f(x) ≤ f(y)
- strictement décroissante ssi ∀x,yE, xy ⇔ f(y) ≤ f(x).

Toute composée d'une chaine de fonctions croissantes ou décroissantes, est croissante si le nombre de fonctions décroissantes dans la chaine est pair, ou décroissante s'il est impair.
Toute fonction strictement croissante ou strictement décroissante est injective.
Si fFE et gEF sont toutes deux croissantes (resp. toutes deux décroissantes) et gf=IdE, alors f est strictement croissante (resp. strictement décroissante).

Ordre sur les ensembles de fonctions

Pour tous ensembles E, FF est ordonné, l'ensemble FE (et donc tout sous-ensemble de FE) est ordonné par

fg ⇔ (∀xE, f(x) ≤ g(x))

Alors, ∀f,gFE, ∀hEG, fgfhgh, autrement dit ffh est toujours croissante.
Le cas particulier F=V2 est que ℘(E) (et donc tout ensemble d'ensembles) est naturellement ordonné par ⊂, et que h* est croissante de ℘(E) à ℘(G).
Si F et G sont ordonnés et uGF est croissante (resp. décroissante) alors FEfufGE est croissante (resp. décroissante).
Dans un ensemble ordonné E, une fonction fEE est dite extensive si
xE, xf(x)
autrement dit IdEf. La composée de deux fonctions extensives est extensive.

Théorie des ensembles et fondements des mathématiques
1. Premiers fondements des mathématiques
2. Théorie des ensembles (suite)
2.1. Uplets, familles
2.2. Opérateurs booléens sur les ensembles
2.3. Produits, graphes et composition
2.4. Quantificateurs d'unicité, graphes fonctionnels
2.5. L'ensemble des parties
2.6. Injectivité et inversion 

2.7. Relations binaires, ensembles ordonnés
2.8. Bijections canoniques
2.9. Relations d'équivalence et partitions
2.10. Axiome du choix
2.11. Correspondance de Galois
3. Théorie des modèles