2
$\begingroup$

I have the following problem.

Suppose that $r \subseteq X \times Y$ is a relation with domain $X$ and codomain $Y$. Define a new relation $R^\circ \subseteq Y \times X$ by the rule that $(y, x) \in R^\circ$ if and only if $(x,y) \in R$.

Decide whether the following statements about $R^\circ$ are true or false, giving a proof or counterexample as required.

(a) If $R$ is a transitive relation, then $R^\circ$ is also a transitive relation.


My Proof

We have the following proposition:

If $R$ is a transitive relation, then $R^\circ$ is also a transitive relation.

The hypothesis is

$R$ is a transitive relation.

The conclusion is

$R^\circ$ is also a transitive relation.

So we can assume that the hypothesis is true and work forwards from it to conclude that the conclusion must also be true.

Let $(x,y) \in R$ and $(y, z) \in R$.

$\therefore (x, z) \in R$, since $R$ is assumed to be transitive (the hypothesis).

$\therefore (z, y), (y, x), (z, x) \in R^\circ$, by the definition of $R^\circ$.

$\therefore R^\circ$ must be transitive.


However, my instructor says that this proof is automatically incorrect:

Any proof that starts with "Let $(x,y), (y,z) \in R$" is automatically incorrect.

However, using my previous knowledge of proof-writing, I'm struggling to understand why this would be incorrect. As I mentioned above, my reasoning is that we can assume that the hypothesis is true, and then work forwards to conclude that the conclusion must also be true. Based on my prior studies of proof-writing, I was under the impression that this was the correct way to go about writing proofs.

I would greatly appreciate it if people could please take the time to clarify this.

$\endgroup$
1
$\begingroup$

To prove that $R^0$ is transitive, you must apply the definition of "transitive" to $R^0$. In the middle of the proof, you must use the definition of "transitive" on $R$. What OP did was just the latter.

Here is a correct proof structure:

Let $(x,y), (y,z)\in R^0$.

(details)

Hence $(x,z)\in R^0$.

The details will involve using the definition of $R^0$ to conclude things about $R$, then using the transitivity of $R$ to conclude more things about $R$, and lastly to use the definition of $R^0$ to conclude that $(x,z)\in R^0$.

$\endgroup$

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.