Skip to main content
Logo image

Exercises 19.8 Exercises

Recognizing a partial order from its graph.

In each of Exercises 1–2, you are given a directed graph for a relation on the set \(A = \{a,b,c,d\}\text{.}\) Determine whether the relation is a partial order. Justify your answers.

1.

An example graph for verifying the partial order definition.

2.

An example graph for verifying the partial order definition.

Testing partial orders.

In each of Exercises 3–6, you are given a set \(A\) and a relation \(R\) on \(A\text{.}\) Determine whether the relation is a partial order. Justify your answers.

3.

\(A\) is the set of all Augustana students; \(a \mathrel{R} b\) means that student \(a\) has a higher GPA than student \(b\text{.}\)

4.

\(A\) is the power set of some finite set; \(S \mathrel{R} T\) means \(\card{S} \le \card{T}\text{.}\)

5.

\(A\) is the set of words on some alphabet; \(w \mathrel{R} w'\) means \(\length{w} \le \length{w'}\text{,}\) where \(\length{w}\) means the length of word \(w\text{.}\)

6.

\(A = \R \cartprod \R\text{;}\) \((x1,y1) \mathrel{R} (x2,y2)\) means \(x_1 \le x2\) and \(y_1 \le y2\text{.}\)

Drawing Hasse diagrams.

In each of Exercises 7–8, you are given a finite, partially ordered set \(A\text{.}\) Draw the Hasse diagram.

7.

\(A = \powset{\{1,2,3,4\}}\) under the subset relation.

8.

\(A = \words{\Sigma}_4\text{,}\) the set of words of length \(4\) in the alphabet \(\Sigma = \{0,1\}\text{,}\) under dictionary order.

9.

Draw all possible valid Hasse diagrams for each of the sets \(A = \{a,b\}\) and \(B = \{a,b,c\}\text{.}\) (Thus, you will have determined all possible partial orders on those sets.)

10.

Consider the “divides” relation \(\mathord{\mid}\) on \(\posset{\N}\text{.}\) Provide an example of a set \(A \subseteq \posset{\N}\)

(a)

that is finite, and on which \(\mathord{\mid}\) is a total order.

(b)

that is infinite, and on which \(\mathord{\mid}\) is a total order.

(c)

on which \(\mathord{\mid}\) is a partial order but not a total order.

11.

Let \(A = \{0,1,2\}\text{,}\) and consider the partial order \(\mathord{\subseteq}\) on the power set \(\powset{A}\text{.}\) List all pairs of incomparable elements in \(\powset{A}\text{.}\)

Determining maximal/maximum/minimal/minimum elements.

In each of Exercises 12–16, you are given a partially ordered set \(A\text{.}\) Determine any and all maximal, maximum, minimal, and minimum elements.

12.

\(A = \posset{\N}\) under the usual \(\mathord{\le}\text{.}\)

13.

\(A = \posset{\Q}\) under the usual \(\mathord{\le}\text{.}\)

14.

\(A = \N \relcmplmnt \{0,1\}\) under the “divides” relation \(\mathord{\mid}\text{.}\)

15.

\(A = \{2,5,11,13,22,65,110,143,496\}\) under the “divides” relation \(\mathord{\mid}\text{.}\)

16.

\(A\) is the set of the first ten prime numbers under the “divides” relation \(\mathord{\mid}\text{.}\)

17.

Suppose \(\mathord{\partorder}\) is a partial order on the set \(A = \{0,1,2\}\) such that \(1\) is a maximal element. What are the possibilities for the Hasse diagram of \(\mathord{\partorder}\text{?}\)

Topological sorting.

In each of Exercises 18–19, you are given the Hasse diagram for a partially ordered set \(A\text{.}\) Use the Topological sorting algorithm to determine a compatible total order on \(A\text{.}\)

18.

A Hasse diagram for a topological sorting exercise.

19.

A Hasse diagram for a topological sorting exercise.