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.
A group (G, +) - a set G and one binary operation (e.g. addition) that has the following properties:
operation is closed - magma
operation is associative - semigroup
has identity element - monoid
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
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())
1.2 Pointed set
A set and an element of the set (N, p)
a = N print(a) b = N print(b)
1.3 Unary set
A Set with unary operation (negation) over the set.
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)
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 r = (a + b) + c == a + (b + c) print(r)
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 N°
NN = NonNegativeIntegers() e = NN a = NN print("IDENTITY: " + str(e)) if e + a == a else "NOPE"
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 b = -a print(b in Z) print("INVERSE: " + str(b)) if a + b == e else "NOPE"
True INVERSE: -1
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 b = Z print("COMMUTATIVE") if a + b == b + a else "NOPE"
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))
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.
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.
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
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
inverse: has inverse elements under addition
3.4 Ring - a semiring whose set is abelian group under addition
commutativity: additive operation is commutative
3.5 Commutative ring - a ring with commutative multiplication
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.
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
+ 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
* 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.