2.6. Graphes

Un graphe est un ensemble de couples.

Pour tout symbole liant Q et tout graphe G, la formule QxG, A(x0, x1) qui lie la variable z = (z0, z1) sur une structure binaire A admissible sur G, peut se voir comme liant 2 variables z0, z1 sur A(z0, z1), et donc se noter par un couple de variables: Q(x,y)∈G, A(x,y).

Le transposé d'un couple est

t(x,y) = (y,x)

Celui d'un graphe R est l'image de la transposition dessus:

tR = {(y,x)|(x,y) ∈ R}.

On définit le domaine et l'image d'un graphe comme les images respectives de π0 et π1 dessus:

Dom R = {x|(x,y) ∈ R}
Im R = {y|(x,y) ∈ R} = Dom tR

Notations de curryfication

Les graphes s'expriment sous formes curryfiées comme foncteurs R et R:

x,   R(x) = {y | (z,y)∈Rz=x}.
yR(y) = {x | (x,z)∈Rz=y} = tR (y).
x,y,   yR (x) ⇔ (x,y) ∈ R ⇔ xR (y)
xx ∈ Dom RR (x) ≠ ∅
Dom RE ⇒ Im R = ⋃xE R(x) ∧ ∀y, R(y) = {xE | (x,y) ∈ R}

Ils peuvent aussi apparaitre comme fonctions

RE = (ExR(x))
RF = (FyR(y))
(R) = RDom R
(R) = RIm R.

Graphes fonctionnels

Le graphe d'une fonction f se définit par

Gr f = {(x,f(x)) | x ∈ Dom f}
x,y, (x,y) ∈ Gr f ⇔ (x ∈ Dom fy = f(x))
Dom f = Dom Gr f
Im f = Im Gr f

Pour toute fonction f et tout graphe R,

Gr fR ⇔ ∀x∈Dom f, f(x) ∈ R(x)
R ⊂ Gr f
⇔ (Dom R ⊂ Dom f ∧ ∀(x,y)∈R, y = f(x))
R = Gr f
⇔ (Dom R ⊂ Dom f ∧ ∀x∈Dom f, R(x) = {f(x)} )

Un graphe R est dit fonctionnel si c'est le graphe d'une fonction. Cette condition peut s'écrire de 2 manières équivalentes

x∈ Dom R, !: R(x)
x,yR, x0 = y0x1 = y1.

C'est alors le graphe d'une unique fonction ℩R = ((Dom R) ∋ x ↦ ℩(R(x))).

Partitions indexées

Deux ensembles E et F sont dits disjoints quand EF = ∅, ce qui équivaut à ∀xE, xF.
Les ensembles d'une famille (Ai)iI sont dits deux à deux disjoints si ∀ijI, AiAj = ∅
Pour tout graphe R avec Im RF, (R(y))yF est une famille d'ensembles deux à deux disjoints si et seulement si R est fonctionnel :

(∀yzF, ¬∃xR(y), xR(z)) ⇔ (∀(x,y)∈R, ∀zF, xRzy = z)

Pour toute fonction f et tout y on définit la fibre de y par f comme

f(y) = {x∈Dom f | f(x) = y} = ⃖(Gr f)(y)

Quand f : EF cela définit une famille fF = (f(y))yF de parties de E deux à deux disjointes :

y,zF, f(y)⋂f(z) ≠ ∅ ⇒ ∃xf(y)⋂f(z), y = f(x) = z
yF f(y) = E
Im f = {yF | f(y) ≠ ∅}.

Une partition indexée d'un ensemble E est une famille de parties de E non vides, deux à deux disjointes et dont l'union est E.
Autrement dit c'est une famille de la forme (f) = fIm f pour toute function f de domaine E.

Somme ou union disjointe

Le symbole liant ∐ de somme d'une famille d'ensembles (Ei)II done un graphe ∐iI Ei défini par

iI
Ei =
iI
{(i,x) | xEi}
i,x, (i,x) ∈
iI
Ei ⇔ (iIxEi)
(∀(i,x)∈
iI
Ei, A(i,x)) ⇔ (∀iI, ∀xEi, A(i,x))
(∀iI, EiEi) ⇔ ∐iI Ei ⊂ ∐iI Ei
E0⊔…⊔En−1 = ∐iVn Ei
Ce symbole sert d'inverse à la curryfication : R = ∐iI Ei ⇔ (Dom RI ∧ ∀iI, R(i) = Ei).
On l'appelle aussi union disjointe comme la famille de copies {(i,x) | xEi} de chaque Ei est 2 à 2 disjointe, la function de R vers I étant donnée par π0.

Images directe et inverse par un graphe

La restriction d'un graphe R à un ensemble A se définit par

R|A = {(x,y)∈R | xA} = ∐xA R(x)

L'image directe d'un ensemble A par un graphe R est
R(A) = Im R|A = xA R(x) = {y |(x,y)∈RxA} ⊂ Im R.
Dom RA ⇔ R|A = RR(A) = Im R
R(
iI
Ai) =
iI
R(Ai)
R(
iI
Ai) ⊂
iI
R(Ai)

ABR(A) ⊂ R(B)
De même, l'image inverse ou préimage d'un ensemble B par un graphe R est

R*(B) = tR(B) = yB R(y) = {x | (x,y)∈RyB} ⊂ Dom R.

Image directe et préimage par une fonction

L'image directe d'une partie A ⊂ Dom f par une fonction f, notée f[A] ou f(A), est
f[A] = (Gr f)(A) = {f(x) | xA} ⊂ Im f
Pour tous f : EF et BF, l'image inverse de B par f, notée f*(B), se définit par

f*(B) = (Gr f)*(B) = {xE | f(x) ∈ B} =
yB
f(y)
f(y) = f*({y})

f*(∁F B) = ∁Ef*(B)

Pour toute famille (Bi)iI de parties de F, f*(iI Bi) = iI f*(Bi), où les intersections sont respectivement interprétées comme parties de F et E.

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
Temps en théorie des ensembles
Interprétation des classes
Concepts de vérité en mathématiques
3. Algebra - 4. Arithmetic - 5. Second-order foundations
Other languages:
EN : 2.6. Graphs