Quasigroups by Mark Seemann
A brief introduction to quasigroups for object-oriented programmers.
This article is part of a larger series about monoids, semigroups, and other group-like algebraic structures. In this article, you'll get acquainted with the concept of a quasigroup. I don't think it plays that big of a role in software design, but it is a thing, and I thought that I'd cover it briefly with a well known-example.
During all this talk of monoids and semigroups, you've seen that normal arithmetic operations like addition and multiplication form monoids. Perhaps you've been wondering where subtraction fits in.
Subtraction forms a quasigroup.
What's a quasigroup? It's an invertible binary operation.
Inversion #
What does it mean for a binary operation to be invertible? It means that for any two elements a and b, there must exist two other elements x and y that turns a into b.
This is true for subtraction, as this FsCheck-based test demonstrates:
[Property(QuietOnSuccess = true)] public void SubtractionIsInvertible(int a, int b) { var x = a - b; var y = a + b; Assert.True(a - x == b); Assert.True(y - a == b); }
This example uses the FsCheck.Xunit glue library for xUnit.net. Notice that although FsCheck is written in F#, you can also use it from C#. This test (as well as all other tests in this article) passes.
For any a and b generated by FsCheck, we can calculate unique x and y that satisfy a - x == b and y - a == b.
Subtraction isn't the only invertible binary operation. In fact, addition is also invertible:
[Property(QuietOnSuccess = true)] public void AdditionIsInvertible(int a, int b) { var x = b - a; var y = b - a; Assert.True(a + x == b); Assert.True(y + a == b); Assert.Equal(x, y); }
Here I added a third assertion that demonstrates that for addition, the inversion is symmetric; x and y are equal.
Not only is integer addition a monoid - it's also a quasigroup. In fact, it's a group. Being associative or having identity doesn't preclude a binary operation from being a quasigroup, but these properties aren't required.
No identity #
No identity element exists for integer subtraction. For instance, 3 - 0 is 3, but 0 - 3 is not 3. Therefore, subtraction can't be a monoid.
No associativity #
Likewise, subtraction is not an associative operation. You can easily convince yourself of that by coming up with a counter-example, such as (3 - 2) - 1, which is 0, but different from 3 - (2 - 1), which is 2. Therefore, it can't be a semigroup either.
Summary #
A quasigroup is an invertible binary operation. Invertibility is the only required property of a quasigroup (apart from being a binary operation), but if it has other properties (like associativity), it's still a quasigroup.
I haven't had much utility from thinking about software design in terms of quasigroups, but I wanted to include it in case you were wondering how subtraction fits into all of this.
What if, however, you have a binary operation with no other properties?
Next: Magmas.
