# 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 |