Skip to content

8. Introduction to Algebraic Structures

  • Group: a group G denoted by \(\{G, \circ\}\) is a set G together with a binary operation \(\circ\) on G such that the following CAIN axioms hold:
    • Closure: \(\forall a, b \in G, a \circ b \in G\)
    • Associativity: \(\forall a, b, c \in G, (a \circ b) \circ c = a \circ (b \circ c)\)
    • Identity: \(\exists e \in G, \forall a \in G, a \circ e = e \circ a = a\)
    • Inverse: \(\forall a \in G, \exists a^{-1} \in G, a \circ a^{-1} = a^{-1} \circ a = e\)
  • When the CAIN properties are true for a set and operation on it; we call it a group.
  • Abelian Group: a group G is called an abelian group if the previous CAIN axioms hold, and the following Commutativity axiom holds:
    • Commutativity: \(\forall a, b \in G, a \circ b = b \circ a\)

  • List of common sets:

    • \(\mathbb{N}\): Natural numbers \(\{1, 2, 3, ...\}\) (integers greater than 0)
    • \(\mathbb{Z}\): Integers \(\{..., -3, -2, -1, 0, 1, 2, 3, ...\}\)
    • \(\mathbb{Z}^-\): Negative integers \(\{..., -3, -2, -1\}\)
    • \(\mathbb{Z}^*\): Positive integers \(\{1, 2, 3, ...\}\) (excluding 0)
    • \(\mathbb{Q}\): Rational numbers \(\{\frac{a}{b} | a, b \in \mathbb{Z}, b \neq 0\}\)
    • \(\mathbb{R}\): Real numbers \(\{..., -\pi, -2, -\frac{1}{2}, 0, \frac{1}{2}, 2, \pi, ...\}\)
    • \(\mathbb{C}\): Complex numbers \(\{a + bi | a, b \in \mathbb{R}, i = \sqrt{-1}\}\)
    • \(\mathbb{Z}_n\): Integers modulo n \(\{0, 1, 2, ..., n-1\}\)
    • \(\mathbb{Z}^+\): Positive integers \(\{1, 2, 3, ...\}\)
    • \(\mathbb{Z}^*_n\): Integers modulo n excluding 0 \(\{1, 2, ..., n-1\}\)
    • \(\mathbb{W}\): Whole numbers \(\{0, 1, 2, 3, ...\}\)

  • Semigroup: a semigroup S denoted by \(\{S, \circ\}\) is a set S together with a binary operation \(\circ\) on S such that the following CA axioms hold:

    • Closure: \(\forall a, b \in S, a \circ b \in S\)
    • Associativity: \(\forall a, b, c \in S, (a \circ b) \circ c = a \circ (b \circ c)\)

  • Monoid: a monoid M denoted by \(\{M, \circ\}\) is a set M together with a binary operation \(\circ\) on M such that the following CAI axioms hold (that is, a semigroup with identity):

    • Closure: \(\forall a, b \in M, a \circ b \in M\)
    • Associativity: \(\forall a, b, c \in M, (a \circ b) \circ c = a \circ (b \circ c)\)
    • Identity: \(\exists e \in M, \forall a \in M, a \circ e = e \circ a = a\)
Property Meaning English * (approximation, not very accurate)
Closure \(\forall a, b \in S, a \circ b \in S\) All elements and results of applying \(\circ\) on them enclosed in the group
Associativity \(\forall a, b, c \in S, (a \circ b) \circ c = a \circ (b \circ c)\) Parentheses do not change order
Identity \(\exists e \in S, \forall a \in S, a \circ e = e \circ a = a\) There is an element that does not change the results of all other elements
Inverse \(\forall a \in S, \exists a^{-1} \in S, a \circ a^{-1} = a^{-1} \circ a = e\) For every element there is an element that cancel it out (according to the \(\circ\))
Commutativity \(\forall a, b \in S, a \circ b = b \circ a\) Order does not change the result of \(\circ\)
Name Closure Associativity Identity Inverse Commutativity Example
Semigroup Yes Yes
Monoid Yes Yes Yes
Group Yes Yes Yes Yes
Albelian Group Yes Yes Yes Yes Yes
  • Examples:
Set and Operation Closure Associativity Identity Inverse Commutativity Example
Matrix Addition 3 * 3 Real matrices Yes Yes Yes (0 matrix)
Matrix multiplication 2 * 2 of even integers Yes Yes No (1 is not in set)
Addition on Set of integers Yes Yes Yes (0) Yes Yes
Multiplication on Set of odd integers Yes Yes Yes (1) Yes Yes

Modular Arithmetic

  • Congruence (mod n): \(a \equiv b \pmod{n}\) if \(n | (a - b)\)
  • Example: \(15 \equiv 3 \pmod{12}\)
    • because \(15 \pmod{12} = 3\) and \(3 \pmod{12} = 3\) and \(12 | (15 - 3)\).
    • Think of it as a clock, the 15hour and 3hour are the same pointing to number 3.
    • Available classes for \([n]_{12}\) are \([0]_{12}, [1]_{12}, [2]_{12}, ..., [11]_{12}\) or \(n=12k\) where \(k \in \mathbb{Z}\)
  • Available classes for \([n]_m\) are \([0]_m, [1]_m, [2]_m, ..., [m-1]_m\)
  • Congruence Class (mod n): \([a]_n = \{b \in \mathbb{Z} | a \equiv b \pmod{n}\}\)
  • Example: \([2]_3 = \{..., -4, -1, 2, 5, ...\}\) because \(3 | (2 - b)\)
  • The common divisor of a and b is a number that divides both a and b.
  • The greatest common divisor of a and b is the largest number that divides both a and b.
  • Two numbers are relatively prime if their greatest common divisor is 1.

References