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

#### 1Groups

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.1Variants

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).

Monoid/semigroup are very useful in computer science, e.g. in modeling strings/lists and the algebraic theory of automata.

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.2Examples

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

#### 2Properties 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|.

#### 3Subgroups

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.

#### 4Rings

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.1Variants

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.

#### 5Functions

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.

#### 6Relations

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.

#### 7Orders

##### 7.1Partially-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.

Given a poset \langle S, \sqsubseteq \rangle, we say
• 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.2Lattices

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.

’s book on Lattice Theory has a dedicated development of both the order-theoretic and algebraic characterization. As an algebra, a lattice has the following laws:
• 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 .

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.

#### 8Quantales

Quantales recently have some nice applications in modeling sequential effects of programs , information flow & privacy , 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).

#### 9Kleene Algebra

Kleene algebra generalizes regular expressions and has many applications in program analysis and verification .

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

#### Bibliography

 Patrick Cousot and Radhia Cousot. Abstract Interpretation: AUnified Lattice Model for Static Analysis of Programs by Construction or Approximation of Fixpoints. In Proc. POPL, 1977. Colin S. Gordon. Polymorphic Iterable Sequential Effect Systems. ACMTrans. Program. Lang. Syst. 43(1), 2021. George Grätzer. Lattice theory: First concepts and distributive lattices. 2009. Sebastian Hunt and David Sands. A Quantale of Information. In Proc. CSF, 2021. Zachary Kincaid, Thomas W. Reps, and John Cyphert. Algebraic Program Analysis. In Proc. CAV(1), 2021. Dexter Kozen. Kleene Algebra with Tests. ACMTrans. Program. Lang. Syst. 19(3), pp. 427–443, 1997.