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

Question

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.

Answer 1

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 $

Answer 2

$ \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.