Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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$
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$
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$.
