Algebraic categories

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 ( $\forall$ x, y $\in$ M) xy = yx) then

it is denoted additively
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

( $\displaystyle \forall$ x, y, z $\displaystyle \in$ M) (xy)z = x(yz) and ( $\displaystyle \forall$ x $\displaystyle \in$ 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, %) -> %;
        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

( $\displaystyle \forall$ x $\displaystyle \in$ G) ( $\displaystyle \exists$ y $\displaystyle \in$ G) xy = yx = 1.

(39)

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

( $\displaystyle \forall$ x $\displaystyle \in$ G) ( $\displaystyle \exists$ y $\displaystyle \in$ 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

( $\displaystyle \forall$ x, y, z $\displaystyle \in$ 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 $\mbox{${\mathbb Z}$}$ = {2n | n $\in$ $\mbox{${\mathbb Z}$}$ } is an example of such rings). When a ring R has a multiplicative neutral element that we will denote 1_R then we have the following properties and definitions.

One can convert any integer n $\in$ $\mbox{${\mathbb Z}$}$ 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 $\in$ $\mbox{${\mathbb Z}$}$ 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 $\mbox{${\mathbb Z}$}$ /m $\mbox{${\mathbb Z}$}$ 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 $\mathbb {Z}$ 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 $\in$ R is an associate of the element b $\in$ R if there exists a unit u $\in$ 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₁, q₂ be in R. Assume that we have

a = b q₁ = b q₂ and b $\displaystyle \neq$ 0.

(42)

Then b(q₁ - q₂) = 0. Since R is an integral domain we obtain q₁ = q₂. 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) $\longmapsto$ R is defined and satisfies the following properties

for every a, b $\in$ R the element gcd(a, b) divides a and b.
for every a, b, c $\in$ R, if c divides a and b then it divides gcd(a, b).

Two elements a, b $\in$ 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 $\in$ R is reducible if there are two nonunits c, d $\in$ R such that p = c d, otherwise p is irreducible. Units are neither reducible nor irreducible. A nonzero nonunit p $\in$ R is prime if for every c, d $\in$ R we have we have

(p | cd ) $\displaystyle \Rightarrow$ (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 $\in$ 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 $\longmapsto$ $\mbox{${\mathbb N}$}$ $\cup$ { - $\infty$ } such that for all a, b $\in$ R with b $\neq$ 0 there exist q, r $\in$ 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

**Figure 3:** The hierarchy of algebraic structures in `libalgebra`.

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