# 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 many-sorted 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 UA-Calculators

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 UA-Calculator and some of its special built-in functions you can display the signature in several different ways.
1.  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.
2. 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.
3. 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.
4. 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 well-defined 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 UA-calculator..

Here are some  UA-calculator 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 [ sort-string, array-of-operation- 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 many-sorted signature <S, >, a  <S, >-algebra, A, consists of an assignment of

• a set, As, to each sort sS.  We call Asthe of carrier sort s.
• a function A:Aw As,  to each operator symbol w,s, where , if w=s1...sn then Aw = As1..Asn.
end

Definition:  Given <S, >-algebras A and B we say that A is a subalgebra of B if

• For every s we have  AsBs .
• For every wS*, sS and w,s we have that A and B agree on Aw.
end

Examples of Algebras:

We will give five examples algebras that have the following signature:

Example:

The Signature sigP in programming form:

name: sigP

sorts: {int}

operators
zero: -->int
pred:int-->int
succ:int-->int
mult:int.int-->int

End of signature sigP.

The "obvious" algebra here is the algebra algA in which we take algAint to be the set Z of all integers (an infinite set) and take the operations to be the obvious ones:
• zeroalgA 0
• predalgA (z) = z-1
• succalgA(z) = z+1
• multalgA(z, z') = z*z'
However a programmer might find it more obvious to consider the algebra algB where we take  take algBint 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
• zeroalgB 0
• predalgB(z) = z-1 if z, z-1Zelse 'error'
• succalgB(z) = z+1 if z, z+1Zelse 'error'
• addalgB(z, z') =  z+z' if z, z', z+z'Zelse 'error'
• multalgB(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 algCint = {0,1,2,3,4}  and
• zeroalgC 0
• predalgC(z) = z-1 mod 5
• succalgC(z) = z+1 mod 5
• addalgC(z, z') =  z+z' mod 5
• multalgC(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 Cint = {0,1,...,n-1} 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 sigP-algebra, algD,  when take algDint = {true,  false}and interpret the operators as logical operations
• zeroalgD true
• predalgD(z) = not(z)
• succalgD(z) = not(z)
• addalgD(z, z') =  z or z'
• multalgD(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 sigP-algebra with algEint= 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:

• zeroalgE "",  the empty string
• predalgE(z) = the first, if any, character in z, else the empty string.
• succalgE(z) = z with the first character, if any, removed, else z.
• addalgE(z, z') =  zz',  the concatenation of z and z'
• multalgE(z, z') = z \ z'z with the first, if any, occurence of z' deleted.

### Algebras on the UA-Calculators

To be able to implement these examples so that we can manipulate them using the UA-calculator 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

1. 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".
2. 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 non-numbers 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.
3. 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"],
["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}

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"],
["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 UA-Calculator.  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, a1,...,an,  of arguments for  opalgdrawn from the carrier,  we can evaluate opalg( a1,...,an)  on the UA-Calculator by entering the input  evalOp(alg, op,  a1,...,an) 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 UA-calculator 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 "function-like" things from a signature S1to a signature S2 and from an algebra A to an algebra B.   The "function-like" things between signatures will be called signature morphisms.  The "function-like"   things between algebras will be called homomorphisms.

Definition:  Let S1 = <S11>   and   S2 = <S22>  be signatures, then a signature morphism from S1to S2consists of

1. F, a function    F:SS2
2. f ,  an  (S*S)-indexed family of functions , f = < fw,s:w,sF(w),F(s) | wS*, sS>
We may abreviate  this as:  <F, f>:S1S2 .
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

1. h,  an S-indexed family of mappings,  h = <hs :AsBs | sS >

2. that satisfies the homomorphism property.  That is: for each wS*, sS, and ws,  and a1,...,a|w| Aw, that

h(A(a1,...,an})  = B(hw1(a1),...,hw|w|(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(addA(p, q))      =  (p + q) mod 5
=  (p mod 5)+mod 5(q mod 5)
To test this out, using the UA-calculator 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 1A = <1A,s:AsAs | sS> where for each sS, 1A,s is the identity mapping on As (the mapping that takes each element to itself).
end

Definition:  Given homomorphisms h:A and g:B we define their composite, denoted gh,  to be the homomorphism  gh:AC , where for each sS,  (gh)s  = gsh (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 1Aand g 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 = 1A  and hg = 1B.   In such a case we may call  g the inverse of 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 = { bBs |  there exists aAs  such that hs(a) = b}, i.e., Cs is the image of hs.
• For every wS*, sS and w,s,  that C agrees with B  on Cw.
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.