Notes on Algebraic Structures
Some brief notes of various algebraic structures, with connections to computer science.
Sources include Charles C. Pinter’s A Book of Abstract Algebra (2nd edition), Wikipedia, and several papers.
1 Groups
Definition (Operation): An operation \circledast on A is a rule which assigns to each ordered pair (a, b) of elements of A exactly one element a \circledast b in A. Formally, \circledast : A \times A \to A.
Definition (Commutativity): a \circledast b = b \circledast a.
Definition (Associativity): a \circledast (b \circledast c) = (a \circledast b) \circledast c.
Definition (Identity): e is an identity (or neural element) w.r.t the operation \circledast if \forall a \in A, e \circledast a = a = a \circledast e,
Definition (Inverse): If a \in A, and x \in A such that a \circledast x = e and x \circledast a = e, then x is called an inverse of a, denoted by a^{-1}.
Definition (Group): A group \langle G, \circledast \rangle is a set G with an operation \circledast, such that
\circledast is associative,
there exists an identity element e \in G,
\forall a \in G, there is its inverse a^{-1} \in G.
1.1 Variants
Definition (Finite groups): Groups with finite elements.
Definition (Commutative groups): If \circledast is commutative, then \langle G, \circledast \rangle is called a commutative group (abelian group).
Definition (Monoid): A monoid is a group without inverses.
Definition (Commutative Monoid): A commutative monoid is a commutative group without inverses.
Definition (Semigroup): A semigroup is a monoid without identity.
Definition (Magma): A magma is a semigroup without associativity.
Definition (Groupoid): Note that we implicitly require that \circledast is a total function. If we allow partial functions, then we have a groupoid.
1.2 Examples
Example (Group):
\langle \mathbb{Z}, + \rangle, additive group of the integers
\langle \mathbb{Q}, + \rangle, additive group of the national numbers
\langle \mathbb{R}, + \rangle, additive group of the real numbers
\langle \mathbb{Q}^*, \cdot \rangle, the non-zero national numbers with multiplication
\langle \mathbb{Q}^{pos}, \cdot \rangle, the positive national numbers with multiplication
Example (The group of integers modulo n): \langle \mathbb{Z}_{n}, \oplus \rangle where
\mathbb{Z}_{n} = \{ 0, 1, 2, \dots, n-1 \}
x \oplus y = x + y \text{ mod } n
0 is the identity element
\forall x \in \mathbb{Z}_{n}, n - x is its inverse
2 Properties of Group
Theorem (Cancellation): If G is a group, and a, b, c \in G, then
a \circledast b = a \circledast c \implies b = c
b \circledast a = c \circledast a \implies b = c
Proof: Suppose a \circledast b = a \circledast c, then a^{-1} \circledast (a \circledast b) = a^{-1} \circledast (a \circledast c). By the associativity law, (a^{-1} \circledast a) \circledast b = (a^{-1} \circledast a) \circledast c, i.e., e \circledast b = e \circledast c. Thus b = c.
Note that in general we cannot cancel a in a \circledast b = c \circledast a, because \circledast is not necessarily commutative.
Theorem: If G is a group, and a, b \in G, then a \circledast b = e \implies a = b^{-1} and b = a^{-1}.
Proof: Assume a \circledast b = e, then a \circledast b = a \circledast a^{-1}, by the cancellation law, we have b = a^{-1}. Similarly, a = b^{-1}.
Theorem: If G is a group, and a, c \in G, then
(a \circledast b)^{-1} = b^{-1} \circledast a^{-1}
(a ^{-1})^{-1} = a
Proof:
Since \begin{aligned} & (a \circledast b) \circledast (b^{-1} \circledast a^{-1}) \\ = & a \circledast (b \circledast b^{-1}) \circledast a^{-1} \\ = & a \circledast (e \circledast a^{-1}) \\ = & a \circledast a^{-1} \\ = & e \end{aligned}, therefore, a \circledast b is the inverse of b^{-1} \circledast a^{-1}.
Since a \circledast a^{-1} = e, therefore a is the inverse of a^{-1}, that is (a ^{-1})^{-1} = a.
Definition (Order): If G is finite, then the number of elements in G is called the order of G, denoted by |G|.
3 Subgroups
Let \langle G, \circledast \rangle be a group, and S a nonempty subset of G. If \forall a, b \in S, a \circledast b \in S, we say that S is closed w.r.t. \circledast. If \forall a \in S, a^{-1} \in S, we say that s is closed w.r.t. inverse.
Definition (Subgroup): S is a subgroup of G if it is closed w.r.t. both \circledast and inverse.
Example (Subgroups):
The set of even integers is a subgroup of additive group \mathbb{Z}.
\mathbb{Q}^{*} with multiplication is a subgroup of \mathbb{R}^{*} with multiplication.
Remark: If G is a group and S is a subgroup of G, then S itself is also a group.
Definition (Sum of two functions): Let \mathcal{F}(\mathbb{R}) be the set of all functions of \mathbb{R} \to \mathbb{R}. The sum of two functions is given by: f + g = \lambda x . f(x) + g(x)
Example (Additive Group of \mathcal{F}(\mathbb{R})): \langle \mathcal{F}(\mathbb{R}), + \rangle is a group, where its identity element is \lambda x. 0, and its inverse is f^{-1} = \lambda x. -f(x).
Remark: + is associative.
Proof: We need to show that f + (g + h) = (f + g) + h, by extensionality, it suffices to show that \forall x, [f + (g + h)](x) = [(f + g) + h](x). Since [f + (g + h)](x) = f(x) + g(x) + h(x) and [(f + g) + h](x) = f(x) + g(x) + h(x), + is associative. □
Example (Subgroups):
The set of all continuous functions from \mathbb{R} to \mathbb{R} (i.e., \mathcal{C}(\mathbb{R})) with + is a subgroup of \mathcal{F}(\mathbb{R}).
The set of all differentiable functions from \mathbb{R} to \mathbb{R} (i.e., \mathcal{D}(\mathbb{R})) with + is a subgroup of \mathcal{F}(\mathbb{R}).
Remark: In any group G, the singleton set of the neutral element \{ e \} is a subgroup. It is called the trivial subgroup ; other possible subgroups are called proper subgroups.
Definition (Generator): Suppose G is a group, and K \subseteq G, then we can define a subgroup S of G generated by K. First let K^{-1} = \{ x^{-1} | x \in K \}. Then S contains all possible products of elements in K \cup K^{-1}, in any order, with repetition of factors permitted.
Definition (Cyclic subgroup): The subgroup of a single element a \in G is called a cyclic subgroup of G, denoted by \langle a \rangle. Note that \langle a \rangle contains a, aa, aaa, \dots, as well as a^{-1}, a^{-1}a^{-1}, \dots
Definition (Cyclic group): If a group G is generated by a single element a, it is called cyclic group, also denoted by \langle a \rangle.
Remark: Every finite group is generated by one or more of its elements.
Definition (Defining equations): Example see page 29 of Pinter’s book. A set of equations, involving only the generators and their inverses, is called a set of defining equations of group G, if those equations determine the table of G.
4 Rings
Definition (Ring): A ring is a set R with two binary operations + and \circledast such that:
+ is associative.
+ is commutative.
There exists an identity element 0 for +.
For all x \in R, there exists an inverse element -x such that x + (-x) = 0.
\circledast is associative.
There exists a multiplicative identity element 1 for \circledast .
\circledast is distributive over + (i.e., x \circledast (y + z) = x \circledast y + x \circledast z and (y + z) \circledast x = y \circledast x + z \circledast x).
Note that \langle R, + \rangle is an abelian group, and \langle R, \circledast \rangle is a monoid.
From the definition, we can show that 0 \circledast x = x \circledast 0 = 0 by equational reasoning (we write xy for x \circledast y):
\begin{aligned} & a0 \\ = & a0 + 0 \\ = & a0 + (a + -a) \\ = & (a0 + a) + -a \\ = & (a0 + a1) + -a \\ = & a(0 + 1) + -a \\ = & a + -a \\ = & 0 \end{aligned}
4.1 Variants
Definition (Semiring): A semiring is a ring without the additive inverse and additionally with a multiplicative zero s.t. 0 \circledast a = a \circledast 0 = 0 (annihilation). In other words, \langle R, + \rangle is a commutative monoid (instead of an abelian group). We explicitly need the multiplicative zero since without the additive inverse it is admissible.
Definition (Rng): If \langle R, \circledast \rangle is a semigroup (i.e., it has no identity element), then R is a rng.
Examples of Rng include the set of even integers with + and \times.
Definition (Commutative Ring): A ring \langle R, +, \circledast \rangle is commutative if the multiplication \circledast is commutative.
5 Functions
Definition (Injective): A function f: A \to B is injective if each elements of B is the image of at most one element of A. Formally, a function f: A \to B is injective if and only if \forall x, y. f(x) = f(y) \implies x = y.
Definition (Surjective): A function f: A \to B is surjective if each element of B is the image of at least one element of A. Formally, a function f: A \to B is surjective if and only if \forall x. \exists y. f(x) = y.
Definition (Bijective): A function f: A \to B is bijective if it is both injective and surjective, also called one-to-one correspondence. Formally, a function f: A \to B is bijective if and only if \exists g: B \to A \text{ s.t. } \forall x. (g \circ f)(x) = x \wedge \forall y. (f \circ g)(y) = y.
Remark: If f and g are injective/surjective/bijective, their composition f \circ g is also injective/surjective/bijective.
Definition (Inverse): f^{-1}: B \to A is an inverse of function f: A \to B iff f^{-1}(y) = x \iff f(x) = y.
6 Relations
Definition (Reflexivity): A relation R is reflexive if \forall x, x R x.
Definition (Transitivity): A relation R is transitive if \forall x, y, z, x R y \land y R z \implies x R z.
Definition (Symmetry): A binary relation R is symmetric if a R b implies b R a.
Definition (Antisymmetry): A binary relation R is antisymmetric if a R b and b R a implies a = b.
7 Orders
7.1 Partially-ordered Sets
Definition (Partially-ordered Set): A partially-ordered set (poset) is a set S equipped with a binary relation \sqsubseteq which is reflexive, anti-symmetric and transitive. The ordering relation can be partial, i.e., there exists incomparable elements.
x \in S is an upper bound of X \subseteq S iff \forall y \in X, y \sqsubseteq x.
x \in S is a lower bound of X \subseteq S iff \forall y \in X, x \sqsubseteq y.
x \in S is the least upper bound of X \subseteq S iff \forall y \in X, y \sqsubseteq x (i.e. x is indeed an upper bound) and \forall z \in S s.t. \forall u \in X, u \leq z, we have x \sqsubseteq z (i.e. x is smaller than all other upper bounds).
x \in S is the greatest lower bound of X \subseteq S iff \forall y \in X, x \leq y (i.e. x is indeed a lower bound) and \forall z \in S s.t. \forall u \in X, z \leq u, we have z \sqsubseteq x (i.e. x is greater than all other lower bounds).
7.2 Lattices
Definition (Lattice): \langle L, \sqsubseteq, \sqcup, \sqcap \rangle is a lattice iff \langle L, \sqsubseteq \rangle is a poset and for all a, b \in L, we have a least upper bound a \sqcup b and a greatest lower bound a \sqcap b.
All finite sets in a lattice have least upper bounds and greatest lower bounds, but not necessarily for infinite sets.
absorption: a \sqcup (a \sqcap b) = a and a \sqcap (a \sqcup b) = a.
idempotent: a \sqcup a = a and a \sqcap a = a.
Definition (Join-Semilattice): \langle L, \sqsubseteq, \sqcup \rangle is a join-semilattice.
Definition (Meet-Semilattice): \langle L, \sqsubseteq, \sqcap \rangle is a meet-semilattice.
Lattice theory is the foundation of sound static program analysis (Cousot and Cousot 1977).
Definition (Complete Lattice): A complete lattice \langle L, \sqsubseteq, \bot, \top, \sqcup, \sqcap \rangle is a structure such that
\langle L, \sqsubseteq \rangle is a poset,
\bot is the least element of L, and \bot = \sqcup \varnothing,
\top is the greatest element of L, and \top = \sqcap L,
\forall X \subseteq L, \sqcup X is the least upper bound of X,
\forall X \subseteq L, \sqcap X is the greatest lower bound of X.
Example (Powerset Lattice): If S is a set, then \langle \mathcal{P}(S), \subseteq, \varnothing, S, \cup, \cap \rangle is a complete lattice.
8 Quantales
Quantales recently have some nice applications in modeling sequential effects of programs (Gordon 2021), information flow & privacy (Hunt and Sands 2021), etc.
Definition (Quantale): A quantale is a structure \langle Q, \sqsubseteq, \sqcup, \rhd, 1 \rangle such that
\langle Q, \sqsubseteq, \sqcup \rangle is a complete join-semilattice.
\langle Q, \rhd, 1 \rangle is a monoid where 1 is the identity element.
\rhd distributes over \sqcup: x \rhd (y \sqcup z) = (x \rhd y) \sqcup (x \rhd z) and (y \sqcup z) \rhd x = (y \rhd x) \sqcup (z \rhd x).
9 Kleene Algebra
Kleene algebra generalizes regular expressions and has many applications in program analysis (Kincaid et al. 2021) and verification (Kozen 1997).
Definition (Kleene Algebra): A Kleene algebra is a structure \langle X, +, \circledast, 0, 1, ^\ast \rangle such that
\langle X, +, \circledast, 0, 1 \rangle is a semiring, i.e. \langle X, +, 0 \rangle is a commutative monoid, \langle X, \circledast, 1 \rangle is a monoid, with distributivity and annihilation.
+ is idempotent, i.e. x + x = x.
^\ast : X \to X is a closure operator.
Definition (Closure Operator): We define an ordering relation a \leq b iff there exists an x s.t. a + x = b. The closure operator ^\ast has the following laws (we write xy for x \circledast y):
1 + a(a^\ast) \leq a^\ast.
1 + (a^\ast)a \leq a^\ast.
If a + bx \leq x, then (b^\ast)a \leq x.
If a + xb \leq x, then a(b^\ast) \leq x.
History: 2022/12 Rings, Orders, Quantales, Kleene Algebra; 2020/1 Functions; 2019/12 Groups