# Proofing an uncertain theorem to verify it's truth?

1. Sep 3, 2014

### pandaBee

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 $(a,c) \in (S\T ) ◦ R$ then, we can choose a $b \in B$ such that,

$\exists b \in B\ ((a,b) \in R\land(b,c) \in (S\T))$

Therefore,
$(a,b) \in R$
$(b,c) \in S$
$(b,c) \notin T$

But this means that $(a,c) \in (S\circ R)$

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

Suppose $(a,c) \in (T\circ R)$ Then we instantiate a $b \in B$, say, b' such that:
$(a,b') \in R$
$(b',c) \in T$
-------------

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. Sep 3, 2014

### HallsofIvy

Staff Emeritus
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.