Visual representation of group axioms

Groups are mathematical structures mostly discussed by learners pursuing a degree in mathematics. They are one of the most difficult topics in the undergraduate mathematics degree.

This blog aims to relate it to computer science by discussing axioms in terms familiar to computer science students. This blog will discuss how groups can be represented using an automaton and how its axioms can be understood visually. This visual representation will help in understanding some of the fundamental concepts of group theory, not related to the axioms alone, but also concepts like subgroups, cyclic groups, normal subgroups, etc.

In this blog, we’ll restrict our discussion to the finite groups.

Group axioms#

Let’s start by defining a group. A group is a structure that consists of a set $S$ of elements and a binary operator $(*)$ such that the following four properties hold. These properties are also called the axioms of groups.

• Closure: If $a$ and $b$ are two elements of the set $S$, then applying a binary operator on these elements $(a*b)$ will result in an element that also belongs to the set $S$.

• Associativity: The binary operator is associative, i.e., $a*(b*c) = (a*b)*c$. In simpler words, if we want to perform the calculation $a*b*c$, then the order in which we operate the binary operators doesn’t matter because they’ll give the same results.

• Identity: In the set $S$, there’s an identity element $e$ such that $a*e = a = e*a$.

• Inverse: For every element $a$ in $S$, there’s another element $a^{-1}$ in $S$ such that $a * a^{-1} = a^{-1} * a = e$.

An example of a group#

$\mathbb{Z}$ is the set of integers, $\mathbb{Z}^+$ is the set of positive integers, and $\mathbb{Z}_n$ is the set containing the first $n$ non-negative integers, $\{0, 1, 2, \cdots, n-1\}$. $\mathbb{Z}_5 = \{0, 1, 2, 3, 4\}$. $\mathbb{Z}_5$ is a group under addition modulo $5$. This means that the binary operator for this group is defined as follows:

$a*b = a+b\hspace{2em} (mod \space 5)$

This group can also be represented by the group table, which is shown below.

Consider the cell highlighted in green. It represents the result of the binary operator $a*b$ with the values of $a=3$ and $b=4$. The value of $3+4$ in $mod\space 5$ (remainder when divided by $5$) is $2$.

Now, we’ll briefly discuss automata.

Finite automata#

Finite automata is a mathematical structure consisting of the following:

• A finite set of states, usually represented by $Q$

• A start state, usually represented by $q_0$, $(q_0 \in Q)$

• A set of alphabets, usually represented by $\Sigma$

• A transition function, $\delta: Q \times \Sigma \rightarrow Q$

A transition function takes an element from the set of states, $Q$, and another element from the set of alphabets, $\Sigma$. Based on the combination, it produces an output, which is an element from the set of states, $Q$.

Consider an example where we want to compute the remainder when the given binary number is divided by $5$. There are five possible remainders, so the set of states, $Q = \{0, 1, 2, 3, 4\}$. The number is given in binary, which means that the set of alphabets that represents the binary by number at the input, $\Sigma = \{0, 1\}$. In the beginning, we don’t have any number of bits, which corresponds to the number zero. Since the remainder of $0$ when divided by $5$ is also $0,$ the start state will be $0$. The transition function can be represented by the following table. It’s important to note that the focus of this blog is not to discuss the methods to create finite automaton; we just want to represent finite groups using them.

In the table above, consider the cell in green, where state = $3$ and alphabet = $1$. The state = $3$ means that the remainder of the numbers (bits) read so far is $3$, and alphabet = $1$ means that the next bit has a value of $1$. Appending a zero (in binary) at the end is equivalent to multiplication by $2$, and appending a $1$ instead adds a value of $1$ to this figure. This means that if the next bit (alphabet) is one, then the remainder, or the number, gets multiplied by $2$, and then we add $1$. This means that $3\times2+1=7$, and the remainder is $2$ when we divide it by $5$. This is how we reach the number $2$ as the value placed in the cell.

The good thing about this transition function is that it can be represented by state diagrams. The state diagram for this table is given below. All the states are shown in circles, and the alphabets that correspond to the transitions are shown by arrows. The above-mentioned transition starts from state = $3$ (shown in green), and on reading the input alphabet $1$ (shown in red), goes to the output state $2$ (shown in blue). The start state is $0$, so there’s an arrow pointing at this state.

Among the four axioms of group theory, we won’t be discussing the closure property, mainly because this property is apparent from the group table. If all the entries of the group table belong to the set of elements $S$, then this property holds. We will be discussing the remaining three axioms in this blog.

Visualizing group axioms#

Now, it’s time to represent the group table using automata. This process is very straightforward. We take the group table and simply use it as a transition table. By doing this, we can visualize groups in the form of state diagrams. Let’s visualize the group that we discussed earlier. There are many overlapping arrows, so we color-coded them, making them distinguishable from each other. It makes the visualizing easy.

Visualizing the identity element#

Now, let’s visualize the axioms one by one, starting from the identity element.

The identity element has two parts.

Visualizing the right identity#

Consider the following:

$a*e=a$ (This is called right identity because the identity element is on the right-hand side).

In terms of transitions, it means that if we’re at state $a$ and move on to the transition with the label $e$, then we’ll go back to state $a$. Let’s focus on this point in the state diagram.

We can see that all the identity elements are forming a self-loop over all the states. Given a state diagram of a finite group, this is perhaps the easiest way to figure out the identity element.

Visualizing the left identity#

Consider the following:

$e*a=a$ (This is called left identity because the identity element is on the left-hand side).

In terms of transitions, it means that if we’re at the state corresponding to the identity element, then following any transition $a$ will lead us to the state $a$. Let’s visualize this in the following snapshot of group automata.

If we start from the identity element $0$ and follow the transition with a label $3$, then we’ll reach the state with the same label $3$.

Visualizing inverse#

An inverse generally means the opposite. In addition, adding $+5$ and $-5$ has an inverse effect. They also cancel out the effect of each other. Moreover, the result of $(+5) + (-5)=0$, and $0$ is the identity element in addition. It’s interesting to note that the inverse mostly occurs in pairs. Here, $+5$ and $-5$ are the inverse of each other.

Similarly, moving $5$ steps forward and moving $5$ steps backward are the inverse of each other, and their effects cancel out each other. The same is the case in groups. Like the identity element, we can visualize the inverse in two ways.

Visualizing the inverse in relation to the identity element.#

For an inverse, we know that $a*a^{-1}=e$. In automata, this translates to a transition that starts from a state labeled $a$, with a transition with a label $a^{-1}$, and leads to the state corresponding to the identity element $e$. This means that for inverse, in our case, we need to look at the transitions going to the state with the label $0$. Let’s visualize this in the diagram below.

Here, we can see that the inverse of $2$ is $3$ because there’s a transition from the state $2$ to the identity element $0$, and the label of this transition is $3$. Similarly, the inverse of $2$ is $3$. Recall the earlier discussion about inverse pairs. We can see that the elements $2$ and $3$ are the inverse of each other.

Visualizing inverse as opposite transitions#

We mentioned earlier that inverse pairs are literally the opposite of each other. We’ve also seen that in this group, the elements $2$ and $3$ are the inverse of each other. Let’s look at the transition of these two elements throughout the state diagram below.

Wherever the element $3$ appears, there’s always a $2$ there, but in the opposite direction. This is in line with the mathematics involved behind the inverse because inverses cancel out the effect of each other. Here, we can conclude that the inverse of an element (transition) appears between the same states, but in the opposite direction.

Visualizing the associative law#

According to the associative law, $a*(b*c) = (a*b)*c$. Let’s take a look at this with an example.

Suppose $a=3, b=2, c= 4$. From the group table, we can conclude that $(b*c) = (2*4) = 1$. This translates to the following in the state diagram.

We start from the state $a\space(3)$. Then, we follow the transition of $b\space(2)$ and reach state $0$. Now, from state $0$, we take the transition of $c\space(4)$ and reach state $4$. This corresponds to the right-hand side of the associative law.

$(a*b)*c = (3*2)*4 = 0*4 = 4$

Now, let’s look at the left-hand side of the associative law.

$a*(b*c) = 3*(2*4) = 3*1 = 4$

This means that if we start at the same state $3$ and follow the transition, which is equivalent to $(b*c)$ and happens to be $1$ in our case, we’ll reach the same state $4$. If we look at the diagram closely, we can see a triangle. This triangle forms something that we can refer to as the shortcut rule. Regardless of our starting point $a$, if we perform transitions of $2$ and $4$ in succession, we can reach the same result by performing a single transition of $1$. We can verify this by looking at the state diagram of this group or of any other finite group of our choice.

In this blog, we discussed a visual representation of group axioms. Stay tuned for another blog where we extend this visual representation to subgroups, cyclic groups, normal subgroups, etc.

Meanwhile, take a look at some of our courses that are related to this state diagram, e.g., a course on the theory of computation.