Mathematical Foundation of Computer Science

DHARM

ALGEBRAIC STRUCTURES 79

For example, the additive inverse define the subtraction i.e., x + (– x) = ê. Similarly,
the multiplication inverse defines division i.e., x H (1/x) = ê.
Assume an algebraic system consists of two operators (X, , ), then
VI. Distributive Property. Since and are two binary operations on set X, and if
x, y and z ∈ X then operator is said to be distributive over whenever,
x (y z) = (x y) (x z)
and also operator is distributive over whenever,
x (y z) = (x y) (x z)
For example field is an algebraic system. A field is defined by a set of elements, binary
operations + and H, a set of properties 1 to 5, and combination of both operations fulfilling
property 6. A field of real numbers is a common example consists of set of real numbers (R),
with binary operations + and H denoted by (R, +, H). It is the basis for ordinary algebra.
Example 4.1. Let X = {1, 2, 3, 4} and (X, X, f) is a morphism, where function f is represented
by the expression,

f =

1234

2341

F

H

I

K

Prove that (F, ◊) is an algebraic system, where F is the set of unique composite functions

of f.

Sol. From the composite functions,

f ◊ f = f^2 ; f^2 ◊ f = f^3 ; f^3 ◊ f = f^4 ; and so on.

Determine f^2 , f^3 , f^4 ,.... so we obtain

f ◊ f = f^2 =

123

341

F

H

I

K , f

(^2) ◊ f = f (^3) =^123
412
F
H
I
K, f
(^3) ◊ f = f (^4) = 12 3
12 3
F
H
I
K
Since, f^4 is an identity function or mapping, i.e, f^4 = {(x, x)/x ∈ X) = f^0 (assume) and all
others composite of functions are repeated in the set F = {f, f^2 , f^3 , f^0 } or {f^0 , f^1 , f^2 , f^3 }. Since
operation ◊ is closed, commutative and associative together with the existence of an identity
functions, which results (F, ◊) is an algebraic system.

4.2 Groups

Let X be an nonempty set and be an binary operation on X, then algebraic system (X, ) is

called a group, if operation satisfies the following postulates,

1. is closed,


2. is associative,
   3.Existence of an identity element, and
   4.Existence of the unique inverse.
   (Postulates 1 – 4 are called group axioms)
   For example, algebraic system (X, ), where X = {+, –} and binary operation is
   defined in the table show in Fig. 4.1.
   +–
   ++ –
   –– +
   Fig. 4.1 Operation table