Im trying to prove following statements.

First is that when relation R is transitive then also $R^{2}$ is transitive.

I tried to prove it by following sequences of declarations:

transitivity = $\forall (x,y,z): xRy \wedge yRz \Rightarrow xRz$

$R^{2}$ = $\exists(c):xRc \wedge cRx$

using these two declarations we can rewrite implication such as

$\forall (x,y,z): xRy \wedge yRz \Rightarrow xRz$ $\Rightarrow$ $\forall (x,y,z): xR^{2}y \wedge yR^{2}z \Rightarrow xR^{2}z$

I am not sure how to further adjust the formula to prove that the statement is true ( or false ).

I was also trying to apply same idea for proving following statements:

1) R is asymetric then $R^{2}$ is asymetric ,

where asymetric $\forall(xy):xRy \Rightarrow not(yRx)$

2) R is ireflexive then $R^{2}$ is also ireflexive

where ireflexivity = $\forall(x):not(xRy) $

How could i further proceed in the declarations? Thanks

// edit

$\exists{c}: xRc \wedge cRy \wedge \exists{d}: yRd \wedge dRz \Rightarrow \exists{e}: xRe \wedge eRz$

Is this correct unpacking? If yes how could i proceed and prove the statement?

  • $\begingroup$ @MauroALLEGRANZA But how could i say if statement is true of false from this unpacking? Im quite lost here $\endgroup$ – trolkura Nov 21 '16 at 15:12

Long comment

For $R^2$, you have the transitivity of $R$ :

$∀x,y,z \ (xRy ∧ yRz \to xRz)$

and the def of $R^2$ :

$xR^2y \equiv ∃c (xRc ∧ cRy)$

and you have to prove that :

$∀x,y,z \ (xR^2y ∧ yR^2z \to xR^2z)$.

Thus, you have to start from :

$xR^2y ∧ yR^2z$

and "unpack" it according to the definition of $R^2$ in order to derive, exploiting the transitivity of $R$:


  • $\begingroup$ I updated question for unpacking , $\endgroup$ – trolkura Nov 21 '16 at 14:59

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.