apo :: Functor f ⇒ RCoAlgebra f a → a → Fix f
      peikos :: RCoAlgebra Blog Tea
      
      peikos_net = apo peikos Sencha
         ↦ Blog "Math" "Logic" "Programming" "Natural Language"

Algebrae Everywhere (1)

Tuesday 29 January, 12.019 HE

This is still an early draft version of the article.

A lot of different things get called "algebra" From Al-Jabr, "the setting of broken parts" — Gandz, S. (1926). The Origin of the Term "Algebra". The American Mathematical Monthly, 33(9), 437-440. doi:10.2307/2299605 : starting from secondary school math where one is supposed to find $x$, the term quickly gains a myriad of meanings once one enters higher education in computer science, math, and probably many other subjects. During the last few years I have encountered Algebrae over a Field (or Ring), Boolean Algebra (which may or may not be the actual Algebra defined by George Boole Wildberger, N. J. (2018). The Algebra of Boole is not Boolean Algebra. YouTube. ), Heyting Algebra (the intuitionistic counterpart to Boolean Algebra), Frobenius Algebrae (with applications in linguistics) and F-Algebrae as used in functional programming. In this series of posts we will explore whether these Algebrae can be reduced to a common base, using the Algebra over a Ring as our starting point. This first post will lay the ground-work by building up to our definition of an algebra; future posts will explore the algebrae mentioned above, and maybe even more in the future.

Even though this post will contain moderately advanced concepts from a diversity of subjects, the aim will be to keep everything accessible to an undergraduate level of computer science / mathematics knowledge Whether I succeed in this is up to the reader's judgement and explain everything from the ground up accordingly. As such, this post may also serve as an introduction on the concepts discussed in it.

Algebrae over a Field or Ring

We will begin our journey to algebra with the most general structure on today's list: the algebra over a ring. In the literature you might encounter the algebra over a field instead, which can be a little more common as this better relates to other common mathematical structures. The difference between the two is minor: an algebra over a ring is slightly more general In general the more demanding the definition of a structure is, the more operations will be defined on it and the more "powerful" the object is. On the flip side, more demands in a definition also means less object are going to fit the bill, making an abstraction less general and therefore less "powerful" to abstract over different structures. , but most commonly used algebrae over rings are also algebrae over fields. As can be expected, the differnce between the two results mainly from the difference between rings and fields. Before we dive into the algebra part, we will first take a look at what we mean by those terms.

Some basic building blocks

Both the field and the ring are algebraic structures used to generalise number-systems as well as other more complex Complex and its antonym simple, in this context, do not simply mean easy and difficult. A simple concept is like a building block from which complex things can be built. A lego-block is simple, whereas a stack of lego-blocks is complex and a complete project even more so. mathematical objects. The goal of the abstraction thus provided is to see what intuitions we can develop within simple environments, and how they translate to a more complex setting.

Put a Ring on it

As most terms in this exploration, A ring is a term used to refer to a structure from abstract algebra There's that word again. Here it refers to mathmetical area of study instead of a concept within mathematics. The same holds for linear algebra, which we will touch on when we get to vector spaces further down. . A ring is the combination of a set of elements and two operations defined on the set that satisfy some constraints. Specifically, it behaves as an (Abelian) group on the first operator, which is commonly referred to as addition or $+$. Furthermore, its second operator (multiplication, $\times$ or $\cdot$) is a monoid. Finally, multiplication is said to distribute over addition. Formally, the ring is represented using a three-tuple of the set and the operations $(R, +, \cdot)$, with these axioms (commonly called the Ring-axioms $0$ and $1$ are used here to refer to specific elements in the ring, and may or may not be the numbers $0$ and $1$. ):

The most straightforward example of a ring is the integers $\mathbb{Z}$. Using regular addition and multiplication, we can easily see that the group laws over addition apply. The identity element, conveniently, is $0$, and the additive inverse of any natural number $n$ is $0-n$. We can also multiply natural numbers, where multiplication is associative and has identity element $1$. Multiplication is also commutative (which is not necessary for a ring, but does serve to make our ring a commutative ring Bet you did not see that one coming! ) and distributes over addtion. The only thing missing for us to have a second group over multiplication is an inverse: we cannot find a number $n^{-1}$ which, when multiplied by $n$ gives us $1$. Fractions come to mind, but as we are operating in the domain of the integers, this will not do. Should we expand our views to include those, we encounter a richer structure called a field.

Another example of a ring would be the set of square matrices of order $n$. As an example, consider the set of $2 \times 2$-matrices. Two matrices can be added using matrix addition, which is associative and commutative. The additive identity is the zero-matrix, and the additive inverse of any matrix can be constructed by flipping the sign of each entry. We can also multiply By convention, we do not write a multiplication operator between two matrices; the multiplication sign is implied when two matrices are right next to eachother. two $2 \times 2$-matrices, resulting in another $2 \times 2$-matrix. This operation is associative, but not commutative (as the example below shows). The identity-matrix can be used as the multiplicative identity, but not every matrix will have an inverse. Finally, multiplication distributes over addition.

$$\begin{bmatrix}a & b \\ c & d\end{bmatrix} \begin{bmatrix}e & f \\ g & h\end{bmatrix} = \begin{bmatrix}ae+bg & af+bh \\ ce+dg & cf+dh\end{bmatrix} \neq \begin{bmatrix}ea+fc & eb+fd \\ ga+hc & gb+hd\end{bmatrix} = \begin{bmatrix}e & f \\ g & h\end{bmatrix} \begin{bmatrix}a & b \\ c & d\end{bmatrix}$$

Strawberry Fields

The definition of a field mirrors and expands on the definition of a ring. Any field must obey all ring-axioms, and then some. Specifically, the multiplicative operator $\cdot$ is now required to form a group as well, which means it should be abelian (commutative) and have a (multiplicative) inverse except for the element $0$ (the additive identity) which is ignored. This sounds a little vague, but a few examples should clear things up. Our first example of a ring, the natural numbers, no longer qualifies: there is no multiplicative inverse. To get a field, we must expand to rational numbers $\mathbb{Q}$: any number that can be written as a fraction of two natural numbers. Here, the multiplicative inverse $x^{-1}$ is defined to be $\frac{1}{x}$. As it is impossible to divide by zero (the additive identity) this element has no multiplicative inverse in $\mathbb{Q}$, which exactly fits te definition.

Formally, the definition of a field looks a lot like the definition of a ring In the definition below, unchanged parts have been omitted. . Again, we represent our field using a three-tuple of the set and the operations $(K, +, \cdot)$ Fields are in general represented using the letter $K$, for some reason. , with these axioms (commonly called the Ring-axioms):

Any field must also be a ring, as the requirements for being a field include all the requirements for being a ring. This makes the ring a more general abstraction, whereas the field provides a greater insight into the internal workings of a mathematical object. Not every ring is a field, as the example of $\mathbb{Z}$ shows.

Further examples of fields include the real numbers $\mathbb{R}$ and the complex Complex here refers to the fact that these numbers are composed of two reals, analogous to the use of the term given in the sidenote() above. numbers $\mathbb{C}$. Both of these serve as common bases for our next exposition: the vector space.

Another Dimension

Our next step towards an Algebra over a Field is the concept of a vector space. Just as with rings and fields, the term vector space is used to refer to a specific mathematical structure, but whereas a ring and a field are simple, a vector space is our first example of a complex structure. A vector space $V$ is defined on top of an underlying field $K$ and combines a set of objects called vectors, the aforementioned field and two operators: addition and scalar multiplication. Addition, in this sense, operates on a pair of vectors, producing a new vector. Scalar multiplication operates on an element of the underlying field together with a vector to produce a new vector $K \times V \to V$ Notice the use of $\times$ here not to mean multiplication but the cartesian product of two vector spaces. In general, the notation $A \times B \to C$ will be used to represent the type of a function taking a pair of $A$ and $B$ to something of type $C$. Vector addition has type $V \times V \to V$, and field multiplication $K \times K \to K$. As these types are obvious for operations within a structure, they have been omitted so far, but I will include them whenever necessary. . For a vector space to be well behaved, the following axioms must hold:

Note that we cannot, in general, multiply two vectors together; some vector spaces might have an inner product defined, or a cross product, or a wedge product, but these operations are defined on top of the vector space structure rather than be part of it.

Intuitively, the prime example of a vector space and vectors is, well, a space of vectors: Ordered lists of numbers of a fixed length, representable by arrows in a given space. Addition works element-wise with the all-zero vector $\mathbf 0$ as identity element, and scalar multiplication will multiply every element by the same scalar.

As an example, consider the space of two-dimensional vectors with real coefficients $\mathbb{R}^2$. It can be interpreted as an ordered column of two real numbers, as an arrow in 2D world, or as a combination of a 1-dimensional length and a single angle. Though these representations are all equivalent, we will focus on the numerical form as shown below. Convince yourself that all vector space axioms hold, assuming the axioms of the underlying field are observed.

R-Modules

The idea of a vector space is a powerful tool when working with a structure built upon a field. In many cases, however, the requirement of an underlying field is unnecessarily harsh. If, for example we want to work on "vectors" made of integer numbers, we run into a problem: The integers form a ring, but not a field! Luckily, we can use the same four axioms for scalar multiplication, as the multiplicative inverse of the ring (the one thing missing from our ring compared to a field) is not used in these axioms at all. We can thus define a similar structure, albeit based on a ring instead of a field, to be slightly more general. The resulting structure is called a module, and it is in many ways just a slightly less conformist cousin of the vector-space.

The vector space and R-modules we've seen so far expect scalar multiplication to happen on the left: $K \times V \to V$ for vector spaces and $R \times M \to M$ for modules. In module theory, a distinction is made between left and right R-modules. The left R-module is exactly what we've seen before: Scalar multiplication is $R \times M \to M$, and no operation $M \times R \to M$ is required The operations an instance of a structure can have are not limited to those required by the structure, e.g. a field can support more operations than just addition and multiplication without losing its status as a field. to exists . The right R-module is the exact opposite in this regard: Scalar multiplication is $M \times R \to M$, with the scalar value on the right. Left scalar multiplication is left undefined in a right R-module. When both left and right scalar multiplication are allowed and the result is equal for both variants, the resulting structure is defined as R-bimodule If we have a structure which supports two different kinds of scalar multiplication (one from the left, and one from the right , this is called an R-S-bimodule, where $R$ refers to the ring whose elements multiply from the left, and $S$ refers to the ring multiplying from the right. An example of an R-S-bimodule is a non-square $n \times m$-matrix, which can be multiplied from the left by $n \times n$-matrices and from the right by $m \times m$-matrices.).

Finally! An Algebra!

We're almost there! To turn our vector space or module into a Algebra, the only thing we need to do is define a bilinear operation $A \times A \to A$. In the case of an algebra constructed from a vector space, $A$ is synonymous with $V$ and the resulting structure is called a K-algebra to signify that we are dealing with an algebra over a field. Similarly, when our starting point is an R-module we have defined a R-Algebra over a ring where $A$ is synonymous with $M$.

— TBD —

Recap and To be Continued

The model presented above, the algebra over a ring, will be our mold in checking the algebra-ness algebraicity? of more developed structures. Where possible, we will also check whether the conditions for an algebra over a field are met.

Join me — in the future — when we continue our exploration by considering the Boolean and Heyting Algebrae.