1
$\begingroup$

I'm self-learning set theory, and as an exercise, I tried to prove one of DeMorgan's laws, i.e.,

$$(S \cap T)^c=S^c \cup T^c$$

So my proof goes as follows:

Let $x \in S^c$, and $x \in T^c$. Then, $x \notin S$ and $x \notin T$. Therefore, $x$ is neither a member of $S \cup T$, nor a member of $S \cap T$. As a result, it can be seen that $(S \cap T)^c \subset S^c \cup T^c$. Being that $x$ is a member of both $(S \cap T)^c$ and $S^c \cup T^c$, it follows that $S^c \cup T^c \subset (S \cap T)^c$. Therefore, being that $(A=B) \iff (A\subset B) \land (B\subset A)$, we can conclude that $(S \cap T)^c=S^c \cup T^c$. QED. My question is, does this prove DeMorgan's law?

$\endgroup$
2
$\begingroup$

Good question; however, I do not have much time to answer so I hope you can forgive me for being a little blunt.

The proof is confusing at best.

First, it's unclear why you start with "Let $x \in S^c$, and $x \in T^c$. You are taking an $x$ from $T^c \cap S^c$, and it's unclear why, because this set does not appear in the original statement. You should be taking an $x$ from $(S \cap T)^c$ and try to show it's in $S^c \cup T^c$, and vice versa.

Then you write "As a result, it can be seen that $(S∩T)^c \subset S^c ∪T^c$". Maybe you are able to see this, but the proof so far has not communicated why that is the case; the $x$ you took had nothing to do with the sets $(S∩T)^c$ and $S^c ∪T^c$, since again, the $x$ you took is in $T^c \cap S^c$.

Half of a proof (I leave the other half to you) is:

Take any $x \in (S \cap T)^c$. Then $x \not \in S \cap T$, so $x \not \in S$ or $x \not \in T$. Therefore $x \in T^c$ or $x \in S^c$, so $x \in T^c \cup S^c$.

Feel free to ask any question and I will answer when I can.

$\endgroup$
  • $\begingroup$ Ovi makes a good point here regarding equality of sets. In general you want to choose an element in either set and show that it exists in the other set. Then you want to do the same for the reverse direction. $\endgroup$ – Steve Schroeder Oct 3 '18 at 2:20

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.