Mathematical Foundation of Computer Science

(Chris Devlin) #1

4.1 INTRODUCTION


In the context of algebra a system consisting of a set and one or more n-ary operations on the
set is called an algebraic system. Let X be a finite and nonempty set then algebraic system is
denoted by (X, , , ....), where , , ....are the operations on X. Since, the operations over
the set represent a structure between the elements; therefore an algebraic system is also known
as algebraic structure. Groups, rings, fields, vector spaces, etc. are the examples of the algebraic
systems.
As we said a set with number of operations over the set describes an algebraic system.
Here we restrict our study of algebraic systems to those operations that are only unary or
binary in nature. For example, consider the set of natural number N with usual addition
operation +. Hence, (N, +) represent an algebraic system. Clearly, (N, +, H) is an algebraic
system with two usual operations, addition and multiplication, + and H. It is possible to consider
that more than one set together with different operations describe similar algebraic systems
if operations are of same degree. Conversely, two different algebraic systems (X, , ) and
(Y, s, l) are of same type if, the operations and s, and operations and l are of same
degree.
Since, every systems posses their own property that is obviously, the property holds by
any of its operations, so we now listed some common properties of an algebraic system (X, )
where is a binary operation on X, are as follows,
I. Closure. Operator is said to be closed, if, x y ∈ X and unique for∀(x and y) ∈ X.
II. Commutative. Operator is commutative over set X, if, x y = y x, for ∀(xandy)
∈ X
III. Associative. Operator is associative over set X, i.e. if x, y and z ∈ X , then we
have,
x (y z) = (x y) z
IV. Existence of an unique Identity Element. There exists an identity element ê for
∀x ∈ X with respect to operation , i.e.,
x ê = ê x = x
right identity left identity
For example, 0 is the identity element for algebraic system (I, +), where I is the set of
integers and ‘+’ is the usual addition operation of integers, i.e., x + 0 = 0 + x = x, for ∀x ∈ I.
Therefore, 0 is called additive identity. (Reader self verify that 1 will be multiplicative identity).
V. Existence of Inverse Elements. There exists an inverse element y ∈ X for every
x ∈ X with respect to operation , i.e.,
x y = ê = y x


4 Algebraic Structure

Free download pdf