Initial Algebras

We can now return to the conjectures posed earlier concerning the class of algebras which are models of a given specification :

• how are the algebras which interpret a theory related ?
• is there one particular member or (sub-class) of the class of algebras which captures the essential properties of that entire class ?

It is important to remember that our specification provides a theory which describes the required properties and behaviour of a data type yet to be implemented. When an algebraic specification of an abstract data type is implemented, an appropriate representation for each value of the data type is chosen from the various models of the theory, with each operation being interpreted by a ``function'' or algorithm over that chosen representation. The design of the data type entails determining which of the various models of the presentation is the most appropriate.

The connection or ``family resemblance'' between the various algebras which make up the class (family) of algebras that models a given specification is provided by a special subset of that class. These special algebras are known as initial algebras. An initial algebra has the fundamental property that a unique homomorphism exists between that initial algebra and each member of the class. This means that every algebra which belongs to the class of models can be reached by application of a unique mapping (transformation) from an initial algebra. <sup>10.1</sup> Furthermore, it can be shown that all initial algebras (which interpret a theory) are isomorphic to each other and so are ``indistinguishable''. This formal statement simply expresses the fact that there is more than way of implementing a given data type, all of which are valid with respect to the theory. We can therefore talk about a single initial algebra which is unique up to isomorphism.

Another way of looking at this result is to think of the initial algebra(s) as the hub or centre of a wheel with all the other algebras of the class that interpret a signature placed radially around the wheel's circumference. Each of these perimeter algebras is connected to the hub by a single ``spoke'' which is the unique homomorphism from the ``focal'' initial algebra(s) to that perimeter algebra. Every algebra of the class can therefore be ``reached'' or ``derived'' from an initial algebra.

It is this observation which provides the answers to the two questions posed earlier and explains why the initial algebra is often used as the ``standard'' in the sense of being the ``most representative'' model of a theory presentation. This is the approach adopted in this text. One advantage of using initial models is that they do not have some of the undesirable properties which characterise many of the models. For example, models which have either junk or confusion (evocative terms !) are often discarded - properties not possessed by initial algebras. These ideas will be examined shortly with the aid of an illustrative example using a simple theory for Boolean values.