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 Imf
⊂ Domg (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 ⊂ Domf 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(Grf),
Imf = Im(Grf) and Gr(f_{A})=(Grf)_{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 of B by f, written f^{*}(B),
is defined by
f^{*}(B)=
(^{t}Gr f)_{*}(B) = {x
∈ Ef(x) ∈ B}=⋃
y∈B
f^{ •}(y)
f^{ •}(y)= ( ⃖Gr f)(y)
= f^{*}({y}) = {x ∈ Ef(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.