To prove $(S \circ R) - (T \circ R) \subseteq (S -T) \circ R $

Question

To prove $(S \circ R) - (T \circ R) \subseteq (S -T) \circ R $

Let $(a,c) \in (S \circ R) - (T \circ R)$. So $(a,c) \in (S \circ R)$ and $(a,c) \notin (T \circ R)$.

Since $(a,c) \in (S \circ R)$ so $\exists b \in B$ such that $(a,b) \in R$ and $(b,c) \in S$.

Also $(a,c) \notin (T \circ R)$. So $\forall b \in B$ either $(a,b) \notin R$ or $(b,c) \notin T$ , but (a,b) does belong to R for some b so we have other case. So $(b,c) \notin T$. So $(b,c) \in S -T$ . hence $(a,c) \in (S-T) \circ R$

Please correct if wrong $$Thanks$$

Answer 1

That looks okay. Since I'm a little bored, let's put your proof into fitch style.$\def\fitch#1#2{~~\begin{array}{|l}#1\\\hline#2\end{array}}$

Let $(a,c) \in (S \circ R) \smallsetminus (T \circ R)$. So $(a,c) \in (S \circ R)$ and $(a,c) \notin (T \circ R)$.

Since $(a,c) \in (S \circ R)$ so $\exists b \in B$ such that $(a,b) \in R$ and $(b,c) \in S$.

Also $(a,c) \notin (T \circ R)$. So $\forall b \in B$ either $(a,b) \notin R$ or $(b,c) \notin T$ , but $(a,b)$ does belong to $R$ for some $b$ so we have other case. So $(b,c) \notin T$. So $(b,c) \in S \smallsetminus T$ . hence $(a,c) \in (S\smallsetminus T) \circ R$

[edit: Where did $B$ come from?]

$$\fitch{~1.~[S]\\ ~2.~[T]\\ ~3.~[R]}{\fitch{~4.~[a]\\ ~5.~[c]}{\fitch{~6.~(a,c)\in (S\circ R)\smallsetminus (T\circ R)\qquad\textsf{Assume}}{~7.~(a,c)\in S\circ R\wedge(a,c)\notin(T\circ R)\qquad\textsf{Defn. Set Difference (6)}\\~8.~(a,c)\in S\circ R\qquad\textsf{Conjunction Elimination (7)}\\~9.~\exists z: (a,z)\in R\wedge (z,c)\in S\qquad\textsf{Defn Composition (8)}\\10.~(a,c)\notin T\circ R\qquad\textsf{Conjunction Elimination (7)}\\11.~\neg\exists z:(a,z)\in R\wedge(z,c)\in T\qquad\textsf{Defn Composition (10)}\\12.~\forall z:(a,z)\notin R\vee(z,c)\notin T\qquad\textsf{Quantifier Duality (11)}\\\fitch{13.~[b]~(a,b)\in R\wedge (b,c)\in S\qquad\textsf{Existential Elimination (9)}}{14.~(b,c)\in S\qquad\textsf{Conjunction Elimination (13)}\\15.~(a,b)\in R\qquad\textsf{Conjunction Elimination (13)}\\16.~(a,b)\notin R\vee (b,c)\notin T\qquad\textsf{Universal Elimination (12)}\\17.~(b,c)\notin T\qquad\textsf{Disjunctive Syllogism (15,16)}\\18.~(b,c)\in S\wedge(b,c)\notin T\qquad\textsf{Conjunctive Introduction (14,17)}\\19.~(b,c)\in S\smallsetminus T\qquad\textsf{Defn Set Difference}\\20.~(a,b)\in R\wedge (b,c)\in S\smallsetminus T\qquad\textsf{Conjunctive Introduction (15,19)}}\\21.~\exists z:(a,z)\in R\wedge (z,c)\in S\smallsetminus T\qquad\textsf{Existential Introduction (13,20)}\\22.~(a,c)\in (S\smallsetminus T)\circ R\qquad\textsf{Defn Composition (21)}}\\23.~ (a,c) \in (S \circ R) \smallsetminus (T \circ R)\to(a,c) \in (S\smallsetminus T) \circ R\qquad\textsf{Conditional Introduction (6,22)}}\\{24.~\forall x\forall y: (x,y) \in (S \circ R) \smallsetminus (T \circ R)\to(x,y) \in (S\smallsetminus T) \circ R\qquad\textsf{Universal Introductions (4,5,23)}}\\25.~(S \circ R) \smallsetminus (T \circ R)\subseteq (S\smallsetminus T) \circ R\qquad\textsf{Defn Improper Subset (24)}}$$

Yeap, that checks out.