de Morgan’s laws for sets (proof)

Let $X$ be a set with subsets $A_i\subset X$ for $i\in I$, where $I$ is an arbitrary index-set. In other words, $I$ can be finite, countable, or uncountable. We first show that

${\left({\cup }_{i\in I}{A}_i\right)}^{\prime }$ $=$ ${\cap }_{i\in I}{A}_i^{\prime },$

where $A^{\prime }$ denotes the complement of $A$.

Let us define $S={\left({\cup }_{i\in I}{A}_i\right)}^{\prime }$ and $T={\cap }_{i\in I}{A}_i^{\prime }$. To establish the equality $S=T$, we shall use a standard argument for proving equalities in set theory. Namely, we show that $S\subset T$ and $T\subset S$. For the first claim, suppose $x$ is an element in $S$. Then $x\notin {\cup }_{i\in I}{A}_i$, so $x\notin A_i$ for any $i\in I$. Hence $x\in A_i^{\prime }$ for all $i\in I$, and $x\in {\cap }_{i\in I}{A}_i^{\prime }=T$. Conversely, suppose $x$ is an element in $T={\cap }_{i\in I}{A}_i^{\prime }$. Then $x\in A_i^{\prime }$ for all $i\in I$. Hence $x\notin A_i$ for any $i\in I$, so $x\notin {\cup }_{i\in I}{A}_i$, and $x\in S$.

The second claim,

${\left({\cap }_{i\in I}{A}_i\right)}^{\prime }$ $=$ ${\cup }_{i\in I}{A}_i^{\prime },$

follows by applying the first claim to the sets $A_i^{\prime }$.

Title	de Morgan’s laws for sets (proof)
Canonical name	DeMorgansLawsForSetsproof
Date of creation	2013-03-22 13:32:16
Last modified on	2013-03-22 13:32:16
Owner	mathcam (2727)
Last modified by	mathcam (2727)
Numerical id	7
Author	mathcam (2727)
Entry type	Proof
Classification	msc 03E30