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)) ⇔ ((CE≠∅) ∨ ∃xE, A(x))
(∀xE, CA(x)) ⇔ ((CE=∅) ∧ ∀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) ∐iI Ei:

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

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

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 Im f ⊂ Dom 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 à A ⊂ Dom f est f|A = (Axf(x)) = f০IdA.
Le graphe d'une fonction f se définit par

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

Dom R = {x|(x,y) ∈ R} = Im tR
xx ∈ Dom RR (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 A ⊂ Dom f 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