Definitions

This section provides mathematical definitions of the types of algebras modeled by Python classes in the finite_algebra module, such as groups, rings, fields, etc.

And, in the same way that a square is also a rectangle, and a rectangle is also a polygon, the algebras here follow a hierarchy that starts with an algebra with very few properties (Magma) on down to an algebra rich in properties (Field). Within the hierarchy, inheritance of properties and functionality flows along the arrows from class (parent) to subclass (child), so that each algebra inherits all of the properties of its parent class, in addition to new properties it possesses and passes on to its child classes.

The hierarchy is depicted in the figure, below.

Finite Algebra Hierarchy

The next several sections provide mathematical definitions of the algebraic structures depicted in solid boxes in the figure above.

But first, a brief note about notation.

Notation

\(a, b, c, x, y, \alpha, \beta, \gamma, \dots\) : Lowercase Latin (Roman) or Greek letters are used to denote algebraic elements.

\(F, G, R, S, V \dots\) : Uppercase Latin (Roman) or Greek letters are used to denote sets and finite algebras.

\(\mathscr{V}, \mathscr{M}, \dots\) : Uppercase script letters are used to denote finite composite algebras.

NOTE: In many algebra texts, the binary operations of algebras are often referred to as “multiplication” and/or “addition”, even when the abstract algebraic elements are clearly not numbers. Also, the characters, \(\times\), \(+\), \(0\), and \(1\), are often used as symbols that represent abstract operators and identity elements.

\(\times, +, \cdot, \circ, \oplus, \otimes, \dots\) denote binary operators. Also, juxtaposition is often used for the “multiplication” of two algebraic elements, when it is clear from context that multiplication is intended (\(ab = a \times b\)).

\(\times\) is an overloaded binary operator, so the meaning of \(X \times Y\) depends on \(X\) and \(Y\): If \(X, Y\) are elements of an algebra, then \(\times\) is “multiplication”. If \(X, Y\) are elements of a set, then \(X \times Y\) denotes the cross product of the sets. If \(X, Y\) are algebras, then \(X \times Y\) denotes their direct product.

\(e, 0, 1\) denote abstract identity elements. \(0\) or \(1\) are typically used when the abstract binary operations are referred to as addition or multiplication, along with abstract binary operators, \(+\) and \(\times\), respectively.

\(=, \equiv, \cong\) denote, respectively, equal, equivalent, and isomorphic.

\(\in, \subseteq, \subset\) denote, respectively, member of a set, subset of a set, and proper subset of a set.

\(\setminus, \bigtriangleup\) denote, respectively, set difference, and set symmetric difference.

\(\exists, \forall\) denote, respectively, there exists, and for all.

\(\to, \Rightarrow\) denote, respectively, maps to, and implies.

\(\langle \dots \rangle\) : Angle brackets enclose an algebra’s high-level components: set(s), component algebra(s), and operator(s). For example, a finite algebra is composed of a set and one or two binary operators, such as, \(G = \langle V, \oplus \rangle\) and \(F = \langle S, +, \cdot \rangle\). A finite composite algebra is composed of two finite algebras and a binary operator, such as, \(\mathscr{V} = \langle G, F, \circ \rangle\). This particular notation is specific to this document, not to abstract algebra in general.

And, finally…

This final comment addresses what might might be regarded as an overuse of operator symbols in this document:

In many algebra texts, the notation used to describe binary operations, such as multiplication or addition, in one algebra is the same as the notation used for another, different algebra. Readers are expected to know that the two implicitely refer to different operations. For a computer program, however, the difference in operators must be made explicit. For that reason, care is taken in this document to not conflate the operations of different algebras.

For anything else, see the “Glossary of mathematical notation” on Wikipedia.

Groups, Rings, Fields, etc.

The following list of algebraic structures is ordered such that each successive structure builds on a previous one. The class hierarchy of the finite_algebra module is modeled on this progression.

Magma – \(\langle S, \circ \rangle\), where \(S\) is a set and \(\circ\) is a closed binary operation, \(\circ: S \times S \to S\)
Quasigroup - a Magma where for each \(a, b \in S\), \(\exists\) unique \(x, y \in S\) such that \(a \circ x = y \circ a = b\) \(^*\)
Loop - a Quasigroup with identity element: \(\exists \ e \in S\), such that, for all \(a \in S, a \circ e = e \circ a = a\)
Semigroup – an associative Magma: \(\forall a,b,c \in S \Rightarrow a \circ (b \circ c) = (a \circ b) \circ c\)
Monoid – a Semigroup with identity element: \(\exists \ e \in S\), such that, for all \(a \in S, a \circ e = e \circ a = a\)
Group – a Monoid with inverse elements: \(\forall a \in S, \exists \ a^{-1} \in S\), such that, \(a \circ a^{-1} = a^{-1} \circ a = e\)
Ring – \(\langle S, +, \cdot \rangle\), where \(\langle S, + \rangle\) is an abelian\(^\dagger\) Group, \(\langle S, \cdot \rangle\) is a Semigroup, and \(\cdot\) distributes\(^\ddagger\) over \(+\)
Field – a Ring \(\langle S, +, \cdot \rangle\), where \(\langle S\setminus{\{0\}}, \cdot \rangle\) is an abelian Group\(^{\dagger\dagger}\)

\(^*\) The property possessed by the Quasigroup is referred to in multiple ways: division, or latin square, or cancellation property.

\(^\dagger\) An algebra is abelian (or commutative) for a binary operation, \(\circ\), if \(a \circ b = b \circ a\) for all \(a,b \in S\).

\(^\ddagger\) An operation, \(\cdot\), distributes over another operation, \(+\), if \(a \cdot (b + c) = (a \cdot b) + (a \cdot c)\) for all \(a,b,c \in S\).

\(^{\dagger\dagger}S\setminus{\{0\}}\) is the set \(S\) with the additive identity element removed.

Note: Although it is possible to have a trivial Ring, consisting of only the additive identity, \(S = \{0\}\), it is not possible to have a trivial Field, because we can’t define a Group over the empty set, \(S\setminus{\{0\}} = \emptyset.\)

For Magmas, Semigroups, Monoids, and Groups, the binary operation is often referred to as “multiplication”, but may sometimes be called “addition”. Also, the identity element may be denoted by \(0\) or \(1\), rather than \(e\), depending on whether the operation is called addition or multiplication, resp.

For Rings and Fields, the two operations, \(+\) and \(\cdot\), are usually referred to as addition and multiplication, resp. The identity element for \(+\) is often denoted by \(0\), and, if a multiplicative identity exists, \(1\) for \(\cdot\).

Regarding a Ring’s Semigroup, \(\langle S, \cdot \rangle\):

if the Semigroup is abelian, then the Ring is called a “commutative Ring”
if the Semigroup is actually a Monoid (i.e., has an identity element), then the Ring is called a “unit Ring” or “Ring with identity”

For examples, see the sections “Groups, Monoids, Semigroups, & Magmas” and “Rings and Fields”.

Before proceeding, we’ll briefly discuss a motivation for the definition of a Group.

Group Definition Motivation

In a nutshell, the definition of a Group, \(G=\langle S, \circ \rangle\), consists of the minimum set of properties required to methodically solve equations involving the Group’s elements and its binary operation.

To see this, let \(\boxed{a \circ x = b}\) be an equation made up of elements \(a,b,x \in S\).

Consider the assumptions required to solve the equation for \(x\):

First, assume the group’s binary operation is closed; that is, \(a, b \in S \Rightarrow a \circ b \in S\)
Assume every element has an inverse; so, multiplying \(a^{-1}\) on both sides yields \(a^{-1} \circ (a \circ x) = a^{-1} \circ b\)
Assume the group is associative; therefore \((a^{-1} \circ a) \circ x = a^{-1} \circ b\)
Assume the group has an identity element, \(e\); therefore \(e \circ x = a^{-1} \circ b\)
And finally, since \(e\) is an identity element, \(e \circ x = x \Rightarrow \boxed{x = a^{-1} \circ b}\)

The assumptions made above are precisely those that make up the definition of a Group.

Note that cummutativity was not necessary to solve the equation, and so it is not required of a Group.

Vector Spaces and Modules

Each type of algebra, described above, has only one set of elements. Vector Space and Modules, however, are hybrids of two algebras, each with their own set of elements, called scalars and vectors.

A Vector Space, \(\mathscr{V} = \langle G, F, \circ \rangle\), consists of the following:

an abelian Group, \(G = \langle V, \oplus \rangle\) (i.e., the “vectors”)
a field, \(F = \langle S, +, \cdot \rangle\) (i.e., the “scalars”)
and a binary operator, \(\circ : S \times V \to V\)

where the following conditions hold:

Scaled Vectors: For all \(s \in S\) and \(v \in V \Rightarrow s \circ v \in V\)
Scaling by One: If \(1 \in S\) is the multiplicative identity element of \(F\), then \(1 \circ v = v\)
Distributivity of Scalars Over Vector Addition: \(s \circ (v_1 \oplus v_2) = (s \circ v_1) \oplus (s \circ v_2)\)
Distributivity of Vectors Over Scalar Addition: \((s_1 + s_2) \circ v = (s_1 \circ v) \oplus (s_2 \circ v)\)
Scalar-Vector Associativity: \(s_1 \circ (s_2 \circ v) = (s_1 \cdot s_2) \circ v\)

A Module, \(\mathscr{M} = \langle G, R, \circ \rangle\), has the same conditions as a Vector Space, except that the Field is replaced by a Ring, \(R\).

For examples, see the section “Vector Spaces and Modules”.

More on the Class Hierarchy

Note that, a Field is also a Ring, and a Group, and a Monoid, and so on, since the hierarchy of subclasses of a the FiniteAlgebra class extend from each other, as shown in the figure above. A similar situation holds for the FiniteCompositeAlgebra class: a VectorSpace is a Module. And, since inheritance “flows” along the arrows in the figure, a method that may be usually associated with a particular class might actually be defined in its parent class, or one of its ancestor classes.

For example, the method, is_commutative, answers a question we often ask of Groups, but to answer it only requires that there be a binary operation that can be used to check it. So, is_commutative is defined for Magma. But, since Magma methods and properties are inherited by all classes that extend from Magma (from Semigroup to Field), is_commutative applies to all them also. Same for is_associative, identity, inv, center, isomorphic, etc.

Another example is given by units, which are usually associated with Rings. But the only property an algebra requires to be able to identify units, is that of having an identity element. Identity elements first appear in the class hierarchy in Monoids, so the method, units, is defined for Monoids, and then inherits down through its subclasses. That is, units can be identified for Monoids, Groups, Rings, and Fields. Of course, the concept of units is not that interesting for Groups, since every element of a Group is a unit, but they are interesting in Monoids, and, under multiplication, in Rings. The unit method for Rings applies only to the multiplicative operation and multiplicative identity element, if it exists.

Direct Products

This section provides the usual definition of a direct product for Magmas through Fields, plus a related definition for Rings & Fields, known as the Cayley-Dickson construction.

Like Vector Spaces, Direct Products involve the combination of possibly different algebras, with different sets of elements and different binary operations.

If \(G = \langle S, + \rangle\) and \(H = \langle T, \oplus \rangle\) are two Groups, then their direct product, denoted by \(G \times H\), is also a Group, where

\(G \times H \equiv \langle U, \bullet \rangle\)
\(U = \{(g,h): g \in S, h \in T\}\)
\((g, h) \bullet (g', h') = (g + g', h \oplus h')\) for all \((g, h), (g', h') \in U\)

If \(R_1 = \langle S, +, \cdot \rangle\) and \(R_2 = \langle T, \oplus, \odot \rangle\) are two Rings, then their direct product, denoted by \(R_1 \times R_2\), is also a Ring, where

\(R_1 \times R_2 \equiv \langle U, \circ, \bullet \rangle\)
\(U = \{(s, t): s \in S, t \in T\}\)
\((s, t) \circ (s', t') = (s + s', t \oplus t')\), for all \((s, t), (s', t') \in U\)
\((s, t) \bullet (s', t') = (s \cdot s', t \odot t')\)

The only requirement needed to form a direct product is that there be two finite algebras, each with its own set of elements and binary operation. That is, the direct product definition works for any FiniteAlgebra (Magma through Field). So, if G and H are each instances of FiniteAlgebra, then their direct product can be obtained by multiplying the two instances using Python’s multiplication operator, G * H.

Cayley-Dickson Algebras

An opportunity to define an alternative type of direct product presents itself when we consider the direct product of a ring, \(A = \langle S, +, \cdot \rangle\), with itself, which produces a Cayley-Dickson Algebra (CDA), denoted here as \(\mathscr{C}(A)\). In this case, addition is defined the same as for the usual direct product, but multiplication is defined to be similar to that used for complex numbers. The details on CDAs are presented later on in this document.

Properties of Algebras

This section provides definitions of related algebraic structures and properties.

Center

The center of an algebra is usually defined for Groups, however since the definition only requires a set and a binary operation, it has been extended here to apply to Magmas, and so applies to all finite algebras.

The center of a Magma is the subset of elements of the Magma that commute with every element in the Magma.

That is, \(C \subseteq S\) is the center of the Magma, \(\langle S, \circ \rangle\), if \(c \in C \Rightarrow \forall x \in S, c \circ x = x \circ c.\) (see Pinter’s book, chapter 5, exercise D3)

Note also, the center of a commutative algebra is the entire algebra. The gist of Pinter’s exercise is that, for Groups, the center is closed and hence defines a subgroup. The proof of this follows easily from associativity and the commutative property of center elements, so it will also be true for Semigroups, but not necessarily true for Magmas.

There are two Magma methods related to the center:

center returns the center of a Magma, or it returns an empty list if the center is empty
center_algebra returns the algebra defined by the center, if the center exists and is closed, otherwise it returns None.

Commutators

Let \(G = \langle S, \circ \rangle\) be a Group, then for any pair of elements, \(a, b \in S\), the product, \(a \circ b \circ a^{-1} \circ b^{-1}\), denoted \([a,b]\), is called a commutator of the Group.

Note that \(a \circ b \circ a^{-1} \circ b^{-1} = e\) if and only if \(ab = ba\). The following quote helps explain the motivation behind the definition of commutators:

“Thus, in an abelian group all the commutators are equal to e. In a group which is not abelian, the number of distinct commutators may be regarded as a measure of the extent to which G departs from being commutative. (The fewer the commutators, the closer the group is to being an abelian group.)” – [Pinter 1982]

If \(G\) is abelian, then the identity element, \(e\), is the only commutator in \(G\), because \([a,b] = e\) for all possible \(a,b \in S\).

So, if \(G\) is non-abelian, then for some \(a,b \in S\), we have \([a,b] = c \ne e\).

The set of all commutators of a Group is a subgroup, and is called the Commutator Subgroup.

The following methods exist for Group instances:

commutator, for two elements, \(a,b\), this method will return \([a,b]\)
commutators, will return a list of all the commutators of a Group
commutator_subalgebra, will return the commutator subgroup of a Group

For a Ring, \(R = \langle S, +, \cdot \rangle\), the elements under addition, \(\langle S, + \rangle\) are, by definition, an abelian Group, so commutators for a Ring’s elements are defined using multiplication instead. But, \(\langle S, \cdot \rangle\) is a Semigroup, or at best, a Monoid, which means that we can’t use inverses in the definition of a Ring’s commutator. Consequently, Ring commutators are defined to be elements of the form, \((a \cdot b) - (b \cdot a)\), and are also denoted by \([a, b]\).

The Ring methods, commutator, commutators, and commutator_subalgebra, use the Ring definition of a commutator.

There is currently no method to produce a commutator subring. (See Eroǧlu, Münevver Pınar. “On the subring generated by commutators.” Journal of Algebra and Its Applications (2020): 2250059.)

Units of a Ring

Let \(R = \langle S, +, \cdot \rangle\) be a Ring with identity (or Unit Ring),

then \(x \in S\) is a unit if \(x \cdot y = 1\) and \(y \cdot x = 1\) for some \(y \in S\).

The set of all units of \(R\) are denoted by \(S^\times\) and form an abelian Group under multiplication, \(R^\times = \langle S^\times, \cdot \rangle\), called the Units Subgroup of \(R\).

The method, units, will return the units of a Ring as a list of element names, or optionally, element indices. And, since the only requirement for an algebra to have units is that it have an identity element, the units method also works for Monoids.

The method, units_subgroup, will return the units subgroup of a Ring (or Monoid).

Division Algebra

[NOTE: Need good references for divisibility and cancellation]

A Magma, \(M = \langle S, \circ \rangle\) is a division Algebra if \(\forall a,b \in S, \exists x,y \in S\) such that \(a \circ x = b\) and \(y \circ a = b\).

This property is trivially true for Groups.

The Magma method, is_division_algebra, tests for this property.

Regularity in Semigroups

A Semigroup, \(\langle S, \circ \rangle\) is regular if for each \(a \in S, \exists \bar{a} \in S\) such that \(a \circ \bar{a} \circ a = a\).

The element \(\bar{a}\) is called a weak inverse of \(a\). A weak inverse may not exist or there may be more than one for any particular element. If the algebra is regular, then there will be at least 1 weak inverse for each element, otherwise some elements may not have a weak inverse.

See the paper, “Why Study Semigroups” by John M. Howie

Here are some Semigroup methods related to regularity:

is_regular returns True or False, depending on whether the Semigroup is regular
weak_inverses returns a dictionary of weak inverses, where each key is one of the algebra’s elements and its value is a list of its weak inverses.