How do I derive a contradiction from an assumption that is "not asymmetric"

94 Views Asked by At

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.

1

There are 1 best solutions below

0
On

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.