Set theory proofs

Question

Let $X$ be the set of $A, B \subseteq X$. Show that:

a) $(A \cup B)^c = A^c \cap B^c$
b) If $A \subseteq B $, then $B^c \subseteq A^c$
c) $(A^c)^c = A$
d) $A - B = A \cap B^c$

Using the Venn diagrams is easy to check that is true, but I need to prove the equalities.

How can I do that in a proper, formal manner?

Answer 1

To show two sets $A,B$ are equal, you show

$$A \subseteq B \;\;\; \text{and} \;\;\; B \subseteq A$$

This in turn implies $A = B$.

How would one show this? Typically, you do this in two parts. First, you take $x \in A$, then use the definitions of the identities and such to show $x \in B$, and similarly start with $x \in B$ and show $x \in A$.

Some of the identities involved and the implications you'll use. (These are mostly "if and only if" statements, so the left implies the right, and the right implies the left. Usually going left-to-right is when you "unravel" as I speak on later, and right-to-left to "wrap it back up.")

• $x \in A \iff x \not \in A^c$
• $x \in A^c \iff x \not \in A$
• $x \in A \cup B \iff x \in A \;\;\; \text{OR} \;\;\; x \in B$
• $x \in A \cap B \iff x \in A \;\;\; \text{AND} \;\;\; x \in B$
• $x \in A-B \iff x \in A \;\;\; \text{AND} \;\;\; x \not \in B$
• On the premise $A \subseteq B$, $\;\; x \in A \implies x \in B$ (note the converse need not always hold on this one!)

In the case of part (b) in particular, you will show $x \in B^c \implies x \in A^c$ and the reverse, but on the premise $A \subseteq B$. That means you can take this latter fact as a given and a tool to use in your proof.

Typically the flow of all these arguments would be in "unraveling" the left-hand side to see what sets $x$ is in, then trying to "wrap it back up" into the identity on the right-hand side.

From there, since $x$ is arbitrary and $x \in A \implies x \in B$, it follows $A \subseteq B$ (assuming of course this holds!). Do the same to show $B \subseteq A$, and then you have $A = B$.

Of course this is just a broad overview. Hopefully in class or your text, similar examples were given. If not, I imagine there are plenty of other examples you could easily Google to grasp the overall flow, structure, and motivation of such an argument.

P.S. It is also very helpful to have Venn diagrams on-hand, as you probably can see already. They're a good guiding tool for these sorts of proofs. Of course they aren't a substitute for a formal proof, but if you can verify it through Venn diagrams that's like half the difficulty.