Results 1 to 2 of 2

Thread: Partial Order Relation help

  1. #1
    Junior Member
    Joined
    Nov 2010
    Posts
    40

    Partial Order Relation help

    Let $\displaystyle I_{a}$ denote the identity relation on a set a

    Show that if R is a partial order relation on a then $\displaystyle R\backslash I_{a}$ is a strict partial order relation on a

    Show that if S is a strict partial order relation on a then $\displaystyle S \cup I_{a}$ is a partial order relation on a

    I'm pretty sure I have these down I just want to make sure

    For the first one, this one is just straight forward... I mean if you have a partial order relation and then you take out the identity it becomes irreflexive but I'm not sure how to "show" this. Do I just say:

    $\displaystyle x \epsilon R \backslash I_{a} $ means that x cannot be of the form $\displaystyle (x,x)$ making $\displaystyle R \backslash I_{a}$ irreflexive and thus a strict partial order?

    The second is basicly the same but the opposite way.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,577
    Thanks
    790
    Often, the easiest and shortest way for both the writer and the reader is to write things down formally.

    Suppose $\displaystyle R$ is a partial order on $\displaystyle a$. We need to prove that $\displaystyle R\setminus I_a$ is a strict partial order.

    Irreflexivity. Let $\displaystyle x\in a$. Then $\displaystyle (x,x)\in I_a$, so $\displaystyle (x,x)\notin R\setminus I_a$. That was easy.

    Transitivity. Suppose $\displaystyle (x,y),(y,z)\in R\setminus I_a$, i.e., $\displaystyle (x,y),(y,z)\in R$, $\displaystyle x\ne y$ and $\displaystyle y\ne z$. Then $\displaystyle (x,z)\in R$. It's left to show that $\displaystyle x\ne z$. Suppose $\displaystyle x=z$; then by antisymmetry of R we have x = y, a contradiction.

    Thinking back, it is right that we had to use antisymmetry. If every reflexive and transitive (but not necessarily antisymmetric) relation would produce a strict partial order when one subtracts $\displaystyle I_a$, then it is unlikely that joining a strict order with $\displaystyle I_a$ would produce an antisymmetric relation as the second part of the problem says.

    I recommend similarly writing out the second part in every detail.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. 3rd Order Recurrence Relation
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Apr 26th 2011, 03:44 AM
  2. Partial Order relation and hasse diagram mxa/min
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Sep 27th 2010, 11:02 PM
  3. Second Order Recurrence relation
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: Feb 12th 2008, 01:59 PM
  4. last two problems. order relation
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Nov 15th 2006, 01:30 PM
  5. Partial order relation
    Posted in the Discrete Math Forum
    Replies: 10
    Last Post: Apr 17th 2006, 01:34 PM

Search Tags


/mathhelpforum @mathhelpforum