Prove that a set is a subset of another

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!

• No, do not start with the statement to be proved and derive a tautology. That is considered very sloppy mathematics. It can also lead to errors if your steps aren't reversible. Feb 11 '20 at 18:44

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)$$.

• So I can understand the explanation, after drawings a Venn diagram for it. So basicaly as a predicate it would look like: x $\in$ A and x $\in$ C $\rightarrow$ $x \in (A \cup B) \cap (C \cup D)$ . But how could I say using logic that the statment is true.
– Lino
Feb 12 '20 at 13:09
• Using logic you can see the answer from @Siddharth Bhat. However, I think that solve your problem using the definition of union and intersection is the easiest way Feb 12 '20 at 13:21

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)$$.

• I don’t see how the 2 are equivalent: $(a \land b) \lor (c \land d) = (a \lor c) \land (b \lor d)$ , after trying to come from one side to other I just go in circles.
– Lino
Feb 12 '20 at 13:28

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)$$

Below an almost completed proof

• It would be better to write out the proof using MathJax instead of including a picture. Pictures may not be legible, cannot be searched and are not view-able to some, such as those who use screen readers. Feb 11 '20 at 19:24