$(m, m') \in \mathit R^{n}$ only when sequence $c_0, ..., c_n$ $\mathit M$ with $m = c_0, (c_1, c_{i+1}) \in \mathit R$ and $c_n = m'$ exists

Question

I am having trouble understanding a proof. The complete question is as follows:

Given a relation $\mathit R \subseteq \mathit M \times \mathit M$. For all $n \ge 0$ it applies $(m, m') \in \mathit R^{n}$ only when a sequence $c_0, ..., c_n$ of elements $\mathit M$ with $m = c_0, (c_1, c_{i+1}) \in \mathit R, i = 0, ..., n-1$ and $c_n = m'$ exists.

From the question, I don't understand what this means:

$m = c_0, (c_1, c_{i+1}) \in \mathit R, i = 0, ..., n-1$ and $c_n = m'$ exists.

Since I don't really understand the question, I am not able to follow the answer, which goes as follows:

For the case $n = 0$ the statement is valid, since according to definition $R^{0} = 1_M$ (identical relation).

Given $n \ge 1$ and $(m,m') \in \mathit R^{n}$ then it exists one element $m'' \in \mathit M$ with $(m,m'') \in R^{n-1}$ and $(m'',m') \in \mathit R$, since $\mathit R^{n} = \mathit R \circ \mathit R^{n-1}$.

Following the induction requirement we find a sequence $c_0, ..., c_{n-1}$ with $m=c_0,(c_i,c_{i+1}) \in \mathit R, i = 0,..., n-2$ and $c_{n-1}=m''$. With this, we can create the sequence $c_0, ..., c_{n-1}, m'$

I would be grateful for any help with some explanations regarding what is happening in each step.

Answer 1

The statement in question is:

Given a relation $R \subseteq M \times M$. For all $n \ge 0$ it applies $(m, m') \in R^{n}$ only when a sequence $c_0, ..., c_n$ of elements $M$ with $m = c_0, (c_i, c_{i+1}) \in R, i = 0, ..., n-1$ and $c_n = m'$ exists.

Let's unpack what this is saying. You have a binary relation $R\subseteq M\times M$. Given a binary relation $R$, we have a definition of the $n$-fold composition of $R$, written $R^n$, for any $n\in \mathbb{N}$. This definition is by induction: $R^0$ is the identity relation $1_M = \{(m,m)\mid m\in M\}$, and for any $n>0$, $R^n = R\circ R^{n-1}$.

What does $R\circ R^{n-1}$ mean? Well, given two relations $R,R'\subseteq M\times M$, we have the definition of the relational composition $$R\circ R' = \{(a,b)\mid \text{there exists }c\in M\text{ such that }(a,b)\in R \text{ and }(b,c)\in R'\}.$$ So we have $R^0 = 1_M$ and $$R^n = R\circ R^{n-1} = \{(a,b)\mid \text{there exists }c\in M\text{ such that }(a,b)\in R \text{ and }(b,c)\in R^{n-1}\}.$$

Now this inductive definition of $R^n$ is a bit abstract. The quoted statement is giving a more concrete description of which pairs are in $R^n$. Specifically, $(m,m')\in R^n$ if and only if there exists a sequence of elements $c_0,c_1,c_2,\dots,c_n\in M$ such that $c_0= m$, $c_n = m'$, and $(c_i,c_{i+1}) \in R$ for all $0\leq i \leq n-1$.

For example, $(m,m')\in R_3$ if and only if there exists $c_1$ and $c_2$ in $M$ such that $(m,c_1)\in R$, $(c_1,c_2)\in R$, and $(c_2,m')\in R$. That is, we can go from $m$ to $m'$ be a chain of three instances of the relation $R$.

Does that help?