De Morgan's Law Proof question

111 Views Asked by At

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

Let $x\in (S\cup T)^c \implies x \notin S \land x\notin T \implies x\notin S \cup T$

Since $x\notin S\implies x\in S^c $ $x\notin T \implies x\in T^c$

So $ \{ x: (x\in S^c) \land (x\in T^c)\} = S^c \cap T^c$

$x\in S^c \cap T^c \implies (S \cup T)^c \subseteq S^c \cap T^c $

Let $y \in S^c \cap T^c \implies y \in S^c \land y\in T^c $

$\implies y \notin S \cup T \implies y \in (S \cup T)^c $

$\implies S^c \cap T^c \subseteq (S \cup T)^c$

Therefore $(S \cup T)^c = S^c \cap T^c \quad \square$

My question is this part of the proof:

$x\in S^c \cap T^c \implies (S \cup T)^c \subseteq S^c \cap T^c $

Definition of subset: For two sets $S $ and $T $ we say that $S$ is a subset of $T $ if each element of $ S $ is also an element of $T $. In formal notation $S \subseteq T $ $\implies \forall x (x\in S \implies x \in T )$.

I know that every set is a subset of itself. So this holds

$(S \cup T)^c \subseteq (S \cup T)^c$ and $S^c \cap T^c \subseteq S^c \cap T^c$.

I also believe that I understand these rules:

$ S \cap T = \{ x: (x \in S) \land (x\in T)\}$

$ S \cup T = \{ x: (x \in S) \vee (x\in T)\}$

$ S^c = \{ x: (x \in u) \land (x\notin S) \} $

1

There are 1 best solutions below

0
On

This proof is really unclearly written, but here's what's going on: In the first part of the proof, $x$ is assumed to be an arbitrary element of $(S\cup T)^c.$ Then it is proved that under this assumption that $x\in S^c\cap T^c.$ So they have shown any element of $(S\cup T)^c$ is an element of $S^c\cap T^c.$ And, as you wrote down in your definition, this is exactly what it means to have $$ (S\cup T)^c \subseteq S^c\cap T^c$$