Not sure if this set theory proof attempt involving contradiction is valid

Question

I have recently started studying set theory, so I wanted to try out some exercises to test my understanding. When I came across one of the questions, I have found it quite tricky to tackle, so I tried using proof by contradiction to try and prove it. However, I'm not sure if this proof that I came up with makes sense.

The question asked me the following:
Let $A,B,C \text{ and }D$ be four sets. $$\text{Prove that if } A \cup B \subseteq C \cup D, A \cap B = \emptyset \text{ and } C \subseteq A \text{, then } B \subseteq D.$$ To begin with, I assumed that $B \nsubseteq D$ (to make use of the proof by contradiction technique), and proceeded like so.

Assume $B \nsubseteq D$. Then, this means that there exists an $x \in B$ and $x \notin D$. However, since $A \cup B \subseteq C \cup D$, we can also assume that $(x \in A \text{ or } x\in B) \text{ and } (x \in C \text{ or } x\in D)$. So, this implies that $x \in (A \cup B) \cap (C \cup D)$. Since $C \subseteq A$ is a given piece of information, then $x \in C \text{ and } x \in A$. So, $x \in A \cap C$, which means that $x \notin B$ and this implies that $x \in D$. This is a condradiction. Therefore it must be the case that $B \subseteq D$. ∎

Would this be a valid proof?

Answer 1

Even though proving this statement by contradiction is a good idea, your "proof" presented here, unfortunately, doesn't make sense. Let's walk through your work step-by-step until we hit the major mistake in it.

Assume $B\not\subseteq D$.

Good start. I would wanna do a proof by contradiction too.

Then, this means that $x\in B$ and $x\notin D$.

This is a bit of a problem. Which $x$? What is this $x$ that you're talking about? You never introduced any $x$ before. The correct statement here should be: "Then, this means that there exists some $x$ such that $x\in B$ and $x\notin D$."

However, since $A\cup B\subseteq C\cup D$, we can also assume that $(x\in A \text{ or } x\in B) \text{ and } (x\in C \text{ or } x\in D)$. So, this implies that $x\in (A\cup B)\cap(C\cup D)$.

This is, technicaly speaking, not wrong, but it's too convoluted. And actually, the word "assume" is not appropriate here. We don't need to assume this, because we know this. Remember that by our choice of $x$ we know that $x\in B$, therefore $x\in A\cup B=(A\cup B)\cap(C\cup D)$, where the latter equality is true because it's given that $A\cup B\subseteq C\cup D$.

Since $C\subseteq A$ is a given piece of information, then $x\in C$ and $x\in A$.

And this is the mistake that breaks your argument. It's true that, by definition of set inclusion, $C\subseteq A$ means that any element of $C$ also belongs to $A$. But calling this element "$x$" is a serious mistake, because earlier you assigned the name of $x$ to something else. By using the same name $x$ here again, you're effectively talking about the same element. So you're saying that the same $x$ that you mentioned before also belongs to $C$ and (as a consequence) to $A$. Not only is it a logical mistake in general, but in this problems this is actually impossible: you can't have the same $x$ to be in $B$ as stated above and in $A$ as stated here, because we're given that $A\cap B=\varnothing$.

From this point, unfortunately, the rest of the solution doesn't matter …

But you have the right ideas in your work that can be turned into a valid proof! Hint: to reach a contradiction, demonstrate that this $x$ is not in $C\cup D$.

Answer 2

Before attempting a proof draw a Venn diagram:

For a direct proof it helpful if you know some rules/laws so that you don't have to check whether each element of $B$ is in $D$ - you can operate at a higher level.

Now the Venn diagram doesn't include $D$, but somehow $C \cup D$ has to "cover" $A \cup B$. But $C$ is disjoint from $B$ so can't expect it to "cover" any of $B$. So it is all up to $D$ to "cover" $B$.

One approach is to let $U = A \cup B \cup C \cup D$ be the universal set.
Can you now get 'something going' with the complement $\overline C$ of the set $C$?

Answer 3

An attenpt at showing graphically the logical structure of the proof by contradiction