Ordered set proof review request

[mafagafo]

Homework Statement , relevant equations, and the attempt at a solution are all in the attached file.

I was reading through Invitation to Discrete Mathematics and attempted to solve an exercise that involved a proof. I've typeset everything in LaTeX and made a PDF out of it so that it does not clutter the post. The proof seems somewhat incomplete to me, almost as if I hadn't proofed what I had to. Therefore, I would like someone to assess it for me.

This is **not** homework.

Thanks for your time.

 

[fresh_42]

It appears to me that you have showed that an ordered set cannot have cycles related to that order.
But the question was how to construct an ordering given a relation without any cycles which extends this relation.
To start with a given order leaves the question why there is one? And what has it to do with the given relation?

Edit: If you have produced latex lines anyway you could as well include them here. This makes reading and quoting a lot easier.

 

[andrewkirk]

We can't start by saying 'take any ordering on X' because that presupposes that there exists an ordering on X.
Instead, what we want to do is to construct an ordering on X, starting with the relation.

I would suggest dividing X up into lower, middle and upper elements.

Lower elements would be those that never occur as a second element of a pair in R.
Upper elements would be those that are not Lower elements and never occur as a first element of a pair in R.
Middle elements would be those that occur as both first and second elements of pairs in R.

Then define a relation R' on X such that consists of

• all pairs in R; and
• all pairs in which the first element is Lower and the second is Middle or Upper; and
• all pairs in which the first element is Middle and the second is Upper

Then define the relation R'' to be the transitive and reflexive closure of R'.

You should be able to prove R'' is a partial order on X using the acyclicality property, using the ideas in your existing proof.

If we want the order to be a total order, we can just extend R' to a non-strict total order by adding to it:

1. all pairs formed by two elements from Lower
2. all pairs formed by two elements from Upper
3. all pairs formed by two elements from Middle such that the two elements do not occur in any existing pair, in either order.

This last bit makes all the items in 1 tied for order, all those in 2 tied for order and ditto for 3. So the order will be total because every pair of elements in X is in R'' at least once (and twice if they are tied).