MTH1301: Elementary Mathematics I

Module 01: Elementary Set Theory

(Draft)

Mansur Babagana
Bayero University, Kano
Update: November 21, 2021

Contents

1 Introduction 3

2 Sets 3
2.1 Special Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

3 Set Notations 4
3.1 Statement Form . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
3.2 Roster or Tabular Form . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
3.3 Rule or Set Builder Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

4 Equality of Sets 7

5 Null Set 8

6 Subsets 8
6.1 Proper Subset . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
7 Comparability 10

8 Theorem and Proof 11

8.1 Some Notations used in Mathematical Proofs . . . . . . . . . . . . . . . . . . 11

9 Set of Sets 12

10 Universal Set 12

11 Power Set 13

12 Disjoint Sets 14

13 Venn-Euler Diagrams 14

14 Set Operations 15
14.1 Union . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
14.2 Intersection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
14.3 Difference . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
14.4 Symmetric Difference . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

15 Complement 18

16 Operation on Comparable Sets 20

17 Laws of the Algebra of Sets 21

18 Principle of Duality 21

19 Finite Sets 22

20 Cardinality 22
20.1 Inclusion-Exclusion Principle . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

21 References 24

2
1 Introduction
Why learn Set Theory? Set Theory is an important language and tool for reasoning. It’s a
basis for Mathematics—pretty much all Mathematics can be formalised in Set Theory.
Why is Set Theory important for Computer Science? Set Theory is a useful tool for
formalising and reasoning about computation and the objects of computation. Set Theory is
indivisible from Logic where Computer Science has its roots. It has been and is likely to
continue to be a a source of fundamental ideas in Computer Science from theory to practice;
Computer Science, being a science of the artificial, has had many of its constructs and ideas
inspired by Set Theory. The strong tradition, universality and neutrality of Set Theory make it
firm common ground on which to provide unification between seemingly disparate areas and
notations of Computer Science. Set Theory is likely to be around long after most present-day
programming languages have faded from memory.
A knowledge of Set Theory should facilitate your ability to think abstractly. It will provide
you with a foundation on which to build a firm understanding and analysis of the new ideas in
Computer Science that you will meet.

2 Sets
A fundamental concept in all branches of mathematics is that of a set. Intuitively,
Definition 1 (Set) A set is any well-defined list, collection, or class of objects.

The objects in sets, as we shall see from our examples, can be anything: numbers, people,
letters, rivers, etc. These objects ·are called the elements or members of the set. The objects in
sets, as we shall see from examples, can be anything: But for clarity, we now list ten particular
examples of sets:
Example 1 The numbers 2, 3, 5, 7, 11
Example 2 The solutions of the equation x2 + 5x + 6 = 0
Example 3 The vowels of the alphabet a, e, i, o, u.
Example 4 The people living in Kano State
Example 5 The students Auwal, Emmanuel, Adebayo, Sani
Example 6 The students who have registered MTH1301
Example 7 The universities, BUK, KUST, YUMSUK, SLU
Example 8 Capital cities of the Nigerian states
Example 9 The numbers 1, 3, 5, 7, 9, . . .
Example 10 The shops at BUK New-site Coke Village

Note that the sets in the odd numbered examples are defined, that is, presented, by actually listing
its members; and the sets in the even numbered examples are defined by stating properties that
is, rules, which decide whether or not a particular object is a member of the set.

3
2.1 Special Sets

Some sets occur very often in the mathematics, and special symbols are used to represent such
sets; examples of such symbols are:
N = the set of natural numbers or positive integers: 1, 2, 3, . . .
W = the set of whole numbers: 0, 1, 2, 3, . . .
Z = the set of all integers: . . . , −2, −1, 0, 1, 2, . . .
p
Q = the set of rational numbers: that is numbers that can be written as where p and q are
q
integers and q 6= 0
R = the set of real numbers
C = the set of complex numbers
More on R and C in the next module.

3 Set Notations
Sets will usually be denoted by capital letters;
A, B, C, X, Y, . . .

Elements of a set are usually denoted by lower case letters;

a, b, c, x, y . . .

In representation of a set the following three methods are commonly used:

1. Statement form method
2. Roster or tabular form method
3. Rule or set builder form notation

3.1 Statement Form

In this, well-defined description of the elements of the set is given and the same are enclosed in
curly brackets.
Example 11
(i) The set of even numbers less than 14 is written as: even numbers less than 14.
(ii) A set of FCSIT students that have registered MTH1301 during 2020/2021 Academic
Session.
(iii) A set of numbers less than 55 and greater than 35.

3.2 Roster or Tabular Form

In this, elements of the set are listed within the pair of brackets { } and are separated by commas.
Example 12

4
 (i) Let N denote the set of first five natural numbers. Therefore,
N = {1, 2, 3, 4, 5}
(ii) The set V of all vowels of the English alphabet. Therefore
V = {a, e, i, o, u}
(iii) The set of all odd numbers less than 9. Therefore
X = {1, 3, 5, 7}
(iv) The set of all natural number which divide 12. Therefore
Y = {1, 2, 3, 4, 6, 12}
(v) The set of all letters in the word BAYEROUNIVERSITY. Therefore
Z = {B, A, Y, E, R, O, U, N, I, V, S, T, Y }
(vi) W is the set of last first months of the year. Therefore
W = {January, February, March, April}

Note: The order in which elements are listed is immaterial but elements must not be repeated.

3.3 Rule or Set Builder Notation

In this, a rule, or the formula or the statement is written within the pair of brackets so that the
set is well defined. In the set builder form, all the elements of the set, must possess a single
property to become the member of that set.
In this form of representation of a set, the element of the set is described by using a symbol ‘x’
or any other variable followed by a colon ‘:’ or pipe ‘|’ is used to denote such that and then we
write the property possessed by the elements of the set and enclose the whole description in
braces. In this, the colon stands for ‘such that’ and braces stand for ‘set of all’.
Example 13
(i) Let P is a set of counting numbers greater than 12; the set P in set-builder form is written
as:
P = {x : x is a counting number and greater than 12}
or
P = {x | x is a counting number and greater than 12}
This will be read as, ‘P is the set of elements x such that x is a counting number and is
greater than 12’. Note that the symbol ‘:’ or ‘|’ placed between 2 x’s stands for such that.
(ii) Let A denote the set of even numbers between 6 and 14. It can be written in the set builder
form as;
A = {x | x is an even number, 6 < x < 14}
or
A = {x : x ∈ P, 6 < x < 14 and P is an even number}
(iii) If X = {4, 5, 6, 7}, then X can express in set builder form as
X = {x : x is a natural number and 3 < x < 8}

5
(iv) The set A of all odd natural numbers can be written as
A = {x : x is a natural number and x = 2n + 1 for n ∈ W}
Example 14 Representation of the set of integers lying between -2 and 3 using the three methods
of representation of a set.
Statement Form: {I is a set of integers lying between -2 and 3}
Roster/Tabular Form: I = {−1, 0, 1, 2}
Set Builder Form: I = {x : x ∈ Z, −2 < x < 3}

Note that Examples 1 through 10 uses the statement form. To further demonstrate the use of
the Tabular and Set builder notations, we rewrite the sets in Examples 1 through 10. We denote
the sets by A1 , A2 , . . . , A10
Example 15 A1 = {2, 3, 5, 7, 11}
Example 16 A2 = {x | x2 + 5x + 6 = 0}
Example 17 A3 = {a, e, i, o, u}
Example 18 A4 = {x | x is a person living in Kano State}
Example 19 A5 = {Auwal, Emmanuel, Adebayo, Sani}
Example 20 A6 = {x | x is a student and x have registered MTH1301}.
Note that the “and” connecting the two conditions ‘x is a student”, “x have registered MTH1301”
can be replace by a comma, that is “,”. So A6 can be written as
A6 = {x | x is a student, x have registered MTH1301}
Example 21 A7 = {BUK, KUST, YUMSUK, SLU}
Example 22 A8 = {x | x is a state capital city, x is in Nigeria}
Example 23 A9 = {1, 3, 5, 7, 9, . . .}
Example 24 A10 = {x | x is a shop, x is located BUK at New-site Coke Village}

If an object x is a member of a set A, i.e., A contains x as one of its elements, then we write
x∈A
Which can be read “x belongs to A” or “x is in A”. If, on the other-hand, an object x is not a
member of a set A, i.e A does not contain x as one of its elements, then we write
x∈
/A
It is a common custom in mathematics to put a vertical line “|” or “/” through a symbol to
indicate the opposite or negative meaning of the symbol.
Example 25 Let A = {a, e, i, o, u}. Then u ∈ A, b ∈
/ A, i ∈ A, m ∈
/A
Example 26 Let B = {x | x is odd}. Then 5 ∈ B, 8 ∈
/ A, 13 ∈ A, 16 ∈
/A

Problem 1 State the following set in statement form

(a) A = {x | x lives in Kano}

6
 (b) B = {x | x speaks Hausa}
(c) C = {x | x is older than 20 years}
(d) D = {x | x is a Nigerian citizen}
(e) E = {x | x is a student at FCSIT, BUK}
Problem 2 State the following set in tabular/roster form
(a) P = {x | x2 − x − 2 = 0}
(b) Q = {x | x is a letter in the word “elementary”}
(c) R = {x | x2 = 9, x − 3 = 5}
(d) S = {x | x is a vowel}
(e) T = {x | x is a digit in the number 1301}

4 Equality of Sets
Set A is equal to set B if they both have the same members, i.e if every element which belongs
to A also belongs to B and if every element which belongs to B also belongs to A. We denote
the equality of sets A and B by
A=B
Example 27 Let A = {6, 7, 8, 9} and B = {9, 7, 8, 6}. Then A = B, that is 6, 7, 8, 9 = 9, 7, 8,
6, since each of the elements 6, 7, 8 and 9 of A belongs to B and each of the elements 9, 7, 8 and
6 of B belongs to A. Note therefore that a set does not change if its elements are rearranged.
Example 28 Let X = {2, 3, 2, 4} and Y = {4, 2, 4, 3}. Then X = Y , that is 2, 3, 2, 4 = 4, 2,
4, 3, since each element of X belongs to Y and each element of Y belongs to X. Note that a
set does not change if its elements are repeated. Also the set {2, 3, 4} equals X and Y .
Example 29 Let Q = {x | x2 −7x = −12}, R = {3, 4} and S = {3, 4, 4, 3}. Then Q = R = S

Problem 3 Which of the following sets are equal

(a) A = {a, b, c} (b) B = {c, b, c, a} (c) C = {b, a, b, c} (d) D = {b, c, a, b}
Solution All the sets A, B, C and D are equal (remember repetitions and order do not matter
in regard to elements of a sets), and contains the three elements a, b, c

Problem 4 List the elements of each set where N = {1, 2, 3, . . .}.
(a) A = {x ∈ N | 3 < x < 9}
(b) B = {x ∈ N | x is even, x < 11}
(c) A = {x ∈ N | 4 + x = 3}
Solution
(a) A consists of the positive integers between 3 and 9; hence A = {4, 5, 6, 7, 8}.
(b) B consists of the even positive integers less than 11; hence B = {2, 4, 6, 8, 10}.
(c) No positive integer satisfies 4 + x = 3; hence C = ∅, the empty set.

7
 
Problem 5 Which of the following sets are equal?
(a) A = {x | x2 −4x+3 = 0} (b) B = {x | x2 −3x+2 = 0} (c) C = {x | x ∈ N, x < 3}

(d) D = {x | x ∈ N, x is odd, x < 5} (e) E = {1, 2}

(f) F = {1, 2, 1} (g) G = {3, 1} (h) G = {1, 1, 3}

5 Null Set
It is convenient to introduce the concept of the empty set, that is, a set which contains no
elements. This set is sometimes called the null set. We say that such a set is void or empty, and
we denote its symbol ∅.
Example 30 Let A be the set of students in FCSIT, BUK who are born in the year 1815. As
far the BUK students statistic, A is a null set
Example 31 Let B = {x | x2 = 4, x is odd} be the set of students in FCSIT, BUK who are
born in the year 1815. According known records and statistics, B is a null set.

6 Subsets
If every element in a set A is also a member of a set B, then A is called asubset of B. More
specifically, A is a subset of B if x ∈ A implies x ∈ B. We denote this relationship by writing;
A⊂B
which can also be read “A is contained in B”.
Example 32 The set C = {9, 7, 5} is a subset of D = {9, 8, 7, 6, 5}, since each number 9, 7
and 5 belonging to C also belongs to D.
Example 33 The set E = {2, 4, 6} is a subset of F = {6, 2, 4}, since each number 2,4, and 6
belonging to E also belongs to F . Note, in particular, that E = F . In a similar manner it can
be shown that every set is a subset of itself.
Example 34 Let F = {x | x is a positive power of 2}, that is F = {2, 4, 8, 16, . . .} and let
G = {x | x is even}, that is G = {2, 4, 6, . . .}. Then F ⊂ G, that is F is contained in G.

With the above definition of a subset, we are able to restate the definition of the equality of two
sets.
Definition 2 (Equal Sets) Two set A and B are equal, that is
A = B, if and only if A ⊂ B and B ⊂ A.

8
If A is a subset of B, then we can also write
B⊃A
Which reads “B is a superset of A” or “B contains A”. Furthermore, we write:
A 6⊂ B or B 6⊃ A
if A is not a subset of B.
In conclusion,
Remark 1 The null set ∅ is a subset of every set. That is, ∅ ⊂ A for all sets A.
Remark 2 If A is not a subset of B, that is, if A 6⊂ B, then there is at least one element in A
that is not a member of B.
Remark 3 Observe that N ⊂ W ⊂ Z ⊂ Q ⊂ R ⊂ C, where
N = the set of natural numbers or positive integers: 1, 2, 3, . . .
W = the set of whole numbers: 0, 1, 2, 3, . . .
Z = the set of all integers: . . . , −2, −1, 0, 1, 2, . . .
p
Q = the set of rational numbers: that is numbers that can be written as where p and q are
q
integers and q 6= 0
R = the set of real numbers
C = the set of complex numbers

6.1 Proper Subset

Since every set A is a subset of itself, we call a set B a proper subset of A if, first, B is a subset
of A and secondly, if B is not equal to A. More briefly, B is a proper subset of A if:
B ⊂ A and B 6= A

In some learning resource materials “B is a subset of A” is denoted by

B⊆A
and “B is a proper subset of A” is denoted by
B⊂A
We will continue to use the previous notation in which we do not distinguished between a subset
and a proper subset.

Problem 6 Let A = {2, 3, 4, 5}.

(a) Show that A is not a subset of B = {x ∈ N | x is even}.
(b) Show that A is a proper subset of C = {1, 2, 3, . . . , 8, 9}.
Solution
(a) It is necessary to show that at least one element in A does not belong to B. Now 3 ∈ A
and, since B consists of even numbers, 3 6∈ B; hence A is not a subset of B.
(b) Each element of A belongs to C so A ⊆ C. On the other hand, 1 ∈ C but 1 6∈ A. Hence
A 6= C. Therefore A is a proper subset of C.

9
 
Problem 7 Write the following in set notation
(a) R is a subset of T (b) x is a member of Y (c) M is not a subset pf S
(d) z does not belong to A (e) B is included in F (f) M contains N

Problem 8 Consider the following sets:

∅, A = {1}, B = {1, 3}, C = {1, 5, 9},
D = {1, 2, 3, 4, 5}, E = {1, 3, 5, 7, 9}, U = {1, 2, 3, . . . , 7, 8, 9}
Insert the correct symbol ⊆ or 6⊆ between each pair of sets:
(a) ∅, A (b) A, B (c) B, C (d) B, E (e) C, D (f) C, E (g) D, E (h) D, U
Problem 9 Let U = {1, 2, . . . , 9} be the universal set, and let
A = {1, 2, 3, 4, 5}, B = {4, 5, 6, 7}, C = {5, 6, 7, 8, 9},
D = {1, 3, 5, 7, 9}, E = {2, 4, 6, 8} F = {1, 5, 9}
Find: (a) A ∪ B and A ∩ B (b) A ∪ C and A ∩ C (c)D ∪ F and D ∩ F
Problem 10 Let
A = {1, 2, . . . , 8, 9}, B = {2, 4, 6, 8}, C = {1, 3, 5, 7, 9}, D = {3, 4, 5}, E = {3, 5}.
Which of the these sets can equal a set X under each of the following conditions?
(a) X and B are disjoint (b) X ⊆ D but X 6⊂ B
(c) X ⊆ A but X 6⊂ C (d) X ⊆ C but X 6⊂ A.

7 Comparability
Two sets A and B are said to be comparable if:
A⊂B or B⊂A

That is, if one of the sets is a subset of the other set. Moreover, two sets A and B are said to be
not comparable if:
A 6⊂ B and B 6⊂ A

Note that if A is not comparable to B then there is an element in A which is not in B and also,
there is an element in B which is not in A.
Example 35 Let A = {a, b} and B = {a, b, c}. Then A is comparable to B, since A is a subset
of B.
Example 36 Let R = {a, b} and S = {b, c, d}. Then R and S are not comparable, since a ∈ R
and a 6∈ S and c ∈ S and c 6∈ R.

10
8 Theorem and Proof
In mathematics, many statements can be proven to be true by the use of previous assumptions
and definitions. In fact, the essence of mathematics consists of theorems and their proofs. A
theorem is a statement that has been proven to be true. We now proof our first theorem
Theorem 1 If A is a subset of B and B is a subset of C then A is a subset of C, that is,
A⊂B and B⊂C implies A⊂C

Proof. (Notice that we must show that any element in A is also an element in C). Let x be an
element of A, that is, let x ∈ A. Since A is a subset of B, x also belongs to B, that is, x ∈ B.
But by hypothesis, B ⊂ C; hence every element of B, which includes x, is a number of C. We
have shown that x ∈ A implies xinC. Accordingly, by definition, A ⊂ C.

8.1 Some Notations used in Mathematical Proofs

The proof of Theorem 1 is a bit wordy, in mathematics you can express much with few words.
To showcase glimpse elegance and beauty of mathematical writing we introduce some notations
used in mathematical proofs.
For statements (or assertions) A and B, we shall commonly use abbreviations like:
A & B for (A and B), th conjunction of A and B.
A ⇒ B for (A implies B), which means (if A then B), and so B is automatically true if
A is true.
A ⇐⇒ B to mean (A iff B), which abbreviates (A if and only if B) which indicates
(A ⇒ B and B ⇒ A).
∃, read “there exists”, can be used like
∃x ∈ A
as abbreviation “for some x in A” or “there exists x such that x ∈ A”.
∀, read “for all”, can be used like
∀x ∈ A
as abbreviation “for all x in A” or “for any x such that x ∈ A”.
Let restate Theorem 1 and its proof using the notations above

Theorem 1 Revisited
Let A, B and C be sets, if A ⊂ B & B ⊂ C =⇒ A ⊂ C

Proof of Theorem 1 Revisited

Let A, B and C be sets such that A ⊂ B and B ⊂ C.
A ⊂ B =⇒ ∀x ∈ A, x ∈ B
but B ⊂ C =⇒ ∀x ∈ B, x ∈ C
=⇒ ∀x ∈ A, x ∈ C
=⇒ A ⊂ C

11
9 Set of Sets
It sometimes will happen that the object of a set are sets themselves; for example, the set of all
subsets of A. In order to avoid saying “set of sets”, it is common practice to say “family of sets”
or 11class of sets”. Under the circumstances, and in order to avoid confusion, we sometimes
will let script letters
A , B, C , . . .
denote families, or classes, of sets since capital letters already denote their elements.
Example 37 In geometry we usually say “a family of lines” or “a family of curves” since lines
and curves are themselves sets of points.
Example 38 The set {2, 3, 2, 5, 6} is a family of sets. Its members are the sets {2, 3}, {2} and
{5, 6}.

Theoretically, it is possible that a set has some members, which are sets themselves and some
members which are not sets, although in any application of the theory of sets this case arises
infrequently.
Example 39 Let A = {2, {1, 3}, 4, {2, 5}}. Then A is not a family of sets; here some elements
of A are sets and some are not.

Problem 11 What is meant by the symbol {{4, 5}}

Solution {{4, 5}} is a set which contains one element – the set consisting of the elements 4,
5. Note that {4, 5} ∈ {{4, 5}}; and {4, 5} 6⊂ {{4, 5}}.

Problem 12 Let A = {2, {4, 5}, 4}. Which of the following statements is incorrect and why?
(a) {4, 5} ⊂ A (b) {4, 5} ∈ A (c) {{4, 5}} ⊂ A
Problem 13 Let E = {2, {4, 5}, 4}. Which of the following statements is incorrect and why?
(a) 5 ∈ E (b) {5} ∈ E (c) {{5}} ⊂ A

10 Universal Set
In any application of the theory of sets, all the sets under investigation will likely be subsets of
a fixed set. We call this set the universal set or universe of discourse. We denote this set by U.
Example 40 In plane geometry, the universal set consists of all the points in the plane.
Example 41 In human population studies, the universal set consists of all the people in the
world.
Example 42 In elections, the universal set consists of all eligible voters.

12
Problem 14 List the elements of the following sets if the universal set is U = {a, b, c, . . . , y, z}.
Furthermore, identify which of the sets, if any, are equal.
(a) A = {x | x is a vowel} (b) B = {x | x is a letter in the word “little”}

(c) C = {x | x preceeds f in the alphabet} (d) D = {x | x is a letter in the word “title”}

11 Power Set
The family of all the subsets of any set S is called the power set of S. We denote the power set
of S by
2S
In some resource materials the power set is denoted by P.
Example 43 Let M = a, b. Then
2M = {{a, b}, {a}, {b}, ∅}
Example 44 Let T = {4, 7, 8}. Then
2T = {T, {4, 7}, {4, 8}, {7, 8}, {4}, {7}, {8}, ∅}

If a set S is finite, say S has n elements, then the power set of S can be shown to have 2n elements.
This is one reason why the class of subsets of S is called the power set of S and is denoted by 2S .

Problem 15 Determine the power set of A = {a, b, c, d}.

Solution A has 4 elements, therefore the power set of 2A has 24 = 16 elements. The elements
of A are the subset of A. Hence
2A = {
A, {a, b, c}, {a, b, d}, {a, c, d},
{b, c, d}, {a, b}, {a, c}, {a, d}
{b, c}, {b, d}, {c, d}, {a},
{b}, {c}, {d}, ∅
}

Problem 16 Find the number of elements in the power set of each of the following sets
(a) {departments in FCSIT}
(b) {letters in the word “buk”}
(c) {9Mobile, Airtel, Glo, MTN}
(d) {months of the year}

13
12 Disjoint Sets
If sets A and B have no elements in common, that is if no element of A is in B and no element
of B is in A, then we say that A and B are disjoint.
Example 45 Let A = {1, 3, 7, 8} and B = {2, 4, 7, 9}, Then A and B are not disjoint since 7
is in both sets, i.e 7 ∈ A and 7 ∈ B
Example 46 Let A be the positive numbers and let B be the negative numbers. Then A and B
are disjoint since no number is both positive and negative.
Example 47 Let E = {x, y, z} and F = {r, s, t}, Then E and F are disjoint.

13 Venn-Euler Diagrams
A simple and instructive way of illustrating the relationships between sets is in the use of the
so-called Venn-Euler diagrams or, simply, Venn diagrams. Here we represent a set by a simple
plane area, usually bounded by a circle.
Example 48 Suppose A ⊂ B and, say, A 6= B, then A and B can be described by either
diagram

Example 49 Suppose A and B are not comparable. Then A and B can be represented by the
diagram on the right if they are disjoint, or the diagram on the left if they are not disjoint.

Example 50 Let A = {a, b, c, d} and B = {c, d, e, f }. Then we illustrate these sets a Venn
diagram of the form:

14
Problem 17 Let A = {3, 5, 7, 9, 11, 13, 15, 17, 19} and B = {3, 6, 9, 12, 15, 18}. Illustrate A
and B using a Venn diagram.

14 Set Operations
In arithmetic, we learn to add, subtract and multiply, that is, we assign to each pair of numbers
x and y a number x + y called the sum of x and y, a number x − y called the difference of x and
y, and a number xy called the product of x and y. These assignments are called the operations
of addition, subtraction and multiplication of numbers. In this section, we define the operation
union, intersection, difference and symmetric-difference of sets, that is, we will assign new pairs
of sets A and B. In a later section, we will see that these set operations behave in a manner
some what similar to the above operations on numbers.

14.1 Union

The union of sets A and B is the set of all elements which belong to A or to B or to both. We
denote the union of A and B by;
A∪B
which is usually read “A union B”
Example 51 In the Venn diagram in Figure 1, we have shaded A ∪ B, that is the area of A and
the area of B

A B

U
Figure 1: A ∪ B is shaded

Example 52 Let S = {a, b.c.d} and T = {f, b, d, g}. Then

S ∪ T = {a, b, c, d, f, g}
Example 53 Let P be the set of positive real numbers and let Q be the set of negative real
numbers. The P ∪ Q, the union of P and Q, consist of all the real numbers except zero.

The union of A and B may also be defined concisely by:

A ∪ B = {x | x ∈ A or x ∈ B} (1)
Remark 4 It follows directly from the definition of the union of two sets that A ∪ B and B ∪ A
are the same set, that is,
A∪B =B∪A

15
Remark 5 Both A and B are always subsets of A ∪ B that is,
A ⊂ (A ∪ B) and B ⊂ (A ∪ B)

In some learning resource materials, the union of A and B is denoted by A + B and is called
the set-theoretic sum of A and B or, simply, A plus B.

Problem 18 Let A = {a, b, c, d, e}, B = {a, b, d, f, g}, C = {b, c, e, g, h}, D = {d, e, f, g, h}

Find (a) A ∪ B (b) A ∪ C (c) A ∪ D (d) B ∪ C (e) B ∪ D (f) C ∪ D

14.2 Intersection

The Intersection of sets A and B is the set of elements which are common to A and B, that is,
those elements which belong to A and which belong to B. We denote the intersection of A and
B by:
A∩B
which is usually read “A intersection B”
Example 54 In the Venn diagram in Figure 2, we have shaded A ∩ B, that is the area of A and
the area of B

A B

U
Figure 2: A ∩ B is shaded

Example 55 Let S = {a, b, c, d} and T = {f, b, d, g}. Then

S ∩ T = {b, d}
Example 56 Let V = {2, 4, 6, . . .}, that is multiple of 2; and W = {3, 6, 9, . . .}, that is multiple
of 3. Then
S ∩ T = {6, 12, 18, . . .}

The intersection of A and B may also be defined concisely by:

A ∩ B = {x | x ∈ A, x ∈ B} (2)
Remark 6 It follows directly from the definition of the intersection of two sets that A ∩ B and
B ∩ A are the same set, that is,
A∩B =B∩A
Remark 7 Each of the sets A and B contains A ∩ B as a subset, that is,
(A ∩ B) ⊂ A and (A ∩ B) ⊂ B

16
 Remark 8 If sets A and B have no elements in common, that is if A and B are disjoint, then
the intersection of A and B is the null set, i.e. A ∩ B = ∅.

In some learning resource materials, the intersection of A and B is denoted by AB and is called
the set-theoretic product of A and B or, simply, A times B.

Problem 19 Let A = {a, b, c, d, e}, B = {a, b, d, f, g}, C = {b, c, e, g, h}, D = {d, e, f, g, h}

Find (a) A ∩ B (b) A ∩ C (c) A ∩ D (d) B ∩ C (e) B ∩ D (f) C ∩ D

14.3 Difference

The difference of sets A and B is the set of elements which belong to A but which do not belong
to B. We denote the difference of A and B by
A\B
which is usually read “A difference B” or, simply “A minus B”
Example 57 In the Venn diagram in Figure 3, we have shaded A \ B, that is the area of A
which is not part of B

A B

U
Figure 3: A \ B is shaded

Example 58 Let S = {a, b, c, d} and T = {f, b, d, g}. Then

S \ T = {a, c}
Example 59 Let R be the set of real numbers and let Q be the set of rational numbers. Then
R \ R consists of the irrational numbers.

The difference of A and B may also be defined concisely by:

A \ B = {x | x ∈ A, x 6∈ B} (3)
Remark 9 Set A contains A \ B as a subset, that is,
(A \ B) ⊂ A
Remark 10 The sets A \ B, A ∩ B and B \ A are mutually disjoint, that is, the intersection of
any two is the null set.

In some learning resource materials, the difference of A and B is sometimes denoted by A – B

or A ∼ B.

17
Problem 20 Let A = {a, b, c, d, e}, B = {a, b, d, f, g}, C = {b, c, e, g, h}, D = {d, e, f, g, h}
Find (a) A \ B (b) A \ C (c) A \ D (d) B \ C (e) B \ D (f) C \ D

14.4 Symmetric Difference

The symmetric difference of sets A and B, denoted by A ⊕ B, consists of those elements which
belong to A or B but not to both. That is,
A ⊕ B = (A ∪ B) \ (A ∩ B) or A ⊕ B = (A \ B) ∪ (A \ B) (4)
Example 60 In the Venn diagram in Figure 4, we have shaded A ⊕ B

A B

U
Figure 4: A ⊕ B is shaded

Problem 21 Let A = {a, b, c, d, e}, B = {a, b, d, f, g}, C = {b, c, e, g, h}, D = {d, e, f, g, h}

Find (a) A ⊕ B (b) A ⊕ C (c) A ⊕ D (d) B ⊕ C (e) B ⊕ D (f) C ⊕ D

15 Complement
The complement of a set A is the set of elements that do not belong to A, that is, the difference
of the universal set U and A. We denote the complement of A by
A{
Example 61 In the Venn diagram in Figure 5, we have shaded A \ B, that is the area of A
which is not part of B

18
 A B

Figure 5: A{ is shaded

Example 62 Let S = {a, b.c.d} and T = {f, b, d, g}. Then

S \ T = {a, c}
Example 63 Let the Universal set U be the English alphabet and let T = {w, x, y}. Then
T { = {a, b, c, d, . . . , t, u, v, z}
Example 64 Let F = {1, 3, 5, . . .}, that is, the odd numbers.
Then F { = {2, 4, 6, ...}, the even numbers. Here we assume that the universal set is the natural
numbers, 1, 2, 3, . . ..

The complement of A may also be defined concisely by:

A{ = {x | x ∈ U, x 6∈ A} or, simply, A{ = {x | x 6∈ A} (5)

We state some facts about sets, which follow directly from the definition of the complement of
a set.
Remark 11 The union of any set A and its complement A{ is the universal set, that is,
A ∪ A{ = U
Furthermore, set A and its complement A{ are disjoint, i.e.,
A ∩ A{ = ∅
Remark 12 The complement of the universal set U is the null set ∅, and vice versa, that is,
U{ = ∅ and ∅{ = U
Remark 13 Remark 2.10: The complement of the complement of set A is the set A itself.
More briefly,
(A{ ){ = A

Our next remark shows how the difference of two sets can be defined in terms of the complement
of a set and the intersection of two sets. More specifically, we have the following basic
relationship:
Remark 14 The difference of A and B is equal to the intersection of A and the complement
of B, that is,
A \ B = A ∩ B{

The proof of Remark 14 follows directly from definitions:

/ B} = {x | x ∈ A, x ∈ B { } = A ∩ B {
A \ B = {x | x ∈ A, x ∈

19
Problem 22 Let U = {x | x is a letter of the English alphabet},
A = {a, b, c, d, e}, B = {a, b, d, f, g}, C = {b, c, e, g, h}, D = {d, e, f, g, h}.
Find (a) A{ (b) B { (c) C { (d) D{

16 Operation on Comparable Sets

The operations of union, intersection, difference and complement have simple properties when
the sets under investigation are comparable. The following theorems can be proved.
Theorem 2 Let A be a subset of B. Then the intersection of A and B is precisely A, that is,
A ⊂ B =⇒ A ∩ B = A
Theorem 3 Let A be a subset of B. Then the union of A and B is precisely B, that is,
A ⊂ B =⇒ A ∪ B = B
Theorem 4 Let A be a subset of B. Then B { is a subset of A{ , that is,
A ⊂ B =⇒ B { ⊂ A{

We illustrate Theorem 4 by the Venn diagrams in Figure 6a and diagrams in Figure 6b. Notice
how the area of B { is included in the area of A{ .

(a) B { is shaded (b) A{ is shaded

Figure 6: A ⊂ B =⇒ B { ⊂ A{

Theorem 5 Let A be a subset of B. Then the Union of A and (B \ A) is precisely B, that is,
A ⊂ B =⇒ A ∪ (B \ A) = B
Theorem 6 A \ B = A ∩ B {
Theorem 7 If A ⊂ B, then A{ ⊃ B { or B { ⊂ A{ .
Theorem 8 For all sets A and B, A = (A ∩ B) ∪ (A ∩ B { )

Problem 23 Consider the universal set U = {1, 2, 3, . . . , 8, 9} and sets A = {1, 2, 5, 6},
B = {2, 5, 7}, C = {1, 3, 5, 7, 9}. Find:
(a) A ∩ B and A ∩ C (b) A ∪ B and A ∪ C
(c) A{ and C { (d) A \ B and A \ C
(e) A ⊕ B and A ⊕ C (f) (A ∪ B) \ B and (B ⊕ C) \ A

20
17 Laws of the Algebra of Sets
Sets under the operations of union, intersection, and complement satisfy various laws (identities)
which are listed as Theorems 9 through 16:
Theorem 9 (Idempotent Laws)
(a) A ∪ A = A
(b) A ∩ A = A
Theorem 10 (Associative Laws)
(a) A ∪ (B ∪ C) = (A ∪ B) ∪ C = A ∪ B ∪ C
(b) A ∩ (B ∩ C) = (A ∩ B) ∩ C = A ∩ B ∩ C
Theorem 11 (Commutative Laws)
(a) A ∪ B = B ∪ A
(b) A ∩ B = B ∩ A
Theorem 12 (Distributive Laws)
(a) A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)
(b) A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)
Theorem 13 (Identity Laws)
(a) A ∪ ∅ = A
(b) A ∩ ∅ = ∅
(c) A ∪ U = U
(d) A ∩ U = A
Theorem 14 (Involution Law) (A{ ){ = A
Theorem 15 (Complement Laws)
(a) A ∪ A{ = U
(b) A ∩ A{ = ∅
(c) U{ = ∅
(d) ∅{ = U
Theorem 16 (DeMorgan’s Laws)
(a) (A ∪ B){ = A{ ∩ B {
(b) (A ∩ B){ = A{ ∪ B {

It is interesting to note that if we use the notation A + B instead of A ∪ B and AB instead of

A ∩ B, many of the theorems above on algebra of set are similar to the usual algebra of real
numbers. Thus for example Theorems 10(a) and 12(a) become A + (B + C) = (A + B) + C
and A(B + C) = AB + AC respectively. However, then analogy cannot be relied upon always.
For example Theorem 12(b) becomes A + BC = (A + B)(A + C) which is wrong.

18 Principle of Duality
The identities in Theorems 9 through 16 are arranged in pairs, as, for example, Theorem 10(a)
and Theorem 10(b). We now consider the principle behind this arrangement. Suppose E is an
equation of set algebra. The dual E ∗ of E is the equation obtained by

21
 replacing unions by intersections,
replacing intersections by unions
replacing sets by their complements, and
reverse the inclusion symbols ⊂ and ⊃.
That is replace each occurrence of ∪, ∩, U, ∅ in E by ∩, ∪, ∅, U, respectively. For example, the
dual of
(U ∩ A) ∪ (B ∩ A) = A is (∅ ∪ A) ∩ (B ∪ A) = A

Observe that the pairs of laws in Theorems 9 through 16 are duals of each other. It is a fact of
set algebra, called the principle of duality, that if any equation E is an identity then its dual E ∗
is also an identity.

Problem 24 Write the dual of: (a) (U ∩ A) ∪ (B ∩ A) = A; (b) (A ∩ U) ∩ (∅ ∪ A{ ) = ∅

Solution Interchange ∪ and ∩ and also U and ∅ in each set equation:
(a) (∅ ∪ A) ∩ (B ∪ A) = A; (b) (A ∪ ∅) ∪ (U ∩ A{ ) = U


19 Finite Sets
Sets can be finite or infinite. A set S is said to be finite if S is empty or if S contains exactly m
elements where m is a positive integer; otherwise S is infinite.
Example 65 Let M be the set of Month of the year. Then M is finite.
Example 66 Let N = {1, 3, 5, 7, . . .}. Then N is infinite.
Example 67 Let I be the unit interval, that is I = [0, 1] = {x | x ≤ 0 ≤ 1}. Then I is infinite.
Example 68 Let R = {x | x is a river on the earth}. Although it maybe difficult to count the
number of rivers in the world, R is still a finite set.

Problem 25 Determine which of the following sets are finite

(a) students of FCSIT, BUK (b) Positive multiple of 3 (c) chickens living in Nigeria

20 Cardinality
The cardinality of a set is a measure of a set’s size, meaning the number of elements in the set.
For instance, the set A = {1, 2, 4} has a cardinality of 3 for the three elements that are in it. The
cardinality of a set is denoted n(A) or |A|. When n(A) is finite; n(A) is simply the number of
elements in A, n(∅) = 0 since the empty set has no elements.

22
Theorem 17 Suppose A and B are finite disjoint sets. Then A ∪ B is finite and
n(A ∪ B) = n(A) + n(B)
Theorem 18 Suppose A and B are finite sets. Then
n(A \ B) = n(A) − n(A ∩ B)
Example 69 Suppose a computer class A has 25 students and 10 of them are taking a biology
class B. Then the number of students in class A which are not in class B is:
n(A \ B) = n(A) − n(A ∩ B) = 25 − 10 = 15
Theorem 19 Let A be a subset of a finite universal set U. Then
n(A{ ) = n(U) − n(A)
Example 70 Suppose a computer class U with 30 students has 18 full-time students. Then the
number of part-time students in class U is:
n(A{ ) = n(U) − n(A) = 30 − 18 = 12

20.1 Inclusion-Exclusion Principle

There is a formula for n(A ∪ B) even when they are not disjoint, called the Inclusion–Exclusion
Principle. Namely:
Theorem 20 (Inclusion-Exclusion Principle) Suppose A and B are finite sets. Then A ∪ B
and A ∩ B are finite and
n(A ∪ B) = n(A) + n(B) − n(A ∩ B)

That is, we find the number of elements in A or B (or both) by first adding n(A) and n(B)
(inclusion) and then subtracting n(A ∩ B) (exclusion) since its elements were counted twice.
We can apply this result to obtain a similar formula for three sets:
Theorem 21 Suppose A, B and C are finite sets. Then A ∪ B ∪ C is finite and
n(A ∪ B ∪ C) = n(A) + n(B) + n(C) − n(A ∩ B) − n(A ∩ C) − n(B ∩ C) + n(A ∩ B ∩ C)
Example 71 Suppose a list A contains the 30 students in a mathematics class, and a list B
contains the 35 students in an English class, and suppose there are 20 names on both lists. Find
the number of students: (a) only on list A, (b) only on list B, (c) on list A or B (or both), (d) on
exactly one list.
(a) List A has 30 names and 20 are on list B; hence 30 - 20 = 10 names are only on list A
(b) Similarly, 35 - 20 = 15 are only on list B.
(c) We seek n(A ∪ B). By inclusion-exclusion,
n(A ∪ B) = n(A) + n(B) − n(A ∩ B) = 30 + 35 − 20 = 45
In other words, we combine the two lists and then cross out the 20 names which appear
twice.
(d) By (a) and (b), 10 + 15 = 25 names are only on one list; that is, n(A ⊕ B) = 25.

23
Problem 26 Given n(U) = 20, n(A) = 12, n(B) = 9, n(A ∩ B) = 4. Find:
(a) n(A ∪ B), (b) n(A{ ), (c) n(B { ), (d) n(A \ B), (e) n(∅)
Problem 27 A survey of a newly refurbished 250-room BUK hostel complex to see which
of the rooms have air-conditioning (A), Ceiling Fan (F ), television (T ) installed. The survey
found:
150 had ceiling fan (A), 50 had A and F 120 had Ceiling Fan (F )

90 had A and R 30 had all three options 110 had Television (T )

40 had F and T

find the number of rooms that had

(a) only T ; (b) only A; (c) only F ;

(d) F and T but not A; (e) A and F but not T ; (f) only one of A, F , T ;

(g) at least one of A, F , T ; (h) none of A, F , T ;

Solution

Problem 28 Among 120 pupils of Komputer Secondary School, 40 takes mathematics, 30
takes English and 15 takes both mathematics and English. Find the number of students who
(a) do not take mathematics; (b) take mathematics or English;

(c) take mathematics but not English; (d) take English, but not mathematics;

(e) take exactly one of the two subjects; (f) take neither mathematics nor English;

21 References
1. Schaum’s Outline of Basic Mathematics with Applications to Science and Technology 2nd
Edition by Hayn Kruglak, John T. Moore, Ramon A. Mata-Toledo. (1998) McGraw-Hill
Publishing Company
2. Schaum’s Outline of Theory and Problems of Discrete Mathematics 3rd Edition by Sey-
mour Lipschutz. (2007) McGraw-Hill Publishing Company
3. Schaum’s Outline of Theory and Problems of Set Theory and Related Topics by Seymour
Lipschutz (1964) McGraw-Hill Publishing Company
4. Schaum’s Outline of Probability, Random Variables & Random (1997) by Hwei P. Hsu.
(1998) McGraw-Hill Publishing Company
5. Set Theory With an Introduction to Real Point Sets by Abhijit Dasgupta. (2014) Springer
Science+Business Media New York

24