Algebraic Structures
24 Jul 2016
I've been taking baby steps in abstract algebra, to try to learn more about the mathematics that underlie some of my favorite hashing algorithms.
Definitions:
The elements of P are known as the positive elements of S; all other nonzero elements of S are known as the negative elements of S.
If a and b are elements of S, and if a + -b is positive, then we write a > b and b < a.
The commutative law for addition: a + b = b + a
The commutative law for multiplication: a × b = b × a
The associative law for addition: (a + b) + c = a + (b + c)
The associative law for multiplication: (a × b) × c = a × (b × c)
The (left) distributive law for multiplication over addition: a × (b + c) = (a × b) + (a × c)
Here's a table of algabraic structures and their properties.
| ordered field |
field | division ring (sfield) |
integral domain |
ring with unity |
commutative ring |
ring | Abelian or commutative group |
group | Abelian or commutative semigroup |
semigroup | |
|---|---|---|---|---|---|---|---|---|---|---|---|
| If a and b are in S, then a + b = b + a |
X | X | X | X | X | X | X | ||||
| If a and b are in S, then a × b = b × a |
X | X | X | X | X | ||||||
| If a, b, and c are in S, then (a + b) + c = a + (b + c) |
X | X | X | X | X | X | X | ||||
| If a, b, and c are in S, then (a × b) × c = a × (b × c) |
X | X | X | X | X | X | X | X | X | X | X |
| If a, b, and c are in S, then a × (b + c) = (a × b) + (a × c) and (b + c) × a = (b × a) + (c × a) |
X | X | X | X | X | X | X | ||||
| S contains an element 0 (zero) such that for any element a of S, a + 0 = a |
X | X | X | X | X | X | X | ||||
| S contains an element 1 (unity) different from 0 (zero), such that for any element a of S, a × 1 = a |
X | X | X | X | X | X | |||||
| For each element a in S, there exist an element -a in S such that a + -a = 0 |
X | X | X | X | X | X | X | ||||
| If a, b, and c are in S, c ≠ 0, and c × a = c × b or a × c = b × c then a = b |
X | X | X | X | |||||||
| For each element a ≠ 0 in S, there exists an element a-1 in S such that a × a-1 = 1 |
X | X | X | X | X | ||||||
| There exists a subset P, not containing 0, of the set S such that if a ≠ 0, then one and only one of a and -a is in P |
X | ||||||||||
| There exists a subset P, not containing 0, of the set S such that if a and b are in P, then a + b and a × b are in P |
X |