# 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

 $\displaystyle\displaystyle\big{(}\cup_{i\in I}A_{i}\big{)}^{\prime}$ $\displaystyle=$ $\displaystyle\cap_{i\in I}A_{i}^{\prime},$

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

Let us define $S=\big{(}\cup_{i\in I}A_{i}\big{)}^{\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,

 $\displaystyle\big{(}\cap_{i\in I}A_{i}\big{)}^{\prime}$ $\displaystyle=$ $\displaystyle\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) DeMorgansLawsForSetsproof 2013-03-22 13:32:16 2013-03-22 13:32:16 mathcam (2727) mathcam (2727) 7 mathcam (2727) Proof msc 03E30