Chapter 4: Sets

4.1 The language of sets

Two types of set theory:
• Naive set theory (informal and intuitive, this is what we will cover)
• Axiomatic set theory (based on formal logic, discussed in MA1100T and MA3205)

A set is a collection of objects, each of which is called an element or member of the set.
Some rules:
(1) Fix a a set U, called the universal set, which contains all the mathematical objects under
consideration.
For example, in calculus of one variable, we usually take U be the set R of all real numbers,
and in elementary number theory, we usually take U to be the set Z of integers.

(2) Given a set A and a fixed object x in U, we can say whether x is an element of A or not.
• Write x ∈ A for “x is an element of the set A”.
This is a statement, i.e. x ∈ A is either true or false, but not both.
• We write x < A for “x is not an element of the set A”.
This is the negation of x ∈ A, so x < A is an alternative notation for ¬(x ∈ A).

(3) Two sets are equal if and only if they have the same elements.
So a set is uniquely determined by its elements.

Usual notation for sets: Capital letters A, B, C, etc.

Some standard sets have special notation: N (or Z+ ), Z, Q, R, C, [a, b].

By Rule (3), two sets are equal if and only if they have exactly the same elements.

Definition Let A and B be sets. Then A = B if and only if

(∀x ∈ U)[x ∈ A ⇔ x ∈ B].

How to specify a set?

(1) Explicitly list the elements in the set
(a) If A is the set with elements 1, 2 and 3, then we write A = {1, 2, 3}.
• The order in which the elements of a set are listed is irrelevant, so we can also write
A = {3, 1, 2}.
• Each element should be listed only once, and we should not write A = {1, 1, 2, 3}.
1
 (b) Sometimes we use 3 dots to suggest a pattern (especially when the set has infinitely many
elements). Some examples:
The set of natural numbers: N = {1, 2, 3, 4, ...}.
The set of integers: Z = {..., −2, −1, 0, 1, 2, ...}.
The set of all integers from 3 to 12: B = {3, 4, 5, ..., 12}.
The set of all even positive integers: C = {2, 4, 6, 8, ...}.

(2) Use “set-builder” notation

– specifies the precise property that the elements of the set should satisfy.
Let P(x) be a predicate with a single free variable x.
Then the notation
{x | P(x)} or {x : P(x)}.
denotes the set of all objects x in the underlying universal set U such that P(x) is true.
If X is a set, then
{x ∈ X | P(x)} = {x | (x ∈ X) ∧ P(x)}.

Example (i) The set B = {3, 4, 5, ..., 12} can be written in set-builder notation as
B = {n ∈ Z | 3 ≤ n ≤ 12}.

(ii) Let
D = {x ∈ R | 3 ≤ x ≤ 12}.
Then D is the set of all real number between 3 and 12. So D is the closed interval [3, 12].

More generally, we have the following types of intervals:

(a, b) = {x ∈ R | a < x < b} (open interval).
[a, b] = {x ∈ R | a ≤ x ≤ b} (closed interval).
[a, b) = {x ∈ R | a ≤ x < b}.
(a, b] = {x ∈ R | a < x ≤ b}.
[a, ∞) = {x ∈ R | x ≥ a}.
(a, ∞) = {x ∈ R | x > a}.
(−∞, b] = {x ∈ R | x ≤ b}.
(−∞, b) = {x ∈ R | x < b}.
(−∞, ∞) = R.

2
(iii) In set-builder notation, the set C = {2, 4, 6, 8, ...} of all even positive integers is written as
C = {n ∈ Z+ | n is even}
or
C = n ∈ Z+ | (∃k ∈ Z+ )[n = 2k] .


(3) Use “constructive definition”

The set C can also be written as
C = {2k | k ∈ Z+ }.
Here, the notation indicates that the elements of C are all integers of the form 2k where k ranges
through the set of positive integers, i.e.,
k = 1 : 2k = 2
k = 2 : 2k = 4
k = 3 : 2k = 6
.. ..
. .
Another example:
E ={4n − 3 | n ∈ Z}
={...., −11, −7, −3, 1, 5, 9, ....}.

In general, if X is a given set, and for every x ∈ X, the notation f (x) denotes a well-defined
object in U, then
A = { f (x) | x ∈ X}
is the set defined by
(∀y ∈ U){y ∈ A ⇔ (∃x ∈ X)[y = f (x)]}.
Intuitively, the set A is obtained from the set X by replacing each x ∈ X by f (x).

The empty set

The unique set with no elements is denoted by ∅ and is called the empty set or null set.
So for each x in the universal set U,
• x ∈ ∅ is always false; and so
• x < ∅ is always true.
In logical notation, this is (∀x ∈ U)[x < ∅].

Exercise Is {∅} = ∅?

3
Subsets and the inclusion relation ⊆
Definition Let A and B be sets.
We say that A is a subset of B (in notation A ⊆ B) if every element of A is also an element of B:
A ⊆ B iff (∀x ∈ U) [x ∈ A ⇒ x ∈ B] .
(So to prove A ⊆ B, you need to show that for each x such that x ∈ A, we also have x ∈ B.)

Venn diagram: We can denote a set as the interior of a circle, so that the following diagram
illustrates A ⊆ B.

Venn diagram can be used to show the logical relation between different sets, but they should
not be used as proof.

The negation of A ⊆ B
We will write A ⊈ B for the statement “A is not a subset of B”. So
A ⊈ B ⇐⇒ ¬(A ⊆ B)
⇐⇒ ¬ {(∀x ∈ U) [x ∈ A ⇒ x ∈ B]}
⇐⇒ (∃x ∈ U) ¬ [x ∈ A ⇒ x ∈ B]
⇐⇒ (∃x ∈ U) [(x ∈ A) ∧ ¬(x ∈ B)]
⇐⇒ (∃x ∈ U) [(x ∈ A) ∧ (x < B)] .

So to prove A ⊈ B, you need to show that there exists x ∈ U such that x ∈ A and x < B.

Proper subset
We will write A ⊊ B for the statement (A ⊆ B) ∧ (A , B).
In this case, we say that A is a proper subset of B.

4
Example

(1) Z+ ⊆ Z, Z ⊆ Q, Q ⊆ R.

Q R

+
Z
Z

(2) {{1}, 2} ⊆ {{1}, 2, 3}.

(3) Is {1} ⊆ {{1}, 2, 3}?

(4) Let
A = {4k + 1 | k ∈ Z} and B = {n ∈ Z | n is odd}.
Prove that A ⊆ B and B ⊈ A.

Proof. We first prove A ⊆ B.

Let n ∈ A. Then there exists k ∈ Z such that n = 4k + 1. Note that
n = 2(2k) + 1,
and 2k ∈ Z, so n is odd. It follows that n ∈ B.
Thus, A ⊆ B.

Next, we show B ⊈ A, i.e. (∃x ∈ U) [(x ∈ B) ∧ (x < A)].

Note that 3 is odd, so 3 ∈ B.

Claim: 3 < A.
Assume for the sake of a contradiction that 3 ∈ A.
Then there exists k ∈ Z such that 3 = 4k + 1.
This gives 2 = 4k and so 4 | 2, which is a contradiction.
Hence, 3 < A.

Since 3 ∈ B and 3 < A, B ⊈ A. □

5
Proposition 4.1.1. Let A and B be sets. Then
A = B if and only if [A ⊆ B and B ⊆ A] .

Proof. We have
A = B iff (∀x ∈ U)[x ∈ A ⇔ x ∈ B]
iff (∀x ∈ U)[(x ∈ A ⇒ x ∈ B) ∧ (x ∈ B ⇒ x ∈ A)]
iff {(∀x ∈ U)[x ∈ A ⇒ x ∈ B]} ∧ {(∀x ∈ U)[x ∈ B ⇒ x ∈ A)]}
(using (∀x ∈ U)[P(x) ∧ Q(x)] ≡ {(∀x ∈ U) P(x))} ∧ {(∀x ∈ U) Q(x)})
iff (A ⊆ B) ∧ (B ⊆ A). □

This proposition says that to prove A = B, you first prove A ⊆ B, and then prove B ⊆ A.

Example Let
A = {n ∈ Z | n + 5 is odd} and B = {n ∈ Z | n is even}.
Prove that A = B.

Proof. We shall prove A ⊆ B, and then prove B ⊆ A.

We first show A ⊆ B.
Let n ∈ A. Then n + 5 is odd. So there exists k ∈ Z such that n + 5 = 2k + 1.
From this, we obtain
n = 2k + 1 − 5 = 2k − 4 = 2(k − 2).
Hence, n is even and so n ∈ B.
This shows that A ⊆ B.
Next, we show B ⊆ A.
Let n ∈ B. Then n is even, and so there exists k ∈ Z such that n = 2k. We now have
n + 5 = 2k + 5 = 2(k + 2) + 1,
which shows that n + 5 is odd. Thus n ∈ A.
This shows that B ⊆ A.
Since A ⊆ B and B ⊆ A, we have A = B. □

6
Proposition 4.1.2. Let A, B and C be sets. If A ⊆ B and B ⊆ C, then A ⊆ C.

Proof. Let x ∈ A.
Since x ∈ A and A ⊆ B, x ∈ B.
Since x ∈ B and B ⊆ C, x ∈ C.
Hence A ⊆ C. □

Proposition 4.1.3. For all sets A, ∅ ⊆ A and A ⊆ A.

Proof. Let A be a set.

We first prove ∅ ⊆ A. We need to show the statement
(∀x ∈ U)[x ∈ ∅ ⇒ x ∈ A]
is true.
Note that for each x ∈ U, x ∈ ∅ is false, and so the implication
x∈∅⇒x∈A
is true. Thus, we have ∅ ⊆ A.

Next, we prove A ⊆ A.
Let x ∈ A. Then x ∈ A. So A ⊆ A. □

Remark In general, a statement of the form

(∀x ∈ U)[x ∈ ∅ ⇒ anything ]
is always true, and we say that it is vacuously true, since there is no x such that x ∈ ∅.

7
4.2 Operations on sets
This section deals with operations we may perform on sets to build “new” sets from “old” ones.

Definition Let A and B be sets.

(1) The union of A and B is the set
A ∪ B = {x ∈ U | x ∈ A or x ∈ B}.
In logical notation,
(∀x ∈ U)[x ∈ A ∪ B ⇔ (x ∈ A) ∨ (x ∈ B)].

A∪B
U

A B

(2) The intersection of A and B is the set

A ∩ B = {x ∈ U | x ∈ A and x ∈ B}.
In logical notation,
(∀x ∈ U)[x ∈ A ∩ B ⇔ (x ∈ A) ∧ (x ∈ B)].

A∩B
U

A B

8
(3) The complement of B in A is the set
A − B = {x ∈ A | x < B}
= {x ∈ U | x ∈ A and x < B}.
In logical notation,
(∀x ∈ U)[x ∈ A − B ⇔ (x ∈ A) ∧ (x < B)].
The set difference A − B is sometimes denoted by A \ B.

A−B
U

A B

(4) The set difference U − A is denoted by Ac (or A ) and is called the complement of A; i.e.,
Ac = U − A = {x ∈ U | x < A}
In logical notation,
(∀x ∈ U)[x ∈ Ac ⇔ x < A].

Ac

U
A

Example If U = R, then
Qc = R − Q = {x ∈ R | x is irrational}
is the set of all irrational numbers.
9
 Example Let
A = {1, 3, 4, 5, 7, 9}, B = {3, 6, 7, 10}, C = {2, 6}
and let the universal set be U = Z+ .
Determine A ∪ B, A ∩ B, A − B, B − A, A ∩ C, C c .
Solutions: We have
A ∪ B = {x ∈ Z+ | x ∈ A or x ∈ B} = {1, 3, 4, 5, 6, 7, 9, 10},
A ∩ B = {x ∈ Z+ | x ∈ A and x ∈ B} = {3, 7},
A − B = {x ∈ Z+ | x ∈ A and x < B} = {1, 4, 5, 9},
B − A = {x ∈ Z+ | x ∈ B and x < A} = {6, 10},
A ∩ C = {x ∈ Z+ | x ∈ A and x ∈ C} = ∅ (we say A and C are disjoint),
C c = {n ∈ Z+ | n < C} = {n ∈ Z+ | n , 2 and n , 6}.

Definition Two sets A and B are disjoint if A ∩ B = ∅.

Example Let the universal set be R. then we have:

(2, 4] ∩ (3, 5) = (3, 4],
(2, 4] ∩ (4, 5) = ∅,
(2, 4] ∪ (3, 5) = (2, 5),
(2, 4]c = (−∞, 2] ∪ (4, ∞).

Proposition 4.2.1. Let A, B and C be subsets of some universal set U.

(i) If A ⊆ C and B ⊆ C, then A ∪ B ⊆ C.
(ii) If C ⊆ A and C ⊆ B, then C ⊆ A ∩ B.
(iii) A − B = A ∩ Bc .

Proof. (i) Let x ∈ A ∪ B. Then x ∈ A or x ∈ B.

If x ∈ A, then since A ⊆ C, we obtain x ∈ C.
Similarly, if x ∈ B, then we also obtain x ∈ C.
Thus A ∪ B ⊆ C.
(ii) Let x ∈ C.
Since C ⊆ A and x ∈ C, x ∈ A.
Since C ⊆ B and x ∈ C, x ∈ B.
Hence x ∈ A ∩ B.
This proves C ⊆ A ∩ B.
10
(iii) Let x ∈ U. Then
x ∈ A − B ⇐⇒ (x ∈ A) ∧ (x < B)
⇐⇒ (x ∈ A) ∧ (x ∈ Bc )
⇐⇒ x ∈ A ∩ Bc .
This shows (∀x ∈ U)[x ∈ A − B ⇐⇒ x ∈ A ∩ Bc ].
Hence A − B = A ∩ Bc . □

Proposition 4.2.2. Let A, B and C be subsets of some universal set U. Then we have:
(a) (Idempotent Laws) A ∪ A = A, A ∩ A = A.
(b) (Identity Laws) A ∪ ∅ = A, A ∩ U = A.
(c) (Domination Laws) A ∪ U = U, A ∩ ∅ = ∅.
(d) A ∩ B ⊆ A, A ⊆ A ∪ B.
(e) (Associative Laws) A ∪ (B ∪ C) = (A ∪ B) ∪ C, A ∩ (B ∩ C) = (A ∩ B) ∩ C.
(f) (Commutative Laws) A ∪ B = B ∪ A, A ∩ B = B ∩ A.
(g) (Distributive Laws) A ∪ (B∩C) = (A ∪ B) ∩ (A ∪C), A ∩ (B∪C) = (A ∩ B) ∪ (A ∩C).
(h) (DeMorgan’s Laws) (A ∪ B)c = Ac ∩ Bc , (A ∩ B)c = Ac ∪ Bc .
(i) (Complement Laws) A ∪ Ac = U, A ∩ Ac = ∅.
(j) (Double Complement Law) (Ac )c = A.

We shall prove one of the distributive laws in (g): A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C).

Proof. Let x ∈ U. Then
x ∈ A ∩ (B ∪ C) ⇐⇒ (x ∈ A) ∧ (x ∈ B ∪ C)
⇐⇒ (x ∈ A) ∧ [(x ∈ B) ∨ (x ∈ C)]
⇐⇒ [(x ∈ A) ∧ (x ∈ B)] ∨ [(x ∈ A) ∧ (x ∈ C)]
⇐⇒ (x ∈ A ∩ B) ∨ (x ∈ A ∩ C)
⇐⇒ x ∈ (A ∩ B) ∪ (A ∩ C).
Hence, A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C). □

11
Let us also prove one of the DeMorgan’s laws in (h): (A ∪ B)c = Ac ∩ Bc .
Proof. Let x ∈ U. Then
x ∈ (A ∪ B)c ⇐⇒ x< A∪B
⇐⇒ ¬(x ∈ A ∪ B)
⇐⇒ ¬[(x ∈ A) ∨ (x ∈ B)]
⇐⇒ ¬(x ∈ A) ∧ ¬(x ∈ B)
⇐⇒ (x < A) ∧ (x < B)
⇐⇒ (x ∈ Ac ) ∧ (x ∈ Bc ).
⇐⇒ x ∈ Ac ∩ Bc .
Hence, (A ∪ B)c = Ac ∩ Bc . □

Example Let A, B and C be sets. Prove that

(A ∪ B) − C = (A − C) ∪ (B − C).
Proof. We have
(A ∪ B) − C = (A ∪ B) ∩ C c (by Proposition 4.2.1 (iii)
= C c ∩ (A ∪ B) (by the Commutative Laws)
= (C c ∩ A) ∪ (C c ∩ B) (by the Distributive Laws)
= (A ∩ C c ) ∪ (B ∩ C c ) (by the Commutative Laws)
= (A − C) ∪ (B − C) (by Proposition 4.2.1 (iii). □

4.3 Ordered pairs and Cartesian product

Definition Let A and B be sets. The Cartesian product (or direct product) of A and B is the
set
A × B = {(x, y) | x ∈ A and y ∈ B}
where (x, y) denotes the ordered pair containing x and y in that order. So
(∀z ∈ U) {z ∈ A × B ⇐⇒ (∃x ∈ A)(∃y ∈ B)[z = (x, y)]} .

The equality of ordered pairs is defined as

(x, y) = (a, b) iff x = a and y = b.

12
More generally, if n ∈ Z+ and A1 , A2 , ..., An , A are sets, then
A1 × A2 × · · · × An = {(x1 , x2 , ..., xn ) | (∀i ∈ Z)[1 ≤ i ≤ n ⇒ xi ∈ Ai ]}
is a set of ordered n-tuples and
n copies
z }| {
A = A × A × · · · × A = {(x1 , x2 , ..., xn ) | (∀i ∈ Z)[1 ≤ i ≤ n ⇒ xi ∈ A]}.
n

The equality of ordered n-tuples is defined similarly as

(x1 , x2 , ..., xn ) = (a1 , a2 , ..., an ) iff for all i ∈ Z such that 1 ≤ i ≤ n, we have xi = ai .

Example (1) Let A = {1, 2} and B = {π, e, {0}}. Then

A × B = {(1, π), (1, e), (1, {0}), (2, π), (2, e), (2, {0})},
B × A = {(π, 1), (π, 2), (e, 1), (e, 2), ({0}, 1), ({0}, 2)}.

(2) R2 is the Euclidean plane, R3 is the Euclidean space, and Rn is the n-dimensional Euclidean
space:
R × R = R2 = {(x, y) | x, y ∈ R},
R × R × R = R3 = {(x, y, z) | x, y, z ∈ R},
Rn = {(x1 , x2 , ..., xn ) | x1 , x2 , ..., xn ∈ R}.

(3) Let A = [0, 2] and B = [0, 1]. Then

A × B = {(x, y) | 0 ≤ x ≤ 2, 0 ≤ y ≤ 1}
2
is a rectangle in R .

Proposition 4.3.1. Let A, B, C and D be sets. Then:

(1) A × ∅ = ∅ = ∅ × A.
(2) A × (B ∪ C) = (A × B) ∪ (A × C).
(3) A × (B ∩ C) = (A × B) ∩ (A × C).
(4) (A × B) ∩ (C × D) = (A ∩ C) × (B ∩ D).
(5) (A × B) ∪ (C × D) ⊆ (A ∪ C) × (B ∪ D). ( In general, equality need not hold.)

13
Proof. (2) We have
(x, y) ∈ A × (B ∪ C) ⇐⇒ (x ∈ A) ∧ (y ∈ B ∪ C)
⇐⇒ (x ∈ A) ∧ [(y ∈ B) ∨ (y ∈ C)]
⇐⇒ [(x ∈ A) ∧ (y ∈ B)] ∨ [(x ∈ A) ∧ (y ∈ C)]
⇐⇒ [(x, y) ∈ A × B)] ∨ [(x, y) ∈ A × C)]
⇐⇒ (x, y) ∈ (A × B) ∪ (A × C).

(5) Let (a, b) ∈ (A × B) ∪ (C × D). Then (a, b) ∈ A × B or (a, b) ∈ C × D.

Case I: (a, b) ∈ A × B
Then a ∈ A and b ∈ B. Since A ⊆ A ∪ C and B ⊆ B ∪ D, a ∈ A ∪ C and b ∈ B ∪ D.
So (a, b) ∈ (A ∪ C) × (B ∪ D).

Case II: (a, b) ∈ C × D.

Then a ∈ C and b ∈ D. Since C ⊆ A ∪ C and D ⊆ B ∪ D, a ∈ A ∪ C and b ∈ B ∪ D.
So (a, b) ∈ (A ∪ C) × (B ∪ D).
Therefore, (A × B) ∪ (C × D) ⊆ (A ∪ C) × (B ∪ D).

Finally, we given an example to show that equality needs not hold.

Take A = {1, 2}, B = {5, 6}, C = {3, 4}, D = {7, 8}. Then
(3, 5) ∈ (A ∪ C) × (B ∪ D) but (3, 5) < (A × B) ∪ (C × D).

4.4 Power sets

Definition Let X be a set. The power set of X is the set of all subsets of X, i.e.,
P(X) = {A | A ⊆ X}.

Example Let X = {1, 2, 3}. Then

P(X) = {∅, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}.
Note that P(X) has 2 = 8 elements.
3

Exercise In general, if a set X has n elements, then P(X) has 2n elements. Why?

14
Proposition 4.4.1. Let A and B be sets. Then
A ⊆ B ⇐⇒ P(A) ⊆ P(B).

Proof. (⇒) Assume that A ⊆ B. We will prove P(A) ⊆ P(B).

Let C ∈ P(A). Then C ⊆ A.
Since C ⊆ A and A ⊆ B, by Proposition 4.1.2, C ⊆ B. So C ∈ P(B).
This proves that P(A) ⊆ P(B).
(⇐) Assume that P(A) ⊆ P(B). We will prove A ⊆ B
Let x ∈ A. Then {x} ⊆ A, and so {x} ∈ P(A).
Since P(A) ⊆ P(B), {x} ∈ P(B). So {x} ⊆ B.
Since x ∈ {x} and {x} ⊆ B, x ∈ B.
Hence, A ⊆ B. □

4.5 Arbitrary union and intersection

Recall that the union and the intersection of two sets A and B are defined by
A ∪ B = {x ∈ U | (x ∈ A) ∨ (x ∈ B)}, A ∩ B = {x ∈ U | (x ∈ A) ∧ (x ∈ B)}.
Can we define the union and the intersection of more than 2 sets?

Definition Let n ∈ Z+ and let A1 , A2 , ..., An be subsets of some universal set U. Then
n
[
Ai = A1 ∪ A2 ∪ · · · ∪ An
i=1
= {x ∈ U | (x ∈ A1 ) ∨ (x ∈ A2 ) ∨ · · · ∨ (x ∈ An )}
= {x ∈ U | (∃ j ∈ Z+ )[(1 ≤ j ≤ n) ∧ (x ∈ A j )]}
= {x ∈ U | there exists j ∈ Z+ such that 1 ≤ j ≤ n and x ∈ A j },
n
\
Ai = A1 ∩ A2 ∩ · · · ∩ An
i=1
= {x ∈ U | (x ∈ A1 ) ∧ (x ∈ A2 ) ∧ · · · ∧ (x ∈ An )}
= {x ∈ U | (∀ j ∈ Z+ )[1 ≤ j ≤ n ⇒ x ∈ A j ]}
= {x ∈ U | for all j ∈ Z+ with 1 ≤ j ≤ n, x ∈ A j }.

Example Let A1 = {1, 2, 3}, A2 = {2, 3, 4} and A3 = {3, 4, 5}. Then

A1 ∪ A2 ∪ A3 = {1, 2, 3, 4, 5} and A1 ∩ A2 ∩ A3 = {3}.

15
 Definition
(i) If F is a set such that all the elements of F are sets, then we call F a family of sets.
(ii) If F is a family of sets and there is a nonempty set I such that F = {Ai | i ∈ I}, then we
say F is an indexed family of sets and I is an index set of F .

Example Let I = R+ = {t ∈ R | t > 0}. For each t ∈ I, let At = (−t, t).

For example, if t = 1, then At = A1 = (−1, 1), and if t = 0.2, then At = A0.2 = (−0.2, 0.2). Then
F = {At | t ∈ I}
= (−t, t) | t ∈ R+


is a family of sets indexed by R+ .

Example Let n ∈ Z+ and let A1 , A2 , ..., An be subsets of some universal set U.

Let F = {A1 , A2 , ..., An }. Then F is a family of set, and we can write
F = {Ai | i ∈ I} where I = {1, 2, ..., n}.
So F is indexed by I. Using the index set I, the union and intersection of A1 , A2 , ..., An are given
by
[ n
Ai = {x ∈ U | (∃i ∈ I)[x ∈ Ai ]}
i=1
= {x ∈ U | x ∈ Ai for some i ∈ I} ,
n
\
Ai = {x ∈ U | (∀i ∈ I)[x ∈ Ai ]}
i=1
= {x ∈ U | x ∈ Ai for all i ∈ I} .

This suggests how the union and the intersection of the sets in any indexed family of sets should
be defined.

Definition Let I be a nonempty set and let {Ai | i ∈ I} be a family of sets indexed by I, with
underlying universal set U (i.e. Ai ⊆ U for all i ∈ I). Then we define
[
Ai = {x ∈ U | (∃i ∈ I)[x ∈ Ai ]}
i∈I
= {x ∈ U | x ∈ Ai for some i ∈ I} ,

\
Ai = {x ∈ U | (∀i ∈ I)[x ∈ Ai ]} ,
i∈I
= {x ∈ U | x ∈ Ai for all i ∈ I} .
16
Proposition 4.5.1. Let I be a nonempty set and let {Ai | i ∈ I} be a family of sets indexed by
I, with underlying universal set U, and let B be a set. Then we have:
T S
(a) For all j ∈ I, i∈I Ai ⊆ A j and A j ⊆ i∈I Ai .
(b) (Distributive Laws) B ∪ ( i∈I Ai ) = i∈I (B ∪ Ai ), B ∩ ( i∈I Ai ) = i∈I (B ∩ Ai ).
T T S S

(c) (DeMorgan’s Laws) ( i∈I Ai )c = i∈I Aci , ( i∈I Ai )c = i∈I Aci .

S T T S

S
Proof. (a) Let j ∈ I. We will only prove A j ⊆ i∈I Ai .
Let x ∈ A j . For this x, the statement (∃i ∈ I)[x ∈ Ai ] is true, i.e., by taking i = j. So x ∈ i∈I Ai .
S
S
Hence, A j ⊆ i∈I Ai .
(b) We will only prove B ∪ ( i∈I Ai ) = i∈I (B ∪ Ai ).
T T
T T
We first show B ∪ ( i∈I Ai ) ⊆ i∈I (B ∪ Ai ).
T T
Let x ∈ B ∪ ( i∈I Ai ). Then x ∈ B or x ∈ i∈I Ai .
Case I: x ∈ B.
T
Then for all i ∈ I, x ∈ B ∪ Ai , and hence x ∈ i∈I (B ∪ Ai ).
\
Case II: x ∈ Ai .
i∈I T
Then for all i ∈ I, x ∈ Ai , and so x ∈ B ∪ Ai . This also gives x ∈ i∈I (B ∪ Ai ).
T T
This proves that B ∪ ( i∈I Ai ) ⊆ i∈I (B ∪ Ai ).
T T
Next we show i∈I (B ∪ Ai ) ⊆ B ∪ ( i∈I Ai ).
T
Let x ∈ i∈I (B ∪ Ai ). Then for all i ∈ I, x ∈ B ∪ Ai .
Case I: x ∈ B.
T
Then x ∈ B ∪ ( i∈I Ai ).
Case II: x < B.
Let i ∈ I. Then since x ∈ B ∪ Ai and x < B, we must have x ∈ Ai .
T T
Hence, x ∈ i∈I Ai , and so x ∈ B ∪ ( i∈I Ai ).
T T
This shows that i∈I (B ∪ Ai ) ⊆ B ∪ ( i∈I Ai ). □

Special case I = Z+ = {1, 2, 3, 4, ...}:

If {Ai | i ∈ Z+ } = {A1 , A2 , A3 , A4 , ...} is a family of sets indexed by Z+ , then we also write
[ [∞ \ ∞
\
Ai = Ai , Ai = Ai .
i∈Z+ i=1 i∈Z+ i=1

17
 Example For each i ∈ Z+ , let Ai = {i, i + 1}; i.e.,
A1 = {1, 2}, A2 = {2, 3}, A3 = {3, 4}, ...
Prove that ∞ ∞
[ \
Ai = Z+ and Ai = ∅.
i=1 i=1
+
Solution: First we show that i=1 Ai = Z .
S∞
+
Let n ∈ ∞
S
i=1 Ai . Then there exists j ∈ Z such that n ∈ A j .
Since A j ⊆ Z+ and n ∈ A j , n ∈ Z+ .
+
This shows ∞
S
i=1 Ai ⊆ Z .

Next, we let n ∈ Z+ . Then n ∈ An = {n, n + 1}.

Since An ⊆ ∞ Ai , we have n ∈ ∞
S S
i=1 i=1 Ai .
+ S∞
Thus, Z ⊆ i=1 Ai .
+ + +
Since ∞ i=1 Ai = Z .
S S∞ S∞
i=1 Ai ⊆ Z and Z ⊆ i=1 Ai , we obtain

Next, we shall prove ∞ i = ∅.

T
i=1 AT
By Proposition 4.1.3 , ∅ ⊆ ∞ Ai . So we only need to show ∞
T
i=1 T i=1 Ai ⊆ ∅.
By Part (a) of Proposition 4.5.1, ∞ ∞
T
i=1 iA ⊆ A 1 and A
i=1 i ⊆ A 3 . Then by Part (ii) of Proposition
4.2.1,
\ ∞
Ai ⊆ A1 ∩ A3 = {1, 2} ∩ {3, 4} = ∅. □
i=1

Example For each i ∈ Z+ , let Ai = [0, 1i ). Find

S∞ T∞
i=1 Ai and i=1 Ai .

Solution: We claim that (a) ∞ i=1 Ai = A1 = [0, 1), and (b) i=1 Ai = {0}.
S T∞

Proof of (a): Let x ∈ i=1 Ai . Then there exists j ∈ Z+ such that x ∈ A j = [0, 1j ). So
S∞

0 ≤ x < 1j ≤ 11 = 1. Thus x ∈ A1 = [0, 1). This shows that ∞

S
i=1 Ai ⊆ A1 .

On the other hand, by Part (a) of Proposition 4.5.1, we have A1 ⊆ ∞

S
i=1 Ai .

Hence i=1 Ai = A1 = [0, 1).

S∞

Proof of (b): Note that for all i ∈ Z+ , 0 ∈ Ai = [0, 1i ). So 0 ∈ ∞

T T∞
i=1 Ai , and {0} ⊆ i=1 Ai .
T∞
Next, we let x ∈ i=1 Ai .
Claim: x = 0.
We prove this claim by contradiction. Assume that x , 0. Then x > 0.
Take ε = x. Then by the Archimedean Property, there exists N ∈ Z+ such that N1 < x. So
x < AN and therefore x < ∞
T
i=1 Ai , which is a contradiction.

By the claim, x ∈ {0}. This proves that ∞

T
i=1 Ai ⊆ {0}.

Hence we have i=1 Ai = {0}.

T∞

18
 Exercise For each t ∈ R+ , let At = (−t, t). Prove that
[ \
At = R and Ai = {0}.
t∈R+ t∈R+

Sometimes, a family of sets is not indexed. In this case, we shall use the following notation.
Definition Let F be a nonempty family of sets. Then we define
[
A = {x ∈ U | x ∈ A for some A ∈ F } ,
A∈F
\
A = {x ∈ U | x ∈ A for all A ∈ F } .
A∈F

Exercise Let F be the family of all subsets of Z with 2 elements. Prove that
[ \
A = Z and A = ∅.
A∈F A∈F

4.6 Russell’s paradox

Naive set theory was developed by Dedekind and Cantor in around 1870-1900. It treats set
theory informally and is based on the following two assumptions.
Extensionality: Two sets are equal exactly when they have the same elements.
Comprehension: Any collection {x | P(x)} is a set as long as the defining condition P(x) is well
defined: given x, it must be clear that either x has the property or it does not.
The second assumption says that there is a set containing exactly all the mathematical objects
which has the property P(x). For example, if P(x) is the statement “x is a real number and
x2 = 1”, then
{x | P(x)} = {−1, 1}.
If P(x) is the statement “x is a real number and x2 < 0”, then
{x | P(x)} = ∅.
However, the assumption of Comprehension leads to a contradiction, called Russell’s paradox.

Consider the predicate P(x) x is a set and x < x , and consider the set defined by this predicate:
A = {x | P(x)} = {x | x is a set and x < x}.
Since A is a set, we can ask: Is A ∈ A?
If A ∈ A, then A must satisfy the defining condition of A, i.e A < A.
But if A < A, then A satisfies the defining condition for A, and so A ∈ A.

19
Therefore we have proved:
A ∈ A ⇔ A < A,
which is a contradiction.
This was discovered by the English mathematician Bertrand Russell in 1902.

The barber paradox: The only barber in a village sets a rule that he will shave everyone in
the village who does not shave himself. Should the barber shave himself?

Axiomatic Set Theory was later developed to fix the Russell paradox. Essentially it puts a
restriction on what type of sets exist. In this theory, Russell’s paradox become the proof of the
statement that there is no “set of all sets”.

20