1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Relation closures proof

  1. Mar 17, 2017 #1
    1. The problem statement, all variables and given/known data
    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.
    2. Relevant equations

    3. 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.
  2. jcsd
  3. Mar 21, 2017 #2


    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    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).
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted