Algebraic structures: Set, Group, Ring

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

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

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

1
2

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

  print(-a)

-1

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

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

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

  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

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.

  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

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

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

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)

Properties:

• associativity: under both + and * operations
• identity: has both additive and multiplicative identities

Properties:

• inverse: has inverse elements under addition

Properties:

• commutativity: additive operation is commutative

Properties:

• commutativity: multiplication is commutative

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

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.