Suppose that R and S are relations on a non-empty set A. Prove/disprove that if $R$ and $S$ are both anti-symmetric then $R\setminus S$ is anti-symmetric.

I am pretty sure that this is true but I am having proving it. Here is what I currently have, i am not sure if this is correct:

Suppose that $a,b\in A$ and $(a,b),(b,a)\in R\setminus S$ this means that $(a,b),(b,a)\in R$ and $(a,b),(b,a)\notin S$ from the definition of set difference. Since both $R$ and $S$ are antisymmetric it follows that $a=b$. Therefore $(a,b)\in R\setminus S \land (b,a)\in R\setminus S \implies a=b$ and $R\setminus S$ must be antisymmetric.

  • $\begingroup$ You don't need the assumption that $S$ is antisymmetric. $\endgroup$ – Henning Makholm Feb 21 '16 at 22:03
  • $\begingroup$ So i can just say that since R is antisymmetric R\S will be antisymmetric? $\endgroup$ – sunsunsunsunsun Feb 21 '16 at 22:07
  • $\begingroup$ x @sun: That will be true. Whether you can get away with just asserting it instead of giving an actual argument for it depends on the context you're making the assertion in. $\endgroup$ – Henning Makholm Feb 21 '16 at 22:08
  • $\begingroup$ Where do you use the fact that $S$ is antisymmetric? You recite it, in the 2nd to last sentence, but it doesn't get you anything. You only use, and only need, antisymmetry of $R$. $\endgroup$ – BrianO Feb 21 '16 at 23:19

Your Answer

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

Browse other questions tagged or ask your own question.