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:

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

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.
 

Algebras

Definition:    Given a many-sorted signature <S, >, a  <S, >-algebra, A, consists of an assignment of

end

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

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 algAint to be the set Z of all integers (an infinite set) and take the operations to be the obvious ones: 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 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 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 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:
 

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:
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:

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 = <S1, 1>   and   S2 = <S2, 2>  be signatures, then a signature morphism from S1to S2consists of
 

  1. F, a function    F:S1 S2
  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

 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:AB  and g:BC  we define their composite, denoted gh,  to be the homomorphism  gh:AC , where for each sS,  (gh)s  = gshs  (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 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 = 1A  and hg = 1B.   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

end
Notes: