# 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):

• 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.