1. Prove that is a partial order if and only if −1 is a partial order.
2. Prove that if is a partial order, then {ha, bi : a b and a 6= b} is a strict partial order
3. A cycle in a relation R is a sequence of k distinct elements a0, a1, . . . , ak−1 ∈ A where hai , ai+1 mod k i ∈ R for each i ∈ {0, 1, . . . , k − 1}. A cycle is nontrivial if k ≥ 2. Prove that there are no nontrivial cycles in any transitive, antisymmetric relation R. (Hint: use induction on the length k of the cycle.)
1 Show that R might not be a total order by identifying two incomparable elements of Z≥1 × Z≥1
2 Prove that R must be a partial order.
3 Write out all pairs in the relation represented by the Hasse diagram in Figure 8.38(a).
4 Repeat for Figure 8.38(b).
5 Draw the Hasse diagram for the partial order ⊆ on the set P(1, 2, 3).
6 Draw the Hasse diagram for the partial order on the set S := {0, 1} ∪ {0, 1}
2 ∪ {0, 1}3, where,for two bitstrings x, y ∈ S, we have x y if and only if x is a prefix of y
