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

I've been asked to Prove that $$A\subseteq B$$, $$A\cap \overline{B}=\oslash$$ and $$\overline{A}\cup B=U$$ 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=U$$

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

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 = U$$

$$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 = U$$

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

$$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=U$$

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

• What do $\;\cap !\;,\;!A\;$ and etc. mean?? May 14, 2014 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, 2014 at 3:32
• What is $\mu$ here? May 14, 2014 at 4:15
• Figured it out it means the Universe. May 14, 2014 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}$ May 14, 2014 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$

\newcommand{\calc}{\begin{align} \quad &} \newcommand{\calcop}[2]{\\ #1 \quad & \quad \text{"#2"} \\ \quad & } \newcommand{\endcalc}{\end{align}} \newcommand{\Tag}[1]{\text{(#1)}} \newcommand{\c}[1]{\overline{#1}} \newcommand{\univ}{\mu} \newcommand{\false}{\text{false}} \newcommand{\true}{\text{true}}My approach would be to translate your three statements from the set level to the logic level, by expanding the definitions, and then simplifying.

(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.