2. Static algebras

Q: Please explain to me what static algebras are exactly.

A: Gladly. Let me start at the very beginning. The term signature will be used to mean a finite collection of function names. It is supposed that each function name comes with an indication of its arity, i.e., the number of arguments. A static algebra of a signature is a nonempty set S, called the superuniverse, together with interpretations on S of function names in . A function name of arity r is interpreted as an r-ary function from S to S, i.e., a function from to S, and is called a basic function of the algebra. A basic function of arity zero is called a distinguished element.

Q: I thought a function is always a function of something so that the arity of a function is at least one.

A: Stretching notions is not new to science; recall the notion of zero-speed motion in physics for example. One may insist that zero-speed motion is no motion at all, but it is more convenient1< to view zero-speed motion as a special case of motion. By the way, in standard terminology, the term ``universe'', rather than ``superuniverse'', is used. We reserve the term ``universe'' for other purposes.

Here is an example of a static algebra (which I will have to modify). Suppose that a signature contains zero-ary function names 0, 1 and binary function names + and *. One static algebra of signature is obtained as follows: Take the superuniverse to be the set of integers and interpret the function names in the obvious way. There are other natural static algebras of signature , but in general a static algebra need not be natural; it may be very arbitrary.

Q: I understand that static algebras will represent snapshots of computational processes. Isn't your definition too restrictive? For example, you may want to extend that arithmetical static algebra by the division operation but the division operation is partial.

A: Instead of generalizing the notion of a static algebra by permitting partial functions, we will restrict attention to algebras with a distinguished element undef. In particular, that arithmetical algebra above should be modified by adding a new element undef. It can be further extended by adding the division function; we will have a / b = undef unless both a and b are integers and b divides a. Formally, every r-ary basic function f is defined on every r-tuple of elements of the superuniverse, but we will say that f is undefined at f() if f() = undef; the set of tuples with f() <> undef will be called the domain of f.

Q: Still, your static algebras seem too restrictive to me. How do you deal with different data types?

A: One possibility would be to generalize the notion of a static algebra and to consider many-sorted algebras; such algebras are widely used. But this is not necessary. We will suppose that every static algebra contains distinguished elements true and false. A basic function U, defined on the whole superuniverse, with values in {true, false}will be viewed as the set of elements a such that U(a) = true and called a universe. We will say that a belongs to U if U(a) = true.

Further, we will suppose that every static algebra has the equality relation, a universe Bool, comprising two elements true and false, and the usual boolean operations; the result of any boolean operation is undef if at least one of the arguments is outside Bool. Thus the arithmetical algebra should be modified again; a universe Integer comprising the integers can be declared as well. A relation R on a particular universe U will be represented by (and identified with) the characteristic function of R which is undefined (i.e. equal to undef) if at least one of the arguments is outside of U . Now we may further augment the twice modified arithmetic algebra by the standard ordering of integers.

Q: You can dispense with one of the two boolean values as it is done in Lisp. For example, true may be dropped and then any element different from false, with the possible exception of undef, will represent boolean truth.

A: Sure, but I prefer to distinguish between boolean truth and, say, numbers.

Q: Why do you need the trick of coding relations as functions? Why can't a signature contain relation names?

A: The reason is to make updates, introduced below, applicable to relations as well. By the way, ever-present basic functions with predetermined domains and values are called logical constants. Logical constants may be omitted when a static algebra is described. For example, the thrice modified arithmetical algebra can be described as follows. It has (1) a universe Integer comprising the integer numbers, (2) distinguished integers 0 and 1, (3) the usual total binary operations + and *, the usual partial operation / and the usual ordering < on Integer.

Q: Did we finish with logical constants?

A: Almost. Sometimes it is necessary to suppose that there is auxiliary infinite (or sufficiently large finite) universe Reserve disjoint from other universes and a special function that selects an element of Reserve. The role of Reserve will be clear soon.

Q: I am confused. I thought that we will be dealing with finite feasible static algebras reflecting snapshots of real computer computations. If this is the case, then there is no room for infinite universes.

A: In principle it is possible to keep everything finite and feasible. For example, the Reserve can reflect real computational resources. However, it is much more practical to divide concerns. You permit whatever universes and basic functions are convenient and, if necessary, you keep track of various resources.

Finally, let me recall the definition of closed terms of a given signature (the first clause is superfluous but it seems to make comprehension easier):

• Every zero-ary function name is a closed term.
• If f is a function name of arity r and are closed terms then f() is a closed term.