I am unable to understand what this question means (except that I is the identity relation). Would really appreciate a simple explanation of what it is saying, and also some hints/tips on how to answer it. Thank you.

$R$ is a binary relation on set $S$. $R_0$, $R_1$, $R_2$…. are defined as below:

$R_0 := I = \{(x,x) : x ∈ S\}$

$R_{n+1} := R_n ∪ (R;R_n)$ for $n >= 0$

There exists $i ∈ N$ such that $R_i = R_{i+1}$

Prove the following:

$R_j = R_i$ for all $j \ge i$

$R_j ⊆ R_i$ for all $j \ge 0$

  • 1
    $\begingroup$ You should use mathjax. It is not clear right now what the definitions are right now. What is $R;R_n$? $\endgroup$ – Keen-ameteur Oct 27 '20 at 9:36
  • $\begingroup$ Do you know the def of Composition of relations ? Do you use $(R;S)$ to mean "left composition" ? $\endgroup$ – Mauro ALLEGRANZA Oct 27 '20 at 9:37
  • $\begingroup$ You have to use rel $R$ to build a "sequence" of relations where the first one is $R_0$ (the Identity relations on set $S$), the next step is $R_1 = R_0 \cup (R;R_0)$. $\endgroup$ – Mauro ALLEGRANZA Oct 27 '20 at 9:39
  • 2
    $\begingroup$ What is $\;(R ; R_n)\;$ ? $\endgroup$ – DonAntonio Oct 27 '20 at 9:39
  • 1
    $\begingroup$ Actually you don't need to know what $(R;R_n)$ or about relations to solve the problem (at least this part of the problem. maybe there are more parts that use the relation aspect). Just treat them as sets. You can prove the first part by induction. You know the base case is true. $R_i = R_i$. Then assume $R_k = R_i$. now prove that $R_{k+1} = R_i$ $\endgroup$ – Ameet Sharma Oct 27 '20 at 10:28
  • $R_j=R_i$ for all $j\geq i$

Let $B = \{n : n \in \mathbb{N} \land R_i=R_{i+n}\}$

First $1 \in B$ since, the exercise itself asserts "There exists $i \in \mathbb{N}$ such that $R_i=R_{i+1}$".

Now assume $n \in B$, that is $R_i = R_{i+n}$, by definition of $R$ we have $R_{i+n+1} = R_{i+n} \cup (R; R_n)$, thus we have also,

$R_{i+n+1} = R_i \cup (R; R_n)$, but the right side is $R_i$ itself we can see this from: $$R_{i+1}=R_i \cup (R; R_n) = R_i$$ Thus we got $R_{i+n+1} = R_i$, thus $n+1 \in B$ and we have shown that $n \in B \Rightarrow n+1 \in B$, therefore by mathematical induction $B=\mathbb{N}$.

Now we have just two cases to check because $(j \geq i \Leftrightarrow j \gt i \lor j=i)$, its obvious that if $i=j$ then $R_i=R_j$, but if $j>i$ then $(\exists u)(u \in \mathbb{N} \land i+u = j)$ from which follows $R_j = R_{i+u} = R_i$.

Therefore $j \geq i \Rightarrow R_j = R_i$

  • $R_j \subseteq R_i$ for all $j \geq0$

Here we will proceed by contradiction,

First by the previous part we have that if $j \geq i$ then $R_j=R_i$, from this follows that $j \geq i$ then $R_j \subseteq R_i$ since both are the same.

Now for the sake of contradiction assume that there is some $j \lt i$ such that $R_j \not\subseteq R_i$, that is there is some element $a$ in $R_j$ that is not on $R_i$, in symbols $(\exists a)(a \in R_j \land \notin R_i)$.

Since $j \lt i$ there is some $k$ such that $j+k = i$ we can reach the definition of $R_i$ by using the definition of $R_{n+1}$. We need to apply the definition $k$ times starting from $j$, but by the definition of $R_{n+1}$ it possible to see, that $R_{n+1}$ contains all element of $R_n$.

It suffices to see that for any element $a$, $a \in R_j \Rightarrow a \in R_{j+1}$, and therefore after $k$ times we will have $a \in R_i$ and therefore $R_j \subseteq R_i$ which contradicts our assumption.

Thus we conclude that $j \geq 0 \Rightarrow R_j \subseteq R_i$.


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.