Skip to content

8. Introduction to Algebraic Structures

  • Group: a group G denoted by {G,} is a set G together with a binary operation on G such that the following CAIN axioms hold:
    • Closure: a,bG,abG
    • Associativity: a,b,cG,(ab)c=a(bc)
    • Identity: eG,aG,ae=ea=a
    • Inverse: aG,a1G,aa1=a1a=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: a,bG,ab=ba

  • List of common sets:

    • N: Natural numbers {1,2,3,...} (integers greater than 0)
    • Z: Integers {...,3,2,1,0,1,2,3,...}
    • Z: Negative integers {...,3,2,1}
    • Z: Positive integers {1,2,3,...} (excluding 0)
    • Q: Rational numbers {ab|a,bZ,b0}
    • R: Real numbers {...,π,2,12,0,12,2,π,...}
    • C: Complex numbers {a+bi|a,bR,i=1}
    • Zn: Integers modulo n {0,1,2,...,n1}
    • Z+: Positive integers {1,2,3,...}
    • Zn: Integers modulo n excluding 0 {1,2,...,n1}
    • W: Whole numbers {0,1,2,3,...}
  • Semigroup: a semigroup S denoted by {S,} is a set S together with a binary operation on S such that the following CA axioms hold:

    • Closure: a,bS,abS
    • Associativity: a,b,cS,(ab)c=a(bc)
  • Monoid: a monoid M denoted by {M,} is a set M together with a binary operation on M such that the following CAI axioms hold (that is, a semigroup with identity):

    • Closure: a,bM,abM
    • Associativity: a,b,cM,(ab)c=a(bc)
    • Identity: eM,aM,ae=ea=a
Property Meaning English * (approximation, not very accurate)
Closure a,bS,abS All elements and results of applying on them enclosed in the group
Associativity a,b,cS,(ab)c=a(bc) Parentheses do not change order
Identity eS,aS,ae=ea=a There is an element that does not change the results of all other elements
Inverse aS,a1S,aa1=a1a=e For every element there is an element that cancel it out (according to the )
Commutativity a,bS,ab=ba Order does not change the result of
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): ab(modn) if n|(ab)
  • Example: 153(mod12)
    • because 15(mod12)=3 and 3(mod12)=3 and 12|(153).
    • 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 kZ
  • Available classes for [n]m are [0]m,[1]m,[2]m,...,[m1]m
  • Congruence Class (mod n): [a]n={bZ|ab(modn)}
  • Example: [2]3={...,4,1,2,5,...} because 3|(2b)
  • 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