# Prove that $A\subseteq B$, $A\cap \overline{B}=\oslash$ and $\overline{A}\cup B=\mu$ are equivalent

I've been asked to Prove that $A\subseteq B$, $A\cap \overline{B}=\oslash$ and $\overline{A}\cup B=\mu$ are equivalent. I believe I have done so, but I expect that I have missed something critical.

I have convinced myself that they are equivalent - I just need to prove it.

I appreciate any feedback, if I'm on the right path, if there's a missing portion to the proof, etc..

There are 3 things that need to be proven:

i. $A\subseteq B \equiv A\cap \overline{B} = \oslash$

ii. $A\subseteq B \equiv \overline{A}\cup B=\mu$

iii. $A\cap \overline{B}=\oslash \equiv \overline{A}\cup B=\mu$

i: $A\subseteq B$ = $A\cap \overline{B} = \oslash$

$X\in A \implies X\in B$

$X \notin A \vee X \in B$

$X \in A \wedge X \notin B$

$A \cap \overline{B} \equiv A\cap \overline{B} = \oslash$

ii: $A\subseteq B$ = $\overline{A}\cup B = \mu$

$X\in A \implies X\in B$

$X \notin A \vee X \in B$

Since A contains a subset of B, $\overline{A}$ contains all elements not in A, and thus not in B. So

$X \notin A \vee X \in B = \mu$

iii: $A\cap \overline{B}=\oslash \equiv \overline{A}\cup B=\mu$

$X \in A \wedge X \notin B$

$X \notin A \vee X \in B$

Same as above - A contains a subset of B, \overline{A} contains all elements not in A and thus not in B, and so $\overline{A}\cup B=\mu$

Please pardon the poor TeX syntax. Still trying to learn it a bit.

• What do $\;\cap !\;,\;!A\;$ and etc. mean?? – DonAntonio May 14 '14 at 3:29
• !A as in, not A. $\cap$!B would be not B. I couldn't figure out how to do a bar over the symbol. – Tim May 14 '14 at 3:32
• What is $\mu$ here? – Cameron Williams May 14 '14 at 4:15
• Figured it out it means the Universe. – nerdy May 14 '14 at 4:18
• @Tim: \bar will put a narrow bar over the next symbol. \overline{} will put a wider bar over an expression. $\bar A \bar \cap \bar B = \overline{A\cup B}$ – Graham Kemp May 14 '14 at 4:40

You only need to transform each statement using $\subseteq$ , $=$, $\cap$ and $\cup$ into their exact logical formulas of first-order-language that characterize their definitions, and start using logical equivalences.
Here i'm using $A^c$ as the U \ A.

i: $A \subseteq B \equiv A \cap B^c = \emptyset$ $A \subseteq B \\ \equiv \forall x ( x \in A \to x \in B ) \,\,\,\,\,\,\,\,\, \text{ [Definition of} \subseteq\text{]}\\\equiv y \in A \to y \in B \, \, \,\,\,\,\,\text{ [ Universal Specification]}\\ \equiv \neg( y \in A \wedge y \notin B ) \, \, \,\,\,\,\,\,\,\,\,\,\text{ [ Equivalence of implication]} \\\equiv (y \in A \wedge y\notin B) \leftrightarrow F \,\,\,\,\,\,\,\,\,\,\,\text{ [ F is used to represent any contradiction in Set Theory]} \\\equiv (y \in A \wedge y \notin B) \leftrightarrow (y \in \emptyset ) \,\,\,\,\,\, \text{[} y \in \emptyset \text{ is a contradiction in Set Theory]}\\ \equiv \forall x(x \in A \wedge y \notin B \leftrightarrow x \in \emptyset ) \,\,\, \text{[Universal generalization, definition of equality between sets]} \\\equiv A \cap B^c = \emptyset$

ii: $A \subseteq B \equiv A^c \cup B = U$ $A \subseteq B \\ \equiv \forall x(x \in A \to x \in B) \\ \equiv y \in A \to y \in B \\ \equiv y \notin A \vee y \in B \\ \equiv y \notin A \vee y \in B \leftrightarrow T \,\,\,\,\,\, \text{ [T is used to represent a valid formula in set theory]} \\ \equiv y \notin A \vee y \in B \leftrightarrow y \in U \,\,\,\,\,\,\,\, \text{ [} y \in U\text{ is a valid formula in Set Theory ]} \\ \equiv \forall x(x \notin A \vee x \in B \leftrightarrow x \in U ) \\ \equiv A^c \cup B = U$

iii: $A \cap B^c = \emptyset \equiv A^c \cup B = U$
$A \cap B^c = \emptyset \\ \equiv \forall x( x \in A \wedge x \notin B \leftrightarrow x \in \emptyset ) \\ \equiv y \in A \wedge y \notin B \leftrightarrow y \in \emptyset \\ \equiv ( y \in A \wedge y \notin B \leftrightarrow F ) \\ \equiv \neg( y \in A \wedge y \notin B) \leftrightarrow T \\ \equiv y \notin A \vee y \in B \leftrightarrow y \in U \\ \equiv \forall x ( x \notin A \vee x \in B \leftrightarrow x \in U ) \\ \equiv A^c \vee B = U$


(In this answer $\;x\;$ ranges over our 'universe' $\;\univ\;$.)

For the first statement, we simply have the definition of $\;\subseteq\;$: $$\calc A \subseteq B \calcop{\equiv}{expand definition of \;\subseteq\;} \langle \forall x :: x \in A \Rightarrow x \in B \rangle \calcop{\equiv}{logic: \;\lnot P \lor Q\; is another way to write \;P \Rightarrow Q\;} \tag{*} \langle \forall x :: x \not\in A \lor x \in B \rangle \endcalc$$

For the second statement, we get $$\calc A \cap \c B = \varnothing \calcop{\equiv}{expand definitions of \;=, \cap, \c{\phantom\square}, \varnothing\;} \langle \forall x :: x \in A \land x \not\in B \;\equiv\; \false \rangle \calcop{\equiv}{logic: simplify \;P \equiv \false\; to \;\lnot P\;; DeMorgan} \tag{*} \langle \forall x :: x \not\in A \lor x \in B \rangle \endcalc$$

Finally, the third statement gives us $$\calc \c A \cup B = \univ \calcop{\equiv}{expand definitions of \;=, \cup, \c{\phantom\square}, \univ\;} \langle \forall x :: x \not\in A \lor x \in B \;\equiv\; \true \rangle \calcop{\equiv}{logic: simplify \;P \equiv \true\; to \;P\;} \tag{*} \langle \forall x :: x \not\in A \lor x \in B \rangle \endcalc$$

Since all $\Tag{*}$ are equivalent, the original statements also are equivalent.