2
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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$.

$\endgroup$
  • 1
    $\begingroup$ Thanks. Since there exists $c$ and it's not for all, isn't the statement too weak to be transitive? $\endgroup$ – shinzou Jan 18 '15 at 15:26
2
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ I always thought that "let" means for all.. Why does $aR^2 c \to aRc$, EDIT: got it, because it's a subset. $\endgroup$ – shinzou Jan 18 '15 at 16:14
  • $\begingroup$ @kuhaku: If you look carefully through almost any textbook, they will use "let" for both "for all" and when instantiating an exitentially quantified object such as in "Let $m = 2k+1$.". It is imprecise and a continual source of confusion. $\endgroup$ – user21820 Jan 18 '15 at 18:06

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.