Prove that if $A \setminus B = \emptyset$, then $A \subseteq B$.

The Venn Diagram helped me to visualize what I'm trying to show (thanks @GA316), but the book asks for a written proof (step by step) by contradiction. Sorry if I wasn't more specific at first, is just that I've had many troubles in the past with proofs, somehow I have many ideas but I can't seem to connect them to get to the final proof.

This is what I have so far: $P \rightarrow Q$ is equivalent to $\neg Q \rightarrow \neg P$ contraposition (thanks @The Chaz 2.0)

With P: $ A \setminus B = \emptyset$ and Q: $ A \subseteq B$

so $ \neg Q \equiv A \not\subseteq B\ , \exists x \in A : x \notin B $

be $ t: t \in A \wedge t \notin B $ ...is this right?

as this is the definition for $A \setminus B \ne \emptyset$ ...is this right?

$\therefore \neg Q \rightarrow \neg P \equiv A \not\subseteq B\ \rightarrow A \setminus B \ne\emptyset$

I have many concerns regarding if I'm using the correct notation. I am trying to learn this by myself and have nobody else to ask.

Also, sorry if it took me too long to update, I just started learning about this LaTEX notation.

Thank you very much in advance, you guys are so nice and helpful. You made me feel very welcomed and sure I need to read more about the rules and instructions for using this site.

  • 3
    $\begingroup$ group-theory ?!? $\endgroup$ – Emanuele Paolini Nov 19 '13 at 17:52
  • 3
    $\begingroup$ Welcome to Math.SE! Please, consider updating your question to include what you have tried and where you are getting stuck. That way, people on this site will know exactly what help you need. $\endgroup$ – Brett Frankel Nov 19 '13 at 18:12
  • $\begingroup$ Thank you for the hints and help, I'm still working on it. I'll update if I consider that I got completely stuck . $\endgroup$ – Sarah Nov 19 '13 at 18:29
  • 2
    $\begingroup$ @Emanuele: In a lot of languages (e.g. Hebrew) the natural language words for set and group are often synonymous, and not only that -- when people would translate they would think that group theory is a better fit than set theory. $\endgroup$ – Asaf Karagila Nov 19 '13 at 19:08
  • $\begingroup$ So I'm still confused, in english What's the right classification set theory or group theory? The chapter in the book is called "conjuntos" (spanish) so I thought the translation was "set". Thanks for bringing up the issue. $\endgroup$ – Sarah Nov 20 '13 at 7:42

HINT: Just follow the definitions. In order to show that $A\subseteq B$, you should let $x$ be an arbitrary element of $A$ and somehow use the hypothesis that $A\setminus B=\varnothing$ to show that $x\in B$. What if $x$ were not in $B$? Then you’d have $x\in A$ and $x\notin B$, which would tell you that $x$ is in ... what?

  • $\begingroup$ Thanks @Brian M. Scott the way you put it in words sounds great and make perfect sense when I read it but somehow I can't translate it to math sentences (Sorry...my bad, I know!). I'm definitively a newbie but I'm willing to work on it. $\endgroup$ – Sarah Nov 20 '13 at 7:32
  • $\begingroup$ @Sarah: By definition, if $x\in A$ and $x\notin B$, then $x\in A\setminus B$. But your hypothesis is that $A\setminus B=\varnothing$, so this is impossible. Thus, it cannot be the case that $x\notin B$, and of course that implies that $x\in B$. That completes the argument that if $x\in A$, then $x\in B$, which is what you need to show that $A\subseteq B$. $\endgroup$ – Brian M. Scott Nov 20 '13 at 18:55

Draw venn diagram of $A - B = A \cap B^c$. can you see when it will be empty?

  • $\begingroup$ Thanks @GA316, drawing the Venn Diagramam helped me a lot to picture the problem. $\endgroup$ – Sarah Nov 20 '13 at 7:33

Just for grins, you could prove the (logically equivalent) contrapositive, viz.

If $A$ is not a subset of $B$, then [$A$ "toss" $B$] is nonempty.

If $A$ is not a subset of $B$, then there is some element $x \in A$ that is not in $B$. Then when you "take away" all the things in $A$ that are/were in $B$, you have at least that element $x$ leftover.
So [$A$ "toss" $ B$] is not the emply set.

  • $\begingroup$ Thanks @The Chaz 2.0, this approximation was a little easier for me as an approach to the problem. Although I'm still concerned about my notation and formalism, hope is not too bad... $\endgroup$ – Sarah Nov 20 '13 at 7:37

Here is a complete proof in a calculational style: we start at the most complex side, and then just expand the definitions and simplify, and see where that leads us. \begin{align} & A \setminus B = \emptyset \\ \equiv & \qquad \text{"basic property of $\;\emptyset\;$"} \\ & \langle \forall x :: x \not\in A \setminus B \rangle \\ \equiv & \qquad \text{"definition of $\;\setminus\;$"} \\ & \langle \forall x :: \lnot (x \in A \land x \not\in B) \rangle \\ \equiv & \qquad \text{"logic: DeMorgan -- there is not much else we can do"} \\ & \langle \forall x :: x \not\in A \lor x \in B \rangle \\ \equiv & \qquad \text{"logic: $\;\lnot P \lor Q\;$ is one of the ways to write $\;P \Rightarrow Q\;$"} \\ & \langle \forall x :: x \in A \Rightarrow x \in B \rangle \\ \equiv & \qquad \text{"definition of $\;\subseteq\;$"} \\ & A \subseteq B \\ \end{align}

This completes the proof. (Strictly speaking, this even proves the stronger statement $\;A \setminus B = \emptyset \;\equiv\;A \subseteq B\;$.)


It seems to me you could benefit from writing a proof in multiple stages. Here's an example of my own thought processes on this problem.

  1. Translate the math symbols into English (or Spanish, as the case may be). I literally read "If $A \setminus B = \emptyset$, then $A \subseteq B$" as "If A with the set B removed is empty, then A is a subset of B."

  2. "Understand" the problem. For me with this problem I imagine myself being given A and told to remove all elements of B from it. I find I'm left with nothing, and I remark to myself that each element of A must have been in B, so A must have been contained in B.

  3. Find a proof without symbols. "each element of A must have been in B"--why? Maybe the intuition in (2) is wrong and there is some element of A that's not in B. But then I wouldn't have removed it from A when I removed all elements of B, so I wouldn't have ended up with the empty set, a contradiction.

  4. Translate your proof into math symbols. I'll do it sentence by sentence:

    • "there is some element of A that's not in B." -> "Pick $x \in A$. Suppose $x \not \in B$".
    • "But then I wouldn't have removed it from A when I removed all elements of B" -> "But then it would be in A minus B" -> "$x \in A \setminus B$"
    • "so I wouldn't have ended up with the empty set" -> "$A \setminus B \neq \emptyset$".
    • "a contradiction" -> "so $x \not \in B$ was false, so $x \in B$".
    • "A must have been contained in B." -> "so $A \subset B$".

In all, the proof is now: "Pick $x \in A$. Suppose $x \not \in B$. Then $x \in A \setminus B$. But then $A \setminus B \neq \varnothing$, so $x \not \in B$ was false, so $x \in B$. So $A \subset B$".

This is pretty close to formal logic already. I'm not sure what system you're using, but here's one possible translation to more formal logic:

  1. $A \setminus B = \emptyset$
  2. $x \in A \Rightarrow x \in B$:
    1. $x \in A$
    2. If $x \not \in B$:
      1. $x \in A \setminus B$ (definition of $A \setminus B$)
      2. $A \setminus B \neq \emptyset$ (definition of $\emptyset$)
      3. Contradiction between 1 and 2.2.2.
    3. $\therefore x \in B$
  3. $A \subset B$ (definition of $\subset$)

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.