Let P D .X; / be a poset. We say that P is a semiorder if we can assign to each element

Chapter 0, Problem 6

(choose chapter or problem)

Let P D .X; / be a poset. We say that P is a semiorder if we can assign to each element of x a real number label `.x/ so that the following condition is met: 8x; y 2 X; x < y () `.x/ < `.y/ 1: In other words, x is below y just when its label, `.x/, is well below the ys label. Elements of X whose labels are too close (within 1 of each other) are incomparable. For example, the poset shown in 5(b) is a semiorder as we can assign the following labels: `.a/ D 1, `.b/ D 2:5, and `.c/ D 1:7. Note that a < b and, indeed, `.a/ is more than 1 less than `.b/. But `.c/ is within 1 of both `.a/ and `.b/ as required by the fact that c is incomparable to both a and b. a. Prove that all finite linear orders are semiorders. b. Prove that all finite weak orders are semiorders. c. Prove that neither of the posets in the figure below are semiorders. x y z w x z y w