1.1. Sets and Functions 5

Theorem 1.1.5. If A and B are subsets of a set X and Ac and Bc are their

complements in X, then

(a) (A ∪

B)c

=

Ac

∩

Bc;

and

(b) (A ∩

B)c

=

Ac

∪

Bc.

Proof. We prove (a) first. To show that two sets are equal, we must show that

they have the same elements. An element of X belongs to (A ∪

B)c

if and only if

it is not in A ∪ B. This is true if and only if it is not in A and it is not in B. By

definition this is true if and only if x ∈

Ac

∩

Bc.

Thus, (A ∪

B)c

and

Ac

∩

Bc

have

the same elements and, hence, are the same set.

If we apply part (a) with A and B replaced by Ac and Bc and use the fact that

(Ac)c = A and (Bc)c = B, the result is

(Ac

∪

Bc)c

= A ∩ B.

Part (b) then follows if we take the complement of both sides of this identity.

A statement analogous to Theorem 1.1.5 is true for unions and intersections of

collections of sets (Exercise 1.1.7).

Two sets A and B are said to be disjoint if A ∩ B = ∅. That is, they are

disjoint if they have no elements in common. A collection A of sets is called a

pairwise disjoint collection if A ∩ B = ∅ for each pair A, B of distinct sets in A.

Functions. A function f from a set A to a set B is a rule which assigns to each

element x ∈ A exactly one element f(x) ∈ B. The element f(x) is called the image

of x under f or the value of f at x. We will write

f : A → B

to indicate that f is a function from A to B. The set A is called the domain of f.

If E is any subset of A, then we write

f(E) = {f(x) : x ∈ E}

and call f(E) the image of E under f.

We don’t assume that every element of B is the image of some element of A.

The set of elements of B which are images of elements of A is f(A) and is called

the range of f. If every element of B is the image of some element of A (so that

the range of f is B), then we say that f is onto.

A function f : A → B is said to be one-to-one if, whenever x, y ∈ A and x = y,

then f(x) = f(y) – that is, if f takes distinct points to distinct points.

If g : A → B and f : B → C are functions, then there is a function f◦g : A → C,

called the composition of f and g, defined by

f ◦ g(x) = f(g(x)).

Since g(x) ∈ B and the domain of f is B, this definition makes sense.

If f : A → B is a function and E ⊂ B, then the inverse image of E under f is

the set

f

−1(E)

= {x ∈ A : f(x) ∈ E}.

That is, f −1(E) is the set of all elements of A whose images under f belong to E.