2.3. Products, graphs and composition

Finite product

For any two sets E and F, the product E×F is the set of (x,y) where xE and yF. Similarly, the product of n sets E0×…×En−1 is the set of n-tuples (x0,…,xn−1) where ∀iVn, xiEi.
An n-ary operation is a function with domain a product of n sets.
A relation between any two sets E and F is formalized as a set of oriented pairs GE×F (the domains E and F might be specified by taking the triple (E,F,G)). A set of oriented pairs (such as G) is called a graph.
For any binder Q and any graph G, the formula QxG, A(x0, x1) that binds x = (x0, x1) on a binary structure A with domain G, can be seen as binding 2 variables x0, x1 on A(x0, x1), and thus be denoted with an oriented pair of variables: Q(y,z) ∈ G, A(y,z).
The existence of the product (in all arity) is justified by the set generation principle:

(∃(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))

The quantifier ∀(x,y) ∈ E×E will be abbreviated as ∀x,yE, and the same for ∃.
With 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))

Sum or disjoint union

The transpose of an ordered pair is
t(x,y)=(y,x)
That of a graph R is
tR={(y,x)|(x,y) ∈ R}
Graphs can be expressed in curried forms R andR :
yR (x) ⇔ (x,y) ∈ R ⇔ xR (y) = tR (y)
justified by defining the functor R as
R(x) = {y | (z,y)∈Rz=x}.

Inversely, any family of sets (Ei)II defines a graph called their sum (or disjoint union) ∐iI Ei:

(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 = ∐iVn Ei
E×F = ∐xE F     E×∅ = ∅ = ∅×E
(EE′∧FF′) ⇒E×FE′×F
(∀iI, EiEi) ⇔ ∐iI Ei ⊂ ∐iI Ei

Composition, restriction, graph of a function

For any set E, the function identity on E is defined by IdE = (Exx).
For any functions f,g with ImfDomg (namely, f : E → F and g : F → G), their composite is

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

The same with h:G →H, hgf = (hg)০f = h০(gf) = (Exh(g(f(x)))) and so on.
The restriction of f to ADomf is f|A= (Axf(x)) = fIdA.
The graph of a function f is defined by
Gr f = {(x,f(x)) | x ∈ Dom f} = ∐xDomf {f(x)}
(x,y) ∈ Gr f ⇔ (x ∈ Dom fy=f(x))
We can define domains, images and restrictions for graphs, generalizing those for functions (i.e. Dom f = Dom(Grf), Imf = Im(Grf) and 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)

Then we have R = ∐iI Ei ⇔ (Dom RI ∧ ∀iI, R(i)=Ei) ⇒ Im R = iI Ei.
For any functions f,g, any graph R, and 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)

Direct image, inverse image

The direct image of a set A by a graph R is 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)
The direct image of A ⊂ Dom f by a function f is
f[A] = f*(A) = (Gr f)*(A) = Im(f|A) = {f(x)|xA} ⊂ Im f
For any f : E → F and BF, the inverse image of B by f, written f*(B), is defined by

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)

For any family (Bi)iI of subsets of F, f*(iI Bi)=iI f*(Bi) where intersections are respectively interpreted as subsets of F and E.


Set theory and Foundations of Mathematics

1. First foundations of mathematics
2. Set theory (continued)
2.1. Tuples, families
2.2. Boolean operators on families of sets
2.3. Products, graphs and composition

2.4. Uniqueness quantifiers, functional graphs
2.5. The powerset axiom
2.6. Injectivity and inversion
2.7. Properties of binary relations on a set ; ordered sets
2.8. Canonical bijections
2.9. Equivalence relations and partitions
2.10. Axiom of choice
2.11. Notion of Galois connection
3. Model theory