Proving a Subset Identity: If $A\subseteq B$ and $C\subseteq D$, then $A\cap C\subseteq C\cap D$ and $A\cup C\subseteq C\cup D$

Question

Working on part A of this problem:

Prove each of the following results without using Venn diagrams of membership tables. (Assume a universe $\mathscr U$.)

a) If $A\subseteq B$ and $C\subseteq D$, then $A\cap C\subseteq C\cap D$ and $A\cup C\subseteq C\cup D$.
b) $A\subseteq B$ if and only of $A\cap\overline B=\emptyset$.
b) $A\subseteq B$ if and only of $\overline A\cup B=\emptyset$.

I worked out the first part like this:

1. If $A$ is a subset of $B$ then $\forall~x~[x\in A \implies x\in B]$

2. Same goes for $C$ being a subset of $D$ (If $x$ is in $C$ it is in $D$)

3. If $A\cap C$, then $x\in A \wedge x\in C$

4. $x\in B ~\wedge x\in D$ (From steps $1$ and $2$)

5. Since $A\cap B \implies B\cap D$ we can say $A\cap C \subseteq B\cap D $

I'm wondering if I've made any errors in proving the first part of the consequent?

Answer 1

• Starting with $(3)$ I would instead assume $x \in A\cap C$.

  • Then argue as you did (...so $x \in A \land x\in C$; using this together with the implications in $(1), (2)$ from modus ponens we get $x\in B$ and $x\in D$.
  • Conclude $x \in B\cap D$.

• Therefore $x \in A \cap C \rightarrow x \in B\cap D$. (Having assumed $x \in A\cap C$, we derived $x \in B\cap D.$, Hence this implication is justified.)

• Finally we conclude $A\cap C \subseteq B\cap D$.