Mathematical Foundation of Computer Science

(Chris Devlin) #1
DHARM

ALGEBRAIC STRUCTURES 93

Now check whether (X, •) is a monoid or not. If (X, •) is a monoid then it should have an
identity element 1. It means, for all x ∈ X, there exists an unique y, i.e., x • y = x then y is
called an identity element. Since y = 1 ∉ X or for no y, x • y = x. So it has not an identity
element 1. Therefore, (X, +, •) is a ring without unity.
Further, (X, •) is commutative, i.e., for all x, y ∈ X, x • y = y • x, hence a commutative
ring.
Example 4.15. Let Y = {0, 1, 2, 3, 4, 5}, then algebraic system (Y, + 6 , × 6 ) is a ring, a ring
without unity, and a commutative ring.
Sol. Construct the operation table for both the operation addition modulo 6 (+ 6 ) and multipli-
cation modulo 6 (× 6 ).



  • 6 012345 × 6 012345
    0012345 0000000
    1123450 1012345
    2234501 2024024
    3345012 3030303
    4450123 4042042
    5501234 5054321


Fig. 4.6 Operation Table.
From the operation table shown in Fig. 4.6 (Y, + 6 ) is Abelian, because,
l Each element in the table belongs to set Y hence operation + 6 is closed.
l + 6 is associative.
l Element 0 is an identity element. (Shown in bold at first column).
l Occurrence of 0 (identity) in each row of table + 6 implies existence of the inverse
element for each element of Y.
l Entries of corresponding rows and columns are same hence + 6 is commutative.
Also (Y, × 6 ) is a semigroup, because,
l × 6 is closed.
l Since, 2 × 6 (3 × 6 4) = 0 × 6 2 = 0. Also, (2 × 6 3) = 0, (2 × 6 4) = 2 so (0 × 6 2) = 0. So this is
true for all elements of Y, hence, operation ×6 is associative.
Distributive law holds, i.e. × 6 is distributive over + 6 , i.e., let a, b, c ∈ Y then
a × 6 (b + 6 c) = (a × 6 b) + 6 (a × 6 c)
where, (b + 6 c) returns least nonnegative number when (b + c) is divisible by 6. So, LHS
returns least nonnegative number when a × (b + c) is divisible by 6, that is RHS.
Since (Y, × 6 ) does not posses an identity element 1 hence, algebraic structure (Y, + 6 , × 6 )
is not a ring with unity. Although it is a commutative ring, due to the correspondence be-
tween rows and columns of operation table for × 6.
Using definition of the ring we obtain following results,
l From the property of the additive group (X, +) of the ring, there is an existence of
zero – element of X i.e.
x + 0 = x for all x ∈ X
Free download pdf