Proof that $X^C \cap Y^C= \;(X \cup Y)^c$

Question

Proof that if $X \subset S,\; Y\subset S,\;$ then $\;X^C \cap Y^C= \;(X \cup Y)^c:$

It must be shown that the two sets have the same elements, that each element of the set on the left is an element of the set on the right, and vice versa.

If $x \in X^C \cap Y^C,\;$ then $x \in X^C$ and $x \in Y^C.$ This means that $x \in S, x \notin X, x \notin Y.$ Thus $x \notin X \cup Y,$ so $x \in (X \cup Y)^c.$
QED.

My question is, can you provide a different proof? I'm looking for something more advanced and more interesting. Preferably a proof applied to some subject area of math, involving that area. Thanks.

Answer 1

This is basically DeMorgan's law, but at the set level instead of at the logic level. So this can be proved by translating from sets to predicates by expanding the definitions, applying DeMorgan, and translating back.

So assuming we work within the universe $\;S\;$, we have for every $\;x\;$ \begin{align} & x \in X^C \cap Y^C \\ \equiv & \qquad \text{"definition of $\;\cap\;$"} \\ & x \in X^C \;\land\; x \in Y^C \\ \equiv & \qquad \text{"definition of $\;^C\;$, twice"} \\ & x \not\in X \;\land\; x \not\in Y \\ \equiv & \qquad \text{"logic: DeMorgan"} \\ & \lnot(x \in X \;\lor\; x \in Y) \\ \equiv & \qquad \text{"definition of $\;\cup\;$"} \\ & \lnot(x \in X \cup Y) \\ \equiv & \qquad \text{"definition of $\;^C\;$"} \\ & x \in (X \cup Y)^C \\ \end{align} By set extensionality, this proves the statement.

I think this is really the only 'formal' proof there is-- there are just quite some ways to write it down, e.g., by treating the two directions separately, and by using words instead of symbols.

Then there are of course 'informal' proofs, like those using Venn diagrams.

Answer 2

We can to proof the two contentions simultaneously: $$x_{0}\in (X\cup Y )^{\complement} \Leftrightarrow x_{0}\not \in X \cup Y \Leftrightarrow x_{0} \not \in X \text{ and } x_{0}\not \in Y \Leftrightarrow$$ $$\Leftrightarrow x_{0}\in X^{\complement} \text{ and }x_{0}\in Y^{\complement} \Leftrightarrow x_{0} \in X^{\complement}\cap Y^{\complement}. $$

Answer 3

If you are looking for an "interesting" proof, Venn diagram is one approach. See here.

If you are looking for examples, try flip-flops and see also here.