[ Home ]

Algebraic Structures

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. (It currently looks quite ugly because of the default bootstrap styling; maybe I'll fix it later.)

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