1
$\begingroup$

I'm having difficulty with the following problem:

Prove: if $R$ is a weak partial (linear) order on $X$, then $R^− = R \; \backslash\ Id_X$ is a strict partial (linear) order.

I know that as a weak partial order, $R$ is reflexive, antisymmetric, and transitive. I know that the identity relation $Id_X$ is reflexive, asymmetric, symmetric/antisymmetric and transitive. I also know that as a strict partial order, $R^−$ is irreflexive, asymmetric, and transitive.

I can see that every reflexive relation in $R$ is also in $Id_X$, and that the difference $R \; \backslash\ Id_X$ will thus not contain any $<x, y>$ such that $x = y$, and will therefore be irreflexive.

I can see that this also implies that $R \; \backslash\ Id_X$ will be asymmetric, since the only $<x, y>$ pairs such that $x = y$ have been removed with $Id_X$ and by the definition of antisymmetry those were the only $<x, y>$ pairs for which $<y, x>$ was also the case.

I'm having trouble reasoning through why $R^−$ must be transitive. I think that if it weren't transitive, it would have to be the case that $R$ would also not be transitive, but I'm not sure how to articulate why that seems correct.

Finally, my biggest issue is just that I don't have math experience and have a hard time putting any of the above in formal notation.

Thanks for any help anyone is able to give.

$\endgroup$

1 Answer 1

1
$\begingroup$

Suppose that $\langle x,y\rangle\in R^-$ and $\langle y,z\rangle\in R^-$; then $\langle x,y\rangle,\langle y,z\rangle\in R$, and $R$ is transitive, so $\langle x,z\rangle\in R$. This means that $\langle x,z\rangle$ will be in $R^-$, as desired, unless $x=z$, so we want to rule out that possibility. But if $x=z$, then $\langle y,z\rangle=\langle y,x\rangle$, so our initial supposition is that $\langle x,y\rangle\in R^-$ and $\langle y,x\rangle\in R^-$. But then antisymmetry of $R$ implies that $x=y$, and we know that $\langle x,x\rangle\notin R^-$. Thus, $x\ne z$, and $\langle x,z\rangle\in R^-$.

$\endgroup$
2
  • $\begingroup$ Awesome, that makes complete sense. Thank you! $\endgroup$
    – Nick
    Jul 31, 2016 at 19:48
  • $\begingroup$ @Nick: You're welcome! $\endgroup$ Aug 1, 2016 at 2:04

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .