Adventures in Abstract Algebra Part I

As programmers, we are often on the lookout for structure. If two distinct programs share the same structure, there are probably a variety of properties they also share. This can help us to begin reasoning about them even before we’ve grasped all the details. Ascending the ladder of abstraction allows us to focus on principles that can be applied to a wide range of cases. It also makes it possible to identify the form of a solution to novel problems.

Abstract algebra is the study of an interesting class of structures. We have an algebraic structure whenever we have a set and at least one binary operation on that set (satisfying a few simple properties). In this series, we’re going to try implementing some algebraic structures and think about how we might verify that an implementation satisfies a set of properties. We’ll also look briefly at how proving a piece of code instantiates an algebraic structure can enable us to draw conclusions about how the code will behave.

In this post, we’ll go over the basics of abstract algebra, identifying different algebraic structures by the algebraic properties they satisfy. We’ll then try our hand at implementing these structures in Scala.

In the second post in this series, we’ll turn our attention to finite algebraic structures and develop a method for proving that a given Scala implementation really satisfies the properties it’s supposed to.

In the third post, we’ll look at cases where this verification method breaks down because our target structure is too large to exhaustively test. We’ll use ScalaCheck to construct inductive (as opposed to deductive) arguments that an implementation of an infinite or large structure satisfies the relevant properties.

Defining Algebraic Structures

Let’s begin with a brief overview of algebraic structures and their properties.

An algebraic structure consists of a set $A$ and a binary operation $*$ on $A$, and is written <$A, *$>. The binary operation $*$ must be some total function that is closed over $A$.

$*$ is a total function iff (if and only if) it is defined for any $a, b \in A$.

$*$ is closed over $A$ iff for any $a, b \in A$, $(a * b) \in A$.

As an example, consider addition over the positive integers. First, notice that we can add any two positive integers together. Second, notice that no matter which integers we choose, their sum is another positive integer. This means addition over the positive integers satisfies both totality and closure, respectively.

Addition, of course, is conventionally represented by $+$, but it could just as easily be represented by $*$. We will stick to the conventional symbols when appropriate, but continue to use $*$ when formulating general properties of binary operations.

Does division over the positive integers form an algebraic structure? It turns out that it does not. First, it is false that division is defined for any two positive integers (think of division by zero). Second, it is false that the quotient of any two positive integers is another positive integer. Consider $3 \div 2$. So division over the positive integers fails to satisfy either totality or closure, and thus fails to form an algebraic structure.

Mathematicians are interested in a variety of algebraic properties that can be used to distinguish algebraic structures and prove theorems about them. The properties we’ll be focusing on should be familiar from grade school arithmetic.

The first property we’ll look at is associativity:

• Associativity: A binary operation $*$ is associative iff for any $a, b, c \in A$, $(a * b) * c = a * (b * c)$.

An algebraic structure with an associative operation is called a semi-group. Addition over the positive integers forms a semi-group, for example. For any three positive integers $a$, $b$, and $c$, $(a + b) + c = a + (b + c)$

Next, an algebraic structure can have an identity element:

• Identity Element: An identity element $e$ exists for <$A, *$> iff for any $a \in A$, $e * a = a * e = a$.

A semi-group with an identity element is called a monoid. You’ll notice that addition over positive integers does not form a monoid. That’s because the identity element for addition is $0$. But $0$ is not a positive integer. However, addition over the natural numbers (defined as the non-negative integers) does form a monoid. That’s because the non-negative integers include zero, and so, for any natural number $n$, we have $0 + n = n + 0 = n$.

A monoid for which every element is invertible is called a group. But what does it mean for an element $a$ to be invertible? It means that there exists an inverse of $a$, normally written $a^{-1}$.

• Inverse Element: An inverse element $a^{-1}$ exists for an $a \in A$ iff there exists some element $a^{-1} \in A$ such that $a^{-1} * a = a * a^{-1} = e$.

Notice that the existence of an inverse element depends on the existence of an identity element $e \in A$. This means that any invertible algebraic structure must also contain an identity element. A group is invertible, contains an identity element, and has an associative binary operation.

Unfortunately, addition over the natural numbers fails to form a group, since it is false that every natural number has an inverse. $0$ has an inverse, namely itself. That’s because $0 + 0 = 0$, and $0$ also happens to be the identity element for addition. But what is the inverse of $1$? There is no natural number that when added to $1$ yields $0$.

Addition over the integers (negative and non-negative) does form a group, however. As we have already seen, $0$ is its own inverse. For any other integer $n$, we can find an inverse by taking $-n$. This illustrates an important point. If an algebraic structure is invertible, there should exist a function mapping each element to its inverse. In the case of addition over the integers, that function is

$f(n) = -n$

Since $0 = -0$, this function covers every integer.

Another example of a group is multiplication over the rational numbers without zero. The rational numbers, you’ll recall, are any numbers that can be put in the form $\frac{n}{m}$. We find the inverse of a rational number (other than zero) by $f(n) = \frac{1}{n}$. It is always the case that $n * \frac{1}{n} = 1$. And of course $1$ is the identity element for multiplication.

We will go one step further and consider commutativity:

• Commutativity: A binary operation $*$ is commutative iff for any $a, b \in A$, $a * b = b * a$.

A group with a commutative operation forms an abelian or commutative group. Addition over the integers once again fits the bill. That’s because it doesn’t matter what order you add two integers. You’ll always get the same result. The same holds for multiplication over the rational numbers without zero.

Here’s a table of structures and their corresponding properties:

We’ve considered four kinds of algebraic structures, but we haven’t yet looked at any code. In the next section, we’ll look at one way to represent these algebraic structures in Scala.

Scala Implementation

Let’s begin with the simplest possible algebraic structure. As you’ll recall, all we need is a set $A$ (possibly infinite) and a binary operation that is total and closed over $A$.

  trait AlgStruct[A] {
    def op(a: A, b: A): A
    def is(a: A, b: A): Boolean = (a == b)
  }

Our binary operation is represented by op, which has the signature (A, A) => A. We also add a method is for checking equality between members of our set. We can override this method if we need to define equality or leave it be otherwise.

We are using a polymorphic type variable A to represent the set $A$. Our operation takes two As and returns an A. Is this enough to satisfy totality and closure?

Closure appears to hold since op returns an A wherever it is defined. But totality is not as clear cut. For example, consider a division function with the signature (Double, Double) => Double. This function is not actually defined for every $(a, b) \in$ Double. Think of division by zero.

So although our trait AlgStruct “claims” to represent the simplest possible algebraic structure, our code does not ensure it. We will see this pattern repeated in what follows. It’s only in Part II of this series that we will begin to address the question of how we can verify that a given implementation of AlgStruct really forms an algebraic structure.

We can provide an implementation by extending this trait. For example, if we want to represent addition over integers, we could write the following:

  case class IntAdd extends AlgStruct[Int] {
    def op(a: Int, b: Int): Int = a + b
  }

Our set is all the Ints and our operation is addition. Now, Scala Ints are not identical to integers. For one thing, the integers are infinite and Ints are bounded. So for now we’ll stick with addition over Ints and hope it shares the relevant properties with addition over integers. We’ll address how to verify (or disprove) this guess in a later part of this series.

How do we represent our next algebraic structure, the semi-group? Recall that a semi-group is an algebraic structure with an associative operation. Here’s one approach:

  trait SemiGroup[A] extends AlgStruct[A] {
      //Op is associative
  }

Not very impressive, perhaps. After all, this is just an AlgStruct with a comment thrown in. But since we’ve not yet determined how we’re going to check algebraic properties, we’ll have to be satisfied with it for now. At the moment, our contract with anyone implementing this trait is something like, “Hey programmer, make sure your operation is associative.” We’ve not yet done anything to help verify this.

The monoid (a semi-group with an identity element $e$) adds a little more structure:

  trait Monoid[A] extends SemiGroup[A] {
    //Identity element
    val e: A
  }

Again, we’re counting on the person implementing this structure to supply some e that really does count as an identity element. Here’s an example, sticking to addition over Ints.

  case class IntAdd extends Monoid[Int] {
    def op(a: Int, b: Int): Int = a + b
    val e = 0
  }

The last structure we’ll implement is the group, which we’ve already seen is an invertible monoid. We’ll need to require an inverse function that maps every $a$ in $A$ to its inverse element.

  trait Group[A] extends Monoid[A] {
    def inv(a: A): A
  }

Addition over integers, as we’ve seen already, forms a group. We simply take the negative of any element to get its inverse. Perhaps this will work for addition over Ints as well, so we can write the following code:

  case class IntAdd extends Group[Int] {
    def op(a: Int, b: Int): Int = a + b
    val e = 0
    def inv(a: Int): Int = 0 - a
  }

Though we’re not yet validating the fact that inv really generates inverse elements, it seems intuitively that adding any $a$ to $(0 - a)$ will yield $e$. We’ll have to wait to see if we can verify this intuition for Scala Ints.

We could continue with abelian groups, rings, integral domains, and fields, but we’ll stop here. If you’re curious, you can see implementations of these further structures in my GitHub project algebraic structures in Scala↗(opens in a new tab).

So far, we’ve provided the skeletons for several algebraic structures. However, we’ve not yet proven that putative implementations satisfy the relevant algebraic properties. We’re going to turn to this issue in Part II, where we’ll consider finite structures and employ a method I’ll be calling exhaustion to prove that an implementation really is the structure it claims to be. We’ll then turn to verifying implementations of infinite structures in Part III.