nyuuzyou/wikis huggingface dataset:
De Morgan's Laws (Logic)/Conjunction of Negations/Formulation 2

== Theorem ==
:$\vdash \paren {\neg p \land \neg q} \iff \paren {\neg \paren {p \lor q} }$
This can be expressed as two separate theorems:
=== Forward Implication ===
=== Reverse Implication ===
== Proof 1 ==
== Proof by Truth Table ==
== Sources ==
* : $\text{II}$: 'AND', 'OR', 'IF AND ONLY IF': $\S 5$: Theorem $\text{T66}$
* : $3$: The Method of Deduction: $3.2$: The Rule of Replacement: $10.$
* : $\S \text{II}$: The Logic of Statements $(2): \ 6$: Using logical equivalences: $13$
* : Chapter $1$: Sets and mappings: $\S 1.1$: The need for logic: Exercise $(2) \ \text{(v)}$
* : $\S 1.14$: Exercise $12 \ (9)$
* : Chapter $1$: Elementary, my dear Watson: $\S 1.1$: You have a logical mind if... $\text{(d)}$
::(referring to it as one of the laws of negation)
Category:De Morgan's Laws (Logic)
De Morgan's Laws (Logic)/Conjunction of Negations/Formulation 2/Forward Implication

== Theorem ==
:$\paren {\neg p \land \neg q} \implies \paren {\neg \paren {p \lor q} }$
== Proof ==
== Sources ==
* : $\text{II}$: 'AND', 'OR', 'IF AND ONLY IF': $\S 5$: Theorem $\text{T67}$
Category:De Morgan's Laws (Logic)
De Morgan's Laws (Logic)/Conjunction of Negations/Formulation 2/Proof by Truth Table

== Theorem ==
== Proof ==
We apply the Method of Truth Tables.
As can be seen by inspection, the truth values under the main connective is true for all boolean interpretations.
$\begin{array}{|ccccc|c|cccc|} \hline
\neg & p & \land & \neg & q & \iff & \neg & (p & \lor & q) \\
\hline
\T & \F & \T & \T & \F & \T & \T & \F & \F & \F \\
\T & \F & \F & \F & \T & \T & \F & \F & \T & \T \\
\F & \T & \F & \T & \F & \T & \F & \T & \T & \F \\
\F & \T & \F & \F & \T & \T & \F & \T & \T & \T \\
\hline
\end{array}$
== Sources ==
* : $\S \text{II}$: Exercise $14 \ \text{(b)}$
* : $2$ Arguments Containing Compound Statements: $2.4$: Statement Forms
Category:De Morgan's Laws (Logic)
De Morgan's Laws (Logic)/Disjunction/Formulation 1

== Theorem ==
:$p \lor q \dashv \vdash \neg \paren {\neg p \land \neg q}$
This can be expressed as two separate theorems:
=== Forward Implication ===
=== Reverse Implication ===
== Proof by Truth Table ==
== Sources ==
* : $\S 2.4$: Relations between Truth-Functions
* : Chapter $1$: The Propositional Calculus $1$: $5$ Further Proofs: Résumé of Rules: Theorem $36$
* : $\S 1$: Naive Set Theory: $\S 1.1$: What is a Set?
* : $\S 2.3.3$
* : $\S 2.10$: Exercise $2.3$
Category:De Morgan's Laws (Logic)
De Morgan's Laws (Logic)/Disjunction/Formulation 1/Forward Implication

== Theorem ==
:$p \lor q \vdash \neg \paren {\neg p \land \neg q}$
== Proof ==
== Sources ==
* : Chapter $1$: The Propositional Calculus $1$: $5$ Further Proofs: Résumé of Rules: Theorem $36 \ \text{(a)}$
Category:De Morgan's Laws (Logic)
De Morgan's Laws (Logic)/Disjunction/Formulation 1/Proof by Truth Table

== Theorem ==
== Proof ==
We apply the Method of Truth Tables.
As can be seen by inspection, the truth values under the main connectives match for all boolean interpretations.
$\begin{array}{|ccc||cccccc|} \hline
p & \lor & q & \neg & (\neg & p & \land & \neg & q) \\
\hline
\F & \F & \F & \F & \T & \F & \T & \T & \F \\
\F & \T & \T & \T & \T & \F & \F & \F & \T \\
\T & \T & \F & \T & \F & \T & \F & \T & \F \\
\T & \T & \T & \T & \F & \T & \F & \F & \T \\
\hline
\end{array}$
Category:De Morgan's Laws (Logic)
Category:Truth Table Proofs
De Morgan's Laws (Logic)/Disjunction/Formulation 1/Reverse Implication

== Theorem ==
:$\neg \paren {\neg p \land \neg q} \vdash p \lor q$
== Proof ==
== Sources ==
* : Chapter $1$: The Propositional Calculus $1$: $5$ Further Proofs: Résumé of Rules: Theorem $36 \ \text{(b)}$
Category:De Morgan's Laws (Logic)
De Morgan's Laws (Logic)/Disjunction/Formulation 2

== Theorem ==
:$\vdash \paren {p \lor q} \iff \paren {\neg \paren {\neg p \land \neg q} }$
== Proof 1 ==
== Proof by Truth Table ==
== Sources ==
* : $\S 3.6$: Reference Formulae: $RF \, 15$
* : $\S 4.7$: The Derivation of Formulae: $D \, 26$
* : $\text{II}$: 'AND', 'OR', 'IF AND ONLY IF': $\S 5$: Theorem $\text{T64}$
* 
* 
* 
* 
Category:De Morgan's Laws (Logic)
De Morgan's Laws (Logic)/Disjunction/Formulation 2/Proof by Truth Table

== Theorem ==
== Proof ==
We apply the Method of Truth Tables.
As can be seen by inspection, the truth values under the main connective are true for all boolean interpretations.
:$\begin{array}{|ccc|c|cccccc|} \hline
(p & \lor & q) & \iff & (\neg & (\neg & p & \land & \neg & q)) \\
\hline
\F & \F & \F & \T & \F & \T & \F & \T & \T & \F \\
\F & \T & \T & \T & \T & \T & \F & \F & \F & \T \\
\T & \T & \F & \T & \T & \F & \T & \F & \T & \F \\
\T & \T & \T & \T & \T & \F & \T & \F & \F & \T \\
\hline
\end{array}$
== Sources ==
* : $\S \text{I}: 13$: Logical Equivalences: Exercise $\text{(A)} \ 8$
Category:De Morgan's Laws (Logic)
Category:Truth Table Proofs
De Morgan's Laws (Logic)/Disjunction of Negations

== Theorems ==
==== Formulation 1 ====
==== Formulation 2 ====
== Also see ==
* De Morgan's Laws (Set Theory) for a set theoretic application.
* De Morgan's Laws (Predicate Logic) for a predicate logic application.
== Sources ==
* : $\S 1.2$: Some Remarks on the Use of the Connectives and, or, implies: Exercise $4$
* 
* 
Category:De Morgan's Laws (Logic)
De Morgan's Laws (Logic)/Disjunction of Negations/Formulation 1

== Theorem ==
:$\neg p \lor \neg q \dashv \vdash \neg \paren {p \land q}$
This can be expressed as two separate theorems:
=== Forward Implication ===
=== Reverse Implication ===
== Proof by Truth Table ==
== Sources ==
* : Chapter $1$: The Propositional Calculus $1$: $5$ Further Proofs: Résumé of Rules: Exercise $1 \ \text {(g)}$
* : $\S 1.2.4$: Provable equivalence
Category:De Morgan's Laws (Logic)
De Morgan's Laws (Logic)/Disjunction of Negations/Formulation 1/Forward Implication

== Theorem ==
:$\neg p \lor \neg q \vdash \neg \paren {p \land q}$
== Proof ==
== Sources ==
* : $\S 1.2.1$: Rules for natural deduction: Exercises $1.5: \ 1 \ \text{(b)}$
Category:De Morgan's Laws (Logic)
De Morgan's Laws (Logic)/Disjunction of Negations/Formulation 1/Proof by Truth Table

== Theorem ==
== Proof ==
We apply the Method of Truth Tables.
As can be seen by inspection, the truth values under the main connectives match for all boolean interpretations.
$\begin{array}{|ccccc||cccc|} \hline
\neg & p & \lor & \neg & q & \neg & (p & \land & q) \\
\hline
\T & \F & \T & \T & \F & \T & \F & \F & \F \\
\T & \F & \T & \F & \T & \T & \F & \F & \T \\
\F & \T & \T & \T & \F & \T & \T & \F & \F \\
\F & \T & \F & \F & \T & \F & \T & \T & \T \\
\hline
\end{array}$
== Sources ==
* : $\S 1$: Informal statement calculus: $\S 1.2$: Truth functions and truth tables: Example $1.8 \ \text{(b)}$
Category:De Morgan's Laws (Logic)
Category:Truth Table Proofs
De Morgan's Laws (Logic)/Disjunction of Negations/Formulation 1/Reverse Implication

== Theorem ==
:$\neg \paren {p \land q} \vdash \neg p \lor \neg q$
== Proof ==
== Sources ==
* : $\S 1.2.5$: An aside: proof by contradiction: Exercises $1.6: \ 1 \ \text{(e)}$
Category:De Morgan's Laws (Logic)
De Morgan's Laws (Logic)/Disjunction of Negations/Formulation 2

== Theorem ==
:$\vdash \paren {\neg p \lor \neg q} \iff \paren {\neg \paren {p \land q} }$
== Proof 1 ==
== Proof by Truth Table ==
== Sources ==
* : $\text{II}$: 'AND', 'OR', 'IF AND ONLY IF': $\S 5$: Theorem $\text{T65}$
* : $3$: The Method of Deduction: $3.2$: The Rule of Replacement: $10.$
* : $\S \text{II}$: The Logic of Statements $(2): \ 6$: Using logical equivalences: $13$
* : Chapter $1$: Sets and mappings: $\S 1.1$: The need for logic: Exercise $(2) \ \text{(iv)}$
* : $\S 1.14$: Exercise $12 \ (10)$
* : Chapter $1$: Elementary, my dear Watson: $\S 1.1$: You have a logical mind if... $\text{(c)}$
::(referring to it as one of the laws of negation)
Category:De Morgan's Laws (Logic)
De Morgan's Laws (Logic)/Disjunction of Negations/Formulation 2/Proof by Truth Table

== Theorem ==
== Proof ==
We apply the Method of Truth Tables.
As can be seen by inspection, the truth values under the main connective is true for all boolean interpretations.
$\begin{array}{|ccccc|c|cccc|} \hline
\neg & p & \lor & \neg & q & \iff & \neg & (p & \land & q) \\
\hline
\T & \F & \T & \T & \F & \T & \T & \F & \F & \F \\
\T & \F & \T & \F & \T & \T & \T & \F & \F & \T \\
\F & \T & \T & \T & \F & \T & \T & \T & \F & \F \\
\F & \T & \F & \F & \T & \T & \F & \T & \T & \T \\
\hline
\end{array}$
== Sources ==
* : $\S \text{II}$: Exercise $14 \ \text{(b)}$
* : $2$ Arguments Containing Compound Statements: $2.4$: Statement Forms
* : $\S \text{I}: 13$: Logical Equivalences: Exercise $\text{(A)} \ 9$
Category:De Morgan's Laws (Logic)
Category:Truth Table Proofs
De Morgan's Laws (Logic)/Technical Note

== Technical Note on De Morgan's Laws ==
When invoking De Morgan's Laws in a tableau proof, use the template:
:{{DeMorgan|line|pool|statement|depends|type}}
where:
:line is the number of the line on the tableau proof where the specific instance of De Morgan's Laws is to be invoked
:pool is the pool of assumptions (comma-separated list)
:statement is the statement of logic that is to be displayed in the Formula column, without the $ ... $ delimiters
:depends is the line (or lines) of the tableau proof upon which this line directly depends
:type is the type of De Morgan's Law: Disjunction, Conjunction, Disjunction of Negations or Conjunction of Negations, whose link will be displayed in the Notes column.
Category:Technical Notes
Category:De Morgan's Laws (Logic)
De Morgan's Laws (Predicate Logic)

== Theorem ==
These are extensions of De Morgan's laws of propositional logic.
They are used to connect the universal quantifier $\forall$ with the existential quantifier $\exists$.
They can be stated as:
=== Assertion of Universality ===
=== Denial of Existence ===
=== Denial of Universality ===
=== Assertion of Existence ===
== Also known as ==
== Also see ==
* De Morgan's Laws as they arise in propositional logic
* De Morgan's Laws as they are applied in set theory
== Historical Note ==
Category:Universal Quantifier
Category:Existential Quantifier
Category:De Morgan's Laws (Logic)
De Morgan's Laws (Predicate Logic)/Assertion of Existence

== Theorem ==
Let $\forall$ and $\exists$ denote the universal quantifier and existential quantifier respectively.
Then:
:$\neg \paren {\forall x: \neg \map P x} \dashv \vdash \exists x: \map P x$
::If not everything is not, there exists something that is.
== Proof ==
== Sources ==
* : Chapter $4$: The Predicate Calculus $2$: $4$ The Syllogism: $150$
* : $\S \text{III}$: The Logic of Predicates $(1): \ 3$: Quantifiers: Relations between quantifiers $3$
* : Chapter $1$: Sets and mappings: $\S 1.1$: The need for logic
* : $\S 1$: Naive Set Theory: $\S 1.1$: What is a Set?
* 
* 
Category:Universal Quantifier
Category:Existential Quantifier
Category:De Morgan's Laws (Logic)
De Morgan's Laws (Predicate Logic)/Assertion of Universality

== Theorem ==
Let $\forall$ and $\exists$ denote the universal quantifier and existential quantifier respectively.
Then:
:$\forall x: \map P x \dashv \vdash \neg \paren {\exists x: \neg \map P x}$
::If everything is, there exists nothing that is not.
== Proof ==
== Sources ==
* : $\S 1$: Some mathematical language: Variables and quantifiers
* : $\S \text{III}$: The Logic of Predicates $(1): \ 3$: Quantifiers: Relations between quantifiers $1$
* : Chapter $1$: Sets and mappings: $\S 1.1$: The need for logic
Category:Universal Quantifier
Category:Existential Quantifier
Category:De Morgan's Laws (Logic)
De Morgan's Laws (Predicate Logic)/Denial of Existence

== Theorem ==
Let $\forall$ and $\exists$ denote the universal quantifier and existential quantifier respectively.
Then:
:$\forall x: \neg \map P x \dashv \vdash \neg \paren {\exists x: \map P x}$
::If everything is not, there exists nothing that is.
== Proof ==
== Sources ==
* : $\S 3.1 \ \text{(ii)}$: Statements and conditions; quantifiers
* : $\S \text{III}$: The Logic of Predicates $(1): \ 3$: Quantifiers: Relations between quantifiers $2$
* : $\S 2.1$
Category:Universal Quantifier
Category:Existential Quantifier
Category:De Morgan's Laws (Logic)
De Morgan's Laws (Predicate Logic)/Denial of Universality

== Theorem ==
Let $\forall$ and $\exists$ denote the universal quantifier and existential quantifier respectively.
=== Formulation 1 ===
=== Formulation 2 ===
In text, this can be summarised as:
::If not everything is, there exists something that is not.
== Examples ==
== Sources ==
* : $\S1.2$: Some Remarks on the Use of the Connectives and, or, implies
* : Chapter $4$: The Predicate Calculus $2$: $4$ The Syllogism: $149$
* : $\S \text{III}$: The Logic of Predicates $(1): \ 3$: Quantifiers: Relations between quantifiers $4$
Category:Universal Quantifier
Category:Existential Quantifier
Category:De Morgan's Laws (Logic)
De Morgan's Laws (Predicate Logic)/Denial of Universality/Formulation 1

== Theorem ==
Let $\forall$ and $\exists$ denote the universal quantifier and existential quantifier respectively.
Then:
:$\neg \paren {\forall x: \map P x} \dashv \vdash \exists x: \neg \map P x$
== Proof ==
== Sources ==
* : $\S 3.1 \ \text{(i)}$: Statements and conditions; quantifiers
* : Chapter $4$: The Predicate Calculus $2$: $4$ The Syllogism: $149$
* : $\S \text{III}$: The Logic of Predicates $(1): \ 3$: Quantifiers: Relations between quantifiers $4$
Category:Universal Quantifier
Category:Existential Quantifier
Category:De Morgan's Laws (Logic)
De Morgan's Laws (Predicate Logic)/Denial of Universality/Formulation 2

== Theorem ==
Let $\forall$ and $\exists$ denote the universal quantifier and existential quantifier respectively.
Then:
:$\vdash \neg \paren {\forall x: \map P x} \iff \paren{ \exists x: \neg \map P x }$
This can be expressed as two separate theorems:
=== Forward Implication ===
=== Reverse Implication ===
== Proof ==
== Sources ==
* : $\S 2.1$
* : Chapter $4$: The Predicate Calculus $2$: $4$ The Syllogism: $149$
* : $\S \text{III}$: The Logic of Predicates $(1): \ 3$: Quantifiers: Relations between quantifiers $4$
Category:Universal Quantifier
Category:Existential Quantifier
Category:De Morgan's Laws (Logic)
De Morgan's Laws (Predicate Logic)/Denial of Universality/Formulation 2/Forward Implication

== Theorem ==
Let $\forall$ and $\exists$ denote the universal quantifier and existential quantifier respectively.
Then:
:$\vdash \neg \paren {\forall x: \map P x} \implies \paren{ \exists x: \neg \map P x }$
== Proof ==
== Sources ==
* : $\text{II}.11$ Some Strategies for Constructing Proofs: Example $\text{II}.11.9$
* : Chapter $4$: The Predicate Calculus $2$: $4$ The Syllogism: $149$
* : $\S \text{III}$: The Logic of Predicates $(1): \ 3$: Quantifiers: Relations between quantifiers $4$
Category:Universal Quantifier
Category:Existential Quantifier
Category:De Morgan's Laws (Logic)
Category:Hilbert Proof System Instance 1 for Predicate Logic
De Morgan's Laws (Predicate Logic)/Denial of Universality/Formulation 2/Reverse Implication

== Theorem ==
Let $\forall$ and $\exists$ denote the universal quantifier and existential quantifier respectively.
Then:
:$\vdash \paren{ \exists x: \neg \map P x } \implies \neg \paren {\forall x: \map P x}$
== Proof ==
== Sources ==
* : Chapter $4$: The Predicate Calculus $2$: $4$ The Syllogism: $149$
* : $\S \text{III}$: The Logic of Predicates $(1): \ 3$: Quantifiers: Relations between quantifiers $4$
Category:Universal Quantifier
Category:Existential Quantifier
Category:De Morgan's Laws (Logic)
De Morgan's Laws (Set Theory)

== Theorem ==
De Morgan's laws are a collection of results in set theory as follows.
=== Set Difference ===
=== Relative Complement ===
=== Set Complement ===
== Also known as ==
== Also see ==
* De Morgan's Laws as they arise in logic.
== Historical Note ==
Category:Set Difference
Category:Set Union
Category:Set Intersection
Category:Relative Complement
Category:Set Complement
Category:De Morgan's Laws
De Morgan's Laws (Set Theory)/Proof by Induction/Difference with Intersection

== Theorem ==
Let $\mathbb T = \set {T_i: i \mathop \in I}$, where each $T_i$ is a set and $I$ is some finite indexing set.
Then:
:$\ds S \setminus \bigcap_{i \mathop \in I} T_i = \bigcup_{i \mathop \in I} \paren {S \setminus T_i}$
== Proof ==
Category:De Morgan's Laws
De Morgan's Laws (Set Theory)/Proof by Induction/Difference with Intersection/Proof

== Theorem ==
Let $\mathbb T = \set {T_i: i \mathop \in I}$, where each $T_i$ is a set and $I$ is some finite indexing set.
Then:
:$\ds S \setminus \bigcap_{i \mathop \in I} T_i = \bigcup_{i \mathop \in I} \paren {S \setminus T_i}$
== Proof ==
Let the cardinality $\card I$ of the indexing set $I$ be $n$.
Then by the definition of cardinality, it follows that $I \cong \N^*_n$ and we can express the proposition:
:$\ds S \setminus \bigcap_{i \mathop \in I} T_i = \bigcup_{i \mathop \in I} \paren {S \setminus T_i}$
as:
:$\ds S \setminus \bigcap_{i \mathop = 1}^n T_i = \bigcup_{i \mathop = 1}^n \paren {S \setminus T_i}$
The proof of this is more amenable to proof by Principle of Mathematical Induction.
For all $n \in \N_{>0}$, let $\map P n$ be the proposition:
:$\ds S \setminus \bigcap_{i \mathop = 1}^n T_i = \bigcup_{i \mathop = 1}^n \paren {S \setminus T_i}$
$\map P 1$ is true, as this just says $S \setminus T_1 = S \setminus T_1$.
=== Base Case ===
$\map P 2$ is the case:
:$S \setminus \paren {T_1 \cap T_2} = \paren {S \setminus T_1} \cup \paren {S \setminus T_2}$
which has been proved. 
This is our basis for the induction.
=== Induction Hypothesis ===
Now we need to show that, if $\map P k$ is true, where $k \ge 2$, then it logically follows that $\map P {k + 1}$ is true.
So this is our induction hypothesis:
:$\ds S \setminus \bigcap_{i \mathop = 1}^k T_i = \bigcup_{i \mathop = 1}^k \paren {S \setminus T_i}$
=== Induction Step ===
Now we need to show:
:$\ds S \setminus \bigcap_{i \mathop = 1}^{k + 1} T_i = \bigcup_{i \mathop = 1}^{k + 1} \paren {S \setminus T_i}$
This is our induction step:
So $\map P k \implies \map P {k + 1}$ and the result follows by the Principle of Mathematical Induction.
Therefore:
:$\ds S \setminus \bigcap_{i \mathop = 1}^n T_i = \bigcup_{i \mathop = 1}^n \paren {S \setminus T_i}$
that is:
:$\ds S \setminus \bigcap_{i \mathop \in I} T_i = \bigcup_{i \mathop \in I} \paren {S \setminus T_i}$
Category:De Morgan's Laws
De Morgan's Laws (Set Theory)/Proof by Induction/Difference with Union

== Theorem ==
Let $\mathbb T = \set {T_i: i \mathop \in I}$, where each $T_i$ is a set and $I$ is some finite indexing set.
Then:
:$\ds S \setminus \bigcup_{i \mathop \in I} T_i = \bigcap_{i \mathop \in I} \paren {S \setminus T_i}$
== Proof ==
Category:De Morgan's Laws
De Morgan's Laws (Set Theory)/Proof by Induction/Difference with Union/Proof

== Theorem ==
Let $\mathbb T = \set {T_i: i \mathop \in I}$, where each $T_i$ is a set and $I$ is some finite indexing set.
Then:
:$\ds S \setminus \bigcup_{i \mathop \in I} T_i = \bigcap_{i \mathop \in I} \paren {S \setminus T_i}$
== Proof ==
Let the cardinality $\size I$ of the indexing set $I$ be $n$.
Then by the definition of cardinality, it follows that $I \cong \N^*_n$ and we can express the proposition:
:$\ds S \setminus \bigcup_{i \mathop \in I} T_i = \bigcap_{i \mathop \in I} \paren {S \setminus T_i}$
as:
:$\ds S \setminus \bigcup_{i \mathop = 1}^n T_i = \bigcap_{i \mathop = 1}^n \paren {S \setminus T_i}$
The proof of this is more amenable to proof by Principle of Mathematical Induction.
For all $n \in \N_{>0}$, let $\map P n$ be the proposition:
:$\ds S \setminus \bigcup_{i \mathop = 1}^n T_i = \bigcap_{i \mathop = 1}^n \paren {S \setminus T_i}$.
$\map P 1$ is true, as this just says $S \setminus T_1 = S \setminus T_1$.
=== Base Case ===
$\map P 2$ is the case:
:$S \setminus \paren {T_1 \cup T_2} = \paren {S \setminus T_1} \cap \paren {S \setminus T_2}$
which has been proved.
This is our basis for the induction.
=== Induction Hypothesis ===
Now we need to show that, if $\map P k$ is true, where $k \ge 2$, then it logically follows that $\map P {k + 1}$ is true.
So this is our induction hypothesis:
:$\ds S \setminus \bigcup_{i \mathop = 1}^k T_i = \bigcap_{i \mathop = 1}^k \paren {S \setminus T_i}$
=== Induction Step ===
Now we need to show:
:$\ds S \setminus \bigcup_{i \mathop = 1}^{k + 1} T_i = \bigcap_{i \mathop = 1}^{k + 1} \paren {S \setminus T_i}$
This is our induction step:
So $\map P k \implies \map P {k + 1}$ and the result follows by the Principle of Mathematical Induction.
Therefore:
:$\ds S \setminus \bigcup_{i \mathop = 1}^n T_i = \bigcap_{i \mathop = 1}^n \paren {S \setminus T_i}$
that is:
:$\ds S \setminus \bigcup_{i \mathop \in I} T_i = \bigcap_{i \mathop \in I} \paren {S \setminus T_i}$
Category:De Morgan's Laws
De Morgan's Laws (Set Theory)/Relative Complement

== Theorem ==
Let $S, T_1, T_2$ be sets such that $T_1, T_2$ are both subsets of $S$.
Then, using the notation of the relative complement:
=== Complement of Intersection ===
=== Complement of Union ===
=== General Case ===
=== Family of Sets ===
Category:De Morgan's Laws
De Morgan's Laws (Set Theory)/Relative Complement/Complement of Intersection

== Theorem ==
Let $S, T_1, T_2$ be sets such that $T_1, T_2$ are both subsets of $S$.
Then, using the notation of the relative complement:
:$\relcomp S {T_1 \cap T_2} = \relcomp S {T_1} \cup \relcomp S {T_2}$
== Proof ==
Let $T_1, T_2 \subseteq S$.
Then from Intersection is Subset and Subset Relation is Transitive:
:$T_1 \cap T_2 \subseteq S$
Hence:
== Sources ==
* : $\S 5$: Complements and Powers
* : A Note on Set-Theoretic Concepts: $(6)$
* : Chapter $\text I$: Algebraic Structures: $\S 3$: Unions and Intersections of Sets: Theorem $3.2$
* : Chapter $\text I$: Algebraic Structures: $\S 3$: Unions and Intersections of Sets: Exercise $3.2$
* : $\S 1$. Sets; inclusion; intersection; union; complementation; number systems: $\text{(j)}$
* : $\S 1$: Naive Set Theory: $\S 1.2$: Operations on Sets: Exercise $1.2.2 \ \text{(v)}$
* : $\S 2$
Category:De Morgan's Laws
De Morgan's Laws (Set Theory)/Relative Complement/Complement of Union

== Theorem ==
Let $S, T_1, T_2$ be sets such that $T_1, T_2$ are both subsets of $S$.
Then, using the notation of the relative complement:
:$\relcomp S {T_1 \cup T_2} = \relcomp S {T_1} \cap \relcomp S {T_2}$
== Proof 1 ==
== Proof 2 ==
== Sources ==
* : $\S 5$: Complements and Powers
* : A Note on Set-Theoretic Concepts: $(6)$
* : Chapter $\text I$: Algebraic Structures: $\S 3$: Unions and Intersections of Sets: Theorem $3.2$
* : $\S 1$. Sets; inclusion; intersection; union; complementation; number systems: $\text{(j)}$
* : $\S 1$: Naive Set Theory: $\S 1.2$: Operations on Sets: Exercise $1.2.2 \ \text{(iv)}$
* : $\S 2$
Category:De Morgan's Laws
De Morgan's Laws (Set Theory)/Relative Complement/Complement of Union/Proof 2

== Theorem ==
== Proof ==
Let $x \in S$ througout.
By definition of set equality:
:$\relcomp S {T_1 \cup T_2} = \relcomp S {T_1} \cap \relcomp S {T_2}$
== Sources ==
* : Chapter $\text I$: Algebraic Structures: $\S 3$: Unions and Intersections of Sets: Theorem $3.2$
Category:De Morgan's Laws
De Morgan's Laws (Set Theory)/Relative Complement/Family of Sets

== Theorem ==
Let $S$ be a set.
Let $\family {S_i}_{i \mathop \in I}$ be a family of subsets of $S$.
Then:
==== Complement of Intersection ====
==== Complement of Union ====
== Sources ==
* : $2.22$
Category:De Morgan's Laws
De Morgan's Laws (Set Theory)/Relative Complement/Family of Sets/Complement of Intersection

== Theorem ==
Let $S$ be a set.
Let $\family {S_i}_{i \mathop \in I}$ be a family of subsets of $S$.
Then:
:$\ds \relcomp S {\bigcap_{i \mathop \in I} S_i} = \bigcup_{i \mathop \in I} \relcomp S {S_i}$
== Proof ==
== Sources ==
* : $\S 6$. Indexed families; partitions; equivalence relations: Exercise $2$
* : $\S 1$: Naive Set Theory: $\S 1.4$: Sets of Sets: Exercise $1.4.5 \ \text{(ii)}$
* : $2.22$
Category:De Morgan's Laws
De Morgan's Laws (Set Theory)/Relative Complement/Family of Sets/Complement of Union

== Theorem ==
Let $S$ be a set.
Let $\family {S_i}_{i \mathop \in I}$ be a family of subsets of $S$.
Then:
:$\ds \relcomp S {\bigcup_{i \mathop \in I} S_i} = \bigcap_{i \mathop \in I} \relcomp S {S_i}$
== Proof ==
== Sources ==
* : $\S 6$. Indexed families; partitions; equivalence relations: Exercise $2$
* : $\S 1$: Naive Set Theory: $\S 1.4$: Sets of Sets: Exercise $1.4.5 \ \text{(i)}$
* : $2.22$
Category:De Morgan's Laws