Page 276 - Artificial Intelligence for the Internet of Everything

254 Artificial Intelligence for the Internet of Everything

Here we use the fact that F is functorial. This means two things. First, F can
be applied to a function h as well as to a set X, defining a new function
F(h):FX!FY;thedefinition(bycases)iseasy,sendingc7!candha,xi!ha,h(x)i.
7
Second, F respects the composition of functions: if h and k are compo-
sable then F(h k) ¼ F(h) F(k). Using this observation, we can show that
controlled DDS mappings (and other algebraic mappings) are closed under
composition; if h and k satisfy the DDS mapping condition, then so does the
composite h k:
F (h·k)

FX FY FZ
F (h) F (k)
α β γ
h k
X Y Z
h·k

Fðh kÞ γ ¼ FðhÞ FðkÞ γ ¼ FðhÞ β k ¼ α ðh kÞ
DDS are a bit atypical for algebraic structures because they contain only
constants and unary operations. A more familiar example might involve a
signature with one constant c and one binary operation (written using
infix notation, sometimes with a subscript to emphasize the algebra X). We
can represent this signature using a polynomial (as opposed to linear) functor
2
FX ¼ 1+ X . An algebra homomorphism h: X ! Y preserves the constant
and the operation:
X
hðc Þ¼ c Y 0 0
hðx x Þ¼ hðxÞ hðx Þ
X Y
The inductive type associated with this signature is the set of binary trees.
The constant c is a tree consisting of a single leaf; the composition operation
t ^ t creates a new tree in which t and t are the left and right subtrees, respec-
0
0
tively. Compare the algebraic specification of a binary tree with the usual
graphical representation below:

(c ∧ (c ∧ c)) ∧ (c ∧ c)