this is my first question here. I'm still relatively new to more advanced mathematics and don't have much experience with proofs yet. I'm self-studying at the moment and therefore have no one to check whether my proofs are valid. I hope that math.stackexchange can help me become better at writing proofs.
I'm currently reading 'How to prove it' by Velleman and have been working through the section on relations. Now I have found a statement somewhere that I want to prove, but I'm not sure whether what I have come up with is reasonable and I also have some questions on the logic used in these type of proofs.
The theorem is: Let $R$ be a relation on set $A$. Then it holds that: $R^{2}\subseteq R\iff R\text{ is transitive}\iff R^{i}\subseteq R,\forall i\geq1$.
I'll start with $R^{2}\subseteq R\iff R\text{ is transitive}$:
$\Rightarrow$ Assume that $R^{2}\subseteq R$. Here $xR^{2}z$ means that $xRy\wedge yRz$ for some $y\in A$. The goal is to show that $R$ is transitive, which is basically a conditional statement: if $xRy$ and $yRz$ hold, then I can infer that $xRz$. Therefore I can assume $xRy$ and $yRz$, and now should prove that $xRz$. But because $R^{2}\subseteq R$, I know that $xRy$ and $yRz$ is true for an arbitrary $(x,z)\in A$. It follows that $(x,z)\in R$.
$\Leftarrow$ Assume that $R$ is transitive. Therefore if for any $(x,z)\in A$ it is true that there is a $y\in A$ such that $xRy$ and $yRz$, I know that $xRz$. Now since $R^{2}\subseteq R$ is also a conditional statement of the form $\forall(x,y)\in A\times A\;(x,y)\in R^{2}\Rightarrow(x,y)\in R$. I can assume that there is an ordered pair, call it $(x,z)\in R^{2}$. Since we assumed that $R$ is transitive, it follows by modus ponens that $(x,z)\in R$.
Now I'll try to prove: $R\text{ is transitive}\iff R^{i}\subseteq R\forall i\geq1$.
$\Rightarrow$Assume $R$ is transitive. To prove that $R^{i}\subseteq R,\forall i\geq1$ I can use induction I guess?!
Base case: $i=1\Rightarrow R\subseteq R$ obviously holds.
Now I'm not really sure whether I actually have to use induction here. I think what needs to be shown here is pretty straightforward. If there is a $y\in A$ such that $x1Ry$ and $yRx2$ hold, then because $R$ is transitive it follows that $x1Rx2$. And then you can continue this way with $x2$ and $x3$ and in general any value $i$. But I don't really know how to write this in a formally correct way. Can anybody help me with that? And please give some feedback on the first part of the proof.
It looks fairly good, but I'd suggest a few refinements.
In your proof of the first implication, suppose that $\langle x,y\rangle,\langle y,z\rangle\in R.$ By definition, $\langle x,z\rangle\in R^2,$ and so by assumption, $\langle x,z\rangle\in R.$ Showing the converse is similarly done, much more briefly than your approach.
At this point, it would actually be easier to show that $$R^i\subseteq R\:\forall i\ge 1\iff R^2\subseteq R.$$ One of these implications is trivial. For the other, the $i=1$ case is readily true for any relation, and supposing that $R^i\subseteq R$ for some $i\ge 1,$ we can show readily that $$R^{i+1}=R^i\circ R\subseteq R\circ R=R^2,$$ and so $R^{i+1}\subseteq R$ by definition, finishing the induction step.