Next: Numbers Up: Algebraic types Previous: Algebraic types

### Algebraic categories

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 Mxy = yx) then

• the neutral element is called 0,
• and the monoid is said abelian
otherwise
• it is denoted multiplicatively,
• and the neutral element is called 1.
Hence in the general case we have

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

Here are the definition of the categories Monoid and AbelianMonoid in libalgebra.
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, %) -> %;
zero?: % -> Boolean;
default {
zero?(x:%):Boolean      == x = 0;
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 Group and AbelianGroup in libalgebra
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)

In classical Algebra textbooks, the definition of a ring is more general (the multiplication may not have a neutral element, i.e. a 1 may not exist) but such rings are rare in Computer Algebra (although 2 = {2n  |  n } is an example of such rings). When a ring R has a multiplicative neutral element that we will denote 1R then we have the following properties and definitions.
• One can convert any integer n into the element of R given by 1R + ... + 1R (sum with n terms equal to 1R).
• If there is one positive n that converts to 0R 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.
Here's a fragment (we skip some technical operations) of the definition of a Ring in libalgebra.
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 commutative if its multiplication is commutative. Rational numbers, univariate polynomials over are examples of commutative rings whereas rings of matrices are not commutative. In non-commutative rings a given element x may have a left-inverse y (thus yx = 1) but no right-inverse (i.e. no z such that xz = 1). In a commutative ring an element with inverse (right and left) is called a unit and its inverse is called its reciprocal.

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, q1, q2 be in R. Assume that we have

 a  =  b q1  =  b q2  and  b 0. (42)

Then b(q1 - q2) = 0. Since R is an integral domain we obtain q1 = q2. Therefore if b divides a then there is a unique q such that a = b q.
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).
Two elements a, b R are coprime if gcd(a, b) = 1.

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 R is a Unique Factorization Domain (UFD for short) (or a factorial ring) if every nonzero nonunit a R can be written as a product of irreducible elements in a unique way up to reordering and multiplication by units.
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 q and r are called the quotient and the remainder of a w.r.t. b (although q and r may not be unique). The function d is called the Euclidean size.
define EuclideanDomain: Category == GcdDomain with {
divide: (%, %) -> (%, %);
quo: (%, %) -> %;
rem: (%, %) -> %;
euclid: (%, %) -> %;
euclideanSize: % -> Integer;
extendedEuclidean: (%, %) -> (%, %, %);
}

In the category EuclideanDomain above the operation euclid denotes the gcd computed by the Euclidean algorithm.

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;
}


Next: Numbers Up: Algebraic types Previous: Algebraic types
Marc Moreno Maza
2003-06-06