Proving the Complementation Law for sets

$\begingroup$

I am new to Discrete Mathematics, and have been asked to prove the Complementation Law for sets, that is: $\overline {(\overline A)} \equiv A$. Our teacher advised us to turn the sets into propositions, so would it be as simple as this:

$\overline {(\overline A)}$

$\equiv \neg (\neg p)$

$\equiv p$

$\equiv A$

We have not really seen what a real proof looks like. Thank you!

$\endgroup$ 0

2 Answers

$\begingroup$

For arbitrary $x$ we have:

If $x\in A$ then $x\notin \overline{A}$ so $x\in\overline{\overline{A}}$. So $A\subseteq \overline{\overline{A}}$

And vice versa: If $x\in \overline{\overline{A}}$ then $x\notin {\overline{A}}$ so $x\in A$ and now we have $\overline{\overline{A}}\subseteq A$

So $A=\overline{\overline{A}}$

$\endgroup$ $\begingroup$

Put $p$ to be the proposition $x\in A$. Then $\neg p$ is $x\in \bar{A}$, and $\neg(\neg p)$ is $x\in\bar{\bar{A}}$. Since $p\iff \neg(\neg p)$, we have $$x\in A\iff x\in \bar{\bar{A}}.$$ By the axiom of extensionality, $$A=\bar{\bar{A}}.$$

$\endgroup$

Your Answer

Sign up or log in

Sign up using Google Sign up using Facebook Sign up using Email and Password Submit

Post as a guest

Post Your Answer Discard

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy