### 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