6
$\begingroup$

Question:

Prove that if $ \ A\cup B \subseteq C \cup D,\ A \cap B =$ ∅ $\land \ C \subseteq A \implies B \subseteq D$.

My attempt:

Let $ \ x\in B \implies x \in A \cup B \implies x \in C \cup D \because A\cup B \subseteq C \cup D$.

Now, $ x \in C \lor x\in D$. If $\ x \in C \implies x \in A \because C \subseteq A$. But that's not possible $\because x \notin A \cap B$, in particular $ x \notin A$. So we must have $ x \in D$.

I found this proof a little challenging. Not quite sure if this is the correct way to prove it. Is my logic correct?

$\endgroup$
4
  • 1
    $\begingroup$ Looks good to me! $\endgroup$
    – John Griffin
    Aug 18, 2017 at 1:30
  • 1
    $\begingroup$ That looks good to me! $\endgroup$
    – emma
    Aug 18, 2017 at 1:30
  • 1
    $\begingroup$ Thirded. Phrased colloquially: You're given that B is somehow interspersed among C unioned with D; but B avoids A, which means it also avoids everything within A: specifically, B avoids C. So, all of B is in D. $\endgroup$
    – Benjamin Dickman
    Aug 18, 2017 at 1:33
  • $\begingroup$ If you feel somewhat messy, drawing a Venn diagram helps. Also, if you have a firm understanding of logic(predicate logic), you can easily prove this without drawing any diagram(even without having a picture in mind), just by formal deduction. $\endgroup$
    – Eric
    Aug 18, 2017 at 2:49

2 Answers 2

Reset to default
2
$\begingroup$

It is correct. Well done.

Perhaps a bit of suggested modification in the "But that's not possible part" to make it clearer.

Since we started with $x \in B$, if $x \in A$, then $x \in A \cap B$ which is not possible, as $A \cap B = \phi$.

$\endgroup$
0
$\begingroup$

Theorem. Let $A,~B,~C,~D$ be (any) sets. If $A\cup B\subseteq C\cup D$ and $A\cap B=\emptyset$ and $C\subseteq A$, then $B\subseteq D$.

Proof.(in much detailed, giving you the instruction that what should you do in every step)

Let $A,~B,~C,~D$ be sets. Claim: $A\cup B\subseteq C\cup D\wedge A\cap B=\emptyset\wedge C\subseteq A\to B\subseteq D$.

Suppose $A\cup B\subseteq C\cup D\wedge A\cap B=\emptyset\wedge C\subseteq A$. Claim: $B\subseteq D$, namely $\forall x,x\in B\to x\in D$.

Let $x$ in the domain of discourse, claim: $x\in B\to x\in D$.

Suppose $x\in B$(claim $x\in D$). Then $x\in A\vee x\in B$. Hence $x\in A\cup B$. Since $A\cup B\subseteq C\cup D$, we have $x\in C\cup D$, namely $x\in C\vee x\in D$.

  • If $x\in D$, then done.
  • Suppose $x\in C$. by the hypothesis that $C\subseteq A$, we have $x\in A$. Hence $x\in B\wedge x\in A$, namely $x\in A\cap B$. However, by the hypothesis, $A\cap B=\emptyset$. So it is a contradiction(Reductio Ad Absurdum). It is not the case that $x\in C$.

(The following are the ending steps, which is usually omitted in mathematical literature.) Hence we have shown that $x\in B\to x\in D$. Since $x$ is arbitrary, we have shown that $\forall x,x\in B\to x\in D$, which is $B\subseteq D$.

Hence we have shown that $A\cup B\subseteq C\cup D\wedge A\cap B=\emptyset\wedge C\subseteq A\to B\subseteq D$. Since the sets $A,B,C,D$ are all arbitrary, we have proved the theorem.

$\endgroup$

You must log in to answer this question.