-1

need help with the following question:

let $R$ be a binary relation.

We will define a series of relations $R_1,R_2,R_3\dots$ so that:

$R_0 = R$

$R_{i+1} = R_i\cup\{\langle x,y\rangle :\exists y(xR_iy\wedge yR_iz)\}$

we need to prove that $\bigcup_{i=0}^{\infty}R_i$ is transitive thank you:)

drhab
  • 151,093
blabla
  • 31

1 Answers1

0

Denote $S=\bigcup_{i=1}^{\infty}R_i$.

First observe that $i\leq j\implies R_i\subseteq R_j\subseteq S$.

You can formally prove that by induction.

Let $xSy$ and $ySz$.

Then $xR_iy$ and $yR_jz$ for nonnegative integers $i,j$.

Then if $k=\max(i,j)$ we have $xR_ky\wedge yR_kz$ hence $xR_{k+1}z$.

Then $xSz$ because $R_{k+1}\subseteq S$.

drhab
  • 151,093
  • thank you:)

    is j=i+1 ?

     – blabla Apr 13 '18 at 09:01
  • Not necessarily. – drhab Apr 13 '18 at 09:06
  • ok, cant you just say that if k = max(i,J) then Ri ⊆ Rk and Rj ⊆ Rk then xRky ∧ yRkz and xRk+1z, then because Rk+1 ⊆ S then S is transitive without induction? – blabla Apr 13 '18 at 09:09
  • Yes you can. I do not use any induction in my answer. The phrase "you can prove that by induction" is only referring to a formal proof of $R_i\subseteq R_j$ if $i <j$. Not to what follows. – drhab Apr 13 '18 at 09:49