Maximal and minimal elements of poset.pptx

Discreet Mathematics

1. Maximal and Minimal of a Poset Name: Kiran Kumar Malik Registration no: 200301120128 Branch: B-Tech in Computer Science and Engineering's Section: D Semester: 1 st Sem Campus: Bhubaneswar Guided by: Dr. Padala Hari Krishna

2. Maximal and Minimal elements of a poset An element of a poset is called maximal if it is not less then any element of the poset. That is, a is maximal in the poset (S, ≼) if there is no b ∈ S such that a ≺ b. Similarly, an element of a poset is called minimal if it is not grater than any element of the poset. That is, a is minimal if there is no element b ∈ S such that b ≺ a. Maximal and minimal elements are easy to spot using a Hasse diagram. They are the “ top ” and “ bottom ” elements in the diagram Note: (i). The minimal and maximal members of a partially ordered set need not unique. (ii). Maximal and minimal elements are easily spot (calculated) from the Hasse diagram. They are the ‘top( maximal) and 'bottom' (minimal ) elements in the diagram.

3. Example 1: Which elements of the poset ({2,4,5,10,12,20,25}, |) are maximal, and which are minimal? The Hasse diagram in figure 1 for this poset shows that the maximal elements are 12 , 20 , and 25 , and the minimal elements are 2 and 5 . As this example shows, a poset can have more than one maximal elements and more than one minimal element. 12 4 2 20 10 5 25 Figure 1: The Hasse Diagram of a poset. Solution:

4. Example: Let A= {a, b, c, d, e, f, g, h, i} have the partial ordering ≼ defined by following Hasse diagram. Find all maximal, minimal, greatest and least elements of A. Solution: There is just one maximal element g , which is also the greatest element. The minimal elements are c , d and i , and there is no least element. a c b g f e h i d

5. Question: Answer these questions for the poset ({2, 4, 6, 9, 12, 18, 27, 36, 48, 60, 72}, |). a) Find the maximal elements. b) Find the minimal elements. c) Is there a greatest element? d) Is there a least element? Solution: Given: ({2, 4, 6, 9, 12, 18, 27, 36, 48, 60, 72}, |) S = {2, 4, 6, 9, 12, 18, 27, 36, 48, 60, 72} R = {(a,b) | a divides b} Let us first determine the Hasse diagram 48 60 12 2 4 6 36 72 18 9 27 a) The Maximal elements are all the values in Hasse diagram that do not have any elements above it. Maximal elements = 27 , 48 , 60 , 72 b) The Minimal elements are all the values in Hasse diagram that do not have any elements below it. Minimal elements = 2 , 9 c) The greatest element only exist if there is exactly one maximal element and is then also equal to the maximal element. Greatest element = Does not exist d) The least element only exist if there is exactly one minimal element and is then also equal to the minimal element. Least element = Does not exist

6. Answer these questions for the poset ({3, 5, 9, 15, 24, 45}, |). a) Find the maximal elements. b) Find the minimal elements. c) Is there a greatest element? d) Is there a least element? Solution: Given: ({3, 5, 9, 15, 24, 45}, |) S = {3, 5, 9, 15, 24, 45} R = {(a,b) | a divides b} Let us first determine the Hasse diagram 45 9 3 15 24 5 a) The Maximal elements are all the values in Hasse diagram that do not have any elements above it. Maximal elements = 24, 45 b) The Minimal elements are all the values in Hasse diagram that do not have any elements below it. Minimal elements = 3 , 5 c) The greatest element only exist if there is exactly one maximal element and is then also equal to the maximal element. Greatest element = Does not exist d) The least element only exist if there is exactly one minimal element and is then also equal to the minimal element. Least element = Does not exist

7. Thank You Sir Submitted by Kiran Kumar Malik [email protected]