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 etR :

x,   R(x) = {y | (z,y)∈Rz=x}.
y,   R(y) = {x | (x,z)∈Rz=y} = tR (y).
x, y,   yR (x) ⇔ (x,y) ∈ R ⇔ xR (y)
xx ∈ Dom RR (x) ≠ ∅

Somme ou union disjointe

Inversement, toute famille d'ensembles (Ei)II définit un graphe appelé leur somme (ou union disjointe) ∐iI Ei:

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))
R = ∐iI Ei ⇔ (Dom RI ∧ ∀iI, R(i)=Ei) ⇒ Im R = iI Ei
(∀iI, EiEi) ⇔ ∐iI Ei ⊂ ∐iI Ei
E0⊔…⊔En−1 = ∐iVn Ei

Graphes fonctionnels

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

Gr f = {(x,f(x)) | x ∈ Dom f} = ∐x∈Dom f {f(x)}
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))

Un graphe R est dit fonctionnel si, de façon équivalente

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

C'est la condition pour que R soit le graphe d'une fonction, et donc la condition d'admissibilité de l'expression de celle-ci:

R = ((Dom R) ∋ x ↦ ℩(R(x)))

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 d'un ensemble B par un graphe R est

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

Image inverse par une fonction

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)= (Gr f)(y) = f*({y}) = {xE | f(x) = 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. Products, graphs and composition