Algebraic structures: Set, Group, Ring

Math

The easiest way to understand algebraic structures, starting with basic structure called Set and incrementally add properties on top of it to build more complex structures.

TL;DR;

A group (G, +) - a set G and one binary operation (e.g. addition) that has the following properties:

  1. operation is closed - magma

  2. operation is associative - semigroup

  3. has identity element - monoid

  4. has inverse elements - group

Optionally a group might be:

  • abelian - operation is commutative

  • finite - with finite number of elements

  • cyclic - a generator exists

A ring (R, +, *) - a set R and two binary operations (addition, multiplication):

  • abelian group under addition

  • monoid under multiplication

  • multiplication is distributed over addition

A field (F, +, *) is a ring with:

  • abelian group under both addition and multiplication

  • additive identity is absorbing element under multiplication

Keep reading to see how these structures are related and stack on top of each another.

1. Sets - one unary operation

1.1 Set

The base list-like structure that can be either finite or infinite. Let's look at the simplest positive integers set N (also called natural numbers).

  N = PositiveIntegers()
  print(N.cardinality())
+Infinity

1.2 Pointed set

A set and an element of the set (N, p)

  a = N[0]
  print(a)
  b = N[1]
  print(b)
1
2

1.3 Unary set

A Set with unary operation (negation) over the set.

  print(-a)
-1

2. Groups - one binary operation

2.1 Groupoid (magma) - a set with single binary operation

Let addition be our binary operation over the group (N, +).

  c = a + b
  print(c in N)
True

Properties:

  • closure: if a, b ∈ N and c = a + b then c ∈ N

2.2 Semigroup - groupoid with associative operation

Additive operation is associative over natural numbers.

  c = N[3]
  r = (a + b) + c == a + (b + c)
  print(r)
True

Properties:

  • associativity: let a, b, c ∈ N then the equation (a + b) + c = a + (b + c) holds

2.3 Monoid - semigroup with identity element

Since our natural number set N does not have identity we need to choose another one like non-negative integers

  NN = NonNegativeIntegers()
  e = NN[0]
  a = NN[1]
  print("IDENTITY: " + str(e)) if e + a == a else "NOPE"
IDENTITY: 0

Properties:

  • identity: an element e ∈ S is the identity if equation e + a = a holds

2.4 Group - monoid with inverse elements

Again, non-negative integers set does not have an inverse and we need to expand our set to whole integers Z.

  Z = IntegerRange(-Infinity, Infinity, 1, 0)
  a = Z[1]
  b = -a
  print(b in Z)
  print("INVERSE: " + str(b)) if a + b == e else "NOPE"
True
INVERSE: -1

Properties:

  • inverse: an item a ∈ Z has an inverse b ∈ Z if the equation a + b == e holds.

2.5 Abelian group - a group with commutative operation

  a = Z[1]
  b = Z[2]
  print("COMMUTATIVE") if a + b == b + a else "NOPE"
COMMUTATIVE

Properties:

  • commutativity: let a,b ∈ Z, then a + b = b + a

2.6 Finite group - a group with finite number of elements

A group with finite number of elements is called finite group and the number of elements in group is called order.

  G = [0, 1, 2, 3, 4]
  print(len(G))
5

2.7 Cyclic group - a finite abelian group with a generator

A cyclic group is a group that can be generated by a single element called the generator and according to Cauchy theorem every finite group G over prime number p has a generator of order p.

We can use modular arithmetic (mod 5) and use number 3 to generate our group by adding generator to itself multiple times: g+g+g = g * 3

  print([3*i % 5 for i in range(20)])
[0, 3, 1, 4, 2, 0, 3, 1, 4, 2, 0, 3, 1, 4, 2, 0, 3, 1, 4, 2]

We can easily see that the generator is returning all elements of our group over and over again, hence the cyclic group.

Properties:

  • cyclical: existence of generator g

3. Rings - two binary operations

3.1 Ringoid - a set with two binary operations

A ringoid (R, +, *) is defined as a set R and two closed binary operations.

Properties:

  • closure: under both addition and multiplication

  • distributive: multiplication distributes over addition a * (b + c) = (a * b) + (b * c)

3.2 Semiring - a ringoid whose set is monoid under both operations

Properties:

  • associativity: under both + and * operations

  • identity: has both additive and multiplicative identities

3.3 Near-ring - a semiring whose set is a group under addition

Properties:

  • inverse: has inverse elements under addition

3.4 Ring - a semiring whose set is abelian group under addition

Properties:

  • commutativity: additive operation is commutative

3.5 Commutative ring - a ring with commutative multiplication

Properties:

  • commutativity: multiplication is commutative

3.6. Division ring - a ring with inverse elements under multiplication

Additive identity (e.g. 0) is an absorbing element under multiplication and has no inverse element.

Properties:

  • inverse: all non-zero elements have inverses under multiplication

3.7 Field - a commutative division ring

A field defined as (F, +, *), whose set F (which can be finite or infinite) is an abelian group under both addition and multiplication.

  F = FiniteField(5)
  F
Finite Field of size 5
  F.addition_table(names='elements')
+  0 1 2 3 4
 +----------
0| 0 1 2 3 4
1| 1 2 3 4 0
2| 2 3 4 0 1
3| 3 4 0 1 2
4| 4 0 1 2 3
  F.multiplication_table(names='elements')
*  0 1 2 3 4
 +----------
0| 0 0 0 0 0
1| 0 1 2 3 4
2| 0 2 4 1 3
3| 0 3 1 4 2
4| 0 4 3 2 1

This is it for now, in next part we will have a look at more complex, lattices-like structures.

math  set  group  ring  field  algebra 
comments powered by Disqus