# Playground

## 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 .