Chapter 1

Sets and Their Combinations

1.1 Sets and Membership

What is a set?
Definition 1.1 A set is a collection of distinct objects, considered as an object in its own
right.

Remark:Unfortunately, it is not safe to regard every collection of objects as a set.

For example, “the collection of the best musicians in the world” is not a set. Not safe
means “leads to paradoxes” and an inconsistent theory. To circumvent these difficulties,
we adopt the following convention: there is a universal set U from which we obtain all
the sets we are working with and their members.

ˆ Capital letters A, B, C, X, Y, . . . denote sets.

ˆ Lower case letters a, b, c, x, y, x1 , x2 , . . . denote elements.

ˆ The symbol ∈ indicates membership: x ∈ A means x is an element of A.

Describing a set
There are two principal ways to describe a set:

a) Element list (roster) form The members are listed inside curly braces.

√ 1 √
 
A = {−1, 0, 2, 2}, B= , NAH, Martha , {Africa, Asia, America, Europe, Antarctica}
3

b) Set-builder form A set is defined by a membership property.

A = {x | x is an even non-negative integer}, B = {x | x is a country in Africa}

E = {x | x is a real number and x2 − 1 = 0}

1
2 CHAPTER 1. SETS AND THEIR COMBINATIONS

Equality of sets
The order in which elements are listed is irrelevant.

{1, 2, 3} = {3, 1, 2}

Two sets are equal iff they have exactly the same elements.
 
4
{−1, 2, 3, 4} = 3, −1, , 4
2

{−1, 0, 5, 4} =
̸ {−1, 0, 5}

Exercise 1.1 Which of the following sets are equal?

A = {1, −1}, B = {0, 1, 2, 3}, C = {x ∈ R | x2 −1 = 0}, ∆ = {1, 3, 0, 2}, E = {1, 3, −1, 2}

1.2 Subsets
Definition 1.2 (Subset) Let A and B be sets. We say that A is a subset of B, written
A ⊆ B, if every member of A is also a member of B. Equivalently, x ∈ A ⇒ x ∈ B.

ˆ A ⊆ B can be read “A is contained in B”; also B ⊇ A reads “B contains A”.

ˆ Every set is a subset of itself: A ⊆ A.

ˆ The empty set, denoted ∅ or {}, contains no elements and is a subset of every
set.

Example 1.1 Let A = {0, 1, 2, 3}, B = {1, 2, 3}, C = {0, 1, 2, 3, 8}, D = {0, 1}. Then
A ⊆ A, B ⊆ B, C ⊆ C, D ⊆ D, D ⊆ A, A ⊆ C, B ⊆ C, D ⊆ C.

Remark 1.1 A is a proper subset of B, denoted A ⊂ B, if A ⊆ B and A ̸= B.

1.3 Set Operations

Throughout this section we work inside a universal set U .

Intersection
A ∩ B = {x ∈ U | x ∈ A and x ∈ B}

A A∩B B

Examples:
{1, 2, 3} ∩ {2, 3, 4} = {2, 3}, {1, 2} ∩ {3, 4} = ∅
1.4. ALGEBRA OF SETS 3

Union
A ∪ B = {x ∈ U | x ∈ A or x ∈ B}

A B

A∪B

So A ∪ B contains all members of A together with all members of B.

Relative complement (difference)

A \ B = {x ∈ U | x ∈ A and x ∈
/ B}

A\B
A B

Symmetric difference
A△B = (A \ B) ∪ (B \ A)

A A△B B

The elements of A△B are those that belong to exactly one of A and B.

Example 1.2 Take U = {1, 2, 3, 4, 5, 6, 7}, A = {1, 4, 6, 7}, B = {1, 3, 5, 7}, C =

{2, 4, 6}. Then
A△B = {3, 5, 6, 4}, (A△B)△C = {2, 3, 5}.

1.4 Algebra of Sets

The following laws hold for all sets A, B, C (where complements are taken with respect
to U ):

ˆ Commutative laws: A ∪ B = B ∪ A, A ∩ B = B ∩ A.

ˆ Associative laws: (A ∪ B) ∪ C = A ∪ (B ∪ C), (A ∩ B) ∩ C = A ∩ (B ∩ C).

ˆ Distributive laws:

A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C), A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C).
4 CHAPTER 1. SETS AND THEIR COMBINATIONS

ˆ De Morgan’s laws:

A ∪ B = A ∩ B, A ∩ B = A ∪ B,

where A = U \ A.

ˆ Identity and complement:

A ∪ ∅ = A, A ∩ U = A, A ∪ A = U, A ∩ A = ∅.

These laws can be used to prove set identities (tautologies). For example,

A ∪ (B ∩ A) = A

follows from distributivity and the absorption law.

1.5 Cardinality and Finite Sets

The cardinality (or size) of a finite set A is denoted |A|, n(A), or card(A).
We write [0] = ∅ and for n > 0, [n] = {0, 1, . . . , n − 1}. A set is said to have n
elements if it can be put into one-to-one correspondence with [n]; such a set is called
finite.

Example 1.3 ˆ A = {−1, 3, 20} has |A| = 3.

ˆ B = {x | x is a UNAM student} has at most 30 000 elements.

ˆ The sets N = {0, 1, 2, . . . }, Z, Q, R are infinite.

Inclusion–Exclusion Principle
For finite sets A and B,
|A ∪ B| = |A| + |B| − |A ∩ B|.
For three sets,

|A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|.

A A∩B∩C B

In general, for finite sets A1 , . . . , An ,

n
[ n
X X X
Ai = |Ai |− |Ai ∩Aj |+ |Ai ∩Aj ∩Ak |−· · ·+(−1)n+1 |A1 ∩· · ·∩An |.
i=1 i=1 1≤i<j≤n 1≤i<j<k≤n
1.6. POWER SET 5

1.6 Power Set

The power set of a set A, denoted P(A), is the set of all subsets of A.

P(A) = {X | X ⊆ A}.

Example 1.4 If A = {1, 2}, then P(A) = {∅, {1}, {2}, {1, 2}}. Hence |P(A)| = 2|A| =
4.

1.7 Cartesian Product and Relations

Ordered pairs
An ordered pair (a, b) differs from the set {a, b} in that order matters: (a, b) = (c, d) iff
a = c and b = d.

Cartesian product
The Cartesian product of sets A and B is

A × B = {(a, b) | a ∈ A, b ∈ B}.

Example 1.5 If A = {1, 2} and B = {x, y}, then

A × B = {(1, x), (1, y), (2, x), (2, y)}.

Relations
A relation from A to B is any subset of A × B. If R ⊆ A × B and (a, b) ∈ R, we
often write a R b. The domain of R is {a ∈ A | ∃b ∈ B, (a, b) ∈ R}; the range is
{b ∈ B | ∃a ∈ A, (a, b) ∈ R}.

Example 1.6 Let A = {1, 2, 3}, B = {2, 4}. The relation R = {(1, 2), (1, 4), (3, 2)} has
domain {1, 3} and range {2, 4}.

Number Fields
Commonly used sets of numbers:

N ⊆ Z ⊆ Q ⊆ R ⊆ C.

Each is an example of a number field with its own arithmetic operations.

6 CHAPTER 1. SETS AND THEIR COMBINATIONS

Exercises for Chapter 1

1. Decide whether the following collections are sets (justify briefly):

(a) The five best novels of the 20th century.

(b) The planets of the solar system.

2. Write the set {x ∈ R | x2 − 3x + 2 = 0} in roster form.

3. Prove that A ⊆ B and B ⊆ C imply A ⊆ C.

4. For U = {1, 2, . . . , 10}, A = {2, 4, 6, 8, 10}, B = {1, 2, 3, 4, 5}, find A ∩ B, A ∪ B,

A \ B, B \ A, and A△B.

5. Verify De Morgan’s law (A ∪ B)c = Ac ∩ B c using a Venn diagram.

6. If |A| = 12, |B| = 17 and |A ∪ B| = 25, find |A ∩ B|.

7. List all elements of P({a, b, c}).

8. Let A = {1, 2}, B = {3, 4}. Write A × B and list all relations from A to B that
contain exactly two ordered pairs.