0
$\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$
0
$\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$
  • $\begingroup$ Awesome, that makes complete sense. Thank you! $\endgroup$ – Nick Jul 31 '16 at 19:48
  • $\begingroup$ @Nick: You're welcome! $\endgroup$ – Brian M. Scott Aug 1 '16 at 2:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.