Relation closures proof

[Terrell]

Homework Statement

Suppose R1 and R2 are relations on A and R1 ⊆ R2.
Let S1 and S2 be the transitive closures of R1 and R2 respectively.
Prove that S1 ⊆ S2.
Please check my proof and please explain my mistakes. thank you for taking the time to help.

Homework Equations

N/A

The Attempt at a Solution

1. Suppose R1⊆ R2 and S1 and S2 are transitive closures of R1 & R2 respectively.
2. Suppose (x,y)∈S1 such that S1=∩F where F={T⊆A x A| R1⊆T and T is transitive}
3. case1:
3.1) Suppose (x,y)∈S1 and (x,y)∉R1 such that ∃z∈A((x,z)∈R1 ∧ (z,y)∈R1) because S1 is transitive.
3.2) because R1⊆T, (x,z)∈T and (z,y)∈T. since T is transitive (x,y)∈T and S1⊆T.
3.3) since R1⊆R2, then (x,z)∈R2 and (z,y)∈R2.
3.4) let S2=∩G where G={U⊆AxA| R2⊆U and U is transitive}
3.5) since R2⊆U, (x,z)∈U, (z,y)∈U, and U is transitive then (x,y)∈U.
3.6) since U is arbitrary, ∀U∈G((x,y)∈U) then (x,y)∈∩G=S2 or (x,y)∈S2
4. case2:
4.1) Suppose (x,y)∈R1 and (x,y)∈S1
4.2) since R1⊆R2 then (x,y)∈R2
4.3) since R2⊆S2 then (x,y)∈S2
5. Therefore, S1⊆S2.
QED

 

[andrewkirk]

In line 3.1 you cover the case where (x,y)∈S1 and (x,y)∉R1 and there exists a third element z such that x R1 z and z R1 y - ie where the chain of R1 relations connecting x transitively to y has length two. You do not appear to have covered the cases where the chain is longer than two, eg where we need z and w such that x R1 z, z R1 w, w R1 y. You may need to use induction on the length of the chain to fill in this gap, unless a more direct approach can be found.

At line 3.2 you refer to T, which is undefined. The letter T is only used inside a set definition, in line 2, and has no meaning outside of the scope of that set (which is F, and not referred to in line 3.2).