4
$\begingroup$

Prove that $A \subseteq B$ if and only if $A \cap \overline{B}=\emptyset.$


Proof:

Since $A \cap \overline{B}$ implies that $x \in A$ but $x \notin B$, whilst $A \subseteq B$ implies that $x \in A$ and $x \in B$, we have a contradiction, since $x \in B$ and $x \notin B$. Thus, $A \cap \overline{B}=\emptyset.$


Is this sufficient? How else can this be proved?

$\endgroup$
  • 2
    $\begingroup$ What is $\overline{B}$? Do you mean it to be the complement of $B$? If so, we usually use the notation $B^{c}$ for the complement of $B$, as $\overline{B}$ is usually reserved for the closure of $B$ (in a topological space). $\endgroup$ – layman Mar 16 '15 at 1:05
  • $\begingroup$ @user46944 Yes it is the complement, sorry this is the notation used in my course $\endgroup$ – user265675 Mar 16 '15 at 1:05
  • 1
    $\begingroup$ @crash Conflicting notations bother me lol. Although as you said, being extra clear counteracts any conflict. $\endgroup$ – layman Mar 16 '15 at 1:20
  • 2
    $\begingroup$ @crash Off topic, but I'm sorry you had such a bad experience with your $\pi$ day question. I've had one or two bad experiences with questions I've asked, too. I hope you'll reconsider staying on the site (I read your about me). What kind of a site will this become if only the sticklers for the rules remain? $\endgroup$ – layman Mar 16 '15 at 1:25
  • 2
    $\begingroup$ @Meryll I just pulled up this problem from a long while back that is somewhat similar to proving the kind of question you just asked. It may help to read through it to better understand how to prove if and only statements, how the flow of your proof(s) should look, etc. $\endgroup$ – Daniel W. Farlow Mar 16 '15 at 1:41
3
$\begingroup$

You have to prove an "if and only if" statement. When you have to prove "$p$ if and only if $q$", it always means you have to prove two statements. You need to prove that $p \implies q$ and $q \implies p$ (where $p$ is the statement $A \subseteq B$ and $q$ is the statement $A \cap \overline{B} = \emptyset$).


Let's prove $p \implies q$ first. To prove $p \implies q$, we need to assume $p$ is true, and prove $q$ is true. So we need to assume $A \subseteq B$. Let's prove $A \cap \overline{B} = \emptyset$. It seems like the easiest way to prove this is by contradiction. Suppose that $A \cap \overline{B} \neq \emptyset$. Then there is some $x \in A \cap \overline{B}$. That means there is some $x$ such that $x \in A$ and $x \not \in B$. But we assumed $A \subseteq B$, which means for all $y \in A$, $y \in B$. But we just found an element $x$ in $A$ that is not in $B$. So we have an element that is both in $B$ and not in $B$, which is a contradiction. Thus, $A \cap \overline{B} = \emptyset$, as desired.


Now let's prove the $q \implies p$ direction. We have to assume $q$ and prove $p$. Suppose $q$ is true, i.e., $A \cap \overline{B} = \emptyset$. Let's prove $A \subseteq B$. To prove this, we need to show if $x \in A$, then $x \in B$. Let $x \in A$. We know $A \cap \overline{B} = \emptyset$, which means if $x \in A$, $x$ can't be in $\overline{B}$. But elements are either in $B$ or $\overline{B}$, since these two sets are complements of each other. That means $x \in B$, which is what we wanted to show. So $ A \subseteq B$, as desired.

$\endgroup$
  • $\begingroup$ Thank you, this is very clear. It has never been taught to me that this is the approach with proving if and only if statements. $\endgroup$ – user265675 Mar 16 '15 at 1:34
  • $\begingroup$ @Meryll You're welcome! I'm glad it's clear. $\endgroup$ – layman Mar 16 '15 at 1:46
5
$\begingroup$

Try mutual subset inclusion.

($\to$): Suppose $x\in A\subseteq B$. Then $x\in A\to x\in B$; that is, $x\not\in A\lor x\in B$. The negation of this is $x\in A\land x\not\in B$; that is, $x\not\in A\cap \overline{B}$.

The other direction is trivial since you are dealing with the empty set.

$\endgroup$
2
$\begingroup$

First $A\subset B \Longrightarrow\overline{B}\subset \overline{A}\Longrightarrow A\cap \overline{B}\subset A\cap\overline{A}=\emptyset$ and hence $A\cap \overline{B}=\emptyset$. Conversely, $A\cap \overline{B}=\emptyset$ implies $A=A\cap(B\cup \overline{B})=(A\cap B)\cup(A\cap\overline{B})=A\cap B \Longrightarrow A\subset B$.

$\endgroup$
0
$\begingroup$

$ (\Rightarrow) $; Suppose $ A\subseteq B $. Then $ \forall x\in A,x\in B $. Therefore $ \forall x\in A,x\notin B^c $. So $ A\cap B^{c}=\varnothing $.

$ (\Leftarrow) $; Conversely suppose $ 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\subseteq B $.

Here I use $B^c$ for your $\overline{B}$ :)

$\endgroup$
0
$\begingroup$

If $A\subseteq B$, then $x\in A \implies x \in B$, and if $x\in B$, then $x\not\in B^c$. So no $x$ be be in $A$ and $B^c$ at the same time, so $A\cap B^c=\emptyset$.

If $A\cap B^c=\emptyset$, we have $B\cup B^c=\omega$, where $\omega$ represents the entire space. If $x\in A, x\not\in B^c$, and so $x\in B$. Therefore $A\subseteq B$.

$\endgroup$

Your Answer

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