Signatures, Algebras and Homomorphisms
This chapter introduces the key concepts of signatures,
algebras and homomorphisms. While examples are given of all these
concepts, the interesting examples will be found in later chapters.
Informal Introduction
Universal algebra is the study of algebras.
An algebra is just a collection of named sets together with
a collection of named functions (operations) between those sets.
Computer science is full of algebras. For example, in most programming
languages there is a set of primitive data types (e.g,,
integer, boolean, string) and
an associated set of primitive operations such as
+
: integer x integer > integer
eq
:
integer x integer > boolean
length
: string > integer
etc.
It is sometimes convenient to represent
such a collection pictorially. Here is a pictorial presentation
of an expanded version of the above example
This kind of diagram is often called a "spaghetti and meatball diagram".
Note that this is a different use of the word "diagram" than that in the
definition of a commuting diagram. Spaghetti and meatball diagrams
are convenient for informal presentations and/or informal development of
algebras as they are, of course, easy to visualize.
Looking at the diagram we realize that it only tells us part of the
story  it gives the names of the sets and functions functions and the
types of the arguments of the functions but it does not give us the
actual sets and functions. (Also, as given, they do not tell us the
order of the arguments of a function  but this could be added if really
wanted.) If we think about these sets and operations
as being those of some real or imagined programming language we realize
that different programming languages will provide different
sets for Integer.
For
example:

In Pascal
the Integer
type ranges from 32,768 to 32,767

In Java
the int type
ranges from 2,147,483,648 to 2,147,483,647.

In Mathematica
there are no restrictions on the Integer
type (other than those imposed by the size of the computer).
This illustrates
the fact that what we are talking about consists of two interacting ideas:
one, which we will call a signature, is a collection of names for
sets and operations, the other, which we will call an algebra,
is an assignment of actual sets and operations to the names.
Signatures:
Definition:
A
manysorted
signature is given by the following data

S,
a set (called the set of sorts)

,
an (S*S)indexed
family of sets,=
<_{w,s}
 wS*, sS>.
The elements of _{w,s
}are
called the operators of arity w
and sort s.
The operators of arity "", the empty string, will
generally be refered to as constants or constant operators.
We say a signature is overloaded
if there exist <w,s>,<u,t>S*S
such that <w,s><u,t>
but _{w,s u,t}.
We will sometimes write (w,s)
rather
than _{w,s}
when this aids the typesetting.
We sometimes write
for this disjoint union of the (S*S)indexed
family of sets,=
<_{w,s}
 wS*, sS>
and
write expressions such as "".
If the signature is not overloaded we can take the "disjoint union" just
to be the union of family members,
while if the signature is overloaded we can take the disjoint union to
consist of all triples <,
w, s> such that wS*,
sS and _{w,s}.
end
Note: The elements
of _{w,s}
are called "operators", not "operations". As you will see,
operators are names of operations , and
operations are functions. Or, put another way, operators are syntactical
while operations are semantical.
Signatures on the UACalculators
In applications,
a signature often comes with an additional piece of data, its name,
which
we can regard as a string of letters and digits enclosed in quotation marks.
The signature pictured above is represented within the system by the name
"sig01".
Using the UACalculator and some of its special builtin functions you
can display the signature in several different ways.

The mathematical form  similar to the abstract definition
given above. To see that form of the signature, type, or copy, MSigPrint("sig01")
to
the INPUT line on the calculator and then click on the PERFORM button.

The programming form  a version that (loosely) resembles
a programming declaration. To see that form of the signature, type, or
copy, PSigPrint("sig01") to the INPUT
line on the calculator and then click on the PERFORM button.

The internal form  this is the form used to communicate with the
system. This is the form used to edit and/or create signatures.
To see that form of the signature, type, or copy, showSig("sig01")
to
the INPUT line on the calculator and then click on the PERFORM button.

The object form  this is the actual form of the program objects
that are signatures, these objects include public and private methods as
well as instance variables. To see that form of the signature, type,
or copy, UAObj_sig01 to the INPUT line on
the calculator and then click on the PERFORM button.
In the above example the signatures is very small, that is, it only contains
a small number of operators. This is because the only integers we
put in the signature are 1, 0 and 1 and the only strings we put
in the signature are "A", "B" and "C". Clearly there will be times
when we want to deal with signatures that have much larger sets of operators.
For example, it might be desireable to talk about a signature for arithmetic
that contained all the integer numerals. Rather than write
down such large sets explicitly we will represent them by means of their
characteristic functions, that is, functions on the "set of all symbols"
which take the value "true" on the symbols in the desired set and take
the value "false" outside the given set. Of course there really
isn't any welldefined set of all symbols, but in most, if not all,
cases of interest this will not cause us any problems. Because we
are interested in implementing algebras on the computer and we are writing
on web pages we will generally use JavaScript programs to implement the
characteristic functions. Here, for example, is a JavaScript program
for the characteristic function of the set of "numbers" used in JavaScript:
function isaNum(item)
/*recognizes JavaScript numbers */
{var out = false;
if (typeof(item)=="number") out=true;
return(out)
}
Similarly, we can use the following JavaScript program for the characteristic
function of the set of "strings" used in JavaScript:
function isaString(item)
/*recognizes JavaScript strings */
{var out = false;
if (typeof(item)=="string") out=true;
return(out)
}
Signature sig02 shows the result of using
this approach to modify signature sig01.
To see this signature, perform MSigPrint("sig02")
on
the UAcalculator..
Here are some UAcalculator
operations that allow us to create new (temporary) signatures
and extract particular information from signatures.

makeSig(name, sorts, operators) Given a string, name,
an array of strings, sorts, and an array
of arrays of the form [ sortstring, arrayofoperation names],
operations,
this operation will construct a new signature with that data. Example:
try performing
makeSig("mysig", ["egg", "plate"], [["egg,plate", ["cook"]]])
You may then display this signature in, say, mathematical form, by
performing MSigPrint("mysig").
WARNING: Signatures defined in this manner are
temporary and will not survive reloading of pages.

SigAccess(name, field): Given a signature name, name, and a string,
field,
from the set {"name", "sorts", "operations"},
this operations returns the indicated information. Try performing
SigAccess("sig01",
"sorts"), or, if you have already used makeSig to define
a new signature try this operation on that signature.
Algebras
Definition:
Given a manysorted signature <S, >,
a <S, >algebra,
A,
consists
of an assignment of

a set, A_{s},
to each sort sS.
We call A_{s}the
of carrier sort s.

a function _{A}:A^{w} A_{s},
to each operator symbol _{w,s},
where , if w=s_{1}...s_{n}
then A^{w} = A_{s1}..A_{sn}.
end
Definition:
Given <S, >algebras
A and B we say that
A is a subalgebra of B if

For every sS
we have A_{s}B_{s}
.

For every wS*,
sS
and _{w,s}
we have that _{A
}and _{B}
agree on A^{w}.
end
Examples
of Algebras:
We will give
five examples algebras that have the following signature:
Example:
The "obvious" algebra
here is the algebra algA
in which we take algA_{int }to
be the set Z of all integers (an infinite
set) and take the operations to be the obvious ones:

zero_{algA}_{ }=
0

pred_{algA }(z)
= z1

succ_{algA}(z)
= z+1

add_{algA}(z,
z') = z+z'

mult_{algA}(z,
z') = z*z'
However a programmer might find it more obvious to consider the algebra
algB
where
we take take algB_{in}_{t}
to be a finite subset of Z , such as
the set Z = {z
 2,147,483,648
z 2,147,483,647
} together with an additional element 'error'.
Then we take

zero_{algB}=
0

pred_{algB}(z)
= z1 if z, z1Z
, else 'error'

succ_{algB}(z)
= z+1 if z, z+1Z
, else 'error'

add_{algB}(z,
z') = z+z' if z, z', z+z'Z
, else 'error'

mult_{algB}(z,
z') = z*z' if z, z', z*z'Z
,
else 'error'
Another possibility is to employ modular arithmetic,
say mod 5. Let algC
be the algebra we get by taking algC_{int}
= {0,1,2,3,4} and

zero_{algC}_{ }= 0

pred_{algC}(z)
= z1 mod 5

succ_{algC}(z)
= z+1 mod 5

add_{algC}(z,
z') = z+z' mod 5

mult_{algC}(z,
z') = z*z' mod 5
Note there is nothing special here about the use of 5
as the modulus  any positive integer n would
do  that is, we can take C_{int} = {0,1,...,n1}
and do all the operations mod n.
All the above examples are essentially arithmetic. However there
is nothing here (other than the suggestive names of the operators) that
says we have to be arithmetic, for example, we have a sigPalgebra,
algD,
when take algD_{int} = {true,
false}and interpret the operators as logical
operations

zero_{algD}_{ }=
true

pred_{algD}(z)
= not(z)

succ_{algD}(z)
= not(z)

add_{algD}(z,
z') = z or z'

mult_{algD}(z,
z') = z & z'
Actually that example is more arithmetic than it might appear  compare
it with the algebra similar to the third example but with n=2. So
here is an even less arithmetic example:
Take algE to be the sigPalgebra with algE_{in}_{t}=
A*,
the set of all strings on the alphabet A =
{a,b,c,...,z,A,B,C,...,Z}. Then we can take the operations
to be the following string operations:

zero_{algE}_{ }= "",
the empty string

pred_{algE}(z)
= the first, if any, character in z, else
the empty string.

succ_{algE}(z)
= z with the first character, if any, removed,
else z.

add_{algE}(z,
z') = zz',
the concatenation of z and z'

mult_{algE}(z, z') = z
\ z', z with the first, if any,
occurence of z' deleted.
Algebras on the UACalculators
To be able to implement these examples so that we can manipulate
them using the UAcalculator we have to write programs (in JavaScript)
for the operations and find computer representations for the elements of
the carrier. This is relatively straight forward for all but
the first example  the problem there is that we can not implement
all of the integers on a finite computer. However JavaScript (ala
Netscape) will handle very large integers  so we can pretend that we
have all of Z . The ith argument of an operation is written
as arg[i].
To describe an algebra we need to give: its signature,
the set of its carriers and the set of its operators. To present
this material to the computer we use the function Algebra(signame, carriers,
operations) where

The first argument, signame, is the name of the signature of the
algebra  that is a string. For the first example given above
the name is the string "alg_A".

The second element is an array of pairs where each pair consists of the
name of a carrier (i.e., a sort) and a JavaScript expression for the characteristic
function of the carrier but written as a string. For the first example
given above there is only one sort, int, and the corresponding characteristic
function is the function isaNum(arg[1]), a
function which returns the value true for numbers and false for nonnumbers
and we take the second argument to be the string "isaNum(arg[1])".
For many examples it is either difficult (or possibly impossible) to write
a JavaScript program for the characteristic function. In such cases
we can just enter the empty string. While the characteristic function of
the carrier(s) can be omitted, having the characteristic functions
of the carriers makes it possible to check arguments to see if they are
of the required type.

The third element is an array of pairs. There are two cases  one for
each way of presenting the constants in the signature:

If the constants in the signature are given individually, as in Sig01,
then each pair consists of the name of an operation and a JavaScript
expression written as a string. For the first example given above
the corresponding array of name/expression pairs is:
[
["zero", "0"],
["pred", "arg[1]1"],
["succ", "arg[1]+1"],
["add", "arg[1]+arg[2]"],
["mult", "arg[1]*arg[2]"]
]

If the constants in the signature are given by characteristic functions,
as in Sig02, then the pairs for the constants
consist of the characteristic function paired with another function which
takes each constant to its corresponding value. For example, if we
modify SigP so as to get a new signature,
SigQ,
with all natural numbers as constants, so that we have
The Signature sigQ in mathematical form:
name: sigQ
sorts: {int}
operations:
sigQ(int) = {zero, JSInt}
sigQ(int,int) = {pred, succ}
sigQ(int.int,int) = {add, mult}
End of signature sigQ.
where isaNat is a characteristic function
for the set of (JavaScript) natural numbers, then a corresponding algebra
could have the following operations
[
["zero", "0"],
[ JSInt, parseInt], // note that the functions
are not in quotes!
["pred", "arg[1]1"],
["succ", "arg[1]+1"],
["add", "arg[1]+arg[2]"],
["mult", "arg[1]*arg[2]"]
]
where parseInt is a function which, for
a number n, takes
the string "n" to the number n.
For the above examples this information has been built into the UACalculator.
The last example is the algebra alg_AA. You
can produce your own examples by using the function
new Algebra(signame,
carriers, operations)
The difficult part, of course, is writing the functions (in JavaScript)
needed for the characteristic functions of the sets of constants and operations.
More complex examples than the above (such as the upcoming programming
language syntax, semantics and compiling) require experience with
some of the more exotic parts of JavaScript.
Given an algebra name, alg, an operator
name , op, and a sequence,
a_{1},...,a_{n},
of arguments for op_{alg}drawn
from the carrier, we can evaluate op_{alg}(
a_{1},...,a_{n}) on the UACalculator by entering
the input evalOp(alg, op, a_{1},...,a_{n})
and
clicking on the perform button.
Exercise:

Try evaluating evalOp("alg_A", "add",
33, 77)  copy the green expression to the input line of the UAcalculator
and click on the perform button.

Now edit the input line by either changing the operator name (to
"zero", "succ", "pred" or "mult") or by changing the arguments and
click again on the perform button. Note, to edit a piece of
the text proceed as you would with a fullscreen editor (Basically:
put the curson in the desired position in the input and either insert text
by typing or delete text using the delete key on your keyboard).

Now try changing the algebra to one of the other examples ("alg_B",
"alg_C", "alg_D" or "Alg_E")  remember to change the arguments
to ones that are "appropriate" to the given algebra. If the
arguments are inappropriate you may either get a spurious answer or an
error message from the system. What is "appropriate"
varies from algebra to algebra.
In a later section we will see how to evaluate complicated
expressions built up from operators.
Homomorphisms:
We all know that, informally speaking, a function from a set A
to a set B is a rule which assigns to each
element of A an element of
B. The goal of this section is to generalize this idea to
signatures and algebra. That is, we want to define "functionlike"
things from a signature S_{1}to a
signature S_{2} and from an algebra
A
to an algebra B. The "functionlike"
things between signatures will be called signature morphisms. The
"functionlike" things between algebras will be called homomorphisms.
Definition:
Let S_{1} =
<S_{1}, _{1}>
and S_{2} = <S_{2}, _{2}>
be signatures, then a signature morphism from S_{1}to
S_{2}consists
of

F, a function
F:S_{1 }S_{2}

f , an (S*S)indexed
family of functions , f = < f_{w,s}:_{w,sF(w),F(s)
}
wS*, sS>
We may abreviate this as: <F,
f>:S_{1}S_{2}
.
end
Definition:
Let <S, >
be a signature, and let A and B
be <S, >algebras
then an <S, >homomorphism,
h:A
B, from A to B
consists of

h, an Sindexed
family of mappings, h = <h_{s }:A_{s}B_{s}
 sS >
that satisfies the homomorphism property. That is: for
each wS*,
sS,
and _{ws},
and a_{1},...,a_{w}
A^{w}, that
h(_{A}(a_{1},...,a_{n}})
= _{B}(h_{w1}(a_{1}),...,h_{ww}(a_{w})).
end
Example: An example of a homomorphism
for our examples is the homomorphism from the algebra A
of the first example to the algebra C of the
third example is the function, h, that takes
each integer n to the
integer n mod 5. We see
that, for example, for any two integers
p
and q in {0,1,2,3,4}
that
h(add_{A}(p, q))
= (p + q) mod 5
= (p mod 5)+_{mod 5}(q mod 5)
= add_{C}( h(p), h(q)).
To test this out, using the UAcalculator we must express the homomorphism
as a JavaScript function. In JavaScript
n mod 5 is written as n%5 thus
one can test (that's test, not prove) the homomorphism by evaluating
the expression evalOp("alg_A","add",
n,
p)%5
== evalOp("alg_C","add", n%5,
p%5)
for various choices of n
and p.
The operator == in the middle of the expression is an equality operator,
and what the test does is to check that the expressions to the left and
right of the equality yield the same value. Thus performance of this
expression should always yield the result true.
By
evaluating the sides separately you can see the actual values that they
produce and then do you own checking for equality.
If this notation puzzles or bothers you because the homorphism is written
using an infix operator (%) rather than as a prefix operator
(h) this problem can be eliminated as follows:
Define a temporary mod function by performing
the expression mod5 = function (x) {return
x%5} and then test the homomorphism by evaluating
the expression mod5(evalOp("alg_A","add",
n, p))
== evalOp("alg_C","add", mod5(n),
mod5(p))
for various choices of n
and p.
end
Definition:
Given an <S,>algebra
A,
we define the identity homomorphism for A
to be the homomorphism 1_{A} = <1_{A,s}:A_{s}A_{s}
 sS> where for each sS,
1_{A,s}
is the identity mapping on
A_{s} (the
mapping that takes each element to itself).
end
Definition:
Given homomorphisms h:AB
and g:BC
we define their composite, denoted gh,
to be the homomorphism gh:AC
, where for each sS,
(gh)_{s} = g_{s}h_{s }
(where the composition on the right side of the equation is the compositon
of mappings).
end
Exercise: Show that the above
definitions are well defined, i.e., that 1_{A}and
gh
are indeed homomorphisms.
end
Definition: A
homomorphism h:AB
is
said to be an isomorphism if there exists a homomorphism g:BA
such that gh
= 1_{A} and hg
= 1_{B}. In such
a case we may call g the inverse
of h and sometimes write it as
h^{1}.
end
Exercise: Show that if h:AB
is an isomorphism then its inverse is uniquely determined.
end
Definition:
Given a homomorphism h:AB
we
define its image to be the subalgebra C
of B where

For every sS,
Cs
= { bB_{s
} there
exists aA_{s} such
that h_{s}(a) = b}, i.e., C_{s}
is the image of h_{s}.

For every wS*,
sS and _{w,s},
that _{C}
agrees with _{B}
on C^{w}.
end
Notes:

Homomorphisms will play a major role in our computer science applications
of universal algebra. For example, many definitions such as that
of the "height of a tree" can be viewed as homomorphisms, and the
syntax, semanitics and compilation of structured programming languages
correspond to homomorphisms. They key to this applications is the
concept of
initial algebras.

We will also see later how we can generalize the notion of a homomorphism
so that we can "have homomorphisms between algebras with different signatures".
The trick there will be to combine the above definition of a homomorphism
with the above definition of a signature morphism.