# Question about an De Morgan Law

#### Aion

##### Junior Member
Proof for $$\displaystyle (S \cup T)^c = S^c \cap T^c$$

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

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

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

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

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

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

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

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

My question is this part of the proof:

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

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

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

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

I also believe that I understand these rules:

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

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

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

Last edited:

#### Dr.Peterson

##### Elite Member
Proof for $$\displaystyle (S \cup T)^c = S^c \cap T^c$$

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

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

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

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

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

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

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

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

My question is this part of the proof:

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

Definition of subset: For two sets $$\displaystyle S$$ and $$\displaystyle T$$ we say that $$\displaystyle S$$ is a subset of $$\displaystyle T$$ if each element of $$\displaystyle S$$ is also an element of $$\displaystyle T$$.
In formal notation $$\displaystyle S \subseteq T$$ $$\displaystyle \implies \forall x (x\in S \implies x \in T )$$.
Some aspects of the proof are poorly written; did you copy it exactly? There are too many "implies" symbols (in the wrong places) and too few words to make it clear; and some statements, as I read them, are backwards.

The line you are asking about, $$\displaystyle x\in S^c \cap T^c \implies (S \cup T)^c \subseteq S^c \cap T^c$$, should be stated quite differently. It is not that x being in this set implies that the other set is a subset of it; that is nonsense. It is really all that comes before (starting with the "let" statement) that implies the subset relation.

What they have shown is that IF $$\displaystyle x\in (S\cup T)^c$$, THEN $$\displaystyle x\in S^c \cap T^c$$. By the definition you stated for subsets, this tells us that the first set is a subset of the second.

That's all there is!

#### Aion

##### Junior Member
Some aspects of the proof are poorly written; did you copy it exactly? There are too many "implies" symbols (in the wrong places) and too few words to make it clear; and some statements, as I read them, are backwards.

The line you are asking about, $$\displaystyle x\in S^c \cap T^c \implies (S \cup T)^c \subseteq S^c \cap T^c$$, should be stated quite differently. It is not that x being in this set implies that the other set is a subset of it; that is nonsense. It is really all that comes before (starting with the "let" statement) that implies the subset relation.

What they have shown is that IF $$\displaystyle x\in (S\cup T)^c$$, THEN $$\displaystyle x\in S^c \cap T^c$$. By the definition you stated for subsets, this tells us that the first set is a subset of the second.

That's all there is!
So I can write it like this?

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

#### Dr.Peterson

##### Elite Member
Q!

So I can write it like this?

$$\displaystyle \forall x( x\in (S\cup T)^c\implies x\in S^c\cap T^c) \implies (S \cup T)^c \subseteq S^c \cap T^c$$
Yes. The parentheses are important; I missed one of them at first! You have an implication implying a statement, which is appropriate.