1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Ordered set proof review request

  1. May 20, 2016 #1
    The problem statement, all variables and given/known data, 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.

    Attached Files:

  2. jcsd
  3. May 20, 2016 #2


    User Avatar
    2017 Award

    Staff: Mentor

    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.
  4. May 20, 2016 #3


    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    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).
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted

Similar Discussions: Ordered set proof review request
  1. Set proof (Replies: 1)

  2. Set Proof (Replies: 14)