DHARM
80 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE
Since,
Operation is associative and closed, because of, + + = + ∈ X and similarly it is true
for others in the table.
Operation is also associative, because of,
+ (– +) = + – = – ; which is same to (+ –) + = – + = – ; and similarly
true for others in the table.
There exists an identity element for each element of X i.e.,
+ + = + + = + and – + = + – = –
(For both operations + and – identity element is +)
For every element of X there exists a unique inverse, i.e.
- – = + (identity element) and + + = + (identity element)
Therefore, algebraic system (X, ) is a group.
In a group (X, ) the cardinality of the set X i.e. | X | gives the order of the group. If
| X | is finite and consists of n elements, then group is said to be a finite group of order n,
conversely if | X | = ∞, then group is an infinite group.
N H Abel (in early 19’s) had make something their own and the group called Abelian
group, i.e., a group (X, ) is said to be abelian if the binary operation is commutative as well.
For example, system (I, +), where I is the set of all integers and operation + is addition of
integers is an abelian group.
If an algebraic system (X, ) follows only restrictions 1 and 2 such that, binary opera-
tion is closed and associative then (X. ) is called a semigroup. For example, algebraic
system (I+, +) is a semigroup, where I+ is the set of positive integers and operation + is usual
addition operations; because addition operation is closed and associative on I+. Similarly,
system (I+, ×) is also a semigroup, where operation × is usual multiplication operation.
Consider another example, Let N be the set of natural numbers, i.e. N = {0, 1, 2, ....}
and + is an addition operation then algebraic system (N, +) and (N, ×) are semigroup in
addition to that there exists an identity element 0 and 1 with respect to operations + and ×
respectively. Such semigroups are called monoids. A semigroup there may or may not have
an identity element.
An algebraic system (X, ) is called monoid, if operation satisfies the following
postulates 1, 2, and 3 i.e.,
- is closed,
- is associative, and
3.Existence of an identity element,
For example, let Σ = {a, b, c} and Σ = {ε, a, b, c, a b, b c, c a, .......} is the set of all
possible strings form over the alphabets Σ then algebraic system (Σ, .) is monoid, where. is a
binary concatenation operation, i.e., for any two strings x, y ∈ Σ, x.y yields the string xy.
Since,
1.For any x any y ∈ Σ, x. y ⇒ xy ∈ Σ; hence operation. is closed.
2.For any x, y, and z ∈ Σ, (x. y). z = x. (y. z) ⇒ x y z ∈ Σ; so operation. is associative.
3.Set Σ contains an identity element ε called null string i.e. | ε | = 0, then for any
x ∈ Σ*,
x. ε = ε. x = x
