4.7.1: Identifying partial, strict, and total orders.

For each relation, indicate whether the relation is a partial order, a strict order, or neither. If the relation is a partial or strict order, indicate whether the relation is also a total order. Justify your answers.

(a)

The domain is the set of all words in the English language (as defined by, say, Webster's dictionary). Word x is related to word y if x appears before y in alphabetical order. Assume that each word appears exactly once in the dictionary.

(b)

The domain is the set of all words in the English language (as defined by, say, Webster's dictionary). Word x is related to word y if x appears as a substring of y. x is a substring of y if all the letters in x appear in consecutive order somewhere in y. For example, "logical" is substring of "topological" because the letters l-o-g-i-c-a-l appear consecutively in order in the word "topological". However, "local" is not a substring of "topological" because the letters l-o are separated from c-a-l by the letters g and i.

(c)

The domain is the set of all cell phone towers in a network. Two towers can communicate if they are within a distance of three miles from each other. Tower x is related to tower y if x can send information to y through a path of communication links. You can assume that there are at least two towers that are within three miles of each other.

(d)

The domain is the set of all positive integers. x is related to y if y = 3nx, for some positive integer n.

(e)

The domain of relation P is the set of all positive integers. For x, y Z+, xPy if there is a positive integer n such that xn = y.

(f)

The domain for the relation is ZZ. (a, b) is related to (c, d) if a c and b d.

(g)

The domain is the set of girls at a basketball camp. Player x is related to y if x is taller or weighs more than player y (inclusive or). You can assume that no two players have the same height and that no two players have the same weight. The answer may depend on the actual weights or heights of the players, in which your answer may be "not necessarily", but you need to give an example to justify your answer.

(h)

The domain is the set of all runners in a race. x is related to y if x beat y in the race. No two players tied.

(i)

The domain is the set of all runners in a race. x is related to y if x beat y in the race. At least two runners in the race tied.