Question about an De Morgan Law

Aion

Junior Member
Joined
May 8, 2018
Messages
91
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:
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!
 
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 \)
 
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.
 
Top