Prove that a set is a subset of another

Question

Prove that a set is a subset of another, using predicates and (if needed) quantifiers:

(A $\cap$ C) $\cup$ (B $\cap$ D) $\subseteq$ (A $\cup$ B) $\cap$(C $\cup$ D)

Should I start with the whole statement, and rewrite it using predicates and logic until a tautology comes out or am I supposed to somehow come from the left side of the $\subseteq$ to the right side?

I tried the first option and only ended up going in circles and the second one I’m not sure how it’s supposed to look like.

Thanks!

Answer 1

Let $x \in (A \cap C) \cup ( B \cap D)$. Then $x \in A \cap C$ or $x \in B \cap D$.

Suppose $x \in A \cap C$, then $x \in A$ and $x \in C$. Therefore $x \in A \cup B$ and $x \in C \cup D$, i.e. $x \in (A \cup B) \cap (C \cup D)$.

Suppose $x \in B \cap D$, then $x \in B$ and $x \in D$. Therefore $x \in A \cup B$ and $x \in C \cup D$, i.e. $x \in (A \cup B) \cap (C \cup D)$.

It follows that $(A \cap C) \cup ( B \cap D) \subseteq(A \cup B) \cap (C \cup D)$.

Answer 2

You can write the predicate for the left hand side and the right hand side, then attempt to show one implies the other. The answers are in a spoiler tag so you can try them out yourself :)

• find some predicate $P$ which models $x \in (A \cap C) \cup (B \cap D)$

  $P \equiv (x \in A \land x \in C) \lor (x \in B \land x \in D)$

• Now find a predicate $Q$ for $x \in (A \cup B)\cap (C \cap D)$

  $P \equiv (x \in A \lor x \in B) \land (x \in C \lor x \in D)$

• For subsets relations $L \subseteq R$, the predicate is: $\forall x \in L \implies x \in R$. That is, prove that $P \implies Q$.

To show that $P \implies Q$:

the rule that will come in handy is the distributivity of $(\lor)$ over $(\land)$: $(a \land b) \lor (c \land d) = (a \lor c) \land (b \lor d)$.

Answer 3

Use the definition of a subset.

$B$ is a subset of $A$ if for all $x\in B$, $x\in A.$

Now let $x\in (A\cap C)\cup(B\cap D)$. Then either $x\in (A\cap C)$ or $x\in (B\cap D)$

Case I: $x\in (A\cap C)$

Then $x\in A$ and $x\in C$. Thus $x\in (A\cup B)$ and $x\in (C\cup D)$. Thus $x\in (A\cup B) \cap (C\cup D)$.

Case II: $x\in (B\cap D)$

Then $x\in B$ and $x\in D$. Thus $x\in (A\cup B)$ and $x\in (C\cup D)$. Thus $x\in (A\cup B) \cap (C\cup D)$.

So in either case $x\in (A\cup B) \cap (C\cup D)$. Therefore $(A\cap C)\cup(B\cap D) \subseteq (A\cup B) \cap (C\cup D)$

Answer 4

Below an almost completed proof