1. Is the relation represented by the set S a partial ordering?

S = { (a, a), (b, b), (c, a), (c, c), (c, d), (d, c), (d, d) }

If S is a partial ordering, then explain why. If S is not a partial ordering, then state what properties of partial orderings it does not have. Also, if S does not have a property, then show a counterexample.

2. Suppose that the relation R is a partial ordering, so x R y means that x precedes y in the ordering. Also suppose that we know the following facts about R.

aRc eRh

cRg hRf

gRd bRh

dRf iRb

gRe iRe

Show a total ordering ? that is compatible with what we know about the partial ordering R.

These questions are about partial orderings. In both questions, lower-case letters a, b, c, etc. represent arbitrary distinct objects. 1. (10 points.) Is the relation represented by the set S a partial ordering? If S is a partial ordering, then explain why. If S is not a partial ordering, then state what properties of partial orderings it does not have. Also, if S does not have a property, then show a counterexample. 2. (10 points.) Suppose that the relation R is a partial ordering, so x Ry means that x precedes y in the ordering. Also suppose that we know the following facts about R. a Rc eRh g Rd bRh dRf iRb gRe iRe Show a total ordering that is compatible with what we know about the partial ordering R