DeMorgansLawsProof 2003-03-30 12:34:28 2005-03-18 22:41:43 Proof de Morgan's laws 0 % this is the default PlanetMath preamble. as your knowledge % of TeX increases, you will probably want to edit this, but % it should be fine as is for beginners. % almost certainly you want these \usepackage{amssymb} \usepackage{amsmath} \usepackage{amsfonts} % used for TeXing text within eps files %\usepackage{psfrag} % need this for including graphics (\includegraphics) %\usepackage{graphicx} % for neatly defining theorems and propositions %\usepackage{amsthm} % making logically defined graphics %\usepackage{xypic} % there are many more packages, add them here as you need them % define commands here 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 \begin{eqnarray*} \displaystyle \big( \cup_{i\in I} A_i \big)' &=& \cap_{i\in I} A_i', \end{eqnarray*} where $A'$ denotes the complement of $A$. Let us define $S=\big( \cup_{i\in I} A_i \big)'$ and $T=\cap_{i\in I} A_i'$. 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'$ for all $i\in I$, and $x\in \cap_{i\in I} A_i'=T$. Conversely, suppose $x$ is an element in $T=\cap_{i\in I} A_i'$. Then $x\in A_i'$ 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, \begin{eqnarray*} \big( \cap_{i\in I} A_i \big)' &=& \cup_{i\in I} A_i', \end{eqnarray*} follows by applying the first claim to the sets $A_i'$.