Problem 1: Linear Extension
Let be an arbitrary relation and a partial order on .
a) Assume to be incomparable: and . Show that the transitive closure of the relation is a partial order on .
b) Use (a) to show if is finite then every order on has a linear extension. A total order is a linear extension of a partial order if, whenever implies that .
c) Use (a) to show there is a finite number of total orders such that for all we have
d) Show that is a linear extension of if and only if is a total order and the identity function is a monotone function from to .