Exercise · ZW-PARTIAL-ORDER-RELATION-008 · ★★☆ Intermediate
\(R=\{(1,1),(2,2),(3,3),(1,2),(2,3)\}\) on \(\{1,2,3\}\) is not a partial order. Which pair suffices to add to make it one?
Choose one option.
Show answer
- A. \((1,3)\)
Explanation
Transitivity fails: \(1R2\) and \(2R3\) require \(1R3\). Adding \((3,1)\), \((2,1)\) or \((3,2)\) breaks antisymmetry.
Review the concept: Partial order relation
A relation \(\preceq\) on a set \(S\) that is reflexive, antisymmetric and transitive, and therefore orders some pairs of elements of \(S\).
\[a\preceq a;\quad (a\preceq b\ \wedge\ b\preceq a)\Rightarrow a=b;\quad (a\preceq b\ \wedge\ b\preceq c)\Rightarrow a\preceq c\]
More practice problems: partial order relation
- ZW-PARTIAL-ORDER-RELATION-001 Which of these relations on ℤ is a partial order?
- ZW-PARTIAL-ORDER-RELATION-002 Which partial-order property fails for R=\(1,1),(2,2),(1,2),(2,1)\ on \1,2\?
- ZW-PARTIAL-ORDER-RELATION-003 In \1,2,3,4,6,12\ under divisibility, which pair of elements is incomparable?
- ZW-PARTIAL-ORDER-RELATION-004 If preceq is a partial order with apreceq b and bpreceq a, what follows?
- ZW-PARTIAL-ORDER-RELATION-005 Why is < on ℤ not a partial order?
- ZW-PARTIAL-ORDER-RELATION-006 How many pairs (a,b) with a,b∈\1,dots,6\ satisfy a| b?
- ZW-PARTIAL-ORDER-RELATION-007 In P(\a,b\) under ⊆, how many pairs (A,B) satisfy Asubsetneq B?
- ZW-PARTIAL-ORDER-RELATION-009 How many different partial orders are there on the set \1,2\?
← ZW-PARTIAL-ORDER-RELATION-007 ZW-PARTIAL-ORDER-RELATION-009 →