CIC-205 Discrete Mathematics

Unit -3

CIC-205 Discrete Structures

1

Algebraic Structures

CIC-205 Discrete Structures

2

N = {1,2,3,4,…..∝ } = Set of all natural numbers.

Z = { 0, ± 1, ± 2, ± 3, ± 4 , ….. ∝} = Set of all integers.

Q = Set of all rational numbers.

R = Set of all real numbers.

​

Binary Operation: The binary operator * is said to be a binary operation (closed operation) on a non empty set A, if a * b ∈ A for all a, b ∈ A (Closure property).

​

Algebraic System: A set ‘A’ with one or more binary (closed) operations defined on it is called an algebraic system.

​

Ex: (N, + ), (Z, +, – ), (R, +, . , – ) are algebraic systems.

Properties

CIC-205 Discrete Structures

3

• Commutative: Let * be a binary operation on a set A.

The operation * is said to be commutative in A if

a * b= b * a for all a, b in A

• Associativity: Let * be a binary operation on a set A. The operation * is said to be associative in A if

(a * b) * c = a *( b * c) for all a, b, c in A

• Identity: For an algebraic system (A, *), an element ‘e’ in A is said to be an identity element of A if

a * e = e * a = a for all a ∈ A.

• Note: For an algebraic system (A, *), the identity element, if exists, is unique.
• Inverse: Let (A, *) be an algebraic system with identity ‘e’. Let a be

an element in A. An element b is said to be inverse of A if

a * b = b * a = e

Semi group

CIC-205 Discrete Structures

4

• Semi Group: An algebraic system (A, *) is said to be a semi group if
1. * is closed operation on A.
2. * is an associative operation, for all a, b, c in A.

Ex. (N, +) is a semi group.

Ex. (N, .) is a semi group.

Ex. (N, – ) is not a semi group.

​

• Monoid: An algebraic system (A, *) is said to be a monoid if the following conditions are satisfied.
• * is a closed operation in A.
• * is an associative operation in A.
• There is an identity in A.

Group

CIC-205 Discrete Structures

5

• Group: An algebraic system (G, *) is said to be a group if the following conditions are satisfied.
1. * is a closed operation.
2. * is an associative operation.
3. There is an identity in G.
4. Every element in G has inverse in G.

​

• Abelian group (Commutative group): A group (G, *) is said to be abelian (or commutative) if

a * b = b * a .

Theorem

CIC-205 Discrete Structures

6

• In a Group (G, * ) the following properties hold good
• Identity element is unique.
• Inverse of an element is unique.
• Cancellation laws hold good

a * b = a * c ⇒ b = c

a * c = b * c ⇒ a = b

(left cancellation law)

(Right cancellation law)

(a * b) ^-1 =

_b-1 _{* a}-1

​

• In a group, the identity element is its own inverse.

​

• Order of a group : The number of elements in a group is called order of the group.

​

• Finite group: If the order of a group G is finite, then G is called a finite group.

CIC-205 Discrete Structures

7

Example: Show that set of all non zero real numbers is a group with respect to multiplication

Solution: Let R^* = set of all non zero real numbers. Let a, b, c are any three elements of R^* .

1. Closure property : We know that, product of two nonzero real

numbers is again a nonzero real number .

i.e.,a . b ∈ R^* for all a,b ∈ R^* .

2. Associativity: We know that multiplication of real numbers is associative.

i.e., (a.b).c = a.(b.c) for all a,b,c ∈ R^* .

3. Identity : We have 1 ∈ R^* and a .1 = a for all a ∈ R^* .

∴ Identity element exists, and ‘1’ is the identity element.

4. Inverse: To each a ∈ R^* , we have 1/a ∈ R^* such that

a .(1/a) = 1 i.e., Each element in R^* has an inverse.

CIC-205 Discrete Structures

8

5Commutativity: We know that multiplication of real numbers is

commutative.

i.e., a . b = b . a for all a,b ∈ R^*. Hence, ( R^* , . ) is an abelian group.

​

Example : Show that set of all real numbers ‘R’ is not a group with respect to multiplication.

Solution: We have 0 ∈ R .

The multiplicative inverse of 0 does not exist. Hence, R is not a group.

CIC-205 Discrete Structures

9

Multiplicative Group

Additive Group

�Notation and Terminology��In general , we shall use “e” to denote the identity element of a group

Subgroups

Subgroups

Definition:

If G is a group, then the order |G| of G is the number of elements in G.

​

Definition:

If a subset H of a group G is closed under the binary operation of G and if H with the induced operation from G is itself a group, then H is a subgroup of G.

​

We shall let H ≤ G denote that H is a subgroup of G, and H < G denote H≤G but H ≠ G.

​

Note : Every group G has G and {e} as its subgroups.

​

​

​

CIC-205 Discrete Structures

10

Examples

Definition:

If G is a group, then the subgroups consisting of G itself is the improper subgroup of G. All other subgroups are proper subgroups.

​

The subgroup {e} is the trivial subgroup of G. All other subgroups are nontrivial.

​

Example:

• 〈 Z, + 〉< 〈 R, + 〉 but 〈 Q⁺, ⋅ 〉 is not a subgroup of 〈 R, + 〉.
• 〈 Q⁺, ⋅ 〉< 〈 R⁺, ⋅ 〉

​

CIC-205 Discrete Structures

11

Group Z_n

When a=qn+r, where q is the quotient and r is the remainder upon

dividing a by n, we write

a mod n = r .

Example: 12 mod 4 = 0,

3 mod 4 = 3 etc.

​

The set Z_n={0, 1, …, n-1} for n ≥1 is a group under addition modulo n. This group is referred as the group of integers modulo n.

​

Example: Z₄={0, 1, 2, 3} under addition modulo 4

+ 0 1 2 3

0 0 1 2 3

1 1 2 3 0

2 2 3 0 1

3 3 0 1 2

​

CIC-205 Discrete Structures

12

Klein 4-group

The set V={e, a, b, c} under the following operation is a group. We call it the Klein 4-group.

​

e a b c

e e a b c

a a e c b

b b c e a

c c b a e

​

CIC-205 Discrete Structures

13

Subgroup Diagrams of Z₄ and V

• The only nontrivial proper subgroup of Z₄ is {0, 2}.

Here {0, 3} is not a subgroup since it’s not closed under +.

​

• However, the group V has three nontrivial proper subgroups:

{e, a}, {e, b} and {e, c}. Here {e, a, b} is not a subgroup since it’s not closed under the operation of V.

​

Z₄ V

​

​

{0, 2} {e, a} {e, b} {e, c}

​

{0} {e}

CIC-205 Discrete Structures

14

Theorem

A subset H of a group G is a subgroup of G if and only if

• H is closed under the binary operation of G,
• The identity element e of G is in H,
• For all a ∈ H it is true that a⁻¹ ∈ H also.

CIC-205 Discrete Structures

15

Cyclic Subgroups

Theorem: Let G be a group and let a ∈ G. Then H={ aⁿ | n ∈ Z} is a subgroup of G and is the smallest subgroup G that contains a, that is, every subgroup containing a contains H.

​

Proof: We check the three conditions

​

1. Since a^r a^s=a^r+s for r, s ∈ Z, we see that H is closed under the group operation of G.
2. Also a⁰=e, so e ∈H,
3. for a^r ∈ H, a^-r ∈ H and a^r a^-r =e.

Hence H ≤G.

Since every subgroup of G containing a must contain all element aⁿ for all n ∈ Z, H is the smallest subgroup of G containing a.

​

CIC-205 Discrete Structures

16

Generator

Definition: Let G be a group and let a ∈ G. Then the subgroup { aⁿ | n ∈ Z} of G, characterized in Theorem 5.17, is called the cyclic subgroup of G generated by a, and denoted by 〈 a 〉.

​

An element a of a group G generates G and is a generator for G if 〈 a 〉=G.

A group is cyclic if there is some element a in G that generates G.

​

Example:

• Z₄ is cyclic and 〈 1 〉= 〈 3 〉= Z₄
• V is not cyclic since 〈 a 〉, 〈 b 〉, 〈 c 〉 are subgroups of two elements, and

〈 e 〉 is the trivial subgroup of one element.

CIC-205 Discrete Structures

17

Examples

• 〈 Z, + 〉 is a cyclic group:

〈 1 〉 =〈 -1 〉 =Z, and no other generators

​

• For n ∈ Z⁺, Z_n under addition modulo n is cyclic.

If n>1, then 〈 1 〉 = 〈 n-1 〉 = Z_n, there may be others.

​

• nZ= 〈 n 〉 is a cyclic subgroup generated by n consists of all multiples of n, positive, negative, and zero.

Note that 6Z < 3Z.

​

CIC-205 Discrete Structures

18

Cyclic Groups

Recall: If G is a group and a∈G, then H={aⁿ|n ∈Z} is a subgroup of G. This group is the cyclic subgroup 〈a〉 of G generated by a.

​

Also, given a group G and an element a in G, if G ={aⁿ|n ∈Z} , then a is a generator of G and the group G= 〈a〉 is cyclic

​

Let a be an element of a group G. If the cyclic subgroup 〈a〉 is finite, then the order of a is the order | 〈a〉 | of this cyclic subgroup. Otherwise, we say that a is of infinite order.

CIC-205 Discrete Structures

19

Elementary Properties of Cyclic Groups

Theorem : Every cyclic group is abelian.

​

Proof: Let G be a cyclic group and let a be a generator of G so that

G = 〈a〉 ={aⁿ|n ∈Z}.

If g₁ and g₂ are any two elements of G, there exists integers r and s such that g₁=a^r and g₂=a^s. Then

g₁g₂= a^ra^s = a^r+s = a^s+r = a^sa^r = g₂g₁,

So, G is abelian.

CIC-205 Discrete Structures

20

Division Algorithm for Z

Division Algorithm for Z

​

If m is a positive integer and n is any integer, then there exist unique integers q and r such that

n = m q + r and 0 ≤ r < m

​

Here we regard q as the quotient and r as the nonnegative remainder when n is divided by m.

​

Example: Find the quotient q and remainder r when 38 is divided by 7.

Solution: q=5, r=3

​

CIC-205 Discrete Structures

21

CIC-205 Discrete Structures

22

We are going to generalize the idea of congruent classes mod n in (Z,+).

Theorem. Let H is a subgroup of G. Define a relation: a~b iff a ♦ b^-1 ∈ H. Then ~ is an equivalence relation.

​

Cosets

a = b (mod n) iff a - b ∈ <n>

CIC-205 Discrete Structures

23

Theorem. Let H is a subgroup of G. Define a relation: a~b iff a ♦ b^-1 ∈ H.

Then ~ is an equivalence relation.

​

Proof.

Reflexive: a~a iff a ♦ a^-1 =e ∈ H

Cosets

Transitive: a ♦ c^-1=(a ♦ b^-1)(b ♦ c^-1) ∈ H

Symmetric: b ♦ a^-1=(a ♦ b^-1)^-1 ∈ H

CIC-205 Discrete Structures

24

​

The equivalent classes for this relation is called the right cosets of H in G.

Cosets

If H is a subgroup of a group G then for any element g of the group the set of products

of the form h ♦ g where h∈H is a right coset of H denoted by the symbol Hg.

CIC-205 Discrete Structures

25

Example: Write down the right coset of the subgroup {0,3,6,9} of Z₁₂ under +.

Cosets

Right coset = {h g | h ∈ H, g ∈ G}

{0,3,6,9} + {0,1,2,3,4,5,6,7,8,9,10,11} =

​

[3]+0 = {0,3,6,9}

[3]+1 = {1,4,7,10}

[3]+2 = {2,5,8,11}

CIC-205 Discrete Structures

26

Theorem. If H is a finite subgroup of G and x∈G, then |H|=|Hx|

Cosets

Proof. We prove this by finding a bijection between H and Hx.

It is onto, because Hx consists of the elements of the form hx, where h∈H.

Assume that there are h₁, h₂∈H. .

Then h₁x= h₂x. It follows, h₁=h₂.

CIC-205 Discrete Structures

27

Theorem. If H is a finite subgroup of G, then G = ⋃_x∈G Hx.

Cosets: partitioning

Proof. Cosets are equivalent classes. The two cosets are either equal or disjoint.

Since G is finite, there are finitely many such cosets.

Every element x of G belongs to the coset determined by it.

x = x e ∈ Hx, since e∈H.

Lagrange’s Theorem

Theorem:

​

• If G is a finite group, and H is a subgroup then the order of H divides the order of G.

​

• In symbols, |H| divides |G|.

​

CIC-205 Discrete Structures

28

Lagrange’s Theorem

Theorem: |H| divides |G|.

​

CIC-205 Discrete Structures

29

Proof: G is partitioning into cosets.

Pick a representative from each coset

G = ⋃_j=1…k Hx_j

​

Each coset contains |H| elements.

It follows |G| = k |H|. Thus |H| is a divisor of |G|.

Lagrange’s Theorem: what is for?

• The theorem simplifies the problem of finding all subgroups of a finite group.

​

CIC-205 Discrete Structures

30

Consider group of symmetry of square

​

Except {R₀} and Y_sq, all other subgroups must have order 2 or 4.

​

CIC-205 Discrete Structures

31

R₉₀

R₁₈₀

R₂₇₀

R₀

F_|

F_—

R₀

R₉₀

R₁₈₀

R₂₇₀

F_|

F_—

R₀

R₉₀

R₁₈₀

R₂₇₀

F_|

F_—

R₉₀

R₁₈₀

R₂₇₀

F_|

F_—

R₁₈₀

R₂₇₀

R₀

R₂₇₀

R₀

R₉₀

R₀

R₉₀

R₁₈₀

F_|

F_—

F_—

F_|

F_—

F_|

F_—

F_|

F_—

F_|

F_|

F_—

R₀

R₀

R₀

R₀

R₁₈₀

R₉₀

R₂₇₀

R₁₈₀

R₂₇₀

R₉₀

R₂₇₀

R₉₀

R₁₈₀

R₉₀

R₂₇₀

R₁₈₀

Order 2

CIC-205 Discrete Structures

32

R₉₀

R₁₈₀

R₂₇₀

R₀

F_|

F_—

R₀

R₉₀

R₁₈₀

R₂₇₀

F_|

F_—

R₀

R₉₀

R₁₈₀

R₂₇₀

F_|

F_—

R₉₀

R₁₈₀

R₂₇₀

F_|

F_—

R₁₈₀

R₂₇₀

R₀

R₂₇₀

R₀

R₉₀

R₀

R₉₀

R₁₈₀

F_|

F_—

F_—

F_|

F_—

F_|

F_—

F_|

F_—

F_|

F_|

F_—

R₀

R₀

R₀

R₀

R₁₈₀

R₉₀

R₂₇₀

R₁₈₀

R₂₇₀

R₉₀

R₂₇₀

R₉₀

R₁₈₀

R₉₀

R₂₇₀

R₁₈₀

Order 4

Lagrange’s Theorem

Example.

• Suppose that H and K are subgroups of G and assume that

|H| = 9, |K| = 6, |G| < 50.

​

• What are the possible values of |G|?

​

CIC-205 Discrete Structures

33

LCM(9,6) = 18, so |G|=18 or 36

​

Isomorphism

CIC-205 Discrete Structures

34

Mapping between objects, which shows that they are structurally identical.

Any property which is preserved by an isomorphism and which is true for one of the objects, is also true of the other.

Isomorphism

CIC-205 Discrete Structures

35

Example.

{1,2,3,…}, or {I, II, III,…}, or

{один, два, три,…}

Mathematically we want to think about

these sets as being the same.

Group Isomorphism

CIC-205 Discrete Structures

36

Definition. Let G be a group with operation * and H with ♦.

An isomorphism of G to H is a bijection

f: G•H that satisfies

f(x * y) = f(x) ♦ f(y)

If we replace bijection by injection, such mapping is called a homomorphism.

Group Isomorphism

CIC-205 Discrete Structures

37

Example.

G = (Z, +), H = (even, +)

Isomorphism is provided by f(n) = 2 n

f(n + m) = 2 (n+m) = (2n)+(2m)=f(n)+f(m)

Group Isomorphism

CIC-205 Discrete Structures

38

Theorem. Let G be a group with operation *, H with ♦ and they are isomorphic f(x * y) = f(x) ♦ f(y). Then

f(e_G) = e_H

Proof. f(e_G)= f(e_G * e_G) = f(e_G) ♦ f(e_G).

On the other hand, f(e_G)=f(e_G) ♦ e_H

f(e_G) ♦ e_H = f(e_G) ♦ f(e_G) • f(e_G) = e_H

Group Isomorphism

CIC-205 Discrete Structures

39

Theorem. Let G be a group with operation *, H with ♦ and they are isomorphic f(x * y) = f(x) ♦ f(y). Then

f(x^-1) = f(x)^-1, x∈G

Proof.

f(x) ♦ f(x^-1) = f(x * x^-1) =f(e_G) = e_H.

CIC-205 Discrete Structures

40

In order to prove that two groups and are not isomorphic, one needs to demonstrate that there is no isomorphism from onto .

Usually, in practice, this is accomplished by finding some property that holds in one group, but not in the other.

Examples. (Z₄, +) and (Z₆, +)

They have different orders_.

CIC-205 Discrete Structures

41

Exercise.

Verify that (Z₄, +) is isomorphic to (Z*₅, _*)

Permutation Groups

CIC-205 Discrete Structures

42

If the set is given by A = {1, 2, 3, . . . , n} then let S_n denote the set of all permutations on A.

It forms a group under function composition.

We call Sn the symmetric group of degree n and call any subgroup of Sn a permutation group.

An element of Sn is represented by

Permutation Groups

CIC-205 Discrete Structures

43

Cayley’s Theorem. Every group is isomorphic to a permutation group.

Sketch of proof. Let G be a group with operation *. For each x∈G, we define

λ_x:G •G given by λ_x(g) = x * g for all g∈G.

This function λ_x is a permutation on G.

Next we create a permutation group out of λ_x.

Now we define f: G •S_n by f(x)= λ_x

CIC-205 Discrete Structures

44

Cayley’s Theorem. Every group is isomorphic to a permutation group.

We define f: G •S_n by f(x)= λ_x

One-to-one. Suppose f(a)=f(b). It follows

λ_a= λ_b and in particular λ_a(e)= λ_b(e).

Thus, a e = b e and then a = b.

Onto. It follows from definition of λ_x

Homomorphism. f(a b) = λ_ab, f(a)♦f(b)= λ_a♦λ_a

To prove λ_ab= λ_a♦λ_a , we write

λ_ab(x)=(ab)x=a (bx)=λ_a(bx)=λ_a(λ_b(x))=(λ_a♦λ_b)(x)