Unit 4 | DSTL Notes |Discrete Structure and Theory of Logic Notes | Aktu Notes
Algebraic Structure
- An algebraic structure is a mathematical system comprising a collection of elements.
- One or more operations defined on the set, such as addition, multiplication, or binary operations.
- Suppose * is a binary operation on G. Then (G, *) is an algebraic structure
The behavior of elements within the structure is determined by properties like:
1. Closure property : Result of combining elements is always in the group
(a * b) ∈ S ∀ a, b, ∈ S
2. Associativity: Grouping doesn't change the result
(a * b) * c = a * (b * c) ∀ a, b, c ∈ S
3. Commutativity: Order of operands doesn't matter.
(a * b) = (b * a)
4. Distributivity: Operation interacts with another in specific way.
a * (b + c) = (a * b) + (a * c) (right distributive)
(b + c) * a = (b * a) + (c * a) (left distributive)
5. Identity Elements: Elements that don't change others.
a * e = a = e*a
6. Inverse Elements: Elements that cancel each other
a * a –1 = e = a – 1 * a
Semigroup
- Set with closure and associative property .
- Ex: (N,+) (Z, +), (R, +), and (Q, +) are all semigroups
Group
- Set with closure , associative property, identity, inverses.
- Ex: (Z, +), (R, +), and (Q, +) are all groups
Abelian Group
- Group with commutative operation.
- Ex: (Z, +) is abelian group
Note: z = set(integer), N = set(natural), Q = set(rational), R = set(real)
Question:
Show that the set G = {x + 2y |x, y Q} is a group with respect to addition
i) Closure :
- Let X = x1 + 2y1 Y = x2 + 2y2 where x1 , x2 , y1 , y2 ∈ Q and X, Y ∈ G
Then X + Y = (x1 + 2y1 ) + (x2 + 2y2 )
= (x1 + x2 ) + 2(y1 + y2 )
= X1 + 1 2Y ∈ G where X1 , Y1 ∈ Q
Therefore, Sum of two rational numbers is rational.
ii) Associativity :
Let X, Y and Z ∈ G
Therefore X = x1 + 2y1
Y = x2 + 2y2
Z = x3 + 2y3 where x1 ,x2 , x3 , y1 , y2 , y3 ∈ Q
Consider (X + Y) + Z = (x1 + 2 y1 + x2 + 2y2 ) + (x3 + 2 y3 )
= ((x1 + x2 ) + 2(y1 + y2 ) ) + (x3 + 2y3 )
= (x1 + x2 + x3 ) + (y1 + y2 + y3 ) ---- eq(1)
Also X + (Y + Z) = (x1 + 2y1 ) + ((x2 + 2y2 ) + (x3 + 2y3 ))
= (x1 + 2y1 ) + ((x2 + x3 ) + 2(y2 + y3 ) ) ---- eq(2)
= (x1 + x2 + x3 ) + (y1 + y2 + y3 )
From eq. ( 1) and (2) (X + Y) + Z = X + (Y + Z)
Therefore, G is associative under addition.
iii) Identity element :
Let e ∈ G be identity elements of G under addition then (x + 2y ) + (e 1 + 2e2 ) = x +2y where e = e 1 + 2e2 and e1 , e2 , x,
y ∈ Q
e1 + 2e2= 0 + 0 2 e1 = 0 and e 2 = 0 Therefore, 0 ∈ G is identity element.
iv) Inverse element :
– x – 2y ∈ G is inverse of x + 2y ∈ G. Therefore, inverse exist for every element x + 2y ∈ G
such that, y ∈ Q. Hence, G is a group under addition.
Ring
- A ring is an algebraic system (R, +, •) where R is a non-empty set and + and • are two binary operations
- if the following conditions are satisfied :
1. (R, +) is an abelian group.
2. (R, •) is semigroup
3. The operation • is distributive over +.
i.e., for any a, b, c ∈ R
a • (b + c) = (a • b) + (a • c)
or (b + c) • a = (b • a) + (c • a)
- Ex: (Z, +,*), (R, +,*), and (Q, +,*) are all ring
Integral Domain
- A ring is called an integral domain if :
1. It is commutative
2. It has unit element
3. It is without zero divisors
- Ex:(Z, +, *),(R, + ,*), and (Q, + ,*) are all integral domain
Field
- A ring R with at least two elements is called a field
- if it has following properties :
- R is commutative
- R has unity
- R is such that each non-zero element possesses multiplicative inverse
- Ex: (R, +, *), and (Q, +, *) are fields
Order of Group
- it refers to the number of elements in the group.
- It represents the size or cardinality of the group.
- For Ex: Z4={0,1,2,3} with order 4.
Cyclic Group
- A cyclic group is a group that is generated by a single element, often denoted <g>.
- where g is called a generator.
- The group consists of all powers of g, including positive and negative powers.
Question:
Prove that every cyclic group is an abelian group
Let G be a cyclic group and let a be a generator of G so that G = {a n : n ∈ Z} If g1 and g2 are any two elements of G, there
exist integers r and s such that g1 = a^r
and g2 = a^s>
Then g1 g2 = a^r a s = a^(r+s) = a^(s+r) = a^s . a^r = g2 g1 So, G is abelian.
Subgroup
- If (G, *) is a group and H ⊆ G. Then (H, *) is said to subgroup of G if (H, *) is also a group by itself. i.e.,
1. a * b ∈ H ∀ a, b ∈ H (Closure property)
2. ∃ e ∈ H such that a * e = a = e * a ∀ a ∈ H where e is called identity of G.
3. ∃ a^(-1) ∈ H such that a * a^(–1) = e = a^(–1) * a ∀ a ∈ H
Permutation Group
- A permutation group G on a non-empty set A under the binary operation ∗.
- If A={1,2,3,…,n}, then the permutation group formed by A is called the symmetric group of degree n, denoted by Sn.
- Number of Elements in Symmetric Group:
- The number of elements in Sn is n!
Cyclic Permutation
- Cyclic permutation cyclically rearranges elements in a fixed sequence, typically returning to the initial element after a certain number of steps
- For example : Consider A = {a, b, c, d, e}. Then P =[ a b c d e ]
[ c b d a e ].
then P has a cycle of length 3 given by (a, c, d).
Cosets
- Let H be a subgroup of group G and let a∈G then
- set Ha = {ha : h ∈ H} is called right coset generated by H and a.
- Also the set aH = {ah : h ∈ H} is called left coset generated by a and H
Question:
Find the left cosets of {[0], [3]} in the group (Z6 , +6 ).
Let Z6 = {[0], [1], [2], [3], [4], [5]} be a group.
H = {[0], [3]} be a subgroup of (Z6 , +6 ).
The left cosets of H are,
[0] + H = {[0], [3]} [1] + H = {[1], [4]}
[2] + H = {[2], [5]} [3] + H = {[3], [0]}
[4] + H = {[4], [1]} [5] + H = {[5], [2]}
Normal Subgroup
- A subgroup H of group G is a normal subgroup if aH=Ha for all a in G, indicating that left and right cosets of H generated by a are identical.
- Property:
1. every subgroup H of an abelian group G is a normal subgroup of G. For a ∈ G and h ∈ H, ah = ha.
2. Since a cyclic group is abelian, every subgroup of a cyclic group is normal.
No comments:
Post a Comment