# Prove, that for all sets A, B, C and D, in which $A \subseteq B$ and $C \subseteq D$, given formula: $A \setminus D \subseteq B\setminus C$ is true.

Knowing $$A \subseteq B \Leftrightarrow (x\in A \Longrightarrow x\in B)$$ $$C \subseteq D \Leftrightarrow (x\in C \Longrightarrow x\in D)\\$$ I tried to prove, that for any $$y\in A$$ and $$z\in D$$, given formula $$A \setminus D \subseteq B\setminus C$$ is true, but I got stuck almost at the beginning, when I tried to show $$(y,z)\in A\setminus D\equiv \{y\in A\}\wedge \{z\notin D\}$$ and I am not really sure what should I do now. Although I know, that if $$x\notin D$$, then $$x\notin C$$, but it really leads me to nowhere. I would like to see a formal proof of this. Thanks in advance.

• It's supposed to be $y\in A\setminus D\iff \{y\in A\}\wedge \{y\notin D\}$. No $z$ anywhere. – Arthur Nov 25 '18 at 14:47
• Thank you, I was trying to prove it the same way as I did for $A\cup C \subseteq B\cup D$, that's why I used two elements. – whiskeyo Nov 25 '18 at 15:01

The problem is in your assumption: $$(y,z) \in A \setminus D$$

When showing membership for a non-relational set we suppose a single element in the set, not an ordered pair. This is how it should go: $$x\in (A\setminus D)\implies x\in A \land x \notin D$$

Notice, $$C\subseteq D \implies (\forall x)[(x \in C)\rightarrow (x \in D)]$$, consequently, by modus tollens $$x\notin D \implies x\notin C$$

Since $$A \subseteq B \land C \subseteq D$$, then: $$(x\in A \implies x\in B) \land (x\notin D \implies x\notin C)$$

Therefore, $$x \in A \setminus D \implies x\in B \setminus C$$ $$A\setminus D \subseteq B\setminus C$$

$$C \subseteq D \Leftrightarrow D^{\complement} \subseteq C^{\complement}$$

So $$A \setminus D = A \cap D^{\complement} \subseteq B \cap C^{\complement} = B \setminus C$$ as $$A \subseteq B$$ as well, and if we replace two sets in the intersection by posibly larger sets, we get a possibly larger set.