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