Sets and Set Operations

A set represents a collection of items, where each item is called a member of the set.

The most common way to represent a set is by using list notation, where the set members are listed
one-by-one, and the list is delimited by braces. For example,

{2, 3, 5, 7, 11}

uses list notation to describe the set consisting of all prime numbers that do not exceed 11. Note
that the order in which the members are listed does not matter. Indeed the sets {2, 3, 5, 7, 11}
and {3, 11, 5, 2, 7} are identical. Also, each member occurs only once in the set, meaning that, e.g.
{1, 2, 2, 3, 3, 3} = {1, 2, 3}.

The set having no members is called the empty set, and is denoted by ∅.

It is often convenient to provide a name or label for a given set. For example, I is used to denote
the set whose members are the numbers 0, ±1, ±2, . . .. This book uses the convention that set names
begin with a capital letter. Moreover, capital letters A, B, C, . . . are used when denoting an abstract
set, meaning some arbitrary set whose members have not been specified. In later sections and chapters
we shall see several other methods for naming and representing a set.

We may use the membership symbol ∈ to indicate that an item is a member of some set. For
example, −2 ∈ I asserts that -2 is a member of I. On the other hand, 3.14 6∈ I asserts that 3.14 is
not a member of I.

Sometimes we need to use informal list notation by including the ellipsis . . . to indicate that a
pattern is to be continued up to some value. The beginning pattern usually consists of one or more
members, followed by an ellipsis, and ending with a final member of the set.

Example 1. Use informal list notation to describe the set of integers between 1 and 100 that are
divisible by 3.

Solution.

1
Set cardinality

The cardinality of set A, denoted |A|, is equal to the number of members of A. A set may be
classified based on its type of cardinality.

Finite a set of the form A = {s1 , s2 , . . . , sn }, in which case |A| = n

Countably Infinite a set whose members can be written in an infinite list, with no members being
repeated, in which case |A| = ∞

Uncountably Infinite a set that is not finite and whose members cannot be written in an infinite
list having no repeats

Example 2. The set of natural numbers N = {0, 1, 2, . . .} is countably infinite since its members
may be listed as 0, 1, 2, . . ..

Example 3. Show that the set of integers I is countably infinite.

Solution.

2
Example 4. A rational number is any number that may be written as a fraction p/q, where p and
q are integers, and q 6= 0. Perhaps somewhat surprising is that the set Q of rational numbers is
countably infinite. To show this we use a method called dovetailing, where members of Q are listed
in rounds. In particular, i members of Q are listed in round i, i = 1, 2, . . .. In what follows we show
how the positive rationals can be listed with dovetailing. In round 1 we list 1/1. In round 2 we list
1/2, 2/1. In round 3 we list 1/3, 2/2, 3/1. In round 4 we list 1/4, 2/3, 3/2, 4/1. See the pattern? To
generalize, in round i we list 1/i, 2/(i − 1), 3/(i − 2), . . . , i/1. We leave it as exercise to compute the
round for which fraction p/q is listed, for positive integers p and q. Finally, notice that in odd rounds
the number 1 is always listed. For example, in round 1 it is listed as 1/1 = 1, and in round 3 as
2/2 = 1. Since our infinite list is not allowed to have repeats, before listing a fraction we must first
check if it has already been listed (in the form of a different fraction) in a previous round. If yes,
then we do not list it again. Therefore, we’ve demonstrated a way to list all rational numbers in a
way that each number appears exactly once in the list.

3
Example 5. Using the dovetailing technique of the previous example (with no removal of repeats,
for what value of i ≥ 1 is 51/137 the i th fraction listed?

Solution.

4
Example 6. Using the dovetailing technique of the previous example, what fraction will be the
100th fraction listed?

Solution.

5
For the remainder of the book, N denotes the natural numbers {0, 1, 2, . . .}, I the integers, Q the
rational numbers, and R the real numbers. Also, the addition of a plus, such as R+ , denotes the
positive members of a numerical set, while the addition of a minus, such as I − denotes the negative
members of a numerical set.

Subsets

Set A is said to be a subset of set B iff every member of A is also a member of B. This is symbolically
denoted by A ⊆ B. Moreover, A is said to be a proper subset of B, denoted A ⊂ B, iff it is a
subset of B, but there is some member of B who is not a member of A.

6
Example 7. Sets {3} and {1, 3} are proper subsets of {1, 2, 3}, while {1, 2, 3} is a subset of {1, 2, 3},
but not a proper subset. Also, is A = {{1, 2}, {3, 4}, 5} a subset of B = {1, 2, 3, 4, 5}? No since, e.g.,
{1, 2} ∈ A (yes, a set can be a member of another set!), but {1, 2} 6∈ B. This is true since {1, 2} is a
set, and B’s members are the natural numbers 1 through 5.

Example 8. List all subsets of the set {∅, 1, {2, 3}}.

Solution.

7
The power set of a set S, denoted P(S), is defined as the set of all subsets of set S.

Example 9. For S = {1, 2, 3} we have

P(S) = {∅, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}.

Proposition 1. If S is a finite set with |S| = n, then |P(S)| = 2n .

Proof of Proposition 1. Without loss of generality, we may assume that S = {1, 2, . . . , n}. Let
A be a subset of S and consider the statements i ∈ A, for i = 1, 2, . . . , n. Each of these statements
will either evaluate to true (1) or false (0), depending on the choice of i and A. For example, if
A = {1, 3, 5} and i = 2, then the statement 2 ∈ A evaluates to 0, since 2 is not a member of A.
Placing these statement evaluations side-by-side, we get the binary sequence

(1 ∈ A, 2 ∈ A, . . . , n ∈ A).

For example, if n = 5 and A = {1, 3, 5}, then

(1 ∈ A, 2 ∈ A, 3 ∈ A, 4 ∈ A, 5 ∈ A) = (1, 0, 1, 0, 1).

Conversely, every binary sequence of length n corresponds with a subset of S. For example, if
n = 5, then (0, 0, 1, 0, 0) corresponds with subset {3}, while (1, 1, 1, 0, 1) corresponds with {1, 2, 3, 5}.
Therefore, the number of subsets of S is equal to the number of binary sequences having length n, and
the reader may check that there are 2n such sequences. As an example, the following subset table
shows the correspondence between binary sequences of length three and subsets of S = {1, 2, 3}.

1∈A 2 ∈ A 3 ∈ A Subset A
0 0 0 ∅
0 0 1 {3}
0 1 0 {2}
0 1 1 {2, 3}
1 0 0 {1}
1 0 1 {1, 3}
1 1 0 {1, 2}
1 1 1 {1, 2, 3}

8
Set operations

A binary arithmetic operation represents a way of taking two numbers, a and b, and associating
with them a third number c that is obtained by performing the operation on a and b. For example,
the binary addition operation associates with a and b the number c = a + b. In what follows we
introduce some analogous binary set operations. Each of these operations takes two sets, A and B,
and associates with them a third set in accordance with some rule of operation.

Union x ∈ A ∪ B iff either x ∈ A or x ∈ B

Intersection x ∈ A ∩ B iff x ∈ A and x ∈ B

Difference x ∈ A − B iff x ∈ A and x 6∈ B

Symmetric Difference x ∈ A ⊕ B iff x ∈ A or x ∈ B, but not both; i.e. A ⊕ B = (A − B) ∪ (B − A)

Cartesian Product (a, b) ∈ A × B iff a ∈ A and b ∈ B

Notice that for the Cartesian product, a member of A × B has the form (a, b), which is called
a (binary) tuple, while a and b each represent a component of the tuple. Note that the term
“tuple” is synonymous with several others in math and computing, including array, vector, list, and
sequence. These tuples of A × B represent all possible ways of combining a member of A with a
member of B. Also, the Cartesian product may be generalized to an arbitrary number of sets, such
as A1 × A2 × · · · × Ak , in which case the members of this set are k-tuples of the form (a1 , a2 , . . . , ak ),
such that ai ∈ Ai , for all i = 1, 2, . . . , k.

9
Example 10. Given sets A = {1, 3, 5, 6, 7, 9} and B = {0, 2, 4, 5, 6, 7, 8, 10}, we have A ∪ B =
{0, 1, 2, . . . , 10}, A ∩ B = {5, 6, 7}, A − B = {1, 3, 9}, and A ⊕ B = {0, 1, 2, 3, 4, 8, 9, 10}.

Example 11. Let E denote the set of all even integers. Compute N ∪ E, N ∩ E, N − E, E − N , and
N ⊕ E.

Solution.

10
Example 12. Given sets A = {a, b}, B = {1, 2, 3}, then A×B = {(a, 1), (a, 2), (a, 3), (b, 1), (b, 2), (b, 3)}.

11
In addition to the above binary operations, there one important unary operation called the com-
plement of set A, and denoted A. In particular, x ∈ A iff x 6∈ A. The complement is only useful
in cases when there is a pre-defined universe U consisting of all possible items that could appear in
any set. In this case we have A = U − A. For example, if the universe U is given as the integers from
1 to 10, and A = {1, 3, 4, 8}, then A = {1, 2, 5, 7, 9, 10}.

We say that two sets A and B are disjoint iff A ∩ B = ∅. For example, the set of even integers and
the set of odd integers are disjoint, since no integer is both even and odd.

The following is a table of identities that are always true for any three sets A, B, and C.

Identity Description
A∪∅=A Identity
A∩U =A
A∪U =U Domination
A∩∅=∅
A=A Double Complement
A∪A=A Idempotent
A∩A=A
A∪B =B∪A Commutative
A∩B =B∩A
(A ∪ B) ∪ C = A ∪ (B ∪ C) Associative
(A ∩ B) ∩ C = A ∩ (B ∩ C)
A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C) Distributive
A ∩ (B ∪ C) = (A ∩ B) ∪ (B ∩ C)
A∪B =A∩B De Morgan
A∩B =A∪B

12
A membership table is a table that can be used to verify a set identity of the form S1 = S2 , where
S1 and S2 are set expressions that depend on a finite number of arbitrary sets, meaning each set can
be any possible set. The rows of the table consist of binary vectors that encode the membership (or
lack of membership) of an arbitrary item x in each of the arbitrary sets that comprise the identity.
For example, if the identity uses arbitrary sets A, B, and C, then the binary vectors will have a
length equal to three, and a vector such as (0 1 0), would indicate x 6∈ A, x ∈ B, and x 6∈ C. Using
this vector, we may compute x ∈ S1 and x ∈ S2 , and verify that the values are equal. If they are ever
unequal, then S1 = S2 is not an identity. However, if they are always equal for all 23 = 8 different
vector encodings, then S1 = S2 is in fact an identity.

Example 13. Verify the first distributivity axiom using a membership table

13
Exercises
1. Which of the following pairs of sets are equal?
a. {1, 3, 3, 3, 5, 5, 5, 5, 5}, {1, 3, 5}
b. {{1}}, {1, {1}}
c. ∅, {∅}
2. Use list notation to express the set of positive integers that are perfect squares and do not
exceed 100.
3. Use list notation to express the set of nonnegative integers that are less than 7.
4. Use list notation to express the set of rational numbers x for which x2 = 2.
5. Use informal list notation to express the set of fractions of the form 1/n, where n is an even
positive integer between 1 and 1000 (inclusive).
6. Given A = {2, 4, 6}, B = {2, 6}, C = {4, 6}, and D = {4, 6, 8}, consider each pair of sets and
determine which, if any, is a subset of the other. For example is A a subset of B? B of A? etc..
7. Prove that the set of positive integers divisible by either 2 or 3 is countably infinite.
8. Prove that if A and B are countably infinite sets, then so is A ∪ B.
9. Prove that if A and B are countably infinite sets, then so is A × B. Hint: describe a dovetailing
procedure similar to that used to show that the set of rational numbers is countably infinite.
10. Recall the dovetailing procedure described in Example 4. In what round will 59/457 be listed?
11. Recall the dovetailing procedure described in Example 4. What fraction will be the 1000th
listed?
12. List all the subsets of the set {1, 2, 3, 4}.
13. List all the subsets of {∅, {a}}.
14. How many elements are in P(A), where A is the set from Exercise 2?
15. Let A = {1, 2, 3, 4, 5}, and B = {0, 3, 6}. Find A ∪ B, A ∩ B, A ⊕ B, A − B, and B − A.
16. Let A = {a, b, c, d, e}, and B = {a, b, c, d, e, f, g, h}. Find A ∪ B, A ∩ B, A ⊕ B, A − B, and
B − A.
17. Let A be the set of nonnegative integers divisible by 2, while B is the set of nonnegative integers
divisible by 3. Use set-builder notation to express A ∪ B, A ∩ B, A ⊕ B, A − B, and B − A.
18. Let Ai = {1, 2, . . . , i}, for i = 1, 2, 3, . . .. Use list notation to express
n
[
Ai = A1 ∪ A2 ∪ · · · ∪ An ,
i=1

and n
\
Ai = A1 ∩ A2 ∩ · · · ∩ An ,
i=1

14
19. Repeat the previous problem, but now assume Ai = {. . . , −2, −1, 0, 1, 2, . . . , i}, for i = 1, 2, 3, . . ..

20. Find A × B and B × A, where A = {a, b, c, d}, and B = {y, z}.

21. Provide sets A, B, and C for which A × (B × C) 6= (A × B) × C. Justify your conclusion.

22. Show in general (i.e. not by a specific example) that if A and B are nonempty, and A 6= B,
then A × B 6= B × A.

23. Let E denote the set of English words that appear in your textbook, while, P denotes the set
of pages. Give an estimate of the size of E × P . Give an estimate of the size of the subset A
of E × P , where (w, p) ∈ A iff word w appears on page p.

24. Use a membership table to prove that the ⊕ operation is associative, i.e.

A ⊕ (B ⊕ C) = (A ⊕ B) ⊕ C.

25. What can you say about the sets A and B if A ⊕ B = A? Hint: use the previous exercise and
the fact that A ⊕ A = ∅ for arbitrary set A.

26. Use a membership table to verify that, for any sets A, B, and C, (B−A)∪(C −A) = (B∪C)−A.

27. Verify De Morgan’s first law using a membership table.

28. Prove or disprove the following statements about arbitrary sets A, B, and C.

a. If A ∪ C = B ∪ C, then A = B.
b. If A ∩ C = B ∩ C, then A = B.
c. If A ∪ C = B ∪ C and A ∩ C = B ∩ C, then A = B.

15
Exercise Solutions
1. Which of the following pairs of sets are equal?

a. {1, 3, 3, 3, 5, 5, 5, 5, 5} = {1, 3, 5} since each set member is only counted once; i.e. both sets
are assumed to contain exactly the numbers 1, 3, and 5.
b. {{1}} =
6 {1, {1}} since the first set has one member, while the second has two.
c. ∅ 6= {∅} since the first set has no members, while the second has one, namely the empty
set.

2. {1, 4, 9, 16, 25, 36, 49, 64, 81, 100}

3. {0, 1, 2, 3, 4, 5, 6}

4. ∅

5. {1/2, 1/4, 1/6, . . . , 1/1000}

6. We have B ⊂ A, C ⊂ A, and C ⊂ D.

7. {2, 3, 4, 6, 8, 9, 10, 12, 14, 15, . . .}.

8. Let a1 , a2 , a3 be a listing of members of A, and b1 , b2 , b3 be a listing of members of B. Then

a1 , b1 , a2 , b2 , a3 , b3 , . . . is a listing of members of A ∪ B.

9. Let a1 , a2 , a3 be a listing of members of A, and b1 , b2 , b3 be a listing of members of B.

Round 1. Add (a1 , b1 ) to the list.
Round 2. Add (a1 , b2 ), and (a2 , b1 ) to the list.
Round 3. Add (a1 , b3 ), (a2 , b2 ), and (a3 , b1 ) to the list.
Round i ≥ 4. Add (a1 , bi ), (a2 , bi−1 ), (a3 , bi−2 ), . . . , (ai , b1 ) to the list.

10. In Round 59 59/1 is listed. Moreover, in 456 additional rounds 59/457 is listed. This makes
for a total of 59 + 456 = 515 rounds.

11. We’re looking for the first n for which 1 + 2 + · · · + (n − 1) + n = n(n + 1)/2 ≥ 1000. This
means that n2 + n − 2000 ≥ 0. But the equation

n2 + n − 2000 = 0

has positive solution √

n = −0.5 + 7999/2 ≈ 44.22.
Therefore, our desired n is n = 45. Moreover, after 45 rounds, 1035 fractions will have been
listed, and the last one listed is 45/1. Finally, moving back 34 places takes us to the 1000th
listed fraction (45 − 35)/(1 + 35) = 11/35.

16
12. The following subset table lists all the subsets of the set {1, 2, 3, 4}.
1∈S 2∈S 3∈S 4∈S Subset S
0 0 0 0 ∅
0 0 0 1 {4}
0 0 1 0 {3}
0 0 1 1 {3, 4}
0 1 0 0 {2}
0 1 0 1 {2, 4}
0 1 1 0 {2, 3}
0 1 1 1 {2, 3, 4}
1 0 0 0 {1}
1 0 0 1 {1, 4}
1 0 1 0 {1, 3}
1 0 1 1 {1, 3, 4}
1 1 0 0 {1, 2}
1 1 0 1 {1, 2, 4}
1 1 1 0 {1, 2, 3}
1 1 1 1 {1, 2, 3, 4}

13. The subsets of {∅, {a}} are ∅, {∅}, {{a}}, and {∅, {a}}.

14. |P(A)| = 210 = 1024

15. A ∪ B = {0, 1, 2, 3, 4, 5, 6}, A ∩ B = {3}, A ⊕ B = {0, 1, 2, 4, 5, 6}, A − B = {1, 2, 4, 5}, and

B − A = {0, 6}

16. A ∪ B = B, A ∩ B = A, A ⊕ B = {f, g, h}, A − B = ∅, and B − A = {f, g, h}.

17. A ∪ B = {x|x mod 2 = 0 ∨ x mod 3 = 0}, A ∩ B = {x|x mod 2 = 0 ∧ x mod 3 = 0},

A ⊕ B = {x|x mod 2 = 0 ⊕ x mod 3 = 0}, A − B = {x|x mod 2 = 0 ∧ x mod 3 6= 0},
B − A = {x|x mod 2 6= 0 ∧ x mod 3 = 0}.

18. We have n n
[ \
Ai = {1, 2, . . . , n} and Ai = {1}.
i=1 i=1

19. We have n n
[ \
Ai = {. . . , −2, −1, 0, 1, 2, . . . , n} and Ai = {. . . , −2, −1, 0, 1}.
i=1 i=1

20. A × B = {(a, y), (b, y), (c, y), (d, y), (a, z), (b, z), (c, z), (d, z)},
B × A = {(y, a), (y, b), (y, c), (y, d), (z, a), (z, b), (z, c), (z, d)}.

21. Let A = {1}, B = {a}, and C = {z}. Then (1, (a, z)) 6= ((1, a), z), since the first tuple has
elements 1 and (a, z), while the second has elements (1, a), and z. Hence, they are two different
tuples.

22. Assume A and B are nonempty and A 6= B. Let a ∈ A and b ∈ B be members of A and B, such
that either a 6∈ B or b 6∈ A is true. Case 1. a 6∈ B. Then (a, b) ∈ A × B, but (a, b) 6∈ B × A.
Case 2. b 6∈ A. Then (b, a) ∈ B × A, but (b, a) 6∈ A × B.

17
23. The estimate equals w × p, where w is your estimate of the number of words per page of your
textbook, and p is the number of pages of your textbook.

24. Since its last two columns are identical, the following membership table establishes A⊕(B⊕C) =
(A ⊕ B) ⊕ C.
x∈ x∈ x∈ x∈
x∈A x∈B x∈C A⊕B B⊕C A ⊕ (B ⊕ C) (A ⊕ B) ⊕ C
0 0 0 0 0 0 0
0 0 1 0 1 1 1
0 1 0 1 1 1 1
0 1 1 1 0 0 0
1 0 0 1 0 1 1
1 0 1 1 1 0 0
1 1 0 0 1 0 0
1 1 1 0 0 1 1
25. We have
A ⊕ (A ⊕ B) = (A ⊕ A) ⊕ B = ∅ ⊕ B = B,
where the first equality makes use of the associativity of ⊕. But since A ⊕ B = A, we also have

A ⊕ (A ⊕ B) = A ⊕ A = ∅.

Therefore, B = ∅.

26. The following membership table establishes (B − A) ∪ (C − A) = (B ∪ C) − A.

x∈ x∈ x∈ x∈ x∈
x∈A x∈B x∈C B−A C −A B∪C (B ∪ C) − A ((B − A) ∪ (C − A))
0 0 0 0 0 0 0 0
0 0 1 0 1 1 1 1
0 1 0 1 0 1 1 1
0 1 1 1 1 1 1 1
1 0 0 0 0 0 0 0
1 0 1 0 0 1 0 0
1 1 0 0 0 1 0 0
1 1 1 0 0 1 0 0

27. Since the final two columns are equal, the following membership table establishes A ∪ B =
A ∩ B.
x ∈ A x ∈ B x ∈ A x ∈ B x ∈ (A ∪ B) x ∈ A ∪ B x ∈ (A ∩ B)
0 0 1 1 0 1 1
0 1 1 0 1 0 0
1 0 0 1 1 0 0
1 1 0 0 1 0 0
28. Prove or disprove the following statements about arbitrary sets A, B, and C.

a. If A ∪ C = B ∪ C, then A = B. Sometimes false: Let A = ∅, B = {1}, C = {1}. Then

A ∪ C = B ∪ C, but A 6= B

18
b. If A ∩ C = B ∩ C, then A = B. Sometimes false: Let A = {1, 2}, B = {1, 3}, C = {1}.
Then A ∩ C = B ∩ C, but A 6= B.
c. Always true. Proof: suppose x ∈ A is true. If x 6∈ B, then, since we’re assuming
A ∪ C = B ∪ C, it must be true that x ∈ C since, otherwise, x would not be a member
of B ∪ C, even though it is a member of A ∪ C. But if x ∈ C, then x ∈ A ∩ C. But this
contradicts A ∩ C = B ∩ C, since x ∈ B ∩ C contradicts x 6∈ B. Therefore, we must have
x ∈ B, and so A ⊆ B. Similarly, we may prove that B ⊆ A, and so A = B.

19