Page 274 - Artificial Intelligence for the Internet of Everything

252 Artificial Intelligence for the Internet of Everything

Second, the signature defines an inductive datatype, called the term algebra,
whichis constructeddirectly from the elements of the signature. Structural recur-
siondescribesaprocessforconstructingauniquemappingfromthetermalgebra
to any other. To display the general pattern at work here we will walk through
several examples, introducing some technical vocabulary as we go along.
Thesimplestimaginablesignatureisasingleconstantvalue{c}.Analgebra
for this signature is a pointed set, consisting of a set X together with a chosen
X
elementc 2X.Becausetherearenooperationstobuildupmorecomplicated
terms, the term algebra for this signature is justa singleton set 1¼ {c} (whichis
also the chosen element). The (rather trivial) recursion property for these
X
structures says that there is exactly one function 1 ! X; it sends c7!c . Sim-
ilarly, the Boolean set 2 ¼ {>, ?} and other enumerations can be constructed
as term algebras for a signature with two or more constants.
Next consider a signature with one constant c and one unary (one-place)
operation t. We can think of an algebra for this signature as a discrete dynam-
X
X
ical system (DDS); X is the set of states, c is the initial state, and t is a tran-
sition function X ! X. Since we can apply t repeatedly, the term algebra for
this signature is isomorphic to the natural numbers:

The recursion principle for  rests on a more general notion of mappings
between DDS. A DDS homomorphism is a function h: X ! Y such that
X Y X Y
h(c ) ¼ c and h(t (x)) ¼ t (h(x)). We can represent these conditions graph-
3
ically using commutative diagrams:

Condition (i) just says that h maps initial states to initial states. Condition
(ii) says that we should get the same result if we transition in X and then
map across to Y, or if we map across first and then transition.
The recursion principle for  can then be stated as follows: there
is exactly one DDS homomorphism from  into any DDS X.To
see why, imagine constructing such a function. By (i), we have no

3
A diagram commutes if any two directed paths between the same nodes yield the same result.