4.4: Partially Ordered Sets
- Page ID
- 88863
Terminology
Poset.
A relation is an partially ordered set (poset) if and only if the relation is reflexive, anti-symmetric, and transitive.
Consider the following poset defined by listing the relations explicitly.
\(R=\{(a,a), \) \((a,d), \) \((a,f), \) \((a,g), \) \((a,h),\) \((b,b), \) \((b,d), \) \((b,e), \) \((b,f), \) \((b,g), \) \((b,h),\) \((c,c), \) \((c,d), \) \((c,f), \) \((c,g), \) \((c,h),\) \((d,d), \) \((d,f), \) \((d,g), \) \((d,h),\) \((e,e), \) \((e,g), \) \((e,h),\) \((f,f), \) \((g,g), \) \((h,h) \}.\)
Another way to define the elements of the relation is a Hasse diagram. Figure \(\PageIndex{2}\) shows the Hasse diagram for \(R.\) The rules for constructing these diagrams are in List \(\PageIndex{3}\).
List \(\PageIndex{3}\) Constructing a Hasse Diagram
- If \((a,b) \in R\) then \(a\) is below \(b\) on the diagram.
- If \((a,b) \in R\) then there is a line from \(a\) to \(b\)
- unless \(a=b\) (reflexive), or
- unless \((a,c), (c,b) \in R\) (transitive set).
Note that constructing a Hasse diagram requires sorting the elements of the set. Each level of the diagram in some sense is “before” the levels above it. Because of this ordering in posets we write \(a \preceq b\) to mean \(aRb\text{.}\)
Practice
Checkpoint \(\PageIndex{4}\)
Determine whether the following relation is a poset. Let the relation \(R\) on the set of numbers \(\{1,2,3,6\}\) be defined by \(aRb\) if and only if \(a|b.\)
Checkpoint \(\PageIndex{5}\)
Determine whether the following relation is a poset. Let the relation \(R\) on the set of numbers \(\{1,2,3,5,6,10,15,30\}\) be defined by \(aRb\) if and only if \(a|b.\)
Checkpoint \(\PageIndex{6}\)
Determine whether the following relation is a poset. Let the relation \(R\) on the set of positive integers be defined by \(aRb\) if and only if \(a|b.\)
Checkpoint \(\PageIndex{7}\)
Determine whether the following relation is a poset. Let the relation \(R\) on the set of real numbers be defined by \(aRb\) if and only if \(a \le b.\)
Checkpoint \(\PageIndex{8}\)
Determine whether the following relation is a poset. Consider the set \(P(X)\) for the set \(X=\{a,b,c\}.\) Let the relation \(R\) be defined by \(A\) is related to \(B\) if and only if \(A \subseteq B\text{.}\)
Checkpoint \(\PageIndex{9}\)
Draw the Hasse diagrams for the following posets.
- \(\subseteq\) on \(P(\{0,1\}).\) Note it may help to list all the elements first.
- \(|\) (i.e., \(aRb\) iff \(a|b\)) on \(\{1,2,3,6\}.\)
- \(|\) on \(\{1,2,3,5,6,10,15,30\}.\)
- \(X=\{ \)(0,0,0), (1,0,0), (0,1,0), (0,0,1), (0,1,1), (1,0,1), (1,1,0), (1,1,1) \(\}\) with the relation \((a_1,a_2,a_3) \preceq (b_1,b_2,b_3)\) iff \(a_i \le b_i\) for all \(i.\)
Poset Properties
Terminology
Two elements \(a,b\) of a poset are comparable if and only if either \(a \preceq b\) or \(b \preceq a.\)
For the poset represented by the Hasse diagram in Figure \(\PageIndex{2}\) the elements d and g are comparable. The elements b and f are incomparable.
A partially ordered set is a totally ordered set if and only if all pairs of elements are comparable.
An element \(c\) is a least upper bound of two elements \(a\) and \(b\text{,}\) denoted \(a \wedge b\text{,}\) if and only if \(a \preceq c,\) \(b \preceq c\) and if \(a \preceq d,\) \(b \preceq d\) for any other element then \(c \preceq d.\)
For the poset represented by the Hasse diagram in Figure \(\PageIndex{2}\) \(lub(a,b)=d\text{.}\) Note h is another upper bound of a and b, but \(d \preceq h\text{.}\)
An element \(c\) is a greatest lower bound of two elements \(a\) and \(b\text{,}\) denoted \(a \vee b\text{,}\) if and only if \(c \preceq a,\) \(c \preceq b\) and if \(d \preceq a,\) \(d \preceq b\) for any other element then \(d \preceq c.\)
For the poset represented by the Hasse diagram in Figure \(\PageIndex{2}\) \(glb(d,e)=b\text{.}\) There are no other lower bounds for this pair.
An element \(a\) in a poset is a minimal element if and only if there does not exist an element \(b\) such that \(b \preceq a.\)
For the poset represented by the Hasse diagram in Figure \(\PageIndex{2}\) the minimal elements are a,b, and c. a is a minimal element because there is no element x such that \(x \preceq a\text{.}\) Notice where the minimal elements are in the Hasse diagram.
An element \(a\) in a poset is a maximal element if and only if there does not exist an element \(b\) such that \(a \preceq b.\)
For the poset represented by the Hasse diagram in Figure \(\PageIndex{2}\) the maximal elements are f,g, and h. f is a maximal element because there is no element x such that \(f \preceq x\text{.}\)
Practice
Checkpoint \(\PageIndex{21}\)
Find two comparable elements in each of the relations in Checkpoint \(\PageIndex{9}\)
Checkpoint \(\PageIndex{22}\)
Find two incomparable elements in each of the relations in Checkpoint \(\PageIndex{9}\)
Checkpoint \(\PageIndex{23}\)
Find all minimal and maximal elements of the posets in Problem Checkpoint \(\PageIndex{9}\)
Checkpoint \(\PageIndex{24}\)
Consider the poset given in Figure \(\PageIndex{2}\) Find the following upper and lower bounds.
(a) Find \(f \vee h\)
(b) Find \(a \wedge e\)
(c) Find \(a \wedge d\)
(d) Does \(d \wedge e\) exist?
(e) Does \(g \vee h\) exist?
A poset in which every pair of elements has both a least upper bound and a greatest lower bound is a lattice
Checkpoint \(\PageIndex{26}\)
Which of the posets in Checkpoint \(\PageIndex{9}\) are lattices?
Checkpoint \(\PageIndex{27}\)
Why is the name “lattice” appropriate?