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

Quantifiers Q(x,y)∈E×E will be written Qx,yE, and those with domain {(x,y)∈E×E | xy} will be written QxyE.
Thus ∀xyE,... means ∀x,yE, xy⇒..., that is ∀xE,∀yE, xy⇒...
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)) ⇔ ((CE≠∅) ∨ ∃xE, A(x))
(∀xE, CA(x)) ⇔ ((CE=∅) ∧ ∀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∈∐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, graph of a function

For any set E, the function identity on E is defined by IdE = (Exx).
For any functions f,g with Im f ⊂ Dom g (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 A ⊂ Dom f is f|A = (Axf(x)) = f০IdA.
The graph of a function f is defined by

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

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 or preimage 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