properties of complement

Let $X$ be a set and $A,B$ are subsets of $X$.

1. 1.

$(A^{\complement})^{\complement}=A$.

Proof.

$a\in(A^{\complement})^{\complement}$ iff $a\notin A^{\complement}$ iff $a\in A$. ∎

2. 2.

$\emptyset^{\complement}=X$.

Proof.

$a\in\emptyset^{\complement}$ iff $a\notin\emptyset$ iff $a\in X$. ∎

3. 3.

$X^{\complement}=\emptyset$.

Proof.

$a\in X^{\complement}$ iff $a\notin X$ iff $a\in\emptyset$. ∎

4. 4.

$A\cup A^{\complement}=X$.

Proof.

$a\in A\cup A^{\complement}$ iff $a\in A$ or $a\in A^{\complement}$ iff $a\in A$ or $a\notin A$ iff $a\in X$. ∎

5. 5.

$A\cap A^{\complement}=\emptyset$.

Proof.

$a\in A\cap A^{\complement}$ iff $a\in A$ and $a\in A^{\complement}$ iff $a\in A$ and $a\notin A$ iff $a\in\emptyset$. ∎

6. 6.

$A\subseteq B$ iff $B^{\complement}\subseteq A^{\complement}$.

Proof.

Suppose $A\subseteq B$. If $a\in B^{\complement}$, then $a\notin B$, so $a\notin A$, or $a\in A^{\complement}$. This shows that $B^{\complement}\subseteq A^{\complement}$. On the other hand, if $B^{\complement}\subseteq A^{\complement}$, then by applying what’s just been proved, $A=(A^{\complement})^{\complement}\subseteq(B^{\complement})^{\complement}=B$. ∎

7. 7.

$A\cap B=\emptyset$ iff $A\subseteq B^{\complement}$.

Proof.

Suppose $A\cap B=\emptyset$. If $a\in A$, then $a\in B^{\complement}$, or $a\notin B$, which implies that $A\cap B=\emptyset$. Suppose next that $A\subseteq B^{\complement}$. If there is $a\in A\cap B$, then $a\in B$ and $a\in A$. But the second containment implies that $a\in B^{\complement}$, which contradicts the first containment. ∎

8. 8.

$A\setminus B=A\cap B^{\complement}$, where the complement is taken in $X$.

Proof.

$a\in A\setminus B$ iff $a\in A$ and $a\notin B$ iff $a\in A$ and $a\in B^{\complement}$ iff $a\in A\cap B^{\complement}$. ∎

9. 9.

(de Morgan’s laws) $(A\cup B)^{\complement}=A^{\complement}\cap B^{\complement}$ and $(A\cap B)^{\complement}=A^{\complement}\cup B^{\complement}$.

Proof.

See here (http://planetmath.org/DeMorgansLawsProof). ∎

Title properties of complement PropertiesOfComplement 2013-03-22 17:55:32 2013-03-22 17:55:32 CWoo (3771) CWoo (3771) 5 CWoo (3771) Derivation msc 03E99