• Support PF! Buy your school textbooks, materials and every day products Here!

Ordered set proof review request

  • #1
188
12
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.
 

Attachments

Answers and Replies

  • #2
12,692
9,238
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.
 
  • #3
andrewkirk
Science Advisor
Homework Helper
Insights Author
Gold Member
3,792
1,390
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).
 

Related Threads on Ordered set proof review request

  • Last Post
Replies
3
Views
1K
Replies
1
Views
2K
  • Last Post
Replies
3
Views
11K
Replies
3
Views
8K
Replies
12
Views
3K
Replies
8
Views
951
  • Last Post
Replies
4
Views
1K
  • Last Post
Replies
3
Views
1K
  • Last Post
Replies
3
Views
3K
  • Last Post
Replies
2
Views
6K
Top