# Proofs involving relations

1. Nov 4, 2013

### 4Fun

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:
$R^2 \subseteq R <=>$ R is transitive $<=> R^i \subseteq R ,\forall i \geq 1$

I'll start with $R^2 \subseteq R$ <=> R is transitive:

=> Assume that $R^2 \subseteq R$. R^2 means that for an arbitrary ordered pair (x, z)$\in$A there is a y$\in$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$\subseteq$R, I know that xRy and yRz is true for an arbitrary (x, z)$\in$A. It follows that (x, z)$\in$R.

<= 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)$\ni$AxA((x,y)$\ni$R^2 then (x,y)$\ni$R, I can assume that there is an ordered pair, call it (x,z)$\ni$R^2. Since we assumed that R is transitive, it follows by modus ponens that (x,z)$\ni$R.

Now I'll try to prove: R is transitive <=> R^i $\subseteq$R, $\forall$i$\geq$1.

=> Assume R is transitive. To prove that R^i$\subseteq$R, for all i $\geq$1 we can use induction.

Base case: i=1 -> 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.

2. Nov 6, 2013

### Stephen Tashi

It that a typo?

$R^2$ is a set, so you shouldn't say it "means" something. The definition of a set tells you what it means for an element to be in that set. So you may say "To say an element $x$ is in $R^2$ means that ...".

3. Nov 6, 2013

### economicsnerd

^Agreed.

In particular, it's the set $R^2 = \{(x,z)\in A^2:\enspace \exists y\in A \text{ such that } xRy \text{ and } yRz\}$, and we use the notation $xR^2z$ as a shorthand for $(x,z)\in R^2$.