- #1
4Fun
- 10
- 0
I'm currently reading the section on relations in Velleman's "How to prove it" and 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:
[itex]R^2 \subseteq R <=>[/itex] R is transitive [itex]<=> R^i \subseteq R ,\forall i \geq 1[/itex]
I'll start with [itex]R^2 \subseteq R[/itex] <=> R is transitive:
=> Assume that [itex]R^2 \subseteq R[/itex]. R^2 means that for an arbitrary ordered pair (x, z)[itex]\in[/itex]A there is a y[itex]\in[/itex]A such that xRy and yRz. The goal is to show that R is transitive, which is basically a conditional statement. If xRy and yRz hold, then we can infer that xRz. Therefore I can assume xRy and yRz, and now should prove that xRz.But because R^2[itex]\subseteq[/itex]R, I know that xRy and yRz is true for an arbitrary (x, z)[itex]\in[/itex]A. It follows that (x, z)[itex]\in[/itex]R.
<= Assume that R is transitive. Therefore if for any (x, z)[itex]\in[/itex]A it is true that there is a y[itex]\in[/itex]A such that xRy and yRz, I know that xRz. Now since R^2[itex]\subseteq[/itex]R is also a conditional statement of the form [itex]\forall[/itex](x,y)[itex]\ni[/itex]AxA((x,y)[itex]\ni[/itex]R^2 then (x,y)[itex]\ni[/itex]R, I can assume that there is an ordered pair, call it (x,z)[itex]\ni[/itex]R^2. Since we assumed that R is transitive, it follows by modus ponens that (x,z)[itex]\ni[/itex]R.
Now I'll try to prove: R is transitive <=> R^i [itex]\subseteq[/itex]R, [itex]\forall[/itex]i[itex]\geq[/itex]1.
=> Assume R is transitive. To prove that R^i[itex]\subseteq[/itex]R, for all i [itex]\geq[/itex]1 we can use induction.
Base case: i=1 -> R[itex]\subseteq[/itex]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[itex]\in[/itex]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.
The theorem is: Let R be a relation on set A. Then it holds that:
[itex]R^2 \subseteq R <=>[/itex] R is transitive [itex]<=> R^i \subseteq R ,\forall i \geq 1[/itex]
I'll start with [itex]R^2 \subseteq R[/itex] <=> R is transitive:
=> Assume that [itex]R^2 \subseteq R[/itex]. R^2 means that for an arbitrary ordered pair (x, z)[itex]\in[/itex]A there is a y[itex]\in[/itex]A such that xRy and yRz. The goal is to show that R is transitive, which is basically a conditional statement. If xRy and yRz hold, then we can infer that xRz. Therefore I can assume xRy and yRz, and now should prove that xRz.But because R^2[itex]\subseteq[/itex]R, I know that xRy and yRz is true for an arbitrary (x, z)[itex]\in[/itex]A. It follows that (x, z)[itex]\in[/itex]R.
<= Assume that R is transitive. Therefore if for any (x, z)[itex]\in[/itex]A it is true that there is a y[itex]\in[/itex]A such that xRy and yRz, I know that xRz. Now since R^2[itex]\subseteq[/itex]R is also a conditional statement of the form [itex]\forall[/itex](x,y)[itex]\ni[/itex]AxA((x,y)[itex]\ni[/itex]R^2 then (x,y)[itex]\ni[/itex]R, I can assume that there is an ordered pair, call it (x,z)[itex]\ni[/itex]R^2. Since we assumed that R is transitive, it follows by modus ponens that (x,z)[itex]\ni[/itex]R.
Now I'll try to prove: R is transitive <=> R^i [itex]\subseteq[/itex]R, [itex]\forall[/itex]i[itex]\geq[/itex]1.
=> Assume R is transitive. To prove that R^i[itex]\subseteq[/itex]R, for all i [itex]\geq[/itex]1 we can use induction.
Base case: i=1 -> R[itex]\subseteq[/itex]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[itex]\in[/itex]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.