Empty Intersection iff Subset of Complement

From ProofWiki
Jump to navigation Jump to search

Corollary to Intersection with Complement is Empty iff Subset

$S \cap T = \O \iff S \subseteq \relcomp {} T$

where:

$S \cap T$ denotes the intersection of $S$ and $T$
$\O$ denotes the empty set
$\complement$ denotes set complement
$\subseteq$ denotes subset.


Corollary

Let $A, B, S$ be sets such that $A, B \subseteq S$.

Then:

$\exists X \in \powerset S: \paren {A \cap X} \cup \paren {B \cap \complement_S \paren X} = \O \iff A \cap B = \O$

where $\overline X$ denotes the relative complement of $X$ in $S$.


Proof 1

\(\displaystyle S \cap T\) \(=\) \(\displaystyle \O\)
\(\displaystyle \leadstoandfrom \ \ \) \(\displaystyle S \cap \relcomp {} {\relcomp {} T}\) \(=\) \(\displaystyle \O\) Complement of Complement
\(\displaystyle \leadstoandfrom \ \ \) \(\displaystyle S\) \(\subseteq\) \(\displaystyle \relcomp {} T\) Intersection with Complement is Empty iff Subset

$\blacksquare$


Proof 2

From Intersection with Complement is Empty iff Subset

$S \subseteq T \iff S \cap \relcomp {} T = \O$


Then we have:

\(\displaystyle \) \(\) \(\displaystyle S \nsubseteq \relcomp {} T\)
\(\displaystyle \) \(\leadstoandfrom\) \(\displaystyle \neg \paren {\forall x \in S: x \in \relcomp {} T}\) Definition of Subset
\(\displaystyle \) \(\leadstoandfrom\) \(\displaystyle \exists x \in S: x \notin \relcomp {} T\) Denial of Universality
\(\displaystyle \) \(\leadstoandfrom\) \(\displaystyle \exists x \in S: x \in T\) Definition of Set Complement
\(\displaystyle \) \(\leadstoandfrom\) \(\displaystyle x \in S \cap T\) Definition of Set Intersection
\(\displaystyle \) \(\leadstoandfrom\) \(\displaystyle S \cap T \ne \O\) Definition of Disjoint Sets


Thus:

\(\displaystyle \) \(\) \(\displaystyle S \cap T = \O\)
\(\displaystyle \) \(\leadstoandfrom\) \(\displaystyle \forall x \in S: x \in \relcomp {} T\)
\(\displaystyle \) \(\leadstoandfrom\) \(\displaystyle S \subseteq \relcomp {} T\)

$\blacksquare$


Sources