Let $R$ be a transitive relation on a set $A$. Define another relation, $S$, such that, for any $x,y \in A$, $Sxy$ iff $Ryx$. Moreover, let $S$ be irreflexive.

Prove: $S$ is asymmetric on $A$. (Hint: Try assuming that $S$ is not asymmetric and derive a contradiction.)

Here's what I have so far:

Assume $x \in A$.

Then Not $Sxx$ ($S$ is irreflexive)

Assume $x,y,z \in A$
Assume $Ryz$
Assume $Syx$

Then $Rxy$ (Definition of $S$)

So $Rxy$ and $Ryz$ (SC conjuntion)

Therefore, $Rxz$ ($R$ is transitive)

Assume $x,y \in A$


I don't understand how to prove $S$ is asymmetric by contradiction.

  • $\begingroup$ Don't take three different elements $x, y, z$. Take only two, $x$ and $y$. $\endgroup$ – M. Vinay Jun 7 '14 at 6:37

Proof Outline

  1. Assume that $S$ is not asymmetric. Then $\exists x, y \in A, x \ne y$ such that $Sxy$ and $Syx$.
  2. Use the definition of $S$ to write these in terms of $R$.
  3. Then use transitivity of $R$. What do you get?
  4. Again use the definition of $S$ on the result of Step 3. You get a contradiction.

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.