OVO Tech Blog

# An intro to algebraic structures

Posted by Erica Giordo on .
Featured

# An intro to algebraic structures

Posted by Erica Giordo on .

TL;DR just maths, no code

A couple of weeks ago I was going through the Typelevel libraries and I noticed that I've never played around with Algebra, an experimental project that interoperates with Cats via the kernel module. Algebra is used by Algebird (twitter library, used by Scalding) and Spire. Looking into the latter, it seems pretty interesting, 'cause it introduces the basic maths number types, such as natural, rational and complex numbers. As the other Typelevel libraries, Algebra uses type classes to recreate algebraic structures such as monoids, abelian groups and rings.

Most of the time we stop at the computer science definition of these structures, but what if we look at them from a maths perspective? Maybe it could help to understand what they really are, and it could be fun (for a given value of fun).

# History

The algebraic structures that we're going to explore in this post are basic concepts for group, ring and Galois theories.

The origin of group theory dates back to mid 17th century and sees on his path contributors like Gauss and Galois. The grounds of group theory are numbers theory, geometry and the important studies of algebraic equations: it is indeed from the latter that originates the quest of solutions of polynomial equations of degree higher than 4, problem to which mathematicians such Lagrange and Ruffini tried to find a solution in the 18th century. A great contribution has been given from the mathematician Abel, from which the commutative group take also the adjective "abelian".

Ring theory finds its origins in the 19th century, while trying to prove the last Fermat theorem (there are no solutions for an + bn = cn for n > 2 - solved in 1994). The definition of ring as a structure is attributed to Dedekind, but the name has been given by Hilbert in 1897.

# Algebraic structures

First of all, let's define a binary operation `⦁` on a set `S` (`(S, ⦁)`). Given a set `S` and an operation `⦁:S x S -> S`, we can say that

∀ x, y ∈ S, x ⦁ y ∈ S

This is the definition of magma, a really easy algebraic structure. As the function above describes, for `(S, ⦁)` to be a magma the operation has to be closed, meaning that the result of `x ⦁ y` has to be a value of `S`.

An example could be `(ℕ, +)`, but not `(ℕ, -)`, since the sum of 2 natural numbers will always be in ℕ, but the difference could belong to ℤ.

## Semigroup

Given a set `S` and an operation `⦁` on it, then `(S, ⦁)` is a semigroup if `⦁` is associative, so if

∀ x, y, z ∈ S, (x ⦁ y) ⦁ z = x ⦁ (y ⦁ z)

An example of semigroup could be `(ℕ,*)`.

## Monoid

Given a set S, the identity element can be defined as

∃ e ∈ S | x ⦁ e = e ⦁ x = x

A semigroup with an identity element is a `monoid`.

An example for a monoid could be `(ℕ+{0}, +)` (where 0 is the identity element).

## Group

A group is a couple `(S, ⦁)` where each element has an inverse. Given `e` the identity element of S, the inverse is defined as

∀ x ∈ S, ∃ y ∈ S | x ⦁ y = y ⦁ x = e

A group is called abelian (or commutative) if the operation on it is commutative, so if

∀ x, y ∈ S, x ⦁ y = y ⦁ x

An example of a group is `(ℂ, +)`, which is also an abelian group.

## Ring

Given `S` a set, `*` (product) and `+`(sum) two binary operations on `S`, `(S, *, +)` is a ring if `(S, +)` is an abelian group, `(S, *)` is a monoid and sum and product respect the distributive law:

∀ x, y, z ∈ S => x * (y + z) = x * y + x * z and (x + y) * z = x * z + y * z

An example can be the finite sets `ℤ/nℤ = {0, 1, 2, ..., n - 1}`. If we consider `ℤ/5ℤ`, `3 + 4 = 3` and `2 * 3 = 2`: the identity element for the sum is 0, for the product is 1.
Another example could be `M(n, ℕ)`, the set of matrixes n by n with values in ℕ. Let's consider `M(2, ℕ)`: the identity element for the sum is the zero matrix, while for the product is the 2 by 2 identity matrix.

# Conclusion

Given the all the definitions above, we can then say that every ring is an (abelian) group, that is a monoid, that is a semigroup, that is a magma.
These are really basic concepts, but there's a lot beyond group and ring theories. These structures are not just abstract definitions, but instead they find applications in cryptography, physics and chemistry.
In the end, maths is less abstract than we think, we can find an example of it in every corner we look. As Galileo Galilei said, "the laws of nature are written in the language of mathematics".