Set Theory and Algebra in Computer Science A Gentle Introduction to Mathematical Modeling

Algebra greatly broadened the very notion of algebra in two ways. First, the traditional numerical domains such as Z, Q R, and C, were now seen as instances of more general concepts of equationally-defined algebraic structure, which did not depend on any particular representation for their elements, but only on abstract sets of elements, operations on such elements, and equational properties satisfied by such operations. In this way, the integers Z were seen as an instance of the ring algebraic structure, that is, a set R with constants 0 and 1, and with addition + and mutiplication ∗ operations satisfying the equational axioms of the theory of rings, along with other rings such as the ring Zk of the residue classes of integers modulo k, the ring Z[x1, . . . , xn] of polynomials on n variables, and so on. Likewise, Q, R, and C were viewed as instances of the field structure, that is, a ring F together with a division operator / , so that each nonzero element x has an inverse 1/x with x ∗ (1/x) = 1, along with other fields such as the fields Zp, with p prime, the fields of rational functions Q(x1, . . . , xn), R(x1, . . . , xn), and C(x1, . . . , xn) (whose elements are quotients p/q with p, q polynomials and q , 0), and so on. A second way in which  Algebra broadened the notion of algebra was by considering other equationally-defined structures besides rings and fields, such as monoids, groups, modules, vector spaces, and so on. This intimately connected algebra with other areas of mathematics such as geometry, analysis and topology in new ways, besides the already well-known connections with geometic figures defined as solutions of polynomal equations (the so-called algebraic varieties, such as algebraic curves or surfaces). Universal Algebra (the seminal paper is the one by Garett Birkhoff ), takes one more step in this line of generalization: why considering only the usual suspects: monoids, groups, rings, fields, modules, and vector spaces? Why not considering any algebraic structure defined by an arbitrary collection Σ of function symbols (called a signature), and obeying an arbitrary set E of equational axioms? And why not developing algebra in this much more general setting? That is, Universal Algebra is just  Algebra brought to its full generality. Of course, generalization never stops, so that Universal Algebra itself has been further generalized in various directions. One of them, which we will fully pursue in this Part II and which, as we shall see, has many applications to Computer Science, is from considering a single set of data elements (unsorted algebras) to considering a family of such sets (many-sorted algebras), or a family of such sets but allowing subtype inclusions (order-sorted algebras). Three other, are: (i) replacing the underlying sets by richer structures such as posets, topological spaces, sheaves, or algebraic varieties, leading to notions such as those of an ordered algebra, a topological algebra, or an algebraic structure on a sheaf or on an algebraic variety; for example, an elliptic curve is a cubic curve having a commutative group structure; (ii) allowing not only finitary operations but also infinitary ones (we have already seen examples of such algebras with infinitary operations —namely, complete lattices and complete semi-lattices— in §7.5); and (iii) allowing operations to be partial functions, leading to the notion of a partial algebra. Order-sorted algebras already provide quite useful support for certain forms of partiality; and their generalization to algebras in membership equational logic provides full support for partiality (see [36, 39]).