Group Theory

Table of Contents
1. Semigroup
2. Group
3. Cyclic Group and Subgroup
4. Partially Ordered Set (POSET)
5. Linearly Ordered Set
6. Lattice
View more

Semigroup

A semigroup is a non-empty set S together with a binary operation ο (often written multiplicatively or additively) such that the operation is closed on S and associative:

• Closure - For every a, b ∈ S, the result a ο b belongs to S.
• Associativity - For every a, b, c ∈ S, (a ο b) ο c = a ο (b ο c).

Example

• The set of positive integers S = {1, 2, 3, ...} with addition is a semigroup because addition is closed and associative on S. (Note: S lacks an additive identity 0, so it is not a monoid under addition.)

Monoid

A monoid is a semigroup that has an identity element e (also called the unit) satisfying a ο e = e ο a = a for every a ∈ S. Thus a monoid satisfies Closure, Associativity and Identity.

• Identity element - an element e ∈ S such that for every a ∈ S, a ο e = e ο a = a.

Example

• The set of positive integers S = {1, 2, 3, ...} with multiplication is a monoid. Multiplication is closed and associative on S, and the identity element is 1 because a × 1 = 1 × a = a for all a ∈ S.
• The set of non-negative integers N0 = {0, 1, 2, ...} with addition is also a monoid; here the identity element is 0.

Group

A group is a monoid in which every element has an inverse. Formally, a set G with a binary operation · is a group if it satisfies:

• Closure - For all a, b ∈ G, a · b ∈ G.
• Associativity - For all a, b, c ∈ G, (a · b) · c = a · (b · c).
• Identity element - There exists e ∈ G such that for all a ∈ G, e · a = a · e = a.
• Inverse element - For each a ∈ G there exists an element a^-1 ∈ G such that a · a^-1 = a^-1 · a = e.

The order of a group G is the number of elements in G (finite or infinite). The order of an element a ∈ G is the least positive integer n such that aⁿ = e, if such an n exists.

Example

• The set of all invertible N×N matrices over a field (denoted GL(N)) under matrix multiplication is a group. Matrix multiplication is closed and associative; the identity is the identity matrix; every invertible matrix has an inverse which is also invertible.
• The set of integers Z under addition is a group. The identity is 0 and the inverse of an integer a is -a.

Abelian Group (Commutative Group)

An abelian group is a group in which the operation is additionally commutative: for all a, b ∈ G, a · b = b · a. Thus an abelian group satisfies Closure, Associativity, Identity, Inverse and Commutativity.

Examples

• The group (Z, +) of all integers under addition is an abelian group; the identity is 0 and inverses are negatives.
• The group (Z_n, + mod n) of integers modulo n under addition is a finite abelian group of order n.

Cyclic Group and Subgroup

A cyclic group is a group that can be generated by a single element g, called a generator, meaning every element of the group is some integer power (or multiple, in additive notation) of g. If G = ⟨g⟩, then G = {g^k : k ∈ Z} (or {k g : k ∈ Z} in additive notation).

Example

• The set {1, -1, i, -i} of 4th roots of unity under multiplication is a cyclic group of order 4. The elements i and -i are generators because i, i² = -1, i³ = -i, i⁴ = 1 and similarly for -i.
• The group Z_n under addition modulo n is cyclic; 1 (or any element coprime to n under addition) generates Z_n.

Note - Every cyclic group is abelian, but not every abelian group is cyclic (for example, the additive group of rational numbers Q is abelian but not cyclic).

A subgroup H of a group G (written H ≤ G) is a non-empty subset H ⊆ G that is itself a group under the operation of G. Equivalently, H ≤ G iff for all x, y ∈ H, x · y^-1 ∈ H.

Definitions

• Proper subgroup - H is a proper subgroup of G (written H < G) if H ≤ G and H ≠ G.
• A subgroup of a cyclic group is always cyclic.

Examples

• Let G = {1, i, -1, -i}. Subgroups include H₁ = {1} and H₂ = {1, -1}.
• The set H₃ = {1, i} is not a subgroup of G because it is not closed under taking inverses: i^-1 = -i is not in H₃.

Partially Ordered Set (POSET)

A partially ordered set or poset is a pair (P, ≤) where ≤ is a binary relation on P that is:

• Reflexive - for all x ∈ P, x ≤ x.
• Antisymmetric - for all x, y ∈ P, if x ≤ y and y ≤ x then x = y.
• Transitive - for all x, y, z ∈ P, if x ≤ y and y ≤ z then x ≤ z.

Examples

• The set of real numbers R with the usual ≤ relation is a poset (in fact a total order).
• Let S = {1, 2, 3} with the relation ≤. The set of ordered pairs representing ≤ on S is {(1,1), (2,2), (3,3), (1,2), (1,3), (2,3)}; this relation is reflexive, antisymmetric and transitive, hence a poset.
• The vertices of a directed acyclic graph (DAG) equipped with the reachability relation form a poset.

Hasse Diagram

A Hasse diagram is a simplified drawing of a finite poset. Vertices represent elements of the poset and edges are drawn to show the covering relation: we draw an edge from x up to y when x < y and there is no z with x < z < y. In the diagram, if x < y then x is drawn lower than y. Transitive edges are omitted since they are implied.

Example

The poset of all subsets (the powerset) of {1, 2, 3} ordered by inclusion has elements {∅, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}} and can be represented by a Hasse diagram.

Linearly Ordered Set

A linearly ordered set or total order is a poset (P, ≤) in which every pair of elements is comparable: for all a, b ∈ P either a ≤ b or b ≤ a. This property is sometimes called the trichotomy law in contexts where equality is also considered.

Examples

• The set of real numbers R with the usual ≤ is a linear (total) order because any two real numbers are comparable.
• The powerset of {a, b} ordered by ⊆ is not a total order because the subsets {a} and {b} are not comparable under inclusion.
• A totally ordered set gives a lattice in which the join a ∨ b is the maximum and the meet a ∧ b is the minimum of {a, b}.

Lattice

A lattice is a poset (L, ≤) in which every pair of elements a, b ∈ L has both a least upper bound (join) and a greatest lower bound (meet). The join is denoted by a ∨ b and the meet by a ∧ b.

Examples

The figure above is a lattice because for every pair {a, b} ∈ L both a ∧ b and a ∨ b exist.

The figure above is not a lattice because there exist pairs (for example a and b, or e and f in the figure) for which a meet or join does not exist.

Types of Lattices

• Bounded lattice - A lattice L is bounded if it has a greatest element 1 (top) and a least element 0 (bottom).
• Complemented lattice - A bounded lattice L is complemented if every element x ∈ L has a complement x′ such that x ∧ x′ = 0 and x ∨ x′ = 1.
• Distributive lattice - A lattice is distributive if for all a, b, c ∈ L the following equalities hold:
  • a ∨ (b ∧ c) = (a ∨ b) ∧ (a ∨ c)
  • a ∧ (b ∨ c) = (a ∧ b) ∨ (a ∧ c)
• Modular lattice - A lattice L is modular if for all a, b, c ∈ L with a ≤ c we have
  • a ∨ (b ∧ c) = (a ∨ b) ∧ c

Basic Properties of Lattices

The following laws hold in any lattice:

• Idempotent: a ∨ a = a; a ∧ a = a.
• Absorption: a ∨ (a ∧ b) = a; a ∧ (a ∨ b) = a.
• Commutative: a ∨ b = b ∨ a; a ∧ b = b ∧ a.
• Associative: a ∨ (b ∨ c) = (a ∨ b) ∨ c; a ∧ (b ∧ c) = (a ∧ b) ∧ c.

Dual of a Lattice

The dual of a lattice statement is obtained by interchanging ∨ and ∧ and interchanging the greatest and least elements. For example, the dual of a ∨ (b ∧ c) is a ∧ (b ∨ c).

Concluding remark - The algebraic structures discussed above (semigroup, monoid, group, abelian group, cyclic group, subgroup) and the order structures (poset, Hasse diagram, lattice and its variants) form foundational material in abstract algebra and discrete mathematics. They appear frequently in algebra, combinatorics, computer science (data structures, order theory, automata, cryptography) and in reasoning about algebraic and ordered systems.