1
$\begingroup$

I need to prove that $A ⊂ B$ if and only if $A − B = ∅$. I have the following "proof":

$$ A \subset B \iff A - B = \emptyset$$ proof for $\implies:$

$$\forall x \in A, x \in B$$

Therefore,

$$A - B = \emptyset$$

proof for $\impliedby$:

If $$A - B = \emptyset$$ then $$\forall x \in B, x \in A$$ since $\forall x \in B, x \in A$,

$$ A \subset B $$

However the whole thing seems to be incredibly "fragile" and relies on circular logic (see how I just switched the sets in the for all statements)

Is this a valid proof? Is there a better way to write it?

$\endgroup$
6
  • 1
    $\begingroup$ The last $\forall x \dots$ should be $\forall x \in A, x \in B$. $\endgroup$
    – Bernard
    Mar 1, 2015 at 11:21
  • $\begingroup$ @Bernard Then wouldn't that make my proof the same for both? $\endgroup$
    – Secret
    Mar 1, 2015 at 11:25
  • $\begingroup$ agree with Bernard $\endgroup$
    – user 1
    Mar 1, 2015 at 12:47
  • $\begingroup$ The statement is incorrect. Alberto's answer proves the correct statement (with $\subseteq$ instead of $\subset$), but for some reason doesn't point out this important difference. $\endgroup$ Mar 24, 2015 at 9:28
  • 1
    $\begingroup$ @PeterTaylor "Some authors use the symbols ⊂ and ⊃ to indicate subset and superset respectively; that is, with the same meaning and instead of the symbols, ⊆ and ⊇" en.wikipedia.org/wiki/Subset I personally find it incredibly odd for a very specific and well defined language (math) to be able to use interchangeable symbols like that. My professor uses . $\endgroup$
    – Secret
    Mar 24, 2015 at 10:06

5 Answers 5

8
$\begingroup$

I like using "proof by contradiction" for this one, because it is logically and intuitively clear.

  • (⇒) Assume $A\subseteq B$. By contradiction, suppose $A \setminus B \ne \varnothing$. Therefore there exists $x \in A \setminus B$. Therefore $x \in A$ and $x \notin B$ — a contradiction. As a result, $A \setminus B = \varnothing$.

  • (⇐) Assume $A \setminus B = \varnothing$. By contradiction, suppose $A \nsubseteq B$. Therefore there exists $x \in A$ such that $x \notin B$. Therefore $x \in A \setminus B$ — a contradiction. As a result, $A \subseteq B$.

As a result, $A \subseteq B$ if and only if $A \setminus B = \varnothing$.   ◻

$\endgroup$
3
  • $\begingroup$ Actually, it is a proof by contraposition. $\endgroup$
    – Bernard
    Mar 1, 2015 at 11:24
  • $\begingroup$ @Bernard: It is conventionally called proof by contradiction as he correctly states. It's called that because the goal is to derive a contradiction from the additional assumption that the desired conclusion is false. I think you know that. $\endgroup$
    – MPW
    Mar 1, 2015 at 11:29
  • $\begingroup$ I don't see the point, when proving ¬Q -> ¬P, and say ‘suppose P is true and Q false, then deduce P is false’, to call that a proof by contradiction, if you don't need to suppose P true to deduce P false. $\endgroup$
    – Bernard
    Mar 1, 2015 at 12:07
3
$\begingroup$

One might proceed more directly by noting that $A\subseteq B$ is equivalent to $$\forall x,(x\in A)\implies(x\in B),$$ which is equivalent to $$\forall x,\neg(x\in A)\vee(x\in B).$$ The negation of this is $$\exists x:(x\in A)\wedge\neg(x\in B),$$ which is equivalent to $$\exists x:(x\in A)\wedge(x\notin B),$$ which is equivalent to $$\exists x:(x\in A\setminus B).$$ Renegating then shows us that $A\subseteq B$ is equivalent to $$\forall x,\neg(x\in A\setminus B),$$ at which point we're basically done.

$\endgroup$
1
$\begingroup$

I think your proof is Ok. I just add more details.

$ (\Rightarrow) $; Suppose $ A\subset B $. Then $ \forall x\in A,x\in B $. Therefore if $ x\notin B $ then $ x\notin A $. That is if $ x\in B^{c} $ then $ x\in A^{c} $. Since $ A-B=A\cap B^{c} $ we have that $ A-B=\varnothing $.

$ (\Leftarrow) $; Conversely suppose $ A-B=\varnothing $. So $ A\cap B^{c}=\varnothing $. Therefore $ \forall x\in A,x\notin B^{c} $. Hence $ \forall x\in A,x\in B $. So we have that $ A\subset B $.

$\endgroup$
1
$\begingroup$

Your proof is valid if one can follow the steps, but the step from $A-B=\emptyset$ to $\forall x\in B, x\in A$ looks a bit hasty and might need some clarification. For example using the definition of $A-B$ being the set of $x: x\in A \land x \notin B$, which in turn is equivalent to $x: x\in B\rightarrow x\in A$ ($\phi\rightarrow\psi$ being the same as $\neg\phi\lor\psi$).

$\endgroup$
0
$\begingroup$

Informally:
$A - B$ is all elements of $A$ out of $B$.
and
$A \subseteq B$ means $A$ is surrounded by $B$.
so $\cdots$

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .