Let $R$ be a relation defined on $A . \ R^{\left(0 \right)} = Id_{A}, R^{*} = \bigcup _{\left(n\in \mathbb{N} \right)} R^{\left(n \right)}$

Question

Given a set $A$. let $R$ be a relation defined on the set $A$.

$R$ is defined as the following: $$ R^{\left(0 \right)} = Id_{A},\\\\\\\ R^{\left(n+1\right)} = R^{\left(n \right)} \circ R, \\\\\\ R^{\left( *\right)} = \bigcup _{\left(n\in \mathbb{N} \right)} R^{\left(n \right)}$$

1.given some $n$, prove that for every $m\in\mathbb{N} \ \ :R^{(m+n)}=R^{(m)}\circ R^{(n)}$

2. prove that $R^{\left( *\right)}$ is a reflexive and transitive relation

3. prove that for every countable relation $R$, there exist a relation $S$ such that: $ R \subseteq S$

my attempt:

section 1: by induction. induction base: $n=1$ , therefore according to the properties of $$R^{\left(n+1\right)} = R^{\left(n\right)} \circ R$$ then: $$R^{\left(n+m\right)} = R^{\left(n+1\right)} = R^{\left(n\right)} \circ R$$ suppose that for some $m$, $$R^{(m+n)}=R^{(m)}\circ R^{(n)}$$

induction step: Prove for $m+1$.

$$R^{(n+m+1)} = R^{(n+m)}\circ R = \left(R^{\left(n\right)}\circ R^{\left(m\right)}\right) \circ R = R^\left( n \right) \circ {\left( R^{\left(m\right)} \circ R \right)} = R^\left(n\right) \circ R^\left(m+1\right)$$

I'm confused about the definition of $R^{\left( *\right)}$. I was thinking that it's probably possible to prove it by induction (if i can prove it without completely understanding what IS $R$ then that could be great)

induction base: for $n=0: \ \ R^{\left( *\right)} = \bigcup R^ {\left(0 \right)} = Id_{A}\ $

So I suppose that for every $a\in A, \ \left(a,a\right) \in R^{\left(0\right)} = Id_{A} $ (this is my understandion to the notion of a relation - please correct me if I'm wrong)

suppose this is true for some $n\in \mathbb {N}$, then it's quite clear from here.

Transitivity:

Let $\left(x,y\right)\in R^{\left(*\right)}=\bigcup_{n\in\mathbb{N}}R^{\left(n\right)} $ for some $n$ and $\left(y,z\right)\in R^{\left(*\right)}=\bigcup_{m\in\mathbb{N}}R^{(m)}$ for some $m$.

it seems trivial that $\left(x,z\right)\in R^{\left(*\right)}$ but I'm not sure how to prove that.

for 2. i suppose that this follows from the general definition of countability. as I got stuck on the first section especially because I didn't know how resume.

Let $R$ is a relation defined on $A . \ R^{*} = \bigcup _{\left(n\in \mathbb{N} \right)} R^{\left(n \right)}$ Prove:

Answer 1

Let us revisit the definition of composition of relations.

For relations $S,R$ on $A$, the relation $S\circ R$ consists of pairs $(a,b)\in A\times A$ such that there is an $x\in A$ with $(a,x)\in S$ and $(x,b)\in R$.

Now for $R=S$ this means for $R^{(2)} = R\circ R$ that $$ (a,b) \in R^{(2)} \quad\Longleftrightarrow\quad \exists x_1\in A\colon (a,x_1), (x_1,b) \in R. $$ Let us now consider $R^{(3)}=R^{(2)}\circ R$. We have \begin{align*} (a,b) \in R^{(3)} \quad&\Longleftrightarrow\quad \exists x_2\in A\colon (a,x_2)\in R^{(2)}, (x_2,b)\in R \\ &\Longleftrightarrow\quad \exists x_1, x_2\in A\colon (a,x_1), (x_1, x_2), (x_2, b)\in R. \end{align*} By now you should see where this is going. For general $n>0$ we have $(a,b)\in R^{(n)}$ iff there are $x_1,x_2,\dots,x_{n-1}\in A$ such that $$ (a,x_1), (x_1, x_2), \dots, (x_{n-2}, x_{n-1}), (x_{n-1}, b) \in R. $$ While for $n=0$ you just have $R^{(0)}=\operatorname{Id}_A = \{(a,a):a\in A\}$.

For reflexivity of $R^{(*)}$ you are correct in saying that $(a,a)\in R^{(0)}$ for all $a\in A$ and $R^{(0)}\subseteq R^{(*)}$.

For transitivity, let us consider $(x,y), (y,z)\in R^{(*)}$. Since $R^{(*)}$ is the union of all $R^{(i)}$ this means that $(x,y)\in R^{(n)}$ and $(y,z)\in R^{(m)}$ for some $n,m\ge 0$. If $n=0$ we have $x=y$ so $(x,z)=(y,z)\in R^{(*)}$ and similar when $m=0$. When $n,m>0$ we know that there are $x_1,\dots,x_{n-1}$ and $y_1,\dots,y_{m-1}$ such that $$ (x,x_1), (x_1, x_2), \dots, (x_{n-2}, x_{n-1}), (x_{n-1}, y) \in R $$ and $$ (y,y_1), (y_1, y_2), \dots, (y_{m-2}, y_{m-1}), (y_{m-1}, z) \in R. $$ Now we define $z_1,\dots,z_{n+m-1}\in A$ by: $$ z_i = \begin{cases} x_i &\text{if $i<n$,} \\ y &\text{if $i=n$,} \\ y_{i-n} &\text{if $i>n$}. \end{cases} $$ so that we have a sequence $$ (x, z_1), (z_1, z_2), \dots, (z_{n+m-2}, z_{n+m-1}), (z_{n+m-1}, z) \in R $$ and we can conclude $(x,z)\in R^{(n+m)} \subseteq R^{(*)}$. Hence, we have shown that $R^{(*)}$ is a reflexive and transative relation, regardless of what relation $R$ we start with.