__A MONOID__ is a set *M* endowed with an operation
which is associative and which admits a neutral element.
If this operation is commutative (that is
(*x*, *y* *M*) *xy* = *yx*) then

- it is denoted additively
- the neutral element is called 0,
- and the monoid is said
*abelian*

- it is denoted multiplicatively,
- and the neutral element is called 1.

(x, y, z M) (xy)z = x(yz) and (x M) 1 x = x 1. |
(38) |

Here are the definition of the categories

define Monoid: Category == ExpressionType with { 1: %; *: (%, %) -> %; ^: (%, Integer) -> %; one?: % -> Boolean; times!: (%, %) -> %; default { one?(a:%):Boolean == a = 1; times!(a:%, b:%):% == { a * b; } } } define AbelianMonoid: Category == ExpressionType with { 0: %; +: (%, %) -> %; *: (Integer, %) -> %; add!: (%, %) -> %; zero?: % -> Boolean; default { zero?(x:%):Boolean == x = 0; add!(a:%, b:%):% == { a + b; } } }

__A GROUP__ is a monoid *G* where every element has a symmetric element.
With multiplicative notations this writes

(x G) (y G) xy = yx = 1. |
(39) |

and symmetric elements are called inverses. With additive notations this writes

(x G) (y G) x + y = y + x = 0. |
(40) |

and symmetric elements are called opposites. Here are the definitions of

define Group: Category == Monoid with { /: (%, %) -> %; inv: % -> %; default (x:%) / (y:%):% == x * inv y; } define AbelianGroup: Category == Join(AdditiveType, AbelianMonoid)

__A RING (WITH UNITY)__ is

- an abelian group (that is an abelian monoid where every element has an opposite)
- a (multiplicative) monoid
- such that the multiplication is distributive w.r.t. the addition,
which writes
( *x*,*y*,*z**M*)*x*(*y*+*z*) =*xy*+*xz**and*(*y*+*z*)*x*=*yx*+*zx*.(41)

- One can convert any integer
*n*into the element of*R*given by 1_{R}+^{ ... }+ 1_{R}(sum with*n*terms equal to 1_{R}). - If there is one positive
*n*that converts to 0_{R}then the smallest of such positive integers is called the characteristic of the ring*R*. For instance the modular integer ring /*m*has characteristic*m*.

define Ring: Category == Join(AbelianGroup, ArithmeticType, Monoid) with { characteristic: Z; coerce: Z -> %; .................... random: () -> % default ((x: %) ^ (n: MachineInteger)): % == x^(n::Z); ((n: AldorInteger) * (x: %)): % == n::% * x; random(): % == random()$Z :: %; ((x: %) ^ (n: AldorInteger)): % == binaryExponentiation(x, n)$BinaryPowering(%,Z); }A ring is said

Let *R* be a commutative ring.
The element *a* *R* is an associate of the element *b* *R*
if there exists a unit *u* *R* such that
*a* = *b* *u*.
The operation `unitNormal` below returns
(*b*, *v*, *u*) given *a* such that
*a* = *b* *u* and
*u* *v* = 1.
If this choice is canonical (that is if for every *a* and *a'*
such that
*a'* is associate with *a* the first field of `unitNormal`(*a*)
is equal to that of `unitNormal`(*a'*)
then `canonicalUnitNormal?` returns true.

define CommutativeRing: Category == Ring with { canonicalUnitNormal?: Boolean unitNormal: % -> (%, %, %); reciprocal: % -> Partial(%); unit?: % -> Boolean; ................................. cutoff: MachineInteger -> MachineInteger }

__AN INTEGRAL DOMAIN__ is a ring with no zero-divisors,
that is a ring where if the product of two elements is
zero then at least of them must be zero.
Let *R* be an integral domain.
Let
*a*, *b*, *q*_{1}, *q*_{2} be in *R*. Assume that we have

a = b q_{1} = b q_{2} and b 0. |
(42) |

Then

define IntegralDomain: Category == CommutativeRing with { exactQuotient: (%, %) -> Partial(%); ...................................... }

__A GCD DOMAIN__ is an integral domain *R* where an operation
gcd : (*R*, *R*) *R* is defined and satisfies the following properties

- for every
*a*,*b**R*the element gcd(*a*,*b*) divides*a*and*b*. - for every
*a*,*b*,*c**R*, if*c*divides*a*and*b*then it divides gcd(*a*,*b*).

define GcdDomain: Category == IntegralDomain with { gcd: (%, %) -> % gcd!: (%, %) -> % gcd: Generator(%) -> % lcm: (%, %) -> % lcm: List(%) -> % gcdquo: (%, %) -> (%, %, %) gcdquo: List(%) -> (%, List(%)) ............................... }

__UNIQUE FACTORIZATION DOMAINS.__ A nonzero nonunit *p* *R* is *reducible*
if there are two nonunits *c*, *d* *R* such that
*p* = *c* *d*,
otherwise *p* is *irreducible*.
Units are neither reducible nor irreducible.
A nonzero nonunit *p* *R* is *prime* if
for every *c*, *d* *R* we have
we have

(p | cd ) (p | c or p | d ) |
(43) |

The integral domain

define FactorizationRing: Category == GcdDomain with { ................................................... }

__AN EUCLIDEAN DOMAIN__ is an integral domain *R* endowed with a function
*d* : *R* { - }
such that for all *a*, *b* *R* with *b* 0
there exist *q*, *r* *R* such that

a = bq + r and d (r) < d (b). |
(44) |

The elements

define EuclideanDomain: Category == GcdDomain with { divide: (%, %) -> (%, %); quo: (%, %) -> %; rem: (%, %) -> %; euclid: (%, %) -> %; euclideanSize: % -> Integer; extendedEuclidean: (%, %) -> (%, %, %); }In the category

__A FIELD__ is a ring (with unity) where every nonzero element is a unit.
In `libalgebra` fields are commutative rings.
Then it follows that they are also integral domains, gcd domains and Euclidean domains.

define Field: Category == Join(EuclideanDomain, Group) with { default { canonicalUnitNormal?:Boolean == true; euclideanSize(a:%):Integer == 0; unit?(x:%):Boolean == true; (a:%) quo (b:%):% == a / b; (a:%) rem (b:%):% == 0; gcd(a:%, b:%):% == { zero? a and zero? b => 0; 1 } (a:%)^(n:Integer):% == { import from BinaryPowering(%, Integer); n > 0 => binaryExponentiation(a, n); inv binaryExponentiation(a, -n); }

__THE HIERARCHY OF ALGEBRAIC TYPES__

__FRACTIONCATEGORY.__

define FractionCategory(R: IntegralDomain): Category == Join(IntegralDomain, Algebra R) with { if R has CharacteristicZero then CharacteristicZero; if R has FiniteCharacteristic then FiniteCharacteristic; denominator: % -> R; numerator: % -> R; }

2003-06-06