# A Proof in Elementary Set Theory

I apologize in advance for any lack of clarity in my mathematical symbols; I'm beginning to learn how to use this site.

I'm working through "Introduction to Analysis" by Rosenlicht and he presents an exercise

Prove that if $X\subset S$, $Y\subset S$, then $\complement X\cap\complement Y=\complement(X\cup Y)$

I went about it as follows:

Suppose $X\subset S$ and $Y\subset S$.   Then $\complement X=\{x:x\in S\land x\notin X\}$ And $\complement Y=\{x:x\in S\land x\notin Y\}$ , so $\complement X\cap\complement Y=\{x:x\in S\land x\notin X\land x\in S \land x\notin Y\}$.   Hence $\complement X\cap\complement Y=\{x:x\in S\land x\notin X\land x\in Y\}$.   Therefore $\complement X\cap\complement Y=\{x:x\in S\land x\notin X\cup Y\}$  And thus $\complement X\cap\complement Y=\complement(X\cup Y)$

Whereas the author gives the proof

If $x\in \complement X\cap\complement Y$ then $x\in\complement X$ and $x\in \complement Y$.   This means that $x\in S, x\notin X, x\notin Y$.   Since $x\notin X, x\notin Y$, we know that $x\notin X\cup Y$.   Hence $x\in \complement(X\cup Y)$.

Conversely, if $x\in\complement(X\cup Y)$, then $x\in S$ and $x\notin X\cup Y$.   Therefore $x\notin X$ and $x\notin Y$.   Thus $x\in\complement X$ and $x\in\complement Y$, so that $x\in\complement X\cap\complement Y$.

My questions are

• 1) is my proof correct?
• 2) which proof is better
• 3) what are the subtle (because obviously I know what the difference is, but I'm looking for deeper mathematical understanding) differences between my proof and the authors?

Thank you!

• If you could please fix your post, in order to be more readable. It's $\complement$ rather than $\compliment$. After each command, you'd better leave a space. If you want to write "x in (not in) Y", you can write either $x \in Y$ or $x \notin Y$. – thanasissdr Aug 20 '15 at 23:30
• Thanks you. That's good to know. It appears someone just did now. Im assuming you can read it now? – Liam Cooney Aug 20 '15 at 23:38
• I think that both proofs are correct (barring a typo at the end of the line following "Hence" in your proof). – Akiva Weinberger Aug 20 '15 at 23:40
• It still needs work. You should also note that logical and is \land – Graham Kemp Aug 20 '15 at 23:41

## 1 Answer

Both proofs are correct (typography ignored).

Yours uses set construction format, the author manipulates the constructors directly.   The authors approach is the one usually taken, for reasons of brevity.

One additional thing the author does is explicitly show that the implication works both ways; that $x\in(\complement X\cap\complement Y)\implies x\in \complement(X\cap Y)$ and that $x\in\complement(X\cap Y)\implies x\in(\complement X\cap\complement Y)$.   You rely on each step being an equivalence; but don't explicitly indicate this is so.