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, 2016 at 15:12

1 Answer 1


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, 2016 at 14:59

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .