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: Proofing an uncertain theorem to verify it's truth?

  1. Sep 3, 2014 #1
    1. The problem statement, all variables and given/known data
    Suppose R is a relation from A to B and S and T are relations from
    B to C.
    Must it be true that (S \ T ) ◦ R ⊆ (S ◦ R) \ (T ◦ R)?

    3. The attempt at a solution
    I assume that (S \ T ) ◦ R ⊆ (S ◦ R) \ (T ◦ R) is true and attempt to prove it (if I run into a contradiction I know that it is false)

    Part 1
    let [itex](a,c) \in (S\T ) ◦ R[/itex] then, we can choose a [itex]b \in B[/itex] such that,

    [itex]\exists b \in B\ ((a,b) \in R\land(b,c) \in (S\T))[/itex]

    [itex](a,b) \in R[/itex]
    [itex](b,c) \in S[/itex]
    [itex](b,c) \notin T[/itex]

    But this means that [itex](a,c) \in (S\circ R)[/itex]

    Part 2
    To prove that [itex](a,c) \notin (T\circ R)[/itex] we employ proof by contradiction:

    Suppose [itex](a,c) \in (T\circ R)[/itex] Then we instantiate a [itex]b \in B[/itex], say, b' such that:
    [itex](a,b') \in R[/itex]
    [itex](b',c) \in T[/itex]

    I've hit a dead-end here and I'm not sure how to progress any further. As an exercise I wanted to refrain from plugging-and-chugging random scenarios into the theorem to prove it's veracity and decided instead to reach a contradiction within a contradiction to prove that the theorem is in fact, false.

    However, I haven't (or at least I don't believe) that I have reached a contradiction in the proof, I'm just at a dead end (or at least that's how it seems).

    Any insight would be much appreciated.
    1. The problem statement, all variables and given/known data

    2. Relevant equations

    3. The attempt at a solution
  2. jcsd
  3. Sep 3, 2014 #2


    User Avatar
    Science Advisor

    What does "R\S" mean? "Relations" are sets of pairs so I would assume that "R\S" is the set operation "all members of R that are not in S" but that can't be true here because NO member of R is in S.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted