1
$\begingroup$

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?

$\endgroup$
4
  • 2
    $\begingroup$ "then, this means that x∈B and x∉D." Nitpick. Then this means there exists an $x$ so that $x \in B$ and $x \not \in D$. You can't introduce terms without .... introducing them. $\endgroup$
    – fleablood
    Feb 2 '20 at 1:59
  • 1
    $\begingroup$ You seem to be willy-nilly assuming $x$ is some sets on whim. You have to declare what $x$ is and stick to it. If $x \in B$ and $x \not \in D$ that that is your $x$. You can't just switch to $x$ being an element of $A\cup B$ of $C\cup D$. $\endgroup$
    – fleablood
    Feb 2 '20 at 2:11
  • 1
    $\begingroup$ If $x \in B$ but $x \not \in D$ then that is your $x$. So $x \in B$ so $x \in B\subset A\cup B\subset C\cup D$. So $x\in C$ or $x \in D$ but as $x$ is not $D$ we have $x\in C$. ...etc.... DO you see the difference in what I am saying from what you are saying? So as $x \in C$. But $C\sub A$ so $x \in A$. And this $x \in B$. So $x \in A\cap B$. But $A\cap B =\emptyset$ so that is our contradiction. $\endgroup$
    – fleablood
    Feb 2 '20 at 2:17
  • $\begingroup$ Proof by contradiction is counter-productive here (as it so often is). You want to show $B \subseteq D$: so pick $b \in B$ and work forwards from the hypotheses to show that $b \in D$. $\endgroup$
    – Rob Arthan
    Feb 2 '20 at 3:01
2
$\begingroup$

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

$\endgroup$
6
  • $\begingroup$ Why would you want to do a proof by contradiction, when the forward proof is so much simpler? $\endgroup$
    – Rob Arthan
    Feb 2 '20 at 3:03
  • $\begingroup$ Thanks so much! $\endgroup$
    – user743879
    Feb 2 '20 at 3:12
  • $\begingroup$ @Arthan Could you perhaps show how a direct proof can be used here? $\endgroup$
    – user743879
    Feb 2 '20 at 3:13
  • $\begingroup$ @RobArthan: You're probably right. For whatever reason, proving this by contradiction was the first thought that came to my mind. And once I saw that it works, I didn't think much more about it. But on the second thought, I agree that this can be easily proven directly. $\endgroup$
    – zipirovich
    Feb 2 '20 at 4:41
  • 2
    $\begingroup$ A direct proof would be to select a $x \in B$ and prove that $x \in D$. It's not hard. (if $x\in B$ then $x\not \in A\subset C$ but $x\in B\subset A\cup B$ so $x\in C\cup D$ but not in $C$ so in $D$.) But there's nothing wrong with a proof by contradiction. I don't know if the question was directed to zipirovich or Mmmmm... $\pi$ but I think in answering it's best to follow the OPs approach and guide what is needed. $\endgroup$
    – fleablood
    Feb 2 '20 at 8:06
1
$\begingroup$

Before attempting a proof draw a Venn diagram:

enter image description here

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

$\endgroup$
1
$\begingroup$

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

enter image description here

$\endgroup$

Your Answer

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