Showing $R$ is transitive and reflexive $\to$ $R=R^2$, $R$ is transitive and reflexive $\to$ $R=R^2$

Question

Let $R$ be a relation over $A$. Define $R^{-1}, R^2$ like so:

$aR^{-1}b \iff bRa\\ aR^2b\iff\exists _{c\in A}(aRc\wedge cRb)$

Prove:

1. $R$ is transitive $\iff$ $R^2\subseteq R$

2. $R$ is transitive and reflexive $\to$ $R=R^2$

1. $\Rightarrow$ is fairly simple, let $a,b,c\in A$ since $R$ is transitive then $(a,b),(b,c)\in R$ so there exists $b\in A$ such that from the definition of $R^2$: $(a,b),(b,c)\in R \iff a R^2c$ therefore $R^2\subseteq R$.

   But I get stuck with $\Leftarrow$, suppose $R^2\subseteq R$ so let $a,b\in A$ such that $aR^2b\iff\exists _{c\in A}\color{red}{(aRc\wedge cRb)}\subseteq R$ but now I can't just use the definition of transitivity on the red part to get $aRc$ and I can't assume anything else...

2. We have from definition: $\forall a,b,c\in A(aRa)\wedge((aRb\wedge bRc)\to(aRc))$ $(*)$ and we need to show that $R\subseteq R^2$ and $R^2\subseteq R$.

   So maybe this would work: $aR^2b\iff\exists _{a\in A}(aRa\wedge aRb)$ but I'm not sure how to apply it in the subsets...

$(*)$ Question about this, is there a way to simplify it? is it equivalent to $(aRa)\wedge(aRc)$ or $(aRa)\wedge(aRb\wedge bRc)$? or we can't simplify it any further?

Answer 1

For 1. : consider $a,b,c \in A$ such that $aRc$ and $cRb$.

This means that $aR^2b$ and we have that $R_2 ⊆ R$, and this means that : : $(a,b) \in R^2 \subseteq R$ and thus $(a,b) \in R$.

Thus we have that, from $aRc, cRb$, follows : $aRb$, and this is transitivity.

---

For 2. : we have $R^2 \subseteq R$ form 1. (transitivity); thus we have to check that reflexivity is enough to ensure : $R \subseteq R^2$.

In order that $(a,b) \in R \rightarrow (a,b) \in R^2$, we have to check that :

if $aRb \in R$, then $\exists c (aRc \land cRb)$;

then assume $c=a$ and we have : $aRa$ (by reflexivity) and : $aRb$.

Answer 2

You need to distinguish very clearly between existential and universal quantification, and you should not use "let" when you actually want to say something about "any arbitrary given" something.

Your first part of the first question should therefore be more precisely the following:

If $R$ is transitive on $A$:

  For any $a,b \in A$ such that $a R^2 b$:

    Let $c \in A$ such that $a R c$ and $c R b$ for some $c \in A$.

    Then $a R b$ because $R$ is transitive on $A$.

  Therefore $R^2 \subseteq R$

And here is the second part is in full:

If $R^2 \subseteq R$:

  For any $a,b,c \in A$ such that $a R b$ and $b R c$:

    $\exists x \in A ( a R x \wedge x R c )$.

    Thus $a R^2 c$.

    Thus $a R c$.

  Therefore $R$ is transitive on $A$.