6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Somehow it is the choosing for induction that frees you from finding a formal way to write down your thinkings. $R^{i+1}=R^{i}\circ R\subset R\circ R$ (induction step). Here $R\circ R=R^{2}$ and you allready showed that the transitivity of $R$ implies that $R^{2}\subset R$. This way $R^{i+1}\subset R$ is proved on base of $R^{i}\subset R$. $\endgroup$ – drhab Nov 4 '13 at 19:17
  • $\begingroup$ You can render $\iff$ by \iff, $\implies$ by \implies and $\impliedby$ by \impliedby. $\endgroup$ – Lord_Farin Nov 4 '13 at 19:21
  • $\begingroup$ I have edited your question. Please check it. $\endgroup$ – drhab Nov 4 '13 at 19:43
  • $\begingroup$ @drhab thanks for the suggestion and the edit. $\endgroup$ – eager2learn Nov 4 '13 at 20:36
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks a lot for your answer. For some reason didn't see that you could just let $(x,y)$ and $(y,z)$ be two elements from R and then infer that $(x,z)\in R$, because you know $R^2 \subseteq R. And I understand how you created the induction part. I guess I'll just have to familiarise myself a little more with what the composition operation actually means. Thanks again. $\endgroup$ – eager2learn Nov 4 '13 at 20:27
  • $\begingroup$ You are very welcome. Was that all clear to you, or do you still have some questions about it? In particular, were you able to show that "we can show readily" part? $\endgroup$ – Cameron Buie Nov 4 '13 at 20:29
  • $\begingroup$ It's a good thing to keep in mind that to prove that a particular thing holds for any finite number of iterations of something (composition, union, intersection, etc.), it is often enough to know that it works for $2$ iterations, as we saw in this case. $\endgroup$ – Cameron Buie Nov 4 '13 at 20:30
  • $\begingroup$ Well actually after having thought a bit about the "we can show readily that" part, I'm not sure that I completely understand why $R^i \circ R \subseteq R \circ R$. I understand it from an intuitive reason. Since R is transitive, it has to be the case that you can keep coming up with elements such that $R^i \circ R \subseteq R \circ R$ is correct, but I think I could not formally explain it. Can you tell me how to do that please? $\endgroup$ – eager2learn Nov 4 '13 at 20:35
  • $\begingroup$ Well, what does an arbitrary element of $R^i\circ R$ look like? $\endgroup$ – Cameron Buie Nov 4 '13 at 20:37

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.