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.

  • $\begingroup$ What do $\;\cap !\;,\;!A\;$ and etc. mean?? $\endgroup$ – DonAntonio May 14 '14 at 3:29
  • $\begingroup$ !A as in, not A. $\cap$!B would be not B. I couldn't figure out how to do a bar over the symbol. $\endgroup$ – Tim May 14 '14 at 3:32
  • $\begingroup$ What is $\mu$ here? $\endgroup$ – Cameron Williams May 14 '14 at 4:15
  • $\begingroup$ Figured it out it means the Universe. $\endgroup$ – nerdy May 14 '14 at 4:18
  • $\begingroup$ @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}$ $\endgroup$ – 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 $


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


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.