2.9. Relations binaires sur un ensemble

Une relation binaire sur un ensemble E est une relation dont les 2 domaines sont égaux à E, donc formalisée par un graphe R ⊂ E×E. Abrégeons E×E en E2 et (x,y) ∈ R en x R y.

Préimages et produits

Pour toute fonction f : E → F et toute relation binaire R sur F, la préimage de R par f est la relation binaire f⋆(R) sur E définie par

{(x,y)∈E2 | f(x) R f(y)}

Pour toute famille de relations binaires (Ri)i∈I sur des ensembles respectifs Fi, leur produit est la relation binaire sur P = ∏i∈I Fi définie par

{(x,y)∈P2 | ∀i∈I, xi Ri yi} = ⋂i∈I πi⋆(Ri).

(Elle est en fait en bijection canonique avec le produit d'ensembles ∏i∈I Ri)
En particulier avec une famille constante: toute relation binaire sur un ensemble F en définit une sur tout FI.

Les deux opérations peuvent être combinées en une seule étape: pour toute famille de fonctions fi : E → Fi, la relation

{(x,y)∈E2 | ∀i∈I, fi(x) Ri fi(y)} = ⋂i∈I fi⋆(Ri)

est la préimage de la relation produit des Ri sur P, par la fonction ⊓i∈I fi : E → P.

Ces concepts seront plus tard généralisés à d'autres structures du premier ordre.

Propriétés de base

Une relation binaire sur un ensemble E sera dite

réflexive  ⇔  ∀x∈E, xRx ⇔  𝛿E ⊂ R ⇒ Dom R = Im R = E
antiréflexive  ⇔   ∀x∈E, ¬(xRx)
symétrique  ⇔  (∀x,y∈E, xRy ⇒ yRx) ⇔ R ⊂ tR ⇔ R = tR ⇔ (R⃗) = (R⃖)
antisymétrique  ⇔   ∀x,y∈E, (xRy ∧ yRx) ⇒ x = y
transitive  ⇔   ∀x,y,z∈E, (xRy ∧ yRz) ⇒ xRz

Ces propriétés sont conservées par transposition, préimages et produits, sauf que la préimage d'une relation antisymétrique par une fonction non-injective peut ne pas être antisymétrique, et le produit vide (I=∅) n'est pas antiréflexif.
En particulier pour F ⊂ E, la restriction d'une relation R ⊂ E×E à F, à savoir R∩(F×F), est sa préimage par IdF : F ↪ E, donc préserve toutes les propriétés.

Exemple. Soit A ⊂ EE et R = ⋃f∈A Gr f. Alors

(IdE ∈ A) ⇒ R est réflexive
(∀f,g∈A, g⚬f ∈ A) ⇒ R est transitive
(∀f∈A, f : E↔E ∧ f -1∈ A) ⇒ R est symétrique

Pour toute relation binaire transitive R on note x R y R z ⇔ (x R y ∧ y R z) ⇒ x R z.

Préordre et ordre

Un préordre est une relation binaire réflexive et transitive. Un ordre est un préordre antisymétrique.
Un ensemble préordonné est un ensemble avec un préordre choisi dessus.
Un ensemble ordonné est un ensemble avec un ordre choisi, généralement noté ≤ ou ≤E. La formule x ≤ y peut se lire «x est inférieur à y» ou «y est supérieur à x».
Deux éléments x, y dans un ensemble ordonné sont dits comparables lorsque (x≤y ∨ y≤x).

Sur la classe des ensembles, la méta-relation ⥬ (existence d'une bijection canonique) est un méta-préordre.
La paire booléenne V2 est naturellement ordonnée par ⇒ qui y coïncide avec l'ordre habituel entre les nombres.
L'ordre de produit résultant sur V2E ⥬ ℘(E) (et donc tout ensemble d'ensembles) est celui de l'inclusion (⊂).

Toute relation R ⊂ E×F définit un préordre sur E comme la préimage par R⃗ de l'ordre d'inclusion:

{(x,y)∈E2 | R⃗(x) ⊂ R⃗(y)}.

Inversement, tout préordre R sur un ensemble E est ainsi définissable par lui-même de deux manières (échangées par transposition):

∀x,y∈E, R⃗(y) ⊂ R⃗(x) ⇔ x R y ⇔ R⃖(x) ⊂ R⃖(y)

Preuve. La transitivité est équivalente à (∀x,y∈E, x R y ⇒ R⃗(y) ⊂ R⃗(x)) et à (∀x,y∈E, x R y ⇒ R⃖(x) ⊂ R⃖(y)).
La réflexivité est équivalente aux réciproques:

∀x∈E, (∀y∈E, R⃗(x) ⊂ R⃗(y) ⇒ y R x) ⇔ x R x ⇔ (∀y∈E,  R⃖(x) ⊂ R⃖(y) ⇒ x R y). ∎

Donc R est la préimage de ⊂ by (R⃖). De plus,

∀x,y∈E, R⃖(x) = R⃖(y) ⇔ (R⃖(x) ⊂ R⃖(y) ∧ R⃖(y) ⊂ R⃖(x)) ⇔ (xRy ∧ yRx)

de sorte que (R⃖) est injective si et seulement si R est un ordre.
L'idée de ne considérer qu'un seul ordre noté ≤ sur chaque ensemble E, peut se formaliser en remplaçant l'ensemble ordonné (E,R) par (Im(R⃖), ⊂), quoique cela ne colle pas exactement à la convention suivante: tout sous-ensemble d'un ensemble ordonné sera aussi implicitement ordonné par restriction.

Ordre strict, ordre total

Un ordre strict est une relation binaire transitive et antiréflexive; et donc aussi antisymétrique.

Les ordres stricts < correspondent bijectivement aux ordres ≤ par

x < y ⇔ (x ≤ y ∧ x ≠ y).
x ≤ y ⇔ (x < y ∨ x = y).

Un ordre total sur E est un ordre où tous les éléments sont comparables: ∀x,y∈E, x≤y ∨ y≤x, autrement dit (≤ ∪ t≤) = E×E.
Définitions équivalentes: Un ordre total strict sur un ensemble E, est un ordre strict associé à un ordre total, autrement dit une relation transitive < telle que, de manière équivalente

∀x,y∈E, x < y ⇎ (y < x ∨ x = y)
∀x,y∈E, x = y ⇎ (y < x ∨ x < y)

Relations d'équivalence

Une relation d'équivalence est un préordre symétrique.
Sur tout ensemble E, la relation d'égalité 𝛿E est une relation d'équivalence (comme déjà exprimé par les axiomes de l'égalité), et la seule relation à la fois symétrique, antisymétrique et réflexive.
Sur tout produit d'ensembles, le produit des relations d'égalité est aussi l'égalité.
La préimage de l'égalité par tout f : E → F est une relation d'équivalence sur E qu'on notera ∼f :

∼f = {(x,y)∈E | f(x) = f(y)} = ∐(f•⚬f)
Inj f ⇔ ∼f = 𝛿E

Inversement, toute relation d'équivalence R est ainsi définissable par elle-même: R = ∼R⃗. En effet

∀x,y∈E, x R y ⇔ R⃗(y) ⊂ R⃗(x) ⇔ R⃗(x) ⊂ R⃗(y) ⇔ R⃗(x) = R⃗(y)

Fonctions quotient

Proposition. ∀SetE,F,G, ∀f, (f : E ↠ F) ⇒ (GF ∋ g ↦ g⚬f) : GF ↔ {h∈GE | ∼f ⊂ ∼h}.

Preuve : ∀...∀f∈FE, ∀h∈GE, H = Im(f×h) ⇒

∼f ⊂ ∼h ⇔ (∀x,x'∈E, f(x) = f(x′) ⇒ h(x) = h(x′)) ⇔ (∀(y,z), (y′,z′) ∈ H, y=y′ ⇒ z=z′)
Dom H = Im f ∧ ∀g∈GF, h = g⚬f ⇔ H ⊂ Gr g. ∎

Pour toutes fonctions f,h telles que Dom f = Dom h ∧ ∼f ⊂ ∼h, cet unique g : Im f ↠ Im h tel que h = g⚬f sera appelée le the quotient de h par f:

h/f = (Im f ∋y↦ ℩h[f•(y)])
Gr (h/f) = Im (f×h)
Inj f ⇒ (f -1 = IdDom f /f ∧ h/f = h⚬f -1)
∼f = ∼h ⇔ Inj(h/f) ⇒ (h/f)-1 = f/h

Dans le cas plus général Im f ⊂ Dom g (sans surjectivité de f),

h = g⚬f ⇒ (∼f ⊂ ∼h ∧ h/f = g|Im f)
⇒ (∼f  = ∼h ⇒ f = (g|Im f)−1⚬h)

La formule que ∼f est une relation d'équivalence,

∀x,y ∈ Dom f, x ∼f y ⇔ ∼⃗f(x) =  ∼⃗f(y)

où (∼⃗f) = f•⚬f, reflète l'injectivité de (f•) qu'on peut directement voir par

∀y∈Im f, ∀z, f•(y) = f•(z) ⇒ f•(y) ∩ f•(z) = f•(y) ≠ ∅ ⇒ y = z.

Partitions

Une partition d'un ensemble E est un ensemble d'ensembles non vides, deux à deux disjoints et dont l'union est E.
Autrement dit c'est un ensemble P de parties de E tel que IdP est une partition indexée of E.
L'image de toute partition indexée est une partition du même ensemble: pour toute fonction f d'image E, Im(f•) = f•[E] = Im(f•⚬f) est une partition de E.
∀R ⊂ E×E, si P = R⃗[E] alors

(∀x,y∈E, x∈R⃗(y) ⇔ R⃗(x) = R⃗(y)) ⇔ (∀x∈E, ∀A∈P, x∈A ⇔ R⃗(x) = A) ⇔ IdP = (R⃗E•)

donc si R est une relation d'équivalence alors P est une partition.
Inversement, toute partition P de E définit une fonction g puis un graphe R par

Dom g = E ∧ (g•) = IdP ∴ P = Dom (g•) = Im g
R = ∐g ⊂ E×E ∴ g = R⃗E ∴ (P = R⃗[E] ∧ IdP = (R⃗E•))

donc R est une relation d'équivalence sur E et

∀x,y∈E, xRy ⇔ y∈ ℩{A∈P | x∈A} ⇔ (∃A∈P, x∈A ∧ y∈A) ⇔ (∀A∈P, x∈A ⇒ y∈A).

Pour toute relation d'équivalence R sur E, la partition R⃗[E] = Im (R⃗) est appelée le quotient de E par R, et notée E/R :

(R⃗) : E ↠ E/R.

Pour tout x ∈ E, l'ensemble R⃗(x) = ℩{A∈E/R | x∈A} est appelé la classe de x par R.
Pour toute fonction f telle que Dom f = E ∧ R ⊂ ∼f, abrégeons f/(R⃗) en f/R:

f/R : E/R ↠ Im f
Inj f/R ⇔ R = ∼f

Ainsi lorsque R = ∼f le role de E/R peut être joué par Im f.
En particulier tout préordre R sur un ensemble E donne une relation d'équivalence R∩tR, et le rôle de E/(R∩tR) peut être joué par Im (R⃖).

Théorie des ensembles et fondements des mathématiques
1. Premiers fondements des mathématiques
2. Théorie des ensembles
2.1. Premiers axiomes de théorie des ensembles
2.2. Principe de génération des ensembles
2.3. Curryfication et uplets
2.4. Quantificateurs d'unicité
2.5. Familles, opérateurs booléens sur les ensembles
2.6. Graphes
2.7. Produits et ensembles des parties		 2.8. Injections, bijections ⇦
2.9. Propriétés des relations binaires
⇨ 2.10. Axiome du choix
2.A. Temps en théorie des ensembles
2.B. Interprétation des classes
2.C. Concepts de vérité en mathématiques
3. Algebra - 4. Arithmetic - 5. Second-order foundations