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 x∈E and y∈F.
Similarly, the product of n sets E_{0}×…×E_{n−1}
is the set of ntuples (x_{0},…,x_{n−1})
where ∀i∈V_{n},
x_{i}∈E_{i}.
An nary 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 G ⊂ E×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 Qx∈G,
A(x_{0},x_{1})
that binds x = (x_{0}, x_{1})
on a binary structure A with domain G, can be seen
as binding 2 variables x_{0}, x_{1}
on A(x_{0}, x_{1}), 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))
⇔ (∃x∈E, ∃y∈F, A(x,y))
⇔ (∃y∈F, ∃x∈E, A(x,y))
(∀(x,y)∈E×F, A(x,y))
⇔ (∀x∈E, ∀y∈F, A(x,y))
⇔ (∀y∈F, ∀x∈E, A(x,y))
The quantifier ∀(x,y)∈E×E will be
abbreviated as ∀x,y∈E, and the same for ∃.
With F=V_{2},
(∃x∈E, A(x)∨B(x))
⇔ ((∃x∈E, A(x)) ∨ (∃x∈E, B(x)))
(∀x∈E, A(x)∧B(x))
⇔ ((∀x∈E, A(x)) ∧ (∀x∈E, B(x)))
(∃x∈E, C∨A(x)) ⇔ ((C ∧ E≠∅) ∨ ∃x∈E, A(x))
(∀x∈E, C∧A(x)) ⇔
((C ∨ E=∅) ∧ ∀x∈E, A(x))
Sum or disjoint union
The transpose of an ordered pair is ^{t}(x,y)=(y,x)
That of a graph R is ^{t}R={(y,x)(x,y)
∈ R}
Graphs can be expressed in curried forms ⃗R
and ⃖R :
y ∈ ⃗R (x) ⇔ (x,y)
∈ R ⇔ x ∈ ⃖R
(y) = ^{t}⃗R (y)
justified by defining the functor ⃗R
as
⃗R(x) = {y
 (z,y)∈R ∧ z=x}.
Inversely, any family of sets
(E_{i})_{I∈I} defines a
graph called their sum (or disjoint union)
∐_{i∈I} E_{i}:
(i∈I ∧ x∈E_{i})
⇔ (i,x) ∈ ∐
i∈I
E_{i} =⋃
i∈I
{i}×E_{i}= ⋃
i∈I={(i,x)  x
∈ E_{i}} ⊂ I×⋃
i∈I
E_{i}
(∀
x∈∐
_{i∈I} E_{i},
A(
x)) ⇔ (∀
i∈
I,
∀
y∈
E_{i},
A(
i,
y))
E_{0}⊔…⊔
E_{n−1} =
∐
_{i∈Vn} E_{i}
E×
F = ∐
_{x∈E} F
E×∅ = ∅ = ∅×
E
(
E⊂
E′ ∧
F⊂
F′) ⇒
E×
F ⊂
E′×
F′
(∀
i∈
I,
E_{i} ⊂
E′
_{i})
⇔ ∐
_{i∈I} E_{i} ⊂
∐
_{i∈I} E′
_{i}
Composition, restriction, graph of a function
For any set E, the function identity on E is
defined by Id_{E} = (E
∋ x ↦ x).
For any functions f,g with Im f
⊂ Dom g (namely, f : E →
F and g : F → G), their composite
is
g০f = ((Dom f) ∋ x ↦
g(f(x))): E → G
The same with h:G →H, h০g০f
= (h০g)০f = h০(g০f) = (E
∋ x ↦ h(g(f(x)))) and so on.
The restriction of f to A ⊂ Dom f is f_{A} =
(A ∋ x ↦ f(x)) = f০Id_{A}.
The graph of a function f is defined by
Gr f = {(x,f(x)) 
x ∈ Dom f} = ∐_{x∈Domf}
{f(x)}
(x,y) ∈ Gr f ⇔ (x∈ Dom f
∧ y=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 ^{t}R
∀x, x ∈ Dom R ⇔ ⃗R
(x) ≠ ∅
R ⊂ E×F ⇔ (Dom R ⊂ E ∧ Im R
⊂ F)
R_{A} = R∩(A× Im R) =
{(x,y)∈R  x∈A} = ∐_{x∈A}
⃗R(x)
Then we have R = ∐_{i∈I} E_{i} ⇔ (Dom R ⊂I ∧ ∀i∈I,
⃗R(i)=E_{i})
⇒ Im R = ⋃_{i∈I}
E_{i}.
For any functions f,g, any graph R, and E= Dom f,
Gr f
⊂ R 
⇔ ∀x∈E, f(x) ∈ ⃗R(x) 
R ⊂ Gr f

⇔ (∀(x,y) ∈ R, x∈E
∧ y=f(x)) ⇔ (Dom R ⊂
E ∧ ∀(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}=
⋃_{x∈A} ⃗R(x).
Dom
R ⊂
A ⇔
R_{A}=
R
⇒
R_{∗}(
A)= Im
R
R_{∗}(⋃
i ∈ I
A_{i}) = ⋃
i ∈ I
R_{∗}(A_{i})
R_{∗}(∩
i ∈ I
A_{i}) ⊂ ∩
i ∈ I
R_{∗}(A_{i})
A ⊂
B ⇒
R_{∗}(
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)  x∈A} ⊂ Im f
For any f : E → F and B ⊂ F,
the inverse image or preimage of B by f, written f*(B),
is defined by
f*(B)=
(^{t}Gr f)_{∗}(B) = {x∈E  f(x) ∈ B} = ⋃
y∈B
f^{ •}(y)
f^{ •}(y)= ( ⃖Gr f)(y)
= f*({y}) = {x∈E  f(x)
= y}
f*(∁
_{F} B) = ∁
_{E}f*(
B)
For any family (B_{i})_{i ∈ I}
of subsets of F, f*(∩_{i∈I
}B_{i})=∩_{i∈I}
f*(B_{i}) where
intersections are respectively interpreted as subsets of F
and E.