PARTIAL ORDER RELATION
Partial order relation: On a set G, a binary
relation R is a partial order relation if R is reflexive, antisymmetric and
transitive.
reflexive

xRx

antisymmetric

xRy implies yRx

transitive

xRy and yRz implies xRz

POSET
Partial Order Set (Poset): A set on which
partial ordering relation is defined is known as poset.
HASSE DIAGRAM
Hasse Diagram: Hasse diagram generally used to represent
partial order relations in equivalent but in simpler forms by removing non
critical parts of the relation.
For example:
Below diagram represent a partial order relation.
This can relation can be modify as
 Remove all loops.
 Remove all arrows that can be
inferred from transitivity.
Than above diagram represented as
Above diagram is known as Hasse diagram for a
partial order relation.
LOWER AND UPPER BOUNDS
Upper
Bound: Let A ⊆ S, then an element s ∈ S is called upper bound of A if and only if
a ≤
s, ∀ a ∈ A.
Lower
Bound: Let A ⊆ S, then an element s ∈ S is called the lower bound
of A is and only if
s
≤
a, ∀ a ∈ A.
Least Upper Bound: If A ⊆ S and g ∈ S, then g is called the
least upper bound of A if and only if the following two conditions hold
a)
g is upper bound of the set A.
b)
g ≤ s for every upper
bound s of A.
The least upper bound of A is
denoted by l.u.b.A or supA.
Greatest Lower Bound: If A ⊆ S and l ∈ S, then l is called the greatest
lower bound of A if and only if the following two conditions hold
a)
l is lower bound of the set A.
b)
s ≤ l, for every lower
bound s of A.
The greatest upper bound of
A is denoted by g.l.b.a. or infA.
LATTICE
Infimum: Infimum is also known as greatest lower
bound.
Supremum: Spremum is also known as least upper bound.
LATTICE: A lattice is a poset (P, ≤)
in which every pair of elements has a supremum and an infimum.
Given a, b ∈ P, we write these bounds as
a Î›
b = inf ({a, b})
a
V
b = sup({a, b})
Problems based on above study:
Prob. What is Hasse diagram? Draw
the Hasse diagram of the set D_{30 }of positive integral divisor of 30
with relation ‘1’.
Prob. Let A = ( a, b, c, d} and
P(A) its power set. Draw Hasse diagram of [P(A), ⊆].
Solution. Click here.
Solution. Click here.
Prob. Let A = {2, 3, 6, 12, 24,
36} and the relation ≤ be such that a ≤ b, if a
divides b. Draw the Hasse diagram of (A ≤).
Solution. Click here.
Solution. Click here.
Prob. Let L be the set of all factors of 12 and ‘\’ be the divisibility relation on L. Show that (L, ‘\’) is a lattice.
Solution. Click here.
Solution. Click here.
Prob. Let L = {1, 2, 3, 4, 6, 8, 9, 12, 18, 24} be ordered by the notation ‘\’ where x/y mean ‘x divides y’. Show that D_{24} the set of all divisors of the integer 24 of L is a sublattice of the lattice (L, \ ).
Solution. Click here.
Solution. Click here.
Prob. If B=Divisors of 24 = (D24) be a lattice then find all the sublattices of D(24). Also draw the Hasse diagram.
Solution. Click here.
Solution. Click here.
Related notes:
 SET
 Mathematical Induction
 Relation
 Binary operations
 Algebraic struture
 Group
 Numerical problems on GROUP
 Subgroup
 Abelian Group or Commutative group
 Coset
 Factor or Quotient group
 Cyclic group
 Ring
 Numerical problems on RING
 Field
 POSET, Hasse diagram,Upper and Lower Bounds
 Hasse diagram
 Upper and Lower Bounds
 Lattice
 Recurrence relation numerical problems
 How to solve generating function
A list of Video lectures
Post a Comment
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.