2.3. Produits, graphes et composition

Produit fini

Pour deux ensembles E et F, le produit E×F est l'ensemble des (x,y) où xE et yF.
De même, le produit de n ensembles E0×…×En−1 est l'ensemble des n-uplets (x0,…,xn−1) où ∀iVn, xiEi.
Une opération n-aire est une fonction sur un produit de n ensembles.
Une relation entre deux ensembles E et F se formalise comme ensemble de couples GE×F (les domaines E et F peuvent être spécifiés en prenant le triplet (E,F,G)).
Un ensemble de couples (comme G) est appelé un graphe.
Pour tout symbole liant Q et tout graphe G, la formule QxG, A(x0, x1) qui lie x = (x0, x1) sur une structure binaire A de domaine G, peut se voir comme liant 2 variables x0, x1 sur A(x0, x1), et donc se noter par un couple de variables: Q(y,z) ∈ G, A(y,z).
L'existence du produit (en toute arité) se justifie par le principe de génération des ensembles:

(∃(x,y) ∈ E×F, A(x,y)) ⇔ (∃xE, ∃yF, A(x,y)) ⇔ (∃yF,∃xE, A(x,y))
(∀(x,y) ∈ E×F, A(x,y)) ⇔ (∀xE, ∀yF, A(x,y)) ⇔ (∀yF,∀xE, A(x,y))

Le quantificateur ∀(x,y) ∈ E×E s'abrégera en ∀x,yE, et de même pour ∃.
Avec F=V2,

(∃xE, A(x)∨B(x)) ⇔ ((∃xE, A(x))∨(∃xE,B(x))
(∀xE, A(x)∧B(x)) ⇔ ((∀xE, A(x))∧(∀xE,B(x))
(∃xE, CA(x)) ⇔ ((C∧(E ≠ ∅))∨∃xE, A(x))
(∀xE, CA(x)) ⇔ ((C∨(E=∅))∧∀xE, A(x))

Somme ou union disjointe

Le transposé d'un couple est t(x,y)=(y,x); celui d'un graphe R est tR={(y,x)|(x,y) ∈ R}.
Les graphes s'expriment sous formes curryfiées R etR :
yR (x) ⇔ (x,y) ∈ R ⇔ xR (y) = tR (y)
justifiées en définissant le foncteur R par
R(x) = {y | (z,y)∈Rz=x}.

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

(iIxEi)  ⇔ (i,x) ∈
iI
Ei =
iI
{iEi=
iI
={(i,x)|xEi} ⊂ I×
iI
Ei

(∀x ∈ ∐iIEi, A(x)) ⇔ (∀iI,∀yEi, A(i,y))
E0⊔…⊔En−1 = ∐iVnEi
E×F=∐xEF     E×∅ = ∅ = ∅×E
(EE′∧FF′) ⇒E×FE′×F
(∀iI, EiEi) ⇔ ∐iIEi ⊂ ∐iIEi

Composition, restriction, graphe d'une fonction

Pour tout ensemble E, la fonction identité sur E se définit par IdE=(Exx).
Pour toutes fonctions f,g avec ImfDom g (à savoir f : E → F et g : F → G), leur composée est

gf = ((Dom f) ∋ xg(f(x))) : E → G

De même avec h:G →H, hgf = (hg)০f = h০(gf) = (Exh(g(f(x)))) et ainsi de suite.
La restriction de f à ADomf est f|A= (Axf(x)) = fIdA.
Le graphe d'une fonction f se définit par
Gr f = {(x,f(x)) | x ∈ Dom f} = ∐xDomf {f(x)}
(x,y) ∈ Gr f ⇔ (x ∈ Dom fy=f(x))
On définit les domaines, images et restrictions pour les graphes, généralisant ceux pour les fonctions (Dom f = Dom(Grf), Imf = Im(Grf) et Gr(f|A)=(Grf)|A):

Dom R={x|(x,y) ∈ R}= Im tR  
xx ∈ Dom R ⇔  R (x) ≠ ∅
RE×F ⇔ (Dom RE ∧ Im RF)
R|A=R∩(A× Im R) = {(x,y) ∈ R | xA} = ∐xA R (x)

Alors R = ∐iI Ei ⇔ (Dom RI∧∀iI, R(i)=Ei) ⇒ Im R = iI Ei.
Pour toutes fonctions f,g, tout graphe R, et E= Dom f,

Gr fR ⇔ ∀xE, f(x) ∈ R(x)
R ⊂ Gr f
⇔ (∀(x,y) ∈ R, xEy=f(x)) ⇔ (Dom RE∧∀(x,y)∈R, y=f(x))
Gr f ⊂ Gr g ⇔ ((E ⊂ Dom g)∧ f=g|E)

Image directe, image inverse

L'image directe d'un ensemble A par un graphe R est R*(A) = Im R|A= xA R(x).
Dom RA ⇔ R|A=RR*(A)= Im R
R*(
iI
Ai) =
iI
R*(Ai)
R*(
iI
Ai) ⊂
iI
R*(Ai)

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

f*(B)= (tGr 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 sous-ensembles de F, f*(iI Bi)=iI f*(Bi), où les intersections sont respectivement interprétées comme sous-ensembles de F et E.



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