Questions: Partial Orders

Question 1

In the divisibility partial order on positive integers (m ≤ n means 'm divides n'), which pair of elements is INCOMPARABLE?

• A. 2 and 4, because 2 divides 4
• B. 1 and 7, because 1 divides 7
• C. 4 and 6, because neither divides the other
• D. 3 and 9, because 3 divides 9

Answer: (C)

Two elements are incomparable in a partial order when neither a ≤ b nor b ≤ a holds. For the divisibility order: 4 does not divide 6 (6/4 is not an integer), and 6 does not divide 4 (4/6 is not an integer). So 4 and 6 are incomparable — there is no divisibility relationship between them. This is the defining feature of a *partial* order: not all pairs are required to be related. Options A, B, and D all describe comparable pairs where one element divides the other.

Question 2

A relation R on a set A is a partial order if and only if it satisfies which three properties?

• A. Reflexive, symmetric, and transitive
• B. Reflexive, antisymmetric, and transitive
• C. Irreflexive, antisymmetric, and transitive
• D. Reflexive, antisymmetric, and symmetric

Answer: (B)

A partial order is reflexive (a ≤ a for all a), antisymmetric (if a ≤ b and b ≤ a then a = b), and transitive (if a ≤ b and b ≤ c then a ≤ c). The antisymmetry condition is what distinguishes partial orders from preorders (which lack antisymmetry) and from equivalence relations (which have symmetry rather than antisymmetry). Reflexivity + symmetry + transitivity defines an equivalence relation — a very different structure. The combination reflexive + antisymmetric + transitive defines ordering.

Question 3

In any partial order, nearly every pair of distinct elements is comparable — that is, for any a ≠ b, either a ≤ b or b ≤ a should hold.

• T. True
• F. False

Answer: False

This is precisely what 'partial' means in partial order. A partial order does NOT require all pairs to be comparable. The subset relation ⊆ on a family of sets is the standard example: {1, 2} and {2, 3} are neither a subset of each other, so they are incomparable. A partial order where every pair IS comparable is called a total order (or linear order) — the familiar ≤ on ℝ is a total order. Total orders are a special case of partial orders, not the norm.

Question 4

Every total order (like ≤ on the real numbers) is also a partial order, but not every partial order is a total order.

• T. True
• F. False

Answer: True

A total order satisfies all three partial order axioms (reflexivity, antisymmetry, transitivity) plus the additional comparability condition: for any a, b, either a ≤ b or b ≤ a. So every total order is a partial order with an extra condition. The converse fails: the subset relation ⊆ and the divisibility relation are partial orders that are NOT total orders because they have incomparable pairs. Total order is a strict strengthening of partial order.

Question 5

What does it mean for two elements to be 'incomparable' in a partial order? Give a concrete example from either the subset relation or the divisibility relation.

Model answer: Two elements a and b are incomparable if neither a ≤ b nor b ≤ a holds in the partial order. Example: in the subset partial order on {{1,2}, {2,3}, {1,2,3}}, the sets {1,2} and {2,3} are incomparable because {1,2} ⊄ {2,3} and {2,3} ⊄ {1,2}. Neither is a subset of the other.

Incomparability is not a deficiency of the ordering — it's the defining feature that distinguishes partial orders from total orders. Real-world partial orders like task precedence (some tasks must precede others, but many are independent) or version control ancestry (commits may have multiple parents and diverging branches) have incomparable elements by design. A Hasse diagram makes incomparability visible: elements with no connecting path between them are incomparable.