next up previous contents
Next: Difference Up: Operations with sets Previous: Distributivity   Contents

Complementary set

Definition 3.2.19   Given a subset $ A$ of $ E$ ( $ A \subset E$) we define the complementary set $ \Bar{A}$ of $ A$ in $ E$ as $ \Bar{A} = \{ x \in E : x \notin A \}$.

Another notation for the complement of $ A$ in $ E$ is $ A^C$. When needed, the set $ E$ can be mentioned, via the following notation: the complementary set of $ A$ in $ E$ is denoted by C$ _E (A)$. The advantage of the notation $ \Bar{A}$ is that it reminds the fact that the translation of this definition into formulations as in Chapter 2 is by means of the negation of a predicate.

Figure 10: The complementary set of a subset.
\begin{figure}
\centering
\mbox{\epsfig{file=Complement.eps,height=3.5cm}}
\end{figure}

Proof. Use the truth tables prop logic:distributivity. $ \qedsymbol$

Example 3.2.20       
  1. If $ A=\{ 1,2,3,4 \}$ and $ E=\{ 1,2,3,4,5,6,7 \}$, then C$ _E (A)= \{ 5,6,7 \}$.
  2. The complementary set in $ \mathbb{N}$ of the set of all the even natural numbers is the set of all the odd natural numbers.

Remark 3.2.21   As the negation of the negation of a predicate is equivalent to the origonal predicate, we have that for any subset $ A$ of a given set $ E$, the complementary of the complementary of $ A$ is $ A$ itself:

$\displaystyle (A^C)^C=A.$    

Proposition 3.2.22   Let $ A$ be a subset of a given set $ E$. Then we have:
(i)
$ \overline{( \Bar{A})}=A$;
(ii)
$ A \cup \Bar{A} = E$;
(iii)
$ A \cap \Bar{A} = \emptyset$.

Proof.
(i)
$ \forall x \in E, \;
x \in \overline{( \Bar{A})} \Longleftrightarrow x \notin \Bar{A}
\Longleftrightarrow x \in A$.
(ii)
This is a straightforward consequence of the definition of the complementary set.
(iii)
For any $ x \in E$, the proposition $ (x \in A) \wedge (x \notin A)$ is a contradiction.
$ \qedsymbol$

An immediate consequence is the following corollary:

Corollary 3.2.23   Let $ X$ and $ Y$ be two subsets of the set $ E$. Then $ Y=\Bar{X}$ if, and only if, the two following properties hold:
(i)
$ X \cup Y =E$;
(ii)
$ X \cap Y =\emptyset$.

The following theorem is very important:

Theorem 3.2.24 (De Morgan's Laws)   Let $ A$ and $ B$ be two subsets of the set $ E$. Then the following relations hold:
  1. $ \overline{A \cap B} = \Bar{A} \cup \Bar{B}$
  2. $ \overline{A \cup B} = \Bar{A} \cap \Bar{B}$

Proof. Use truth tables and see prop De Morgan's law logic. $ \qedsymbol$

Figure 11: De Morgan's law number 1
\begin{figure}
\centering
\mbox{\epsfig{file=DeMorgan-1.eps,height=3.5cm}}
\end{figure}

Figure 12: De Morgan's law number 2
\begin{figure}
\centering
\mbox{\epsfig{file=DeMorgan-2.eps,height=3.5cm}}
\end{figure}

We will see another proof of this proposition, using characteristic functions (v.i. prop Morgan's law with characteristic functions). A more general version of this is the following: suppose $ A_1, \dots, A_n \subseteq S$. Then we have:
  1. $ \overline{\bigcap_{i=1}^n A_i} = \bigcup_{i=1}^n \Bar{A_i}$
  2. $ \overline{\bigcup_{i=1}^n A_i} = \bigcap_{i=1}^n \Bar{A_i}$.
These can be proved by induction on $ n$ (for the unfamiliar reader, v.i. chapter numbers).
next up previous contents
Next: Difference Up: Operations with sets Previous: Distributivity   Contents
root 2002-06-10