Discrete Mathematics Group Theory - Discrete Mathematics

What is a Semigroup in Discrete Mathematics?

Semigroup is formulated by a finite or infinite set ‘S’ with the composition of a binary operation ‘o’. This composition is said to be semigroup if the following two conditions are satisfied to be true:

  • Closure − For every pair (a,b)∈S,(aοb) has to be present in the set S.
  • Associative − For every element a,b,c∈S,(aοb)οc=aο(bοc) must hold.

Example

For instance, the set o positive integers, apart from zero, with a binary operation of addition is said to be a semigroup. Say, S={1,2,3,…}.

For every pair, (a,b)∈S,(a+b) is present in the set S, and hence this holds true the closure property.

For example, 1+2=3∈S]

For every element a,b,c∈S,(a+b)+c=a+(b+c), hence holds true the associative proterty.

For example, (1+2)+3=1+(2+3)=5

What is Monoid in Discrete Mathematics?

The semigroup with an identity element is known as a Monoid. This identity element which is either denoted by E or e of a set S is also an element, such that (aοe)=a for every element of a∈S. The identity element may also be called as unit element.

Three properties such as Closure, Associative and the property of Identity elements holds by an monoid.

Example

The set of positive integers (excluding zero) with multiplication operation is a monoid. S={1,2,3,…}

For every pair (a,b)∈S,(a×b) is present in set S and hence holds true the closure property.

For example, 1×2=2∈S.

For every element a,b,c∈S,(a×b)×c=a×(b×c) holds true the associative property.

For example, (1×2)×3=1×(2×3)=6.

For every element a∈S,(a×e)=a, identity property also holds true.

For example, (2×1)=2,(3×1)=3. Here 1 is the identity element.

What is a Group in Discrete Mathematics?

A monoid with inverse element is known as a group. The inverse element I, is the element of the set S such that (aοI)=(Iοa)=a, for each of the element a∈S. It can be said that four properties can be hold by the group – Closure, Associative, Identity and Inverse. The number of elements in the group G is represented by the order of the group G.

Examples

Under the operation of matrix multiplication, the set of N×N non-singular matrices form a group.

Closure property holds true as the product of two N×N non-singular matrices is also an N×N non-singular matrix, thus holding true the associative property.

The set of N×N non-singular matrices contains the identity matrix holding the identity element property.

As all the matrices are non-singular they all have inverse elements which are also nonsingular matrices. Hence, inverse property also holds.

What is an Abelian Group in Discrete Mathematics?

A group for which the element pair (a,b)∈G always holds commutative is known as abelian group G, thus holding true five properties – Closure, associative, identity, inverse and commutative.

Example

The set of positive integers (including zero) with addition operation is an abelian group. G={0,1,2,3,…}

Here closure property holds as for every pair (a,b)∈S,(a+b) is present in the set S.

For example, 1+2=2∈S and so on

Associative property also holds for every element a,b,c∈S,(a+b)+c=a+(b+c)

For example, (1+2)+3=1+(2+3)=6

Identity property also holds for every element a∈S,(a×e)=a

For example, (2×1)=2,(3×1)=3. Here, identity element is 1.

Commutative property also holds for every element a∈S,(a×b)=(b×a)

For example, (2×3)=(3×2)=3

What is a Cyclic Group and Subgroup in Discrete Mathematics?

A group that is generated by using a single element is known as cyclic group. Cyclic group is considered as the power for some of the specific element of the group which is known as a generator. The generator ‘g’ helps in generating a cyclic group such that the other element of the group is written as power of the generator ‘g’.

Example

The set of complex numbers {1,−1,i,−i} under multiplication operation is a cyclic group.

There are two generators − i and –i as i1=i,i2=−1,i3=−i,i4=1 and also (–i)1=−i,(–i)2=−1,(–i)3=i,(–i)4=1 such that it covers all the elements of the group thus forming a cyclic group.

Note – Every cyclic group is an abelian group but not every abelian group is a cyclic group.

If the four properties (Closure, associative, identity and Inverse) are simultaneously satisfied by the subgroup H then it will be a subset of the group G, represented as H≤G.

A subgroup H of a group G that does not include the whole group G is called a proper subgroup (Denoted by H<G). A subgroup of a cyclic group is cyclic and a abelian subgroup is also abelian.

Example

Let a group G={1,i,−1,−i}

Then some subgroups are H1={1},H2={1,−1}

This is not a subgroup − H3={1,i} because that (i)−1=−i is not in H3

What is Partially Ordered Set (POSET) in Discrete Mathematics?

An ordered set which has a binary relation that is transitive, reflexive and antisymmetric is a partially ordered set which is represented as POSET.

Examples

  • The set of real numbers under binary operation less than or equal to (≤) is a poset.

set S={1,2,3} and the operation is ≤

The relations will be {(1,1),(2,2),(3,3),(1,2),(1,3),(2,3)}

This relation R is reflexive as {(1,1),(2,2),(3,3)}∈R

This relation R is anti-symmetric, as

{(1,2),(1,3),(2,3)}∈R and {(1,2),(1,3),(2,3)}∉R

This relation R is also transitive as {(1,2),(2,3),(1,3)}∈R.

Hence, it is a poset.

What is a Hasse Diagram in Discrete Mathematics?

A graph whose vertices represent the elements of the poset and the arcs covering the pairs (x, y) in the poset is known as a Hasse Diagram. In Hasse diagram, the point x appears lower than the point y if x<y in poset.

Example

The poset of subsets of {1,2,3}={∅,{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}} which is represented by the Hasse diagram as depicted below−

Hasse Diagram

What is a Linearly Ordered Set?

A partial order set in which every pair of element is comparable is known as linearly ordered set or total ordered set. If the condition a≤b and b≤a holds true, then the elements a,b∈S are said to be comparable.

Example

The powerset of {a,b} ordered by \subseteq is a totally ordered set as all the elements of the power set P={∅,{a},{b},{a,b}} are comparable.

Example of non-total order set

A set S={1,2,3,4,5,6} under operation x divides y is not a total ordered set.

For all (x,y)∈S,x|y have to hold but it is not true that 2 | 3, as 2 does not divide 3 or 3 does not divide 2. Hence, it is not a total ordered set.

What is a Lattice in Discrete Mathematics?

A poset for which every pair {a,b}∈L has a least upper bound (denoted by a∨b) and a greatest lower bound (denoted by a∧b). GLB ({a,b}) is called the meet of a and b.

Lattice

Example

Lattice Example

The figure above is lattice as for every pair {a,b}∈L a LUB and GLB exists.

Lattice Example 2

For the above figure, GLB(a,b) and LUB(e,f) does not exist and hence it is not a lattice.

Few other lattices are as follows:

Bounded Lattice

The lattice with the greatest element 1 and least element 0 is known as Bounded Lattice.

Complemented Lattice

A bounded lattice with every element having a complement is known as a Complemented Lattice. An element x has a complement x’ if ∃x(x∧x′=0andx∨x′=1)

Distributive Lattice

A lattice is a distributive lattice, if the following distribute properties are satisfied:

  • a∨(b∧c)=(a∨b)∧(a∨c)
  • a∧(b∨c)=(a∧b)∨(a∧c)

Modular Lattice

A lattice is modular lattice, if the following property is satisfied:

a∧(b∨(a∧d))=(a∧b)∨(a∧d)

What are the different properties of Lattices?

The following are the properties of lattices:

Idempotent Properties

  • a∨a=a
  • a∧a=a

Absorption Properties

  • a∨(a∧b)=a
  • a∧(a∨b)=a

Commutative Properties

  • a∨b=b∨a
  • a∧b=b∧a

Associative Properties

  • a∨(b∨c)=(a∨b)∨c
  • a∧(b∧c)=(a∧b)∧c

What is dual of a Lattice?

The interchanging of '∨' and '∧' operations leads to dual of a lattice.

Example

The dual of [a∨(b∧c)] is [a∧(b∨c)]

All rights reserved © 2018 Wisdom IT Services India Pvt. Ltd DMCA.com Protection Status

Discrete Mathematics Topics