Introduction

This second chapter introduces the basic concepts and notations related to equational theories, algebras, and term rewriting systems that are needed for the remainder of the book. Throughout the book, standard mathematical notations are used, in particular from set theory. Notation N = {0, 1, 2, …} denotes the natural numbers.

Equational theories

A central notion of this book is the notion of an equational theory. An equational theory is a signature (defining a ‘language’) together with a set of equations over this signature (the basic laws). Every process algebra in this book is presented as a model of an equational theory, as outlined in the previous chapter.

Definition 2.2.1 (Signature) A signature Σ is a set of constant and function symbols with their arities.

The objects in a signature are called constant and function symbols. The reason for doing so is to distinguish between these purely formal objects and the ‘real’ constants and functions they are meant to represent. In Section 2.3, where interpretations of equational theories are discussed, this point is elaborated further. Note that a constant symbol can also be seen as a function symbol of arity zero.

Example 2.2.2 (Signature) As an example, consider the signature Σ1 consisting of the constant symbol 0, the unary function symbol s, and the binary function symbols a and m.