0
$\begingroup$

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!

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ Feb 11 '20 at 18:44
2
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Lino
    Feb 12 '20 at 13:09
  • $\begingroup$ 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 $\endgroup$
    – user289143
    Feb 12 '20 at 13:21
1
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Lino
    Feb 12 '20 at 13:28
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

Below an almost completed proof

enter image description here

$\endgroup$
1
  • 2
    $\begingroup$ 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. $\endgroup$
    – mrtaurho
    Feb 11 '20 at 19:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.