Next: Difference Up: Operations with sets Previous: Distributivity   Contents

Complementary set

Definition 3.2.19   Given a subset of ( ) we define the complementary set of in as .

Another notation for the complement of in is . When needed, the set can be mentioned, via the following notation: the complementary set of in is denoted by C. The advantage of the notation 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.

Proof. Use the truth tables prop logic:distributivity.

Example 3.2.20
1. If and , then C.
2. The complementary set in 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 of a given set , the complementary of the complementary of is itself:

Proposition 3.2.22   Let be a subset of a given set . Then we have:
(i)
;
(ii)
;
(iii)
.

Proof.
(i)
.
(ii)
This is a straightforward consequence of the definition of the complementary set.
(iii)
For any , the proposition is a contradiction.

An immediate consequence is the following corollary:

Corollary 3.2.23   Let and be two subsets of the set . Then if, and only if, the two following properties hold:
(i)
;
(ii)
.

The following theorem is very important:

Theorem 3.2.24 (De Morgan's Laws)   Let and be two subsets of the set . Then the following relations hold:

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

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 . Then we have:
1. .
These can be proved by induction on (for the unfamiliar reader, v.i. chapter numbers).

Next: Difference Up: Operations with sets Previous: Distributivity   Contents
root 2002-06-10