1. $A\subset B$
  2. $A \cap B^{c} = \emptyset$
  3. $A^{c} \cup B = U$

where set $^c$ is the complement of the set

What I have so far is this. The statements are equivalent if they imply each other.

$1\Rightarrow2$: assuming 1 is true, $x \in A$ implies that $x\in B$ which in turn implies that $x\notin B^{c}$. So, by definition the set $A \cap B^{c}$ is always empty and $A\cap B^{c} = \emptyset$

$2\Rightarrow 3$: for this one, I was wondering If I could just say that applying de morgan's laws shows that $(A \cap B^{c})^{c} = \emptyset^{c}$ is logically equivalent to $A^{c} \cup B = U$ showing that 2 implies 3.

If this is incorrect, how would I go about showing that 2 implies 3?

$3\Rightarrow 1$: Assuming that 3 is true, 3 implies that either $x \in B$ or $x \in A^{c}$ and by definition, $x \in A^{c}$ implies that $x \in A $ and so, this implies that $A \subset B$.


$1\Rightarrow 2$ and $2\Rightarrow 3$ seems fine...for $3\Rightarrow 1$ let $x\in A$ then $x\notin A^{c}$ but $A^{c}\cup B=U$ hence $x\in B$ and so $A\subset B$.


Here is an alternative, more 'logical' proof, i.e., a proof where we first translate from the world of sets to that of logic, and then use the laws of logic to complete our proof.

Translating the given statements to the logic level leads (by set extensionality and the definitions of $\;\subseteq\;$, $\;\cap\;$, $\;{}^c\;$, $\emptyset\;$, $\cup\;$, and $U\;$) to the following equivalents of your 1, 2, and 3: \begin{align} \tag{1'} & \langle \forall x :: x \in A \;\Rightarrow\; x \in B \rangle \\ \tag{2'} & \langle \forall x :: x \in A \land x \not\in B \;\equiv\; \text{false} \rangle \\ \tag{3'} & \langle \forall x :: x \not\in A \lor x \in B \;\equiv\; \text{true} \rangle \\ \end{align} where $\;x\;$ ranges over your universe $\;U\;$. Now, $\text{(2')}$ and $\text{(3')}$ are equivalent by DeMorgan, and $\text{(1')}$ and $\text{(3')}$ are equivalent by rewriting $\;P \Rightarrow Q\;$ as $\;\lnot P \lor Q\;$. That proves that all of the statements are equivalent.


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.