Discrete Mathematics: Haluk Bingol February 21, 2012

Discrete Mathematics
Haluk Bingol
February 21, 2012

ii
Contents
I Preliminaries 1
1 Preliminaries 3
1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 On definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.3 Similar statements . . . . . . . . . . . . . . . . . . . . . . . . 5
1.4 Set of Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . 6
II Basics 7
2 Logic 9
2.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2 Foundations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.2.1 Well-formed formula . . . . . . . . . . . . . . . . . . . 10
2.2.2 Logical Axioms . . . . . . . . . . . . . . . . . . . . . . 11
2.2.3 Rules of Inference . . . . . . . . . . . . . . . . . . . . . 11
2.2.4 Equality . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.3 Propositional Logic . . . . . . . . . . . . . . . . . . . . . . . . 12
2.3.1 Compound Propositions . . . . . . . . . . . . . . . . . 12
2.3.2 Application . . . . . . . . . . . . . . . . . . . . . . . . 15
2.4 Propositional Equivalence . . . . . . . . . . . . . . . . . . . . 16
3 Sets, Relations, and Functions 21

3.1 Set . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.1.1 Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.1.2 Set Operations . . . . . . . . . . . . . . . . . . . . . . 24
3.2 Relation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.2.1 Composition of Relations . . . . . . . . . . . . . . . . . 27
iii
iv CONTENTS
3.3 Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.4 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
4 Relations on a Set 37
4.1 Relations on a Set . . . . . . . . . . . . . . . . . . . . . . . . . 37
4.2 Observations on the Matrix of a Relation . . . . . . . . . . . . 38
4.3 Closure of Relations . . . . . . . . . . . . . . . . . . . . . . . 39
4.4 Compatibility Relation . . . . . . . . . . . . . . . . . . . . . . 39
4.4.1 Application of Compatibility Relation . . . . . . . . . . 41
4.5 Equivalence Relation . . . . . . . . . . . . . . . . . . . . . . . 42
4.5.1 Applications of Equivalence Relations . . . . . . . . . . 43
4.6 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
5 Partial Ordering, Lattice 47

5.1 Partial Ordering . . . . . . . . . . . . . . . . . . . . . . . . . . 47
5.2 Hasse Diagram . . . . . . . . . . . . . . . . . . . . . . . . . . 48
5.3 Lattice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
5.4 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
5.5 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
III Algebra 57
6 Algebraic Structures 59
6.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
6.2 Algebraic Structures . . . . . . . . . . . . . . . . . . . . . . . 61
6.2.1 Binary Operations . . . . . . . . . . . . . . . . . . . . 61
6.2.2 Algebraic Structure . . . . . . . . . . . . . . . . . . . . 62
6.2.3 Sub-Algebraic Structures . . . . . . . . . . . . . . . . . 63
6.3 With One Binary Operation . . . . . . . . . . . . . . . . . . . 65
6.3.1 Semigroup . . . . . . . . . . . . . . . . . . . . . . . . . 65
6.3.2 Monoid . . . . . . . . . . . . . . . . . . . . . . . . . . 65
6.3.3 Groups . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
6.4 With Two Binary Operations . . . . . . . . . . . . . . . . . . 69
6.4.1 Ring . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
6.4.2 Field . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
6.4.3 Lattice . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
6.4.4 Vector Spaces . . . . . . . . . . . . . . . . . . . . . . . 72
CONTENTS v
6.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
6.6 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
7 Boolean Algebras 77
7.1 Reminders . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
7.2 Lattices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
7.3 Boolean Algebras . . . . . . . . . . . . . . . . . . . . . . . . . 78
7.3.1 Distributive Lattice . . . . . . . . . . . . . . . . . . . . 78
7.3.2 n-cube . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
7.3.3 Bounded Lattice . . . . . . . . . . . . . . . . . . . . . 80
7.3.4 Complemented Lattice . . . . . . . . . . . . . . . . . . 80
7.4 Boolean Algebra . . . . . . . . . . . . . . . . . . . . . . . . . 82
7.5 Canonical Expressions in Boolean Algebras . . . . . . . . . . . 82
IV Number Systems 83
8 Number Systems 85
8.1 Natural Numbers . . . . . . . . . . . . . . . . . . . . . . . . . 85
8.2 Integers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
9 Division 89
9.1 Division . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
9.2 Prime Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . 91
9.3 Common Divisors and Multiples . . . . . . . . . . . . . . . . . 93
9.4 Modular Arithmetic . . . . . . . . . . . . . . . . . . . . . . . . 94
V Combinatorics 97
10 Counting 99
10.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
10.2 Cardinality: Finite and Infinite Sets . . . . . . . . . . . . . . . 100
10.2.1 Hierarchy of Infinities . . . . . . . . . . . . . . . . . . . 103
10.3 The Number of Ways . . . . . . . . . . . . . . . . . . . . . . . 104
10.3.1 The Product Rule . . . . . . . . . . . . . . . . . . . . . 105
10.3.2 The Sum Rule . . . . . . . . . . . . . . . . . . . . . . . 107
10.3.3 The Inclusion-Exclusion Rule . . . . . . . . . . . . . . 108
10.4 The Pigeonhole Principle . . . . . . . . . . . . . . . . . . . . . 109
vi CONTENTS
10.5 Counting Methods . . . . . . . . . . . . . . . . . . . . . . . . 110

10.6 Supplementary Materials . . . . . . . . . . . . . . . . . . . . . 114
10.6.1 Some Useful Sequences . . . . . . . . . . . . . . . . . . 114
n
10.6.2 Approximations for n! and r
. . . . . . . . . . . . . . 114
10.7 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
11 Recurrence 121
11.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
11.2 Recurrence Equations . . . . . . . . . . . . . . . . . . . . . . . 121
11.3 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
VI Graphs 125
12 Graphs 127
12.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
12.2 Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128
12.2.1 Reachability and Strong-Connectedness . . . . . . . . . 129
12.2.2 Application of Multigraphs . . . . . . . . . . . . . . . . 133
12.3 Undirected Graphs . . . . . . . . . . . . . . . . . . . . . . . . 135
12.4 Path Problems . . . . . . . . . . . . . . . . . . . . . . . . . . 137
12.5 Planarity and Coloration . . . . . . . . . . . . . . . . . . . . . 138
12.6 Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
12.6.1 Minimal Spanning Tree Algorithm . . . . . . . . . . . 140
12.6.2 Rooted Tree . . . . . . . . . . . . . . . . . . . . . . . . 140
12.7 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142
Index 147
The Notation Index . . . . . . . . . . . . . . . . . . . . . . . . . . . 148
The Concepts Index . . . . . . . . . . . . . . . . . . . . . . . . . . 149
Part I
Preliminaries
1
Chapter 1
Preliminaries
1.1 Motivation
This text is not ment to be printed. It is designed to be read electronically.
You will find many hyperlinks to sources in the web. Especially incredible
wikipedia.com, which this book is dedicated to, gets many of them.
1.2 On definitions
Definitions are one of the starting points of mathematics. We should under-
stand them well. By definition what we actually do is to give a “name” to
“something”. To start with, “that something” should be well-defined, that
is, everybody understand the same without any unambiguity. What is in it,
what is not in it should be clearly understood. Once we are all agree on “it”,
we give a “name”.
The given name is not important. It could be some other name. Consider
a text on geometry. Suppose we replace every occurrence of rectangle with
triangle. The entire text would be still perfectly proper geometry text. This
would be obvious if one considers the translation of the text to another
language.
Example 1.2.1. Suppose we all agree on parallelogram and right angle and try
to define rectangle. A parallelogram is called rectangle if it has a right angle.
Here we have an object which satisfies the conditions of both parallegram
and right angle.
3
4 CHAPTER 1. PRELIMINARIES
Note that in plain English we use the form “A is called B if A satis-

fies the followings . . . ” to define B. This may be falsely interpreted as one
way implication such as “A satisfies the followings . . . −→ B”. Actu-
ally what is intented is two-way implication such as “A is called B if and
only if A satisfies the followings . . . ”. More formally, it should be some-
thing like “A satisfies the followings . . . −→ B” and “B −→ A satisfies
the followings . . . ” at the same time. Instead of this long form, we write
“A satisfies the followings . . . ←→ B” in short.
In the language of mathematics, we use “ ←→ ” symbol in our definition.
For example let n be a natural number. We want to define evenness of natural
numbers.
n is even ←→ n is divisible by 2.
Here the left hand side is not derived from the right hand side. It is just
defined to be that way. In order to emphasize this we use the following
notation:
∆
n is even ←→ n is divisible by 2.
Unfortunately. this symbol is also used in different meaning. “a ←→
b” means b can be obtained from a using some applications of rules, and
similarly, a can also be obtained from b. This is the regular use of “ ←→ ”.
We feel that regular use of “=” should be differentiated from the usage
of “=” in definitions. For example in
1 + (1 + 1) = 1 + 2 = 3
the usage of “=” is the regular usage meaning the right hand side of “=”
is obtained from the left hand side by applying some rules. In the case of
defining subtraction as
a − b = a + b−1
where b−1 is the additive inverse of b, a − b is defined in terms of known
binary operation + and unary operation of additive inverse. Therefore these
will be written as
1 + (1 + 1) = 1 + 2 = 3
∆
a−b = a + b−1
in this text.
1.3. SIMILAR STATEMENTS 5
Example 1.2.2. Golden ration is the ratio of the sides of a rectangle which is
presumable the aesthetically best. It is usually represented by φ. This can
be given as: √
∆ 1+ 5
φ = .
2
∆ ∆
As a summary, we exclusively use = and ←→ in the definitions.
∆
Therefore, it does not make sense trying to prove expressions such as A ←→
∆
B or A = B. On the other hand, in the expressions such as A ←→ B or
A = B, the right hand side should be able to obtained from the left hand
side. At the same time, the left hand side also should be able to obtained
from the right hand side. That is, they are “provable”.
In addition to this notation, the concept defined is presented in different
color as in the case of new concept.
∆
Example 1.2.3. Z+ = { z ∈ Z | z > 0 }.
∆
Example 1.2.4. n is even ←→ n is divisible by 2.
1.3 Similar statements

Sometimes two statements are very similar. They differ in a very few points.
For example definition of evenness and oddness in natural numbers is given
as follows:
∆
Definition 1.3.1. n is even ←→ n is divisible by 2.
∆
Definition 1.3.2. n is odd ←→ n is not divisible by 2.
In order to emphasize the differences of such cases the following notation

is used.
even ∆ divisible
Definition 1.3.3. n is ←→ n is by 2.
odd not divisible
Example 1.3.1. Let ρ be a relation on A, that is ρ ⊆ A × A.
reflexive ∀a ∈ A [a ρ a]
symmetric ∆ ∀a, b ∈ A [a ρ b −→ b ρ a]
ρ is called ←→ .
antisymmetric ∀a, b ∈ A [a ρ b ∧ b ρ a −→ a = b]
transitive ∀a, b, c ∈ A [a ρ b ∧ b ρ c −→ a ρ c]
6 CHAPTER 1. PRELIMINARIES
1.4 Set of Numbers

We use the following symbols to represent the sets of various numbers.
∆
N The set of natural numbers. N = { 0, 1, 2, . . . }
∆
Z The set of integers. Z = { . . . , −2, −1, 0, 1, 2, . . . }
∆
Z+ The set of positive integers. Z+ = { 1, 2, . . . }.
∆
Z− The set of negative integers. Z− = { −1, −2, . . . }.
∆
Z≥0 The set of non negative integers. Z≥0 = Z+ ∪ { 0 }
∆
Z≤0 The set of non positive integers. Z≤0 = Z− ∪ { 0 }
∆
Q The set of rational numbers. Q = { p/q | p, q ∈ Z and q 6= 0 }
∆
Q+ The set of positive rational numbers. Q+ = { p/q | p, q ∈ Z+ }
∆
Q− The set of negative rational numbers. Q− = { −p/q | p, q ∈ Z+ }
∆
Q≥0 The set of non negative rational numbers. Q≥0 = Q+ ∪ { 0 }
∆
Q≤0 The set of non positive rational numbers. Q≤0 = Q− ∪ { 0 }
R The set of real numbers. R
∆
R+ The set of positive real numbers. R+ = { r ∈ R | r > 0 }
∆
R− The set of negative real numbers. R− = { r ∈ R | r < 0 }
∆
R≥0 The set of non negative real numbers. R≥0 = R+ ∪ { 0 }
∆
R≥0 The set of non positive real numbers. R≥0 = R− ∪ { 0 }
∆
C The set of complex numbers. C = { a + ib | a, b ∈ R } where i2 = −
Part II
Basics
7
Chapter 2
Logic
2.1 Motivation
In the first half of 1900s mathematicians believed that entire mathematics
can be constructed from a set of axioms, inference rules and symbolic logic.
In 1910’s, Bertrand Russell, now known due to his works in philosophy, and
Alfred North Whitehead published Principia Mathematica which provided
carefully designed construction of mathematics. They claim that every true
mathematical statement can be proved by this way. Unfortunately in 1931
Kurt Gödel proved, in his incompleteness theorem, that there are some true
statements that cannot be proven if the axiomatic system is consistent and
sufficiently powerful to express the arithmetic of the natural numbers. The
famous incompleteness theorem becomes one of the important milestones in
Computer Science, too.
The logic is important for Computer Science in many ways. Search in the
web is one of them. When we do search using a search engine in the Internet,
we express ourselves using logic. For example typing
“Bertrand Russell Mathematica OR Kurt -philosopher”
to Google for search means we are looking pages which contains “Bertrand”
and “Russell” words together, either of the words “Mathematica” or “Kurt”
but we do not want word “philosopher” in our search. This can be rewritten
in logic as “Bertrand” AND “Russell” AND *“Mathematica” OR “Kurt”)
AND NOT“philosopher”.
9
10 CHAPTER 2. LOGIC
2.2 Foundations
We use the notation of [TZ82] in defining well-formed logical formula. We
use spaces in order to improve readability as in the case of ∀x φ(x) or φ ∧ ψ
which should formally be written as ∀xφ(x) or φ ∧ ψ.
2.2.1 Well-formed formula

It is not possible to evaluate an expression such as 2 + 3 + ×7 since it is not
properly formed.
Example 2.2.1. The following expressions are not meaningful. Try to inter-
pret them.
i. p ∧ q ∧ ∧ qq
ii. 1 + + + 1
iii. × / / + − − + 2 3 4
iv. 1 2 +
v. 1 2 3 × +
It is correct that these expressions cannot be interpreted in the usual
interpretation which is called infix notation. Actually the last two can be
interpreted in postfix notation as 1 + 2 and 1 + (2 × 3), respectively. The
postfix notation is sometimes called reverse polish notation since it is the
reverse of prefix notation invented by Polish mathematician Jan Lukasiewicz
around 1920’s.
Properly formed expressions is the starting point of logic. Formally prop-
erly expression is called well-formed formula.
The language consists of:
Free variables: a0 , a1 , . . .
Bound variables: x0 , x1 , . . .
A predicate symbol: ∈
Logical symbols: ¬, ∨ , ∧ , −→ , ←→ , ∀, ∃.
Auxiliary symbols: (, ), [, ].
φ, ψ, η are meta symbols.
Definition 2.2.1 (well-formed formula (wff)).

∆
A formula is well-formed formula (wff ) ←→ it is deducible from the fol-
lowing rules:
i. If a and b are free variables, then [a ∈ b] is a wff.
2.2. FOUNDATIONS 11
ii. If φ and ψ are wffs, then ¬φ, [φ ∨ ψ], [φ ∧ ψ], [φ −→ ψ], and [φ ←→ ψ]
are wff.
iii. If φ is a wff and x is a bound variable, then ∀x φ(x) and ∃x φ(x) are
wff, where φ(x) is the formula obtained from the wff φ by replacing
each occurrence of some free variable a by the bound variable x. We
call ∀xφ(x) and ∃xφ(x) respectively, the formula obtained from φ by
universally, or existentially qualifying on the variable a.
Example 2.2.2. Examples of wffs are as follows where p = x0 and q = x1 .
i. p and q are wffs due to Definition 2.2.1(i).
ii. ¬p, p ∨ q, p ∧ q, p −→ q, p ←→ q are wffs due to Definition 2.2.1(ii).
iii. [p ∧ q] ∨ ¬p, [p ∧ q] ∨ ¬[p −→ q] are wffs due to Definition 2.2.1(i)
and (ii) .
iv. ∃x [x ∈ a1 ] is a wff. Since
[a0 ∈ a1 ] by Definition 2.2.1(i)
∃x [x ∈ a1 ] by existential qualifying on a0 .
v. ∃x [x ∈ a1 ] ∧ ∀x [x ∈ a1 ] is a wff.
2.2.2 Logical Axioms

Axiom 1 (Logical Axioms).
i. φ −→ [ψ −→ φ].
ii. [φ −→ [ψ −→ η]] −→ [[φ −→ ψ] −→ [φ −→ η]].
iii. [¬φ −→ ¬ψ] −→ [ψ −→ φ].
iv. ∀x[φ −→ ψ(x)] −→ [φ −→ ∀xψ(x)] where free variable a on which
we are quantifying does not occur in φ.
v. ∀xφ(x) −→ φ(a) where φ(a) is the formula obtained by replacing each
occurrence of the bound variable x in φ(x) by the free variable a.
2.2.3 Rules of Inference

Axiom 2 (Rules of Inference).
i. From φ and φ −→ ψ to infer ψ.
ii. From φ to infer ∀x φ(x) where φ(x) is obtained from φ by replacing each
occurrence of some free variable by x.
Notation.
i. φ and φ −→ ψ =⇒ ψ.
ii. φ =⇒ ∀xφ(x).
12 CHAPTER 2. LOGIC
Definition 2.2.2 (Logically Equivalence).

∆
φ is logically equivalent to ψ ←→ φ is deducible using only the logical
axioms. It is denoted by φ ←→ ψ.
2.2.4 Equality
Definition 2.2.3 (Equality).
∆
a=b ←→ ∀x [x ∈ a ←→ x ∈ b].
Proposition 2.2.1.
i. a = a.
ii. a = b −→ b = a.
iii. a = b ∧ b = c −→ a = c.
Proof.
i. ∀x[x ∈ a ←→ x ∈ a].
ii. ∀x[x ∈ a ←→ x ∈ b] =⇒ ∀x[x ∈ b ←→ x ∈ a].
iii. ∀x[x ∈ a ←→ x ∈ b] ∧ ∀x[x ∈ b ←→ x ∈ c] =⇒ ∀x[x ∈ a ←→
x ∈ c].
Remark 2.2.1. If a = b and a wff holds for a, then it must hold for b.
a = b =⇒ [φ(a) ←→ φ(b)].
2.3 Propositional Logic

Definition 2.3.1. A proposition is a statement that is either true or false
but not both. The truth value of a true proposition is true, denoted by T
and that of false proposition is false, denoted by F .
Notation. Propositions are represented by lower case letters such as p, r, q.
2.3.1 Compound Propositions

We generate new propositions from existing ones by means of well-formed-
formulation. Any wff is a generated new proposition based on already estab-
lished propositions.
2.3. PROPOSITIONAL LOGIC 13
f2 = ¬p
f0 = F
f3 = T
f1 = p
p
F F F T T
T F T F T
Table 2.1: Boolean functions of one variable

f2 = ¬(p −→ q)
f14 = p NAND q
f13 = p −→ q
f9 = p ←→ q
f8 = p NOR q
f7 = p ∨ q
f1 = p ∧ q
f6 = p ⊕ q
f12 = ¬p
f10 = ¬q
f15 = T
f0 = F
f3 = p
f5 = q
f11
f4
p q
F F F F F F F F F F T T T T T T T T
F T F F F F T T T T F F F F T T T T
T F F F T T F F T T F F T T F F T T
T T F T F T F T F T F T F T F T F T
Table 2.2: Boolean functions of two variables
∆
Definition 2.3.2. The set B = { T, F } is called boolean domain where T
and F denotes true and false, respectively. An n-tuple (p1 , p2 , . . . , pn ) where
pi ∈ B is called a boolean n-tuple.
Definition 2.3.3. An n-operand truth table is a table that assigns a boolean

value to all boolean n-tuples. A propositional operator is a rule defined by a
truth table.
monadic one
Definition 2.3.4. An operator is called if it has oper-
dyadic two
ant(s).
Remark 2.3.1.
i. A boolean n-tuple is an element of Bn , that is, (p1 , p2 , . . . , pn ) ∈ Bn .
ii. There are 2n different binary n-tuples.
iii. A truth table of a predicate p actually defines a function fp : Bn → B.
14 CHAPTER 2. LOGIC
n
iv. There are 22 different truth tables (functions) of binary n-tuples.
1
v. There are 22 = 4 monadic operators, identity, negation, constant-True,
constant-False, as given in Table 2.3.1.
2
vi. There are 22 = 16 dyadic operators as given in Table 2.3.1.
vii. Note that the functions in the Table 2.3.1 have interesting properties:
Firstly, notice the relation between fi and the binary representation of
i if F and T are represented as 0 and 1, respectively. For example f11
corresponds to T F T T = 1011. Secondly, fi = ¬f15−i as in the case of
f3 = ¬f12
viii. NAND and NOR are extensively used in logic design in Computer Engineer-
ing.
∆
ix. p NAND q = ¬(p ∧ q). That is, f14 (p, q) = ¬f1 (p, q).
∆
x. p NOR q = ¬(p ∨ q). That is, f8 (p, q) = ¬f7 (p, q).
Definition 2.3.5. Any wff is a compound propositions.
Remark 2.3.2. In other words, propositions formed from existing propositions
using logical operators are called compound propositions.
Definition 2.3.6. Let p be a proposition. The negation of p, denoted by ¬p
or p̄, is the statement “It is not the case that p”.
Definition 2.3.7. Let p and q be propositions. The conjunction of p and q,
denoted by p ∧ q, is the proposition “p and q”.
(
∆ T, if both p and q are true,
p ∧ q =
F, otherwise.
Definition 2.3.8. Let p and q be propositions. The disjunction of p and q,
denoted by p ∨ q, is the proposition “p or q”.
(
∆ F, if both p and q are false,
p ∨ q =
T, otherwise.
Definition 2.3.9. Let p and q be propositions.
exclusive or of p and q p⊕q
The conditional statement , denoted by p −→ q , is the function
biconditional statement p ←→ q
f6
f13 in the Table 2.3.1.
f9
2.3. PROPOSITIONAL LOGIC 15
Remark 2.3.3.
i. Conditional p −→ q, sometimes called implication.
ii. Some other English usages are “if p, then q”, “p implies q” and many
more.
iii. p is called the hypothesis. q is called the conclusion.
Remark 2.3.4.
i. Biconditional p ←→ q, sometimes called bi-implication or if-and-only-
if , iff in short.
ii. Some other English usages are “p is necessary and sufficient for q”, “p
iff q”.
iii. Note that p ←→ q is equivalent to (p −→ q) ∧ (q −→ p).
Definition 2.3.10. Two compound propositions φ(x1 , x2 , . . . , xn ) and ψ(x1 , x2 , . . . , xn )

∆
of the same variables x1 , x2 , . . . , xn , are called equivalent ←→ they have the
same truth tables. It is denoted by φ(x1 , x2 , . . . , xn ) ⇐⇒ ψ(x1 , x2 , . . . , xn ),
Remark 2.3.5. The biconditional, p ←→ q, is an operator. The equivalence

of two compound propositions, p ⇐⇒ q, is an equivalence relation on the
set of all propositions.
Definition 2.3.11. Let p −→ q.

converse q −→ p
The contrapositive of p −→ q is ¬q −→ ¬p .
inverse ¬p −→ ¬q
Corollary 2.3.1.
implication, p −→ q contrapositive, ¬q −→ ¬p
The is equivalent to .
converse, q −→ p inverse, ¬p −→ ¬q
2.3.2 Application
Logic descriptions is used in all branches of science and engineering. Unam-
biguous, precise, consistent reporting is a must.
Translating English sentences

Consider a detective story such as one from Sherlock Holmes. There are
people P1 , P2 , . . . , Pn . There are corresponding propositions p1 , p2 , . . . , pn
where pi means person Pi is the murderer. Of course there is a description
16 CHAPTER 2. LOGIC
of the rest of the story which can be represented as q(p1 , p2 , . . . , pn ). In

this formulization if person P3 is the murderer then the truth assignment of
(F, F, T, F, . . . , F ) makes q true, that is, q(F, F, T, F, . . . , F ) = T . Here we
assume that there is one murderer so there is only one entry pi = T .
System specifications
In engineering precise, formal descriptions are needed. Software develop-
ment is one of them. A typical software life cycle is as follows: A customer
who needs a custom tailored software solution defines what she wants. This
definition will be given to the contracting company. The developers start de-
veloping the software. At the end the software is delivered to the costumer.
The costumer checks if the developed software meets the specification.
In such a scenario the definition should be as precise as possible. Think
about the consequences if the definition is not precise, informal, possibly
ambiguous. It is not that unusual that the definitions have some conflict or
contradicting requirements.
Boolean search. Search in web.

It is already mentioned in the motivation that search engines understand the
language of predicates.
• Translating English sentences
• System specifications
• Boolean search. Search in web.
• Logic puzzles
• Logic and bit operations
2.4 Propositional Equivalence

We use wff for compound propositions.
tautology ∆ true
Definition 2.4.1. A wff is called a ←→ it is always
contradiction false
independent of the truth values of its propositions. A wff that is neither
tautology not contradiction is called a contingency.
Example 2.4.1. Some simple forms are as follows:
Tautologies: T , ¬F , p ∨ T , p ∨ ¬p.
2.4. PROPOSITIONAL EQUIVALENCE 17
Equivalence Name
p ∧ T ≡p Identity laws
p ∨ F ≡p
p ∧ F ≡F Domination laws
p ∨ T ≡T
p ∧ p≡p Idempotent laws
p ∨ p≡p
p ∧ q≡q ∧ p Commutativity laws
p ∨ q≡q ∨ p
p ∧ (q ∧ r) ≡ (p ∧ q) ∧ r Associativity laws
p ∨ (q ∨ r) ≡ (p ∨ q) ∨ r
p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r) Distributivity laws
p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r)
p ∧ (p ∨ q) ≡ p Absorption laws
p ∨ (p ∧ q) ≡ p
p ∧ ¬p ≡ F Negation laws
p ∨ ¬p ≡ T
¬(p ∧ q) ≡ ¬p ∨ ¬q De Morgan’s laws
¬(p ∨ q) ≡ ¬p ∧ ¬q
¬(¬p) ≡ p Double negation law
Table 2.3: The laws of logic
Contradictions: F , ¬T , p ∧ F , p ∧ ¬p.
Contingencies: p, ¬p, p ∨ F , p ∧ T .
Definition 2.4.2 (Logically Equivalence).

∆
Two wffs p and q are called logically equivalent ←→ The wff p ←→ q is a
tautology. Logically equivalence of p and q is denoted by p ≡ q or p ⇐⇒ q.
Remark 2.4.1. Note that logically equivalence is an equivalence relation on
the set of all wff since:
i. Reflexivity: ∀p [p ⇐⇒ p].
ii. Symmetry: ∀p, q [(p ⇐⇒ q) −→ (q ⇐⇒ p)].
iii. Transitivity: ∀p, q, r [(p ⇐⇒ q) ∧ (q ⇐⇒ r) −→ (p ⇐⇒ r)].
Laws of logically equivalence are given in Table 2.3.
Example 2.4.2. T ⇐⇒ ¬F , ¬F ⇐⇒ p ∨ T , p ∨ T ⇐⇒ p ∨ ¬p.
18 CHAPTER 2. LOGIC
Acknowledgment. These notes are based on various books but especially

[Ros07, TZ82].
Q1 [20 points]
a) Express each of these statements using quantifiers and the following
predicates where the domain consists of all people.
S(x) : x is a student in this class. M(x) : x is a mathematician
L(x) : x likes discrete mathematics course. C(x, y) : x and y are colleagues
K(x, y) : x knows y
i) There are exactly two students in this class who like discrete math-
ematics course.
ii) Every student in this class knows Kurt Gödel or knows a mathe-
matician who is a colleague of Kurt Gödel.
iii) There is no student in this class who knows everybody else in this
class
b) Using rules of inference provide a formal proof for

If ∀x [S(x) ∨ Q(x)], and ∀x [(¬S(x) ∧ Q(x)) → P (x)] are true then
∀x [¬P (x) → S(x)] is also true where the domains of all quantifiers are
the same.
Solution.
a)
i) ∃x∃y [x 6= y ∧ S(x) ∧ S(y) ∧ L(x) ∧ L(y) ∧ ∀z (S(z) ∧ L(z) → z =
x ∨ z = y)]
ii) ∀x [S(x) → [K(x, Godel) ∨ ∃y (M(y) ∧ C(y, Godel) ∧ K(x, y))]]
iii) ¬∃x∀y [S(x) ∧ ((S(y) ∧ x 6= y) → K(x, y))]
b)
2.4. PROPOSITIONAL EQUIVALENCE 19
1. ∀x [S(x) ∨ Q(x)] Premise

2. ∀x [(¬S(x) ∧ Q(x)) → P (x)] Premise
3. S(a) ∨ Q(a) (1) universal generalization
4. (¬S(a) ∧ Q(a)) → P (a) (2) universal generalization
5. ¬(¬S(a) ∧ Q(a)) ∨ P (a) (4) logical equivalence p → q ≡ ¬p ∨ q
6. (S(a) ∨ ¬Q(a)) ∨ P (a) (5) De Morgan
7. (P (a) ∨ S(a)) ∨ ¬Q(a) (6) Commutativity and associativity of ∨
8. (P (a) ∨ S(a)) ∨ S(a) (7) and (3) resolution
9. P (a) ∨ S(a) (8) Idempotent law
10. ¬P (a) → S(a) (9) logical equivalence p → q ≡ ¬p ∨ q
11. ∀x (¬P (x) → S(x)) Universal generalization (a was arbitrary)
Q2 [20 points]
Solution.
20 CHAPTER 2. LOGIC
Chapter 3
Sets, Relations, and Functions
3.1 Set
3.1.1 Sets
Definition 3.1.1. A set is unordered collection of objects.
Remark 3.1.1. We do not define set, element, and membership properly.

A set is a collection of elements. Sets are usually represented by capital
letters A, B, . . . . Sets are defined either listing of the elements as in A =
{ a1 , a2 , . . . }. set!representation or those elements that satisfy predicate P (a)
as in A = { a | P (a) }. Note that the order of the elements is not important.
Due to that unordered n-tuple is represented as { a1 , a2 , . . . , an }. If a is an
element of A, it is denoted as a ∈ A, otherwise as a ∈ / A.
Example 3.1.1. The set of natural numbers N = { 0, 1, 2, . . . }. 8 ∈ N but
−3 ∈ / N.
E = { x | x ∈ N ∧ x is even } = { x ∈ N | x is even } where the second form
is a short form of the first.
Definition 3.1.2. The empty set, denoted ∅, has no elements in it.
Remark 3.1.2. There is one and only one empty set. ∅ has interesting prop-
erties: Let A = ∅ and B = { ∅ }. Then A ∈ B ∧ A ⊆ B.
Remark 3.1.3. Let P (x) be a property. Then the following two propositions
are true:
21
22 CHAPTER 3. SETS, RELATIONS, AND FUNCTIONS
i) ∀x ∈ ∅ [P (x)]
ii)¬∃x ∈ ∅ [P (x)]
Definition 3.1.3 (Equality of Sets).
∆
A is equal to B: A = B ←→ ∀x [ x ∈ A ←→ x ∈ B ].
∆
A is not equal to B: A 6= B ←→ ∃a (a ∈ A ∧ a ∈
/ B) ∨ ∃b (b ∈
/ A ∧ b ∈ B).
Example 3.1.2. { 1, 2, 3 } = { 2, 1, 3 }. Order of elements is not important.

{ 1, 2, 3 } = { 1, 1, 2, 3 }. Repetition of elements is not important.
x 6= { x } , { x } =
6 { { x } }.
Definition 3.1.4 (Subset).

∆
A is a subset of B: A ⊆ B ←→ ∀a (a ∈ A −→ a ∈ B).
∆
A is a proper subset of B: A ⊂ B ←→ A ⊆ B ∧ ∃b (b ∈
/ A ∧ b ∈ B).
Theorem 3.1.1.
Let A be a set.
i. ∀A [∅ ⊆ A].
ii. ∀A [A ⊆ A].
Definition 3.1.5 (Cardinality, Finite Set, Infinite Set).
∆
A is finite and n is the cardinality of A ←→ There are exactly n distinct
∆
elements in A. The cardinality of A is denoted by | A |. A is infinite ←→
A is not finite.
Remark 3.1.4. This definition of infinity needs elaboration.

Example 3.1.3.
0 = | ∅ |.
1 = | { a } | = | { a, a } | = | { ∅ } | = | { { ∅ } } | = | { { { ∅ } } } | = | { { ∅, { ∅ } } } |.
2 = | { a, b } | = | { ∅, { { ∅ } } } | = | { ∅, { ∅ } } |.
Definition 3.1.6 (Power Set).

∆
The power set of A: 2A = { S | S ⊆ A }.
Example 3.1.4. 2{ 1,2,3 } = { ∅, { 1 } , { 2 } , { 3 } , { 1, 2 } , { 1, 3 } , { 2, 3 } , { 1, 2, 3 } }.
{∅}
2∅ = { ∅ }, 2{ ∅ } = { ∅, { ∅ } }, 22 = { ∅, { ∅ } , { { ∅ } } , { ∅, { ∅ } } }.
S
Theorem 3.1.2. A = S∈2A S.
3.1. SET 23

Theorem 3.1.3. If A is finite, 2A = 2| A | .
Theorem 3.1.4. 2A = 2B −→ A = B.
S S
Proof. By Theorem 3.1.2, 2A = 2B −→ S∈2A S= S∈2B S. ∴ A = B.
Definition 3.1.7 (Ordered n-tuple).
The ordered n-tuple (a1 , a2 , . . . , an ) is the ordered collection that has ai as
its ith element. (a1 , a2 ) is called ordered pairs.
(a1 , a2 , . . . , an ) is equal to (b1 , b2 , . . . , bn ), denoted by (a1 , a2 , . . . , an )=(b1 , b2 , . . . , bn ),
∆
←→ ∀i ∈ { 1, . . . , n } ai = bi .
Remark 3.1.5.
An unordered n-tuple is represented by a set. Sets can be used to repre-
sent ordered tuples, too. Ordered n-tuple can be represented as sets as:
∆
(a1 , a2 ) = { a1 , { a2 } }.
∆
(a1 , a2 , a3 ) = { a1 , { a2 , { a3 } } }.
Definition 3.1.8 (Cartesian Product).

∆
The Cartesian product of A and B: A × B = { (a, b) | a ∈ A ∧ b ∈ B }.
Remark 3.1.6. Note that A × B 6= B × A. As an example A = { 1 } and B =
{ b }. Then A × B = { (1, b) } and B × A = { (b, 1) }. Hence A × B 6= B × A.
Theorem 3.1.5. A × ∅ = ∅ × A = ∅.
Theorem 3.1.6. A × B = ∅ −→ (A = ∅ ∨ B = ∅).
Proof. Suppose ¬(A = ∅ ∨ B = ∅).
⇒ A 6= ∅ ∧ B 6= ∅.
⇒ ∃a ∈ A ∧ ∃b ∈ B.
⇒ (a, b) ∈ A × B.
⇒ A × B 6= ∅.
Hence A = ∅ ∨ B = ∅.
Definition 3.1.9. The Cartesian product of the sets A1 , A2 , . . . , An : A1 ×
∆
A2 × · · · × An = { (a1 , a2 , . . . , an ) | ∀i ∈ { 1, . . . , n } ai ∈ Ai }.
Definition 3.1.10 (Power of a Set An ).
The nth power of a set, denoted by An , is defined as
A1 = A.
An+1 = An × A where n ∈ Z+ .
3.1.2 Set Operations

Definition 3.1.11 (Union).
∆
The union of A and B: A ∪ B = { x | x ∈ A ∨ x ∈ B }.
Definition 3.1.12 (Intersection).
∆
The intersection of A and B: A ∩ B = { x | x ∈ A ∧ x ∈ B }.
(a) Union. (b) Intersection.
(c) Set difference. (d) Symmetric set differ-

ence.
Figure 3.1: Set operations.
Remark 3.1.7. Set operations can be visualized by Venn diagrams as in

Fig. 3.1
'$
BkCk
Example 3.1.5. For sets A, B, C in A
the figure, A ∪ B = A ∪ C ∧ B 6= C.
&%
Definition 3.1.13. Let C = { A1 , A2 , . . . , An } be a collection of sets.

S ∆
The union of collection C: ni=1 Ai = A1 ∪A2 ∪· · ·∪An = { x | ∃i ∈ { 1, . . . , n } x ∈ Ai }.
T ∆
The intersection of collection C: ni=1 Ai = A1 ∩A2 ∩· · ·∩An = { x | ∀i ∈ { 1, . . . , n } x ∈ Ai }.
3.1. SET 25
∆
Definition 3.1.14. A and B are disjoint ←→ A ∩ B = ∅.
Theorem 3.1.7 (Principle of Inclusion-Exclusion).
(
|A|+ |B| if A ∩ B = ∅,
|A ∪ B| =
| A | + | B | − | A ∩ B | if A ∩ B 6= ∅.
Definition 3.1.15 (Set Difference).

∆
The difference of A and B: A\B = { x | x ∈ A ∧ x ∈
/ B }.
Definition 3.1.16 (Symmetric Difference).
∆
The symmetric difference of A and B: A ⊕ B = (A ∪ B)\(A ∩ B).
Definition 3.1.17 (Complement).
∆
The complement of A with respect to the universal set U: A = U\A.
Theorem 3.1.8 (Set Identities).
Let A, B, C be sets and U be the universal set.
A∪∅=A A∩U =A Identity
A∪U =U A∩∅ =∅ Domination
A∪A=A A∩A= A Idempotent
(A) = A Complementation
A∪B =B∪A A∩B = B∩A (Commutativity)
A ∪ (B ∪ C) = (A ∪ B) ∪ C A ∩ (B ∩ C) = (A ∩ B) ∩ C (Associativity)
A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C) A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C) (Distributivity)
A∪B =A∩B A∩B = A∪B (De Morgan)
A ∪ (A ∩ B) = A A ∩ (A ∪ B) = A (Absorption)
A∪A=U A∩A= ∅ (Complement)
Proof of A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C).
A ∩ (B ∪ C)
= { x | x ∈ A ∩ (B ∪ C) } definition of membership
= { x | x ∈ A ∧ (x ∈ B ∪ C) } definition of ∩
= { x | x ∈ A ∧ (x ∈ B ∨ x ∈ C) } definition of ∪
= { x | (x ∈ A ∧ x ∈ B) ∨ (x ∈ A ∧ x ∈ C) } distributivity of ∧ over ∨
= { x | (x ∈ (A ∩ B) ∨ (x ∈ (A ∩ C) } definition of ∩
= { x | x ∈ (A ∩ B) ∪ (A ∩ C) } definition of ∪
= (A ∩ B) ∪ (A ∩ C) definition of membership
3.2 Relation
Remark 3.2.1. A × B = { (a, b) | a ∈ A ∧ b ∈ B }.
Definition 3.2.1 (Matrix). An array of numbers with n rows and m columns

is called an n×m matrix . The entry at the ith row and jth column of matrix
M is denoted by [M]ij . A matrix with entries 0 and 1 only is called a binary
matrix . Binary matrices are also called (0, 1)-matrices.
∆
Definition 3.2.2. α is called a binary relation from A to B ←→ α ⊆ A×B.
We use the infix notation of a α b whenever (a, b) ∈ α.
Remark 3.2.2. If sets A and B are finite with |A| = n and |B| = m, the ele-
ments of A and B can be listed in an arbitrary order as A = { a1 , a2 , . . . , an }
and B = { b1 , b2 , . . . , bm }. Then binary relation α ⊆ A × B can be repre-
sented by an n × m (0, 1)-matrix, denoted by Mα , as
(
∆ 1, ai α bj
[Mα ]ij =
0, otherwise.
Note that there are n rows correspond to the ordered elements of A, and
m columns correspond to the ordered elements of B.
Example 3.2.1.
Let α = { (3, b), (3, c), (7, c) } ⊆ A × B where A = { 1, 3, 7 } and B =
{ a, b, c, d }.
Using the orderings of

A = { 1, 3, 7 } and B = { a, b, c, d } we
have
a b c d
1 0 0 0 0
Mα =
3  0 1 1 0
7 0 0 1 0
Using a different orderings such as
A = { 7, 1, 3 } and B = { c, a, d, b }
the matrix changes to
c a d b
7 1 0 0 0
Mα =
1 0 0 0 0 .
3 1 0 0 1
3.2. RELATION 27
Remark 3.2.3. The cartesian and the matrix representations are related. Ro-
tate the cartesian representation by 90◦ clock wise, and compare with the
matrix representation.
Question 3.2.1. How many different binary relations from A to B can be
defined?
3.2.1 Composition of Relations

Definition 3.2.3 (Composition of Relations).
Let α ⊆ A × B, β ⊆ B × C. The composition of α and β, denoted by α ◦ β,
∆
is defined as α ◦ β = { (a, c) ∈ A × C | ∃b ∈ B [a α b ∧ b β c] }.
Remark 3.2.4. Note that α ◦ β ⊆ A × C. Note that this notation of compo-
sition is different that the notation of composition of functions which will be
discussed at Sec.3.3.
Definition 3.2.4 (Boolean Matrix Multiplication).
Let Mα and Mβ be n × m and m × p binary matrices. The binary product of
Mβ and Mα , denoted by Mα ⊙ Mβ , is an n × p binary matrix defined as
(
∆ 1, ∃k [1 ≤ k ≤ m ∧ [Mα ]ik = 1 ∧ [Mβ ]kj = 1]
[Mα ⊙ Mβ ]ij =
0, otherwise.
Remark 3.2.5. Binary matrix

Wn multiplication can be defined by means of logic
functions. [Mα ⊙ Mβ ]ij = k=1 [Mα ]ik ∧
W [Mβ ]kj where ∧ and
P ∨ are logical
AND and OR functions. The notation nk=1 , is similar to nk=1 , is defined
W ∆
as nk=1 = p1 ∨ p2 ∨ · · · ∨ pn .
Example 3.2.2.
Using orders A = { 1, 2 }, B = { a, b, c } and C = { A, B, C, D }:
 
1 1 1 0
1 1 0 1 1 1 0
⊙ 0 1 1 0 =
0 1 0 0 1 1 0
1 0 0 1
Mα ⊙ Mβ = Mα◦β
But regular matrix multiplication
 gives:
1 1 1 0
1 1 0 1 2 2 0
× 0 1 1 0 =
0 1 0 0 1 1 0
1 0 0 1
Mα × Mβ = Mα × Mβ .
Theorem 3.2.1. Mα◦β = Mα ⊙ Mβ .
Theorem 3.2.2 (Associativity).

(α ◦ β) ◦ γ = α ◦ (β ◦ γ) whenever (α ◦ β) ◦ γ is defined.
Corollary 3.2.3 (Associativity).

Mα ⊙ (Mβ ⊙ Mγ ) = (Mα ⊙ Mβ ) ⊙ Mγ whenever Mα ⊙ (Mβ ⊙ Mγ ) is defined.
Definition 3.2.5 (Inverse of a Binary Relation). The inverse of a binary

∆
relation, denoted by α−1 , is defined as b α−1 a ←→ a α b.
Definition 3.2.6. The transpose of a matrix, denoted by M ⊤ , is defined as

∆
[M ⊤ ]ij = [M]ji .
Theorem 3.2.4. Mα−1 = (Mα )⊤ .
Theorem 3.2.5. [α ◦ β]−1 = β −1 ◦ α−1 .

∆
Definition 3.2.7. The complement of α, denoted as α, is defined as a α b ←→
¬ a α b.
Theorem 3.2.6. Mᾱ = 1 − Mα where 1 is matrix of all 1s.
Example 3.2.3. Show that (α)−1 = (α−1 )

(a, b) ∈ (α)−1 ⇔ (b, a) ∈ α ⇔ (b, a) ∈ / α−1 ⇔ (a, b) ∈ (α−1 ).
/ α ⇔ (a, b) ∈
3.3 Functions
Remark 3.3.1. Let f be a relation from A to B. Pick an a ∈ A and consider
∆
the corresponding set Ba ⊆ B defined as Ba = { b | (a, b) ∈ f }. Note that
3.3. FUNCTIONS 29
| Ba | could be 0, 1, 2, . . . .
0 not mapped to any b ∈ B
If | Ba | = 1 , then a is mapped to exactly one b ∈ B .
n≥2 mapped to n elements of B
Definition 3.3.1. A relation f ⊆ A × B is called partial function

∆
←→ ∀a ∈ A | Ba | ≤ 1.
Remark 3.3.2. Any computer program is actually a partial function from its
input space to its output space. For some inputs in its domain it terminates
and produces outputs. For some other inputs it does not terminate. Hence
for those inputs there is no corresponding outputs. That is the reason that
it is a partial function.
Definition 3.3.2. A relation f ⊆ A × B is called function

∆
←→ ∀a ∈ A | Ba | = 1.
1
Example 3.3.1. Remember function y = f (x) = x−1 from Calculus. It is
considered to be a function from R to R. Properly speaking this statement
is not true since it is not defined at x = 1 ∈ R.
-5 -4 -3 -2 -1 0 1 2 3 4 5
-1
-2
Actually, it is a function from R r { 1 } to R. On the other hand, it is a

partial function from R to R.
A domain
Definition 3.3.3. B is called the codomain of f and written as
f (A) range
dom f
cod f .
ran f
Question 3.3.1. Consider the ceiling function f (x) = ⌈ x ⌉. dom f = ?,

cod f = ?, ran f = ?
Notation.
∆
• b = f(a) ←→ a f b
• A function f from A to B is represented by f : A → B.
• The set all functions from A to B is represented by B A .
• f(C) = { f (c) | c ∈ C } for C ⊆ A.
Remark 3.3.3.
BA functions
Let P be the set of all partial functions from A to B. Then B A ⊆ P ⊆
R relations
R.
Question 3.3.2.
A
• B =?
• | P | =?
• | R | =?

Theorem 3.3.1. If A and B are finite sets, not both empty, then B A =
| B || A | .
Question 3.3.3. Let A be a nonempty set.

A
• ∅ = ?
∅
• A = ?
∅
• ∅ = ?
Definition 3.3.4. Let A1 ⊆ A ⊆ A2 and f : A → B. Then partial function

f2 ⊆ A2 × B is an extension of f to A2
∆
←→ [∀a ∈ A, ∀b ∈ B (a, b) ∈ f2 ←→ (a, b) ∈ f ].
Function f1 ⊆ A1 × B is the restriction of f to A1
3.3. FUNCTIONS 31
∆
←→ [∀a ∈ A, ∀b ∈ B (a, b) ∈ f1 ←→ (a, b) ∈ f ].
Remark 3.3.4 (The inverse of a function). Note that for any relation α from
A to B, there is a unique inverse relation from B to A. This inverse relation
usually denoted by α−1 . Since a function f from A to B is also a relation,
there is an inverse relation from B to A which is also denoted as f −1 . Note
that f −1 is a relation but not necessarily a function. f −1 becomes a function
if and only if f is a bijection.
Definition 3.3.5. Let f : A → B.

a surjection f (A) = B
an injection ∆ ∀a1 , a2 ∈ A [a1 6= a2 → f (a1 ) 6= f (a2 )]
f is called ←→ .
a bijection surjection ∧ injection
a permutation f : A → A and f is a bijection
Theorem 3.3.2. Let f : A → B and g : B → C be functions If f and g

surjections a surjection
are injections , then g ◦ f is also an injection .
bijections a bijection
Remark 3.3.5 (Composition of functions). The notations of composition of

relations and composition of functions are inconsistent. Note that a function
is a special relation. So composition of relations can be extended to functions.
Let f : A → B and f : B → C. Then f and g are also two relations. Then
f ◦g is the composition of relation f with relation g. Note that f ◦g is relation
from A to C. More than that f ◦ g satisfies the requirements of function. So
f ◦ g is actually a function which takes a ∈ A to c ∈ C via some b ∈ B.
Then using the functional notation b = f (a), c = g(b) = g(f (a)) =
(g ◦ f )(a). Note that composition of function f with g is represented by g ◦ f
which is the opposite order of composition of relations which is f ◦ g.
This inconsistency in notation is probably due to the convenience of
matrix representations in the composition of of relations. Remember that
Mα◦β = Mα ⊙ Mβ where Mα◦β is the matrix of the composition of α with β.
A formula such as Mβ◦α = Mα ⊙ Mβ would not be that convenient.
Theorem 3.3.3. Let f : A → B and g : B → C be functions. Then

the composition of relations g ◦ f is a function: g ◦ f : A → C where
(g ◦ f )(a) = g(f (a)).
Remark 3.3.6.
• If functions f : A → B and g : B → C are invertible, then g ◦ f is

also invertible and g ◦ f = f −1 ◦ g −1 .
• f −1 (B) = { a ∈ A } f (a) ∈ B
• Let f : R → R. Then f and f −1 are symmetric with respect to y = x

line.
Example 3.3.2.
Show that any function f : A → B can be represented as the composition
of g and h, f = h ◦ g, where g is a surjection, h is an injection.
Define D = { Di ⊆ A | d1 , d2 ∈ Di ⇔ f (d1 ) = f (d2 ) }.

Define g : A → D ∋ g(a) = Di =
−1
f (f (a)).
Then, clearly g is a surjection since
∀Di ∈ D [∃a ∈ A [Di = f −1 (f (a))]],
hence g(a) = Di .
Define h : D → B ∋ h(Di ) =
h(f −1 (f (a))) = f (a).
Let Di 6= Dj . Then, for di ∈ Di
and dj ∈ Dj , f (di) 6= f (dj ). So
h(Di ) 6= h(Dj ). Therefore, h is an
injection.
(h ◦ g)(a) = h(g(a)) =
−1
h(f (f (a))) = f (a)
So, g ◦ h = f .
Question 3.3.4.
• Are Di ’s disjoint?
• What is f −1 (B)?
• What is f (f −1 (B))?
• What kind of function is f if B\f (A) = ∅?
• What kind of function is f if ∀b ∈ B [| f −1 (b) | = 1]?
3.4. PROBLEMS 33
• If | A | = n, | B | = n, what is the number different functions f ?

For functions from a set to itself has an interesting property that it can
be applied repeatedly. Let f : A → A be a function and a ∈ A. Then f (a),
f (f (a)), , f (f (f (a))), · · · are all defined.
Definition 3.3.6 (Power of a function). Let f : A → A be a function.
Power of a function is defined as
∆
i. f 1 = f .
∆
ii. f n+1 = f n for n ∈ N.
Definition 3.3.7 (fixed point). Let f : A → A be a function. a ∈ A is
∆
called a fixed point of f ←→ f (a) = a,
Remark 3.3.7. Fixed points are important in Computer Science. If a is a
fixed point of f then f n (a) = a for all n ∈ N.
Question 3.3.5. Consider functions from R to R. Let a, b, c ∈ R.
• What are the fixed points of f (x) = ax + b where a and b are real param-
eters? Consider the cases where a = 1 and b = 1, a = 2 and b = 1, and
a = 1 and b = 0.
• What are the fixed points of f (x) = ax2 + bx + c where a, b and c are real
parameters? Consider the cases for different values of a, b and c.
• What are the fixed points of f (x) = sin x?
• The function f (x) = rx(1 − x) from Z to Z is called the logistics map
where r ∈ R is a parameter [Str94]. Although it seems simple logistic map
has unexpectedly rich properties if it is applied iteratively, i.e. xn+1 =
rxn (1 − xn ). Try to plot logistic map for r = 2.8, r = 3.3, r = 3.5,
r = 3.857.
Acknowledgment. These notes are based on various books but espe-
cially [PY73, Ros07, TZ82, Gal89, Hol60, Nes09].
3.4 Problems
Q3 [20 points]
a) Prove or disprove that set difference distributes over union, that is,
A − (B ∪ C) = (A − B) ∪ (A − C).
b) Given a nonempty set A, let f : A → A and g : A → A where

∀a ∈ A f (a) = g(f (f (a))) and g(a) = f (g(f (a)))
Prove that f = g.
Solution.
a) A − (B ∪ C) = (A − B) ∪ (A − C)
Consider the following counter example which disproves the statement.
Let A = {1, 2, 4, 5}, B = {2, 3, 5, 6} and C = {4, 5, 6, 7}.
Then A − (B ∪ C) = {1, 2, 4, 5} − {2, 3, 4, 5, 6, 7} = {1} and
(A−B)∪(A−C) = ({1, 2, 4, 5}−{2, 3, 5, 6})∪({1, 2, 4, 5}−{4, 5, 6, 7}) =
{1, 2, 4}.
Hence, A − (B ∪ C) 6= (A − B) ∪ (A − C).
b) Proof by contradiction: Let f : A → A and g : A → A and
∀a ∈ A f (a) = g(f (f (a))) (I), and g(a) = f (g(f (a))) (II), but f 6= g.
Then ∃s ∈ A f (s) 6= g(s).
f(s) 6= g(s)
⇔ g(f (f (s))) 6= g(s) since f = g(f (f ))
⇔ f (g(f (f (f (s))))) 6= g(s) since g = f (g(f ))
⇔ f (g(f (f (f (s))))) 6= g(s)
| {z }
f
⇔ f (f (f (s))) 6= g(s) since f = g(f (f ))
⇔ f (f ( f ))) 6= g(s)
|{z}
g(f (f (s)))
⇔ f (f (g(f (f (s))))) 6= g(s) since f = g(f (f ))
⇔ f (f (g(f (f (s))))) 6= g(s)
| {z }
g
⇔ f (g(f (s))) 6= g(s) since g = f (g(f ))
⇔ g(s) 6= g(s) since g = f (g(f )). Contradiction!
Hence, f = g.
Q4 [20 points]
Solution.
3.4. PROBLEMS 35
Chapter 4
Relations on a Set
4.1 Relations on a Set

Definition 4.1.1. Let ρ be a relation on A, that is ρ ⊆ A × A.
reflexive ∀a ∈ A [a ρ a]
symmetric ∆ ∀a, b ∈ A [a ρ b −→ b ρ a]
ρ is called ←→
antisymmetric ∀a, b ∈ A [a ρ b ∧ b ρ a −→ a = b]
transitive ∀a, b, c ∈ A [a ρ b ∧ b ρ c −→ a ρ c]
reflexive reflexive
symmetric symmetric
Theorem 4.1.1. If ρ is then ρ−1 is .
antisymmetric antisymmetric
transitive transitive
Example 4.1.1.
 
a> 0 1 1 0 0 A tree
>>
>>
0 0 0 1 1 RST
>>  
> 0 0 0 0 0
 
b= c 0 0 0 0 0
===
== 0 0 0 0 0
==

d e
 
1O ^=o 4 0 0 0 0 greater then relation
== 1 0 0 0 RST
==  
= 1 1 0 0
=
2 o 3 1 1 1 0
37
38 CHAPTER 4. RELATIONS ON A SET
α1 α7
 
0 1 0 ∆
•1 i )
•2 i )
•3 aαb ←→ | a − b | = 1
1 0 1 RST
α3 α9
0 1 0
4.2 Observations on the Matrix of a Relation

Let α ⊆ A × A.
• α
 is ordinary −→ No pattern in the matrix.
1 1 0 0
0 0 1 0
 
1 0 0 1
1 0 1 0
'
• •
Use directed graph.
• 
α is reflexive ←→
 The main diagonal is all 1’s.
1 1 0 0
0 1 1 0
 
1 0 1 1
1 0 1 1
a
• ≡ •
Omit loops.
• α is symmetric ←→ The matrix is symmetric.

  
1 1 0 0 1 . . .
 1 0 1 0  1 0 . .
  
 0 1 1 0  0 1 1 .
0 0 0 1 0 0 0 1
'
•g • ≡ • •
Use undirected graph.

4.3. CLOSURE OF RELATIONS 39
• α
 is both reflexive
 and symmetric.

1 0 1 0 . . . .
0 1 1 0 0 . . .
  
1 1 1 1 1 1 . .
0 0 1 1 0 0 1 .
'
•g • ≡ • •
• α is transitive.
•
' •W
( •
4.3 Closure of Relations

Example 4.3.1. Given a relation α0 which is not reflexive, a new relation
α1 can defined which is reflexive and α0 ⊆ α1 . More than that, there are
many reflexive relations αj with α0 ⊆ αj . Note that α1 is the smallest one
satisfying
 this.     
1 1 0 0 1 1 0 0 1 1 1 0
 α1 =  0 1 1 0  α2 =  0 1 1 0 
 0 1 1 0    
α0 =  1 0 1 1 1 0 1 1 1 0 1 1
1 0 1 0 1 0 1 1 1 0 1 1
Definition 4.3.1. Let α be a relation on a set A. Let P be a property such
as reflexivity, symmetry, transitivity. β is called closure of α with respect to
∆
P ←→ β is a relation with property P and α ⊆ β with ∀γ [α ⊆ γ] where
γ is a relation with property P and β ⊆ γ
Remark 4.3.1. Note that β is the smallest relation satisfying this.
4.4 Compatibility Relation

Let γ ⊆ A × A.
Definition 4.4.1 (Compatibility Relation).

∆
A relation γ is a compatibility relation ←→
i. γ is reflexive
ii. γ is symmetric
Remark 4.4.1. Note that equivalence relation has one more property, namely
transitivity.
β is an equivalence relation −→ β is a compatibility relation.
∆
Definition 4.4.2. C ⊆ A is called a compatibility class (compatible) ←→
∀c1 , c2 ∈ C [c1 γ c2 ] where γ is a compatibility relation.
Definition 4.4.3. A compatibility class which is not properly contained in

any other compatibility class is called a maximal compatibility class (maximal
compatible).
Definition 4.4.4. A complete cover , Cγ (A), of A with respect to γ is a

collection of all and only the maximal compatibles induced by γ.
∆
←→ A collection, Cγ (A), of all and only the maximal compatibles induced
by γ on A is called a complete cover of A.
Theorem 4.4.1. If γ is compatibility relation on a finite set A and C is a

′
compatibility class, then there is a maximal compatibility class C such that
′
C⊆C.
Theorem 4.4.2. There is a one-to-one correspondence between γ and Cγ (A).
∆
Theorem 4.4.3. γ is a compatibility relation on A ←→ ∃ relation ρ from
A to some B ∋ γ = ρρ−1 with ∀a ∈ A [∃b ∈ B [a ρ b]]
Example 4.4.1.
Complete cover
Cγ (A) = {A1 , A2 , A3 , A4 , A5 , A6 } is a complete cover.
′
Cγ (A) = {A1 , A2 , A3 , A4 , A5 , A7 } is not since A4 ⊆ A7 .
4.4. COMPATIBILITY RELATION 41
4.4.1 Application of Compatibility Relation

Example 4.4.2 (Minimization of Incompletely Specified Finite State Ma-
I1 I2 I3
a c,0 e,1 -
b c,0 e,- -
chines). S = { a, b, c, d, e }
c b,- c,0 a,-
d b,0 c,- e,-
e - e,0 a,-
∆
Definition 4.4.5. States a and b are compatible, aγb, where γ ⊆ S × S ←→
If no applicable input sequence to both a and b produce conflicting outputs.
γ is a compatibility relation since ∀a, b ∈ S

i. aγa.
ii. aγb −→ bγa.
√
a
√
b c,c e,e
√
c × b,c c,e
√
d b,c c,e b,c c,e ×
√
e × e,e c,e a,a ×
a b c d e
{ a, b } is a compatible.
{ a, b, d } is a maximal compatible.
{ { a, b, d } , { b, c, e } } is a complete cover.
Let A = { a, b, d } , B = { b, c, e }
I1 I2 I3
A B,0 B,1 B,-
B B,0 B,0 A,-
4.5 Equivalence Relation

Definition 4.5.1 (Equivalence Relation).
∆
A relation γ is a equivalence relation ←→
i. γ is reflexive
ii. γ is symmetric
iii. γ is transitive
Theorem 4.5.1. If γ is an equivalence relation −→ γ is also a compatibility
relation.
Definition 4.5.2 (Equivalence Class).
A maximal compatible of γ is called an equivalence class where γ is an
equivalence relation.
Theorem 4.5.2. Let { Ei } be complete cover. ∀E1 , E2 ∈ Cγ (A) [Ei ∩ Ej = ∅]
Theorem 4.5.3. ∀a ∈ A [a belongs to one and only one equivalence class].
Definition 4.5.3 (Partition).
∆
A setSP = { Ai 6= ∅ | Ai ⊆ A } is called a partition of A ←→
i. i Ai = A
ii. Ai ∩ Aj = ∅ if i 6= j.
Each Ai is called a block of P .
∆
P is called the partition of singletons ←→ ∀Ai ∈ P [| Ai | = 1].
The partition of singletons and the partition { A } are called the trivial par-
titions.
Example 4.5.1. Let A = { 1, 2, 3, 4, 5 }. Then sets P1 = { { 1 } , { 2 } , { 3 } , { 4 } , { 5 } },
P2 = { { 1 } , { 2, 3, 4, 5 } }, P3 = { { 1 } , { 2, 4, 5 } , { 3 } }, P4 = { { 1, 2 } , { 3, 5 } , { 4 } },
P5 = { { 1, 2, 3, 4, 5 } } are partitions of A.
Note that P1 and P5 are the trivial partitions.
Theorem 4.5.4. There is an one-to-one corresponding between equivalence
relations on A and partitions on A.
Definition 4.5.4. Dichotomy is a partition with two blocks.
Theorem 4.5.5. γ is an equivalence relation on A ←→ ∃B [∃f : A → B [γ = f f −1]].
P = { A1 , A2 , A3 , A4 }.
4.5. EQUIVALENCE RELATION 43
Example 4.5.2. Let α and β be equivalence relations on A.

α β is an equivalence relation ←→ αβ = βα
Proof.
(⇒ part:) αβ is an equivalence relation −→ αβ is symmetric −→ αβ =
(αβ)−1 = β −1 α−1 = βα.
Since α and β are symmetric.
(⇐: part)
i. ∀a ∈ A [aαa ∧ aβa] −→ aαβa. reflexivity.
ii. ∀a, b ∈ A a(αβ)b −→ a(βα)b −→ ∃d ∈ A [aβd ∧ dαb] −→
dβa ∧ bαd −→ b(αβ)a. symmetry.
iii. Left as an exercise.
4.5.1 Applications of Equivalence Relations

An application of equivalence relations is state reduction of a completely
specified FSM.
Definition 4.5.5. A finite state machine (FSM ) is a system M = [ Q, S, R, α, β ]

where
Q is a finite set of states
S is a finite set of input symbols (input of alphabet, stimulus)
R is a finite set of output symbols( output alphabet, response)
α : Q × S → Q is the state function
β : Q × S → R is the output function
Example 4.5.3 (State Reduction of a Completely Specified Finite State Ma-

chine).
Let FSM is defined as: Q = { a, b, c, d, e, f, g, h } S = { I1 , I2 } R = { 0, 1 }
and α and β are defined in the following table:
α, β I1 I2 Define ≡⊆ Q × Q as follows:
a b, 1 h, 1 a is equivalent to b ←→ a ≡ b
b f, 1 d, 1 ∆
←→ no input sequence can distinguish a from b.
c d, 0 e, 1
d c, 0 f, 1 ≡ is an equivalence relation
e d, 1 c, 1 since ∀a, b, c ∈ S
f c, 1 c, 1 i. a ≡ a
g c, 1 d, 1 ii. a ≡ b −→ b ≡ a
h c, 0 a, 1 iii. a ≡ b, b ≡ c −→ a ≡ c
a b
a
h c
b,f
d,h
b
g d
c f e
c,d complete cover:
e,f { { a } , { b } , { c, d } , { e, f, g } , { h } }
d
b,d d,f
c,h c,d
e
b,c c,f c,d
c,h c,d c,c
f
b,c c,f c,d c,c
d,h d,d c,d c,d
g
c,d c,c
a,e a,f
h
a b c d e f g h
Let A = { a } , B = { b } , C = { c, d } , E = { e, f, g } , H = { h }
4.6. PROBLEMS 45
I1 I2
A B,1 H,1
B E,1 C,1
C C,0 E,1
E C,0 C,1
H C,1 A,1

cially [PY73, Ros07, TZ82, Gal89]. Class of CMPE220 of Fall 2008 did the
initial LaTeX draft of hand written notes.
4.6 Problems
Q5 [20 points]
Let ρ ⊆ A×A, ρ−1 be the inverse relation of ρ, and iA be the identity relation
of A. What kind of relation is ρ if
i) iA ⊆ ρ.
ii) iA ∩ ρ = ∅ .
iii) ρ−1 = ρ.
iv) ρ ∩ ρ−1 ⊆ iA .
v) ρ ∩ ρ−1 = ∅.
vi) ρ = ∪i∈N ρi .
Justify your answers.
Solution.
iA ⊆ ρ reflexive
iA ∩ ρ = ∅ irreflexive
−1
ρ = ρ. symmetric
If , then ρ is .
ρ ∩ ρ−1 ⊆ iA . antisysmmetric
ρ ∩ ρ−1 = ∅. asymmetric
ρ = ∪i∈N ρi . transitive
Justification is left as exercise.
Q6 [20 points]
Solution.
Chapter 5
Partial Ordering, Lattice
5.1 Partial Ordering

Definition 5.1.1. Let ≤ be a relation on A, ≤ ⊆ A × A.
∆
≤ is a Partial Ordering ←→
i. reflexive
ii. antisymmetric
iii. transitive.
∆
a < b ←→ a ≤ b ∧ a 6= b.
Theorem 5.1.1. The inverse relation ≤−1 of a partial ordering ≤ is also a

partial ordering, denoted by ≥.
Theorem 5.1.2. The directed graph of a partial ordering relation contains

no circuits of length greater than 1.
Definition 5.1.2 (Poset).

A partly ordered set (poset), denoted [ A, ≤ ], consists of a set A and a partial
ordering relation ≤ on A.
Definition 5.1.3. Let [ A, ≤ ] be a poset. a, b ∈ A are said to be comparable

∆ ∆
←→ a ≤ b ∨ b ≤ a. a, b ∈ A are incomparable ←→ a, b ∈ A are not
comparable.
Definition 5.1.4 (Linearly ordered set). [ A, ≤ ] is called a linearly ordered

∆
set ←→ ∀a, b ∈ A [a ≤ b ∨ b ≤ a].
47
48 CHAPTER 5. PARTIAL ORDERING, LATTICE
Remark 5.1.1. Note that some elements of a poset are incomparable but
every two elements in a totally ordered set should be comparable.
Example 5.1.1.
@ a ^== ppp7 b
Let A = { a, b, c, d, e, f, g } and
=p
ppp === b ≤ a represented by b → a.
p p
pp == Note that c ≤ a, f ≤ a. There
ppp
cO _? ? dO should be an arc from f to a, too. In
??
??
?? order to simplify the figure this kind
?
e ^> of arcs are omitted.
>>
>>
>>
> a and b are not comparable. So
f g there is no element that is larger
than all the other elements. Similarly
there is no element that is smaller
than all the other elements.
Definition 5.1.5 (Consistent Enumeration).

A consistent enumeration of a finite poset A is a function i : A → N such
that
∀ap , aq ∈ A [ap ≤ aq −→ i(ap ) ≤ i(aq )].
Theorem 5.1.3. Every finite poset admits of a consistent enumeration.
Example 5.1.2.
{a, b}
A = { a, b } ? O _???
??
2A = { ∅, { a } , { b } , { a, b } }
[ P (A), ⊆ ] is a poset. {a} {b}
_?? ?
??
??

∅
5.2 Hasse Diagram

Definition 5.2.1. Let [ A, ≤ ] be a poset and a, b ∈ A with a 6= b. a
∆
is an immediate predecessor of b, denoted by a ≺ b, ←→ a < b and
6 ∃c ∈ A [a < c < b].
5.2. HASSE DIAGRAM 49
∆
b is an immediate successor of a, denoted by b ≻ a, ←→ a < b and
6 ∃c ∈ A [a < c < b].
Remark 5.2.1.
i. As convention an upper element is larger than a lower element.

ii. Immediate predecessor relation is
• not reflexive
• not symmetric
• not transitive
iii. Given an immediate predecessor relation one can obtain the correspond-
ing partial ordering.
iv. ≤ covers ≺.
v. Immediate relation simplifies the graph of partial ordering relation.
Definition 5.2.2. The graph of ≺ is called Hasse Diagram.
Example 5.2.1. Reflexive+Symmetric+Transitive

? aO _?? ? aO _? ? a _?
?? ??? ???
?? ?? ??

1 c _?? ?b c _?? ?b c _?? ?b
?? ?? ??
? ? ?
1d d d
RST RST RST
Example 5.2.2.
∆
a | b ←→ ∃c ∈ Z [b = ca]
∆
Let A = { a ∈ N | a | 100 } and define a relation ≤ on A as a ≤ b ←→ a | b.

4 100
=z E M O Q aDDj
zz DD
zz DD
z DD
zz
20 50
~? OP R aDDD z= L NO aBBB
~~~ DD z zz BB
~~ DD zz BB
~~ D zz B
4R _@@ 10
= \ aDD 25
@@ zz DD ||= L
@@ zz DD |
@@ zzzz DD ||
z D |||
2 aDD z= 5
DD zz
DD z
DD zz
D zzz
100D
zz DD
z z DD
z DD
Graph of ≤ zz z D
20 DD 50 BB
~~~ DD z zz BB
~~ DDD zz BB
~~ D zz BB
~ z
4 @@ 10 DD 25
@@ zzz DD |||
@@ z DD ||
@@ zzzz DD
D |||
z
2 DD z5
DD zz
DD z
DD zz
D zzz
1
Graph of ≺
• not reflexive
• not symmetric
• not transitive
Hasse diagram.
5.3 Lattice
Definition 5.3.1. Let [ A, ≤ ] be a poset.
maximal ∆ 6 ∃a ∈ A [m < a]
m ∈ A is ←→ .
minimal 6 ∃a ∈ A [a < m]
Definition 5.3.2. Let [ A, ≤ ] be a poset and B ⊆ A.

∆
s ∈ A is called a supremum of set B ←→
i. ∀b ∈ B b ≤ s.
ii. 6 ∃a ∈ A ∀b ∈ B b ≤ a −→ a ≤ s.
Question 5.3.1. Define infimum of B.

Remark 5.3.1. Consider intervals X = [0, 1] and Y = (0, 1) of the real num-
bers R. Then 0 and 1 are minimal and maximal of X, respectively. Since
0∈/ Y , 0 cannot be a minimal of Y . 0 is a infimum of Y . 1 is a supremum of
Y . Since R is totally ordered, there is no other infimum than 0. So we can
say that 0 is the infimum of Y . Similarly 1 is the supremum of Y .
5.3. LATTICE 51
Definition 5.3.3. Let [ A, ≤ ] be a poset and I, O ∈ A.

I greatest ∆ ∀a ∈ A [a ≤ I]
is the ←→ . I and O are called universal
O least ∀a ∈ A [O ≤ a]
upper bound and universal lower bound .
Remark 5.3.2.
• From now on all posets are finite.
• If poset is finite, there are minimal and maximal elements but there may
not be universal upper and lower bounds.
Example 5.3.1.
a maximals: a, b, h.
b
minimals: d,g,j,k.
greatest: none.

c> least: none.
>>
>>
>>
>
d e f

g h

i

j k
Definition 5.3.4. Let [ A, ≤ ] be a poset and a, b ∈ A.
A least upper bound (lub) of a and b is c ∈ A
i. a ≤ c and b ≤ c
ii. 6 ∃x ∈ A [a < x ∧ b < x ∧ x < c]
Remark 5.3.3. Let a, b ∈ A.
i. Least upper bound of a and b may not exist.
ii. There may be more than one lub.
iii. It may be unique. If lub of a and b is unique, then it is denoted as a + b.
Theorem 5.3.1. ∀a, b ∈ A [ lub exists] −→ [ A, ≤ ] has the universal upper
bound I.
Example 5.3.2.
a > pp b • There is no universal upper bound.

p>p>p>p • a and b are maximal elements.
p >>
ppppp >> • a and b are lub of c and d.
pp
c> d • e and f are lower bounds of c and
>>
>> d.
>>
>
e> • e is unique glb of c and d.
>>
>> • f is the universal lower bound O.
>>
>
f
Definition 5.3.5. A greatest lower bound (glb) of a and b is l ∈ A where

i. l ≤ a and l ≤ b
ii. 6 ∃x ∈ A [l < x < a ∧ l < x < b]
Remark 5.3.4. If glb of a and b is unique, then it is denoted as a · b

Remark 5.3.5 (Duality Principle).
Let U be the Hasse diagram of poset [ A, ≤ ]. Upside down version of U,call
it D is the Hasse diagram of [ A, ≥ ].
Any property for U holds in D if the following substitutions are made:

• +↔·
• lub ↔ glb
• ≤↔≥
• I ↔O
Definition 5.3.6 (Lattice). A lattice is a poset [ A, ≤ ] such that any two

elements have a unique lub and glb. It is denoted as [ A, +, · ].
Example 5.3.3.
Division relation and divisors of 12 makes a lattice.
12 @
~~
~~ @@
@@ A = { a ∈ N | a | 12 }
~ @@
~~
~ @ = { 1, 2, 3, 6, 4, h12 } i
4 @@ 6= ∆
and ∀a, b ∈ A a ∼ b ←→ a | b
@@ ~~ ==
@@ ~~~ ==
@@ ~ ==
~~
2 @@ 3
@@
@@
@@

1
5.4. APPLICATIONS 53
Theorem 5.3.2. Let [ A, +, · ] be a lattice and a, b, c ∈ A.

i. a + a = a idempotency
ii. a + b = b + a commutativity
iii. (a + b) + c = a + (b + c) associativity
iv. a + (a · b) = a absorption
v. a + b = b ←→ a · b = a ←→ a ≤ b consistency
5.4 Applications
• PageRank of Google.
• Measure the similarity of two orderings (ranking) on a set, i.e. Pearson

correlation.

cially [PY73, Ros07, Gal89]. Class of CMPE220 of Fall 2008 did the initial
LaTeX draft of hand written notes.
5.5 Problems
Q7 [20 points]
∆
Definition 5.5.1. Let f, g : Z+ → R. g dominates f ←→ ∃m ∈ R+ and
∃k ∈ Z+ such that |f (n)| ≤ m |g(n)| for all n ∈ Z+ where n ≥ k
Definition 5.5.2. For f : Z+ → R, f is big Theta of g, denoted by f ∈ Θ(g),

∆
←→ there exist constants m1 , m2 ∈ R+ and k ∈ Z+ such that m1 |g(n)| ≤
|f (n)| ≤ m2 |g(n)|, for all n ∈ Z+ , where n ≥ k.
+
a) Let RZ be the set of all functions from Z+ to R.
+
Define the relation β on RZ as
∆ +
f βg ←→ f ∈ Θ(g) for f, g ∈ RZ .
+
Prove that β is an equivalence relation on RZ .
+
b) Let [f ]β represent the equivalence class of f ∈ RZ for the relation β.
Let E be the set of equivalence classes induced by β. Define the relation
α on E by
+ ∆
[f ]β α [g]β , for f, g ∈ RZ , ←→ f is dominated by g.
Show that α is a partial order.

+
Use shorthand notations F for RZ and [f ] for [f ]β .
Solution.
a) We need to show that β is reflexive, symmetric and transitive.

i. For each f ∈ F , |f (n)| ≤ 1 |f (n)| for all n ≥ 1. So f βf , and β is
reflexive.
ii. For f, g ∈ F ,
f βg ⇒ f ∈ Θ(g)
⇒ mf |g(n)| ≤ |f (n)| ≤ Mf |g(n)| for n ≥ k where mf , Mf ∈ R+ and k ∈ Z+
⇒ |g(n)| ≤ 1/mf |f (n)| and 1/Mf |f (n)| ≤ |g(n)|
⇒ mg |f (n)| ≤ |g(n)| ≤ Mg |f (n)| for n ≥ k with mg = 1/Mf , Mg = 1/mf ∈ R
⇒ g ∈ Θ(f )
⇒ gβf.
So β is symmetric.
iii. Let f, g, h ∈ F with f βg, gβh. Then, f ∈ Θ(g) and g ∈ Θ(h)
⇒ for all n ∈ Z+ , there exist constants mf , Mf , mg , Mg ∈ R+ and
kf , kg ∈ Z+ such that
mf |g(n)| ≤ |f (n)| ≤ Mf |g(n)| for n ≥ kf , and
mg |h(n)| ≤ |g(n)| ≤ Mg |h(n)| for n ≥ kg . Then for n ≥ max{kf , kg },
mf mg |h(n)| ≤ mf |g(n)| ≤ |f (n)| and
|f (n)| ≤ Mf |g(n)| ≤ Mf Mg |h(n)|. Hence for n ≥ k,
m |h(n)| ≤ |f (n)| ≤ M |h(n)|
where m = mf mg , M = Mf Mg ∈ R+ and k = max{kf , kg } ∈ Z+ .
So f βh, that is, β transitive.
b) We need to show that α is reflexive, antisymmetric and transitive. Let
+
f, g, h ∈ RZ .
5.5. PROBLEMS 55
i. f is dominated by f since |f (n)| ≤ |f (n)| for n ≥ 1. So [f ]α[f ],

hence α is reflexive.
ii. Suppose [f ]α[g] and [g]α[f ]. Then
|f (n)| ≤ mf |g(n)| for n ≥ kf for some mf and kf . Similarly,
|g(n)| ≤ mg |f (n)| for n ≥ kg for some mg and kg . Then for n ≥
max{kf , kg }
1/mf |f (n)| ≤ |g(n)| ≤ mg |f (n)|. That is, g(n) ∈ Θ(f (n)). That
means f and g are in the same equivalence class of β, i.e. [f ] = [g].
So α is antisymmetric.
iii. Suppose [f ]α[g] and [g]α[h]. Then
|f (n)| ≤ mf |g(n)| for n ≥ kf for some mf and kf , and
|g(n)| ≤ mg |h(n)| for n ≥ kg for some mg and kg . Then for n ≥
max{kf , kg }
|f (n)| ≤ mf mg |h(n)|. Therefore [f ]α[h]. Hence α is transitive.
Q8 [20 points]
Let F denote the set of all partial orderings on a set A. Define a relation ≤
∆
on F such that for α, β ∈ F , α ≤ β ←→ ∀a, b ∈ A [aαb → aβb]. Show that
≤ is a partial ordering on F .
Solution.
i. ≤ is reflexive. Since ∀α ∈ F ∀a, b ∈ A [aαb → aαb] ⇒ α ≤ α.

ii. ≤ is antisymmetric. Suppose for α, β ∈ F , α ≤ β and β ≤ α. Then
α ≤ β ⇒ ∀a, b ∈ A [aαb → aβb] and
β ≤ α ⇒ ∀c, d ∈ A [cβd → cαd]. That is, ∀a, b ∈ A [aαb ↔ aβb]. Hence
α = β.
iii. ≤ is transitive. Suppose for α, β, γ ∈ F , α ≤ β and β ≤ γ.
α ≤ β ⇒ ∀a, b ∈ A [aαb → aβb]. Similarly,
β ≤ γ ⇒ ∀a, b ∈ A [aβb → aγb]. Hence
∀a, b ∈ A [aαb → aγb]. That is, α ≤ β.
Hence ≤ on F is a partial ordering.
Part III
Algebra
57
Chapter 6
Algebraic Structures
6.1 Motivation
Suppose there are two research labs A and B. Lab A investigates gravitation.
They do test on two masses m1 and m2 . They discover that the attraction
force Fg is given as
m1 m2
Fg = cg 2
r
where r is the distance between them and cg is a constant.
Lab B investigates electrical charges. The force observed is attractive if
the charges are opposite sign, repulsive otherwise. Yet, they measure that
the force Fe between two spheres charged as q1 and q2 is given as
q1 q2
Fe = ce
r2
where r is the distance between them and ce is a constant.
Yet somewhere else, a theoretical physicist works on hypothetical forces.
She assumes that the force between two bodies is proportional to some prop-
erty of the body denoted by b. She also assumes that the force is inversely
proportional to the square of the distance of the bodies. So she summarize
her assumptions as
b1 b2
Fx = cx 2 .
r
She did continue in her investigations. She figure out many properties of this
hypothetical system.
59
60 CHAPTER 6. ALGEBRAIC STRUCTURES
Then in a conference somebody from Lab A happens to listen her presen-

tation with amazement. This lady did all the work for them. All they have
to do is to apply her findings with changing cx with their constant cg .
Mathematics is an abstraction. Yet, algebraic structures is just this kind
of abstraction. It could be hard to find similarities between polynomials,
integers and N × N square matrices. But actually they have very similar
properties which we will be call ring in this chapter.
Example 6.1.1. Part a. Part b.

Let’s solve a + x = b for x where Let’s solve A + X = B for X where
a, b, x ∈ Z. A, B, X are N × N real matrices.
a+x = b
A+X = B
(−a) + (a + x) = (−a) + b
(−A) + (A + X) = (−A) + B
((−a) + a) + x = (−a) + b
((−A) + A) + X = (−A) + B
0+x = (−a) + b
0+X = (−A) + B
x = (−a) + b.
X = (−A) + B.
Question 6.1.1. Compare Part a and Part b of Example 6.1.1. What are the
differences and similarities?
Question 6.1.2. Solve A + X = B for X if
i. A, B, X are N × N rational matrices.
ii. A, B, X are N × N integer matrices.
iii. A, B, X are N × N natural number matrices.
iv. A, B, X are polynomials with complex coefficients in y.
v. A, B, X are polynomials with real coefficients in y.
vi. A, B, X are polynomials with rational coefficients in y.
vii. A, B, X are polynomials with integer coefficients in y.
viii. A, B, X ∈ C.
ix. A, B, X ∈ R.
x. A, B, X ∈ Q.
xi. A, B, X ∈ Z.
xii. A, B, X ∈ N.
xiii. A, B, X ∈ R r Q.
xiv. A, B, X are 2D vectors.
xv. A, B, X are 3D vectors.
6.2. ALGEBRAIC STRUCTURES 61
Question 6.1.3.
i. Some of the systems given in Question 6.1.2 have no solution. Can you
find a pattern when there is a solution. What properties of what do you
need in order to solve equation A + X = B?
ii. Reconsider Question 6.1.2 when addition is replaced by multiplication,
that is, A × X = B. Note that multiplication may not be defined in
some concepts.
6.2 Algebraic Structures

Consider the equation A+X = B. In order to interpret the equation correctly
we need to know couple of things: What is “+” represents? What are A, B
and X? If A, B and X are of the same “type”, what set do they member
of? The only concept that does not need further explanation is the equality
“=”.
Question 6.2.1. It should be an equivalence relation but do we really know
what actually “=” means? We know that there are more than one equivalence
relations can be defined on a set. So which one is this? Recall that equivalence
relations 4.5.1 is covered in Chapter 4.
6.2.1 Binary Operations

Remark 6.2.1. At this point, you may want to refresh the definition of func-
tion 3.3.2.
Definition 6.2.1. A binary operation ⋆ on set A is a function ⋆ : A×A → A.

A binary operation is represented by a⋆b instead of the traditional functional
notation ⋆((a, b)) where a, b ∈ A.
Question 6.2.2. What is the difference between ⋆((a, b)) and ⋆(a, b)?
Definition 6.2.2. Let A = {a1 , · · · , an }. An operation table represents the

binary operation ⋆ in a table form where ai ⋆ aj = ak .
⋆ a1 · · · ai · · · aj · · · an
a1 . · · · . ··· . ··· .
.. .. .. .. ..
. . . . .
ai . · · · . · · · ak · · · .
.. .. .. .. ..
. . . . .
aj . · · · am · · · . ··· .
.. .. .. .. ..
. . . . .
an . ··· . ··· . ··· .
Remark 6.2.2. This representation is valid if the elements of A can be made

into a list. Some sets have, some cannot have such a list. Making a list of
elements is an importing concept which we will be looking at in Chapter 10
when we discuss finiteness and type of infinities in more detail. The elements
of a finite set can always be made a list. If the set is not finite, there are two
different cases. If the set is countable infinite such as N, there is a natural list
that can be used for operational table. Note that in this case the operational
table would be an infinite table. If the set is uncountable infinite such as
R, then the elements cannot be put in a list. Concepts such as finiteness,
infinity, countable infinity, uncountable infinity will be covered in Chapter 10.
Remark 6.2.3. The order of operation is important. ai ⋆aj = ak 6= am = aj ⋆ai .
∆
Definition 6.2.3. A binary operation ⋆ on A is called associative ←→
∀a, b, c ∈ A [(a ⋆ b) ⋆ c = a ⋆ (b ⋆ c)]
∆
Definition 6.2.4. A binary operation ⋆ on A is called commutative ←→
∀a, b ∈ A [a ⋆ b = b ⋆ a].
6.2.2 Algebraic Structure

Definition 6.2.5. A set A and binary operations f1 , f2 , · · · , fn defined on
A together is called an algebraic structure, denoted by [ A, f1 , f2 , · · · , fn ],
where n ∈ Z+ and A 6= ∅.
Example 6.2.1. Let V be a vector space. Addition of two vectors is repre-

sented as v1 + v2 for v1 , v2 ∈ V . Then [V, +] is an algebraic structure. Note
that + is both associative and commutative.
6.2. ALGEBRAIC STRUCTURES 63
Question 6.2.3. In general, multiplication of two vectors is not defined. Only

in 3D, cross multiplication of two vectors is defined, denoted as v1 × v2 . Let
V be 3D vector space and v1 , v2 , v3 ∈ V .
i. Is × associative?
ii. Is × commutative?
iii. Is it the case that v1 × (v2 + v3 ) = (v1 × v2 ) + (v1 × v3 )?
Question 6.2.4. In vector spaces, scalar multiplication is defined. How do

you put that into algebraic structure notation?
6.2.3 Sub-Algebraic Structures
Two similar but not exactly the same systems can be investigated. A special
case of similar structures is the case when one set if a subset another.
Suppose B ⊆ A and a binary operation ⋆ on A is defined. Since a binary
operation is a function from A × A, and since B × B ⊆ A × A, we can try to
restrict it to B.
One needs to be very careful at this point. The danger can be better seen
in simpler case: What we have is a function f : A → A. We have B ⊆ A
and we want to restrict function to B. It is perfectly possible that for some
elements of B the image under the function may not be in B at all, that is,
f (b) ∈ A r B for some b ∈ B. Whenever that happens, the function can not
be a binary operation. This concern is called closeness.
Example 6.2.2 (Subspace). Think about vectors in X − Y plane. This makes

a 2D vector space. Vectors in X − Y − Z is a vector space in 3D. Let’s
denote 2D and 3D vector spaces by R2 and R3 , respectively. Define addition
of two vectors in the usual way in both R2 and R3 . Then we obtained two
independent algebraic structures [ R2 , + ] and [ R3 , + ].
Are they really independent? Actually [ R2 , + ] is a special case of [ R3 , + ].
Any vector v = [x y]⊤ ∈ R2 can be mapped to a unique vector, denoted by
ṽ = [x y 0]⊤ ∈ R3 . We say that R2 is a subspace of R3 .
Note that for all v1 , v2 ∈ R2 we have v = v1 + v2 ∈ R2 . If we map
v1 , v2 into R3 , we obtain v˜1 , v˜2 ∈ R3 . This time use addition in R3 to obtain
u = v˜1 + v˜2 ∈ R3 . Is it the case that ṽ = u? This can be visualized as: ã
-
7 vK 8 ṽ =
K u
v1 , v˜1
v2 , v˜2
Example 6.2.3 (Addition on Reals and Rationals). Consider the set of real
numbers, R. With ordinary addition, + : R×R → R , it makes the algebraic
system, [ R, + ]. Now, consider the set of rational numbers. Depending how
you look at it, a rational number is a real number or not. Here we assume
that a rational number is also a real number. Hence Q ⊆ R. The addition
+ in reals can be restricted to Q. Let +Q : Q × Q → Q be the restriction of
addition in reals to rationals.
Fortunately addition of any two rational numbers is again a rational num-
ber. So we can safely restrict + in R to Q and obtain binary operation +Q
in Q.
Example 6.2.4 (Multiplication on Reals and Negative Integers). Multiplica-
tion on real numbers is a binary operation.
×R : R × R → R.
On the other hand restriction of it to negative integers
× : Z− × Z− → Z+
is not a function its domain is not Z− any more.

Example 6.2.5 (Multiplication in Irrational Numbers). An irrational number
is a real number that is not rational. Using this definition the set of irrational
numbers can be represented as A = R r Q. Note that we use A since there
is no agreed symbol for the set of irrational numbers as we have R for reals.
Clearly A ⊆ R. Then try to restrict multiplication × in reals to irra-
tionals. The restricted function ×A would be
×A : A × A → R.
Note that it is not the case that
×A : A × A → A
6.3. WITH ONE BINARY OPERATION 65
√ √ √
since 2 ∈ A but 2 ×A 2 = 2 6∈ A. That is, the restriction of multiplica-
tion in the set of reals to the set of irrationals is not a binary operation in
irrationals. In other words, the restriction is not close.
6.3 Algebraic Structures with One Binary Op-

eration
6.3.1 Semigroup
Definition 6.3.1. An algebraic structure G = [ A, ⋆ ] is called semigroup
∆
←→
i. ⋆ is associative.
6.3.2 Monoid
Definition 6.3.2. Let [ A, ⋆ ] be an algebraic structure.
ℓ left-identity ∀a ∈ A [ℓ ⋆ a = a]
∆
r ∈ A is called right-identity ←→ ∀a ∈ A [a ⋆ r = a]
e (two-sided) identity ∀a ∈ A [e ⋆ a = a ⋆ e = a]
.
Remark 6.3.1.
i. There may exist none, one or both of ℓ or r.

ii. There is no need to be semigroup in order to have left, right or two-sided
identities.
Theorem 6.3.1. If ℓ and r are left and right identities of a semigroup G,
then ℓ = r.
Theorem 6.3.2. If two-sided identity exists, then it is unique.
Question 6.3.1. The theorem says that there could not be two different iden-
tities. Is it possible that there are two different left-identities ℓ1 and ℓ2 ? The
same question for right-identities?
∆
Definition 6.3.3. An algebraic structure M = [ A, ⋆ ] is called monoid ←→
i. M is a semigroup.
ii. M has the identity, denoted by e.
Question 6.3.2. Consider a row of the operation table of a monoid. What

can be said about the number of identities?
Definition 6.3.4 (Subsemigroup, Submonoid).

semigroups
Let A = [ A, ⋆ ] and B = [ B, ◦ ] be .
monoids
subsemigroup ∆
B is said to be of A ←→
submonoid
i. B ⊆ A
ii. ◦ is the restriction of ⋆ to B.
Remark 6.3.2. This is a typical definition of sub-structures. An equivalent

but more compact definition would be as follows:
semigroup subsemigroup
A B = [ B, ◦ ] is said to be a of
monoid submonoid
semigroup ∆
another A = [ A, ⋆ ] ←→
monoid
i. B ⊆ A
ii. ◦ is the restriction of ⋆ to B.
Example 6.3.1. Let A = { 1, 2, 3, 4 } and B = { 3, 4 }. Define binary operators
as follows.
∗ 1 2 3 4
1 . 1 . . ◦ 3 4
2 1 2 3 4 3 3 4
3 . 3 3 4 4 4 4
4 . 3 4 4
Then 2 and 3 are identities of ∗ and ◦ in sets A and B, respectively. Note
that ◦ is the restriction of ∗ to B. Note also that 3 is not an identity in A.
Question 6.3.3. Let B = [B, ◦] be a submonoid of A = [A, ∗] with identities
eB and eA , respectively. Is it possible that eA 6= eB .
6.3.3 Groups
Definition 6.3.5 (Inverse).
Let G = [ A, ⋆ ] be a monoid with the identity e. Let a ∈ A.
ℓa left inverse ℓa ⋆ a = e
∆
ra ∈ A is called right inverse of a ←→ a ⋆ ra = e .
ba (two-sided) inverse ba ⋆ a = a ⋆ ba = e
6.3. WITH ONE BINARY OPERATION 67
Table 6.1: default
* 1 2 3 4
1 . 1 . .
2 1 2 3 4
3 . 3 3 4
4 . 3 4 4
Theorem 6.3.3. If ℓ and r are left and right inverses of a, respectively, then
ℓ = r in a monoid.
Question 6.3.4. Is it possible that a has two different left-inverses, ℓ1 and ℓ2 ?
Notation 6.3.1. The inverse of a is represented by a−1 .
Definition 6.3.6 (Group).
∆
An algebraic structure G = [ A, ⋆ ] is called group ←→
i. G is a monoid.
ii. ∀a ∈ A, there is a unique inverse of a, denoted by a−1 .
If A is finite, G is said to be a finite group and | A | is called the order of G.
Theorem 6.3.4. Let G = [ A, ⋆ ] be a group and a, b ∈ A. a ⋆ x = b and
y ⋆ a = b have unique solutions, namely, x = a−1 ⋆ b and y = b ⋆ a−1 .
Theorem 6.3.5 (Cancellation). In a group,
i. a ⋆ b = a ⋆ c ⇒ b = c.
ii. b ⋆ a = c ⋆ a ⇒ b = c.
Remark 6.3.3. We know these two theorems in numbers since primary school.
What the theorems say is that they are valid if the system satisfy the group
axioms.
Notation 6.3.2. a ⋆ b is represented by ab when the binary operation ⋆ is clear
in the context.
Theorem 6.3.6 (Cayley). Every finite group can be represented by a group
of permutations.
Definition 6.3.7 (Permutation). Let A be a finite set. A bijection γ : A →
A is called a permutation.
Example 6.3.2 (Group of Permutations).
∆
Let A = { x1 , x2 , x3 } be a set with Let S3 = { a, b, c, d, e, f } be the
3 elements. set of permutations on A.
Define a binary operation ⊚ on S3 as
∆
the composition, that is, α ⊚ β =
β ◦ α where α, β ∈ S3 . Hence x ∈ A
is mapped to β(α(x)).
b ⊚ c = (132) ⊚ (213)
A permutation onA can be rep- = (213) ◦ (132)

x1 x2 x3 = (213)((132))
resented as: = (213).
x2 x1 x3 = (231) = d
1 / 1= 1
== @
=
==
=
2 == @2 2
==
==
=
3 3 / 3
There are 3! = 6 permutations: ⊚ a b c d e f
a = (123) a a b c d e f
b = (132) b b ? d ? ? ?
c = (213) c c ? ? ? ? ?
d = (231) d d ? ? ? ? ?
e = (312) e e ? ? ? ? ?
f = (321). f f ? ? ? ? ?
Definition 6.3.8. S3 = [ S3 , ⊚ ] is called the symmetric group of order 3, S3 .
Symmetic groups Sn can be extended for any n ∈ N.
Remark 6.3.4. | Sn | = n!
Definition 6.3.9. Let G = [ A, ⋆ ] and H = [ B, ◦ ] be two groups. Group G
∆
is said to be a subgroup of group H ←→
i. A ⊆ B.
ii. ⋆ is the restriction of ◦ to A.
Remark 6.3.5.
6.4. WITH TWO BINARY OPERATIONS 69
i. G is a subgroup of itself.
ii. { e } is a subgroup of G.
Definition 6.3.10. Subgroups G and { e } are called the trivial subgroups.
Any subgroup that is not trivial is called proper subgroup.
Theorem 6.3.7. T 6= ∅ is a subgroup of G
←→ ∀a, b ∈ T [ab−1 ∈ T ].
Theorem 6.3.8. Let H be a subgroup of G. Then the order of H divides
the order of G.
Definition 6.3.11. A group with commutative binary operation is called
abelian group.
6.4 Algebraic Structures with two Binary Op-

erations
6.4.1 Ring
Definition 6.4.1 (Ring). An algebraic structure R = [ A, ⋆, ◦ ] is called ring
∆
←→
i. [ A, ⋆ ] is an abelian group.
ii. [ A, ◦ ] is a semigroup.
iii. ∀a, b, c ∈ A
a ◦ (b ⋆ c) = (a ◦ b) ⋆ (a ◦ c)
(b ⋆ c) ◦ a = (b ◦ a) ⋆ (c ◦ a)
Notation 6.4.1. Usual notation for a ring is R = [A, +, ·]
Use ab for a ◦ b.
0 is the additive identity.
−a is the additive inverse of a.
1 is the multiplicative identity.
a−1 is the multiplicative inverse of a.
Remark 6.4.1. Note that since [ A, + ] is a group, the additive identity and
additive inverse should be there. On the other hand, [ A, · ] is simple a semi-
group. Therefore the multiplicative identity may not exist. Even if the
multiplicative identity exists, multiplicative inverse may not.
Definition 6.4.2 (Commutative Ring). A ring with commutative multipli-

cation is called commutative ring.
Theorem 6.4.1. Let R = [A, ⋆, ◦] be a ring. ∀a, b ∈ A

i. 0 ◦ a = a ◦ 0 = 0
ii. (−a) ◦ b = a ◦ (−b) = −(a ◦ b)
iii. (−a) ◦ (−b) = a ◦ b
Remark 6.4.2. We knew these properties of numbers since primary school.

The theorem says couple of things: Now, you are in a position to prove them.
They are valid not in numbers only but in any ring.
Example 6.4.1.
i. [ N, +, · ] is not a ring, since there is no additive inverse.
ii. [ Z, +, · ] is a ring. So do [ Q, +, · ], [ R, +, · ] and [ C, +, · ].
iii. Consider the set of polynomials with real coefficients in x, denoted by
R[x]. With regular addition and multiplication of polynomials, [ R[x], +, · ]
is a ring, called the ring of polynomials.
Question 6.4.1.
i. What is the additive identity of group [ R[x], + ]?
ii. What is the additive inverse of 5x2 + 3x + 7 in [ R[x], + ]?
iii. Is there a multiplicative identity in semigroup [ R[x], · ]?
iv. What is the multiplicative inverse of 5x2 + 3x + 7 in [ R[x], +, · ]?
Question 6.4.2. Consider the set of N × M matrices with real entries, de-
noted by RN ×M . With regular addition and multiplication of matrices,
[ RN ×M , +, · ] is not a ring. Why? Can you make it a ring by additional
constrains?
Definition 6.4.3 (Subring). A ring A = [ A, ⊕, ⊗ ] is said to be a subring

∆
of another ring B = [ B, +, × ] ←→
i. A ⊆ B.
ii. ⊕ is the restriction of + to A.
iii. ⊗ is the restriction of × to A.
Theorem 6.4.2. T is a subring of R

←→ ∀a, b ∈ T [(a − b), ab ∈ T ].
Definition 6.4.4. Let T be a subring of ring R. If ∀r ∈ T [∀a ∈ R [ar, ra ∈ T ]],

then T is called an ideal of R.
6.4. WITH TWO BINARY OPERATIONS 71
6.4.2 Field
Definition 6.4.5. A field , F = [ A, +, · ], is a ring such that [ A r { 0 } , · ] is
an abelian group. If A is finite, F is called finite field (Galois field ).
Remark 6.4.3. Note that in 0 in A r { 0 } is the additive inverse of group
[ A, + ].
∆
Definition 6.4.6. Let Zn = { 0, · · · , n − 1 } where n ∈ N, n ≥ 2,
∆
a ⊕ b = remainder of a+bn
,
∆ ab
a ⊙ b = remainder of n
.
Theorem 6.4.3. [ Zp , ⊕, ⊙ ] is a field if p is a prime number.

Remark 6.4.4. Take n = 2. Since 2 is prime, [ Z2 , ⊕, ⊙ ] is a field.
Actually, this is the field that Computer Engineering/Science is based on:
Z2 = { 0, 1 } where 0 and 1 are integers. Another interpretation of 0 and 1
would be “false” and “true”, respectively. Then, one can interpret the binary
operations ⊕ and ⊙ as logical functions f : B × B → B and g : B × B → B
where B = { 0, 1 } but this time in the logical meaning.
Question 6.4.3. What logical functions do ⊕ and ⊙ correspond? Can you
express then in terms of ∧ , ∨ and ¬?
Example 6.4.2.
i. [ Z, +, · ] is not a field, since there is no multiplicative inverse.
ii. [ Q, +, · ] is a field. So do [ R, +, · ] and [ C, +, · ].
Question 6.4.4. [ R[x], +, · ] is not a field, since no multiplicative inverse of
x + 1 ∈ R[x] r { 0 } exists. What is 0 in this context? Can you extent it into
a field?
6.4.3 Lattice
Lattice has two definitions: poset-wise and algebraic.
Definition 6.4.7. A (algebraic) lattice, L = [ A, ⊓, ⊔ ] is a nonempty set L
with binary operations ⊓, ⊔, called meet and join, if
i) x⊓y =y⊓x x⊔y =y⊔x
ii) x ⊓ (y ⊓ z) = (x ⊓ y) ⊓ z x ⊔ (y ⊔ z) = (x ⊔ y) ⊔ z
iii) x ⊓ (x ⊔ y) = x x ⊔ (x ⊓ y) = x
Remark 6.4.5. Let L = [L, ⊓, ⊔] and [L, +, ·] be lattices algebraic and poset
sense, respectively. Then a ⊓ b = a + b and a ⊔ b = a · b.
6.4.4 Vector Spaces

Definition 6.4.8. Let V = [V, +] be an additive abelian group. Let F be a
field. Let · : F × V → V be a function. The group V is then called a vector
space over the field F
∆
←→ For a, b ∈ F , v, u ∈ V , the following conditions are satisfied:
i. a · (v + u) = a · v + a · u
ii. (a + b) · v = a · v + b · v
iii. a · (b · v) = (ab) · v
iv. 1 · v = v
where 1 is the multiplicative identity of F . Elements of V and F are called
vectors and scalars, respectively. The function · is called scalar multiplica-
tion.
Remark 6.4.6. Note that vector spaces are not algebraic structures.
Example 6.4.3. Let Q2×2 be the set of 2 × 2 matrices over rational numbers.
Define the product of a rational number by a 2 × 2 matrix as a 2 × 2 matrix
obtained by multiplying each of the entries by the rational number, i.e. For
a ∈ Q and M ∈ Q2×2 , [a · M]ij = a[Mij ] where [M]ij is the i,j-th entry of the
matrix. Then Q2×2 is a vector space over Q.
Example 6.4.4. Let F [x] be the set of all polynomials in x with coefficients
in F . Multiplication of a polynomial by a scalar is defined by multiplying
each coefficient with that scalar. Then F [x] is a vector space over F .
Question 6.4.5. Prove that 0 · v = v.
6.5. SUMMARY 73
6.5 Summary
Single Binary Operation, [ A, ⊕ ] Two Binary Operations,
• Binary operation [ A, ⊕, ⊗ ]
• Semigroup
• Ring R = [ A, ⊕, ⊗ ]
i. associativity
i. [ A, ⊕ ] is an abelian group
• Monoid ii. [A, ⊗] is a semigroup
i. semigroup iii. ⊗ right and left distributes
ii. identity over ⊕
• Group
i. monoid • Field F = [ A, ⊕, ⊗ ]
ii. inverse i. [ A, ⊕, ⊗ ] is a ring
ii. [ A \ { 0 } , ⊗ ] is an abelian
• Abelian Group group
i. group
ii. commutativity
• Lattice L = [ A, ⊕, ⊗ ]

cially [PY73, LP98, Ros07, Gal89].
6.6 Problems
Q9 [20 points]
Prove the following theorem.
Theorem 6.6.1. Let G be a group and a1 , a2 , . . . , an ∈ G. Then (a1 a2 · · · an )−1 =

−1 −1
a−1
n an−1 · · · a1 .
Solution.
Use induction on n.
Induction Base. For n = 1, (a)−1 = a−1 .
Figure 6.1: Note that an operation can be of any combinations of associativ-

ity, commutativity and identity.
6.6. PROBLEMS 75
−1 −1
Induction Hypotesis. Assume that (a1 a2 · · · an )−1 = a−1
n an−1 · · · a1 for n.
[a1 a2 · · · an an+1 ][a−1 −1 −1 −1 −1 −1 −1 −1

n+1 an an−1 · · · a1 ] = [a1 a2 · · · an ][an+1 an+1 ][an an−1 · · · a1 ]
= [a1 a2 · · · an ][e][a−1 −1 −1 −1
n an−1 · · · a1 ] since an+1 an+1 = e
= [a1 a2 · · · an ][a−1 −1 −1
n an−1 · · · a1 ]
= e by the induction hypotesis.
So a−1 −1 −1 −1
n+1 an an−1 · · · a1 is a right inverse of a1 a2 · · · an an+1 .
[a−1 −1 −1 −1 −1 −1 −1 −1 −1
n+1 an an−1 · · · a1 ][a1 a2 · · · an an+1 ] = [an+1 an an−1 · · · a2 ][a1 a1 ][a2 · · · an an+1 ]
= [a−1 −1 −1 −1 −1
n+1 an an−1 · · · a2 ][e][a2 · · · an an+1 ] since a1 a1 = e
= ...
= a−1
n+1 an+1 = e.
So a−1 −1 −1 −1
n+1 an an−1 · · · a1 is a left inverse of a1 a2 · · · an an+1 .
Hence an+1 an · · · a−1
−1 −1
1 is the inverse of a1 a2 · · · an+1 .
Chapter 7
Boolean Algebras
7.1 Reminders
i. Partial ordering = reflexive + antisysmmetic + transitive
ii. Poset [ S, ≤ ]
iii. Immediate predecessor ≺
iv. Immediate successor ≻
v. Hasse diagram
vi. Maximal and minimal elements
vii. Universal upper bound (greatest element), 1
viii. Universal lower bound (least element), 0
ix. Least upper bound (lub, join, **product), a ⊕ b
x. Greatest lower bound (glb, meet, product), a ⊙ b
xi. Lattice, L = [ L, ⊕, ⊙ ]
7.2 Lattices
∆
Definition 7.2.1. a ∈ L is called an atom ←→ 0 ≺ a.
Definition 7.2.2. Let [ L, ⊕, ⊙ ] be a lattice.

∆
a ∈ L is said to be join-irreducible ←→ ∀x, y ∈ L [x ⊕ y = a −→ x = a ∨ y = a].
Remark 7.2.1.
i. The universal lower bound 0 is join-irreducible.
ii. All the atoms are join-irreducible.
77
78 CHAPTER 7. BOOLEAN ALGEBRAS
∆
Definition 7.2.3. A lattice is called finite length ←→ All chains in L are
finite.
Theorem 7.2.1. If L is a finite length lattice then every element a ∈ L can

be represented as a joint of a finite number of join-irreducible elements of L.
Definition 7.2.4. Expression x ⊕ y = a is called an irredundant join of a

∆
←→ Any subset of { x, y } no longer represents a.
Theorem 7.2.2. If L is a distributive, finite length lattice, then ∀a ∈ L there

is a unique representation as the join of irredundant set of join-irreducible
elements.
Example 7.2.1. [ Z+ , | ] is a lattice where | is divisibility. In this lattice prime

numbers are atoms. The powers of primes are the join-irreducible elements.
7.3 Boolean Algebras

Definition 7.3.1. A lattice is a poset [ L, ≤ ], any two elements of which
have unique join and meet, denoted by [ L, ⊕, ⊙ ].
7.3.1 Distributive Lattice

∆
Definition 7.3.2. A lattice [ L, ⊕, ⊙ ] is said to be distributive ←→ ∀a, b, c ∈
L
i. a ⊙ (b ⊕ c) = (a ⊙ b) ⊕ (a ⊙ c)
ii. a ⊕ (b ⊙ c) = (a ⊕ b) ⊙ (a ⊕ c).
Theorem
A 7.3.1. Let A be a set.
i. 2 , ∪, ∩ is a lattice.
ii. ∅ ∈ 2A is the universal lower bound.
iii. A ∈ 2A isthe universal upper bound.
iv. 2A , ∪, ∩ is a distributive lattice.
Example 7.3.1. Let A be a finite set. Then A = { a1 , a2 , . . . , an } be a listing

A A A
of elements of A. Let Aj ∈ 2A . Define bAj = (b1 j , b2 j , . . . , bn j ) ∈ Bn such
that (
Aj 1, ai ∈ Aj ,
bi =
0, ai ∈
/ Aj .
7.3. BOOLEAN ALGEBRAS 79
Notice that
f : 2A → Bn
A A
Aj 7→ (b1 j , b2 j , . . . , bA
n )
j
is a bijection.
Example 7.3.2. Let A = { a, b, c }
b∅ → (0, 0, 0)
b{ a } → (1, 0, 0)
b{ a,c } → (1, 0, 1)
b{ a,b,c } → (1, 1, 1)
Question 7.3.1. Let A1 , A2 ∈ 2A . Then A1 ∪ A2 , A1 ∩ A2 , A1 ∈ 2A . What can

you say about bjA1 ∪A2 , bA
j
1 ∩A2
, bA
j ?
1
7.3.2 n-cube
Definition 7.3.3. Bn is called n-cube where n ∈ N.
Example 7.3.3.
•B
||| BBB
| BB
|| BB
||
• BB • BB • BB •
| BB BB ||| BB |||
|| BB B| |B
||| BB || BBB ||| BBB
|| || |
• • BB • • BB • •
| BB | BB ||
|| BB || BB |
||| BB ||
|
BB |||
|
|| || |
• • • •
B0 B1 B2 B3
Note that
i. The diagram of Bn can be generated by two of diagrams of Bn−1 .
ii. The diagram of Bn is a undirected graph where vertices are b ∈ Bn , and

∆
b1 , b2 ∈ Bn are adjacent ←→ they differ in exactly one coordinate.
Theorem
A 7.3.2. Let A be a finite set with | A | = n. The Hasse diagram of
2 , ∪, ∩ is the n-cube.
Example 7.3.4. Let A = { a, b, c }.
{ a, b, c }
KKK
ss KKK (1, 1, 1)
ssss KKK r KKK
sss
s K rrrrr KKK
KKK
r
{ a, b }K { a, c }K { b, c } rrr K
KKK sss
Ks
KKK ss
K s (1, 1, 0) (1, 0, 1) (0, 1, 1)
sssKKKKK sssKsKKK LLL
LLrLrrrr
KKK
KKsKssss
sss sss K
rr LLL ss KKKK
{a} L {b} {c} rrr L sss
LLL
LLL ssss
s (1, 0, 0) (0, 1, 0) (0, 0, 1)
LLL s LLL s
LL sss LLL sss
sss LLL sss
∅ L sss
(0, 0, 0)
7.3.3 Bounded Lattice

∆
Definition 7.3.4. A lattice L is called bounded ←→ L has universal upper
and lower bounds, 1 and 0, respectively.
7.3.4 Complemented Lattice

Definition 7.3.5. Let L = [ L, ⊕, ⊙ ] be a bounded lattice. b ∈ L is called a
∆
complement of a ∈ L ←→ a ⊙ b = 0 ∧ a ⊕ b = 1.
Remark 7.3.1.
i. In general, complement may not exist.
ii. If it exists, it may not be unique. So complement is a relation rather
then a function.
0 1
iii. is a complement of .
1 0
Example 7.3.5.
7.3. BOOLEAN ALGEBRAS 81
1 ==

== b
== is a complement of a

== c
a= b c
==
==
==
=
0
Example 7.3.6.
{4} M
qq MMM The lattice of partitions of 4 is not
qqqq MMM
qqq
qq MMM
M complemented.
{ 1, 3 } { 2, 2 }
MMM q
MMM
MMM qqqqq
q
M qqq
{ 1, 1, 2 }
{ 1, 1, 1, 1 }
Theorem 7.3.3 (Uniqueness of complement). Let L = [ L, ⊕, ⊙ ] be a bounded,

distributive lattice. If b and c are complements of a, then b = c.
Remark 7.3.2. Note that complement of a may not exist. If it exists, then it
is unique.
Theorem 7.3.4 (Involution). Let L = [ L, ⊕, ⊙ ] be a bounded, distributive

lattice. If a ∈ L has the complement a ∈ L, then a has its complement which
is a. That is a = a.
Theorem 7.3.5 (De Morgan). Let L = [ L, ⊕, ⊙ ] be a bounded, distributive

lattice. If complements of a and b exist, then
a ⊕ b = a ⊙ b and a ⊙ b = a ⊕ b
Definition 7.3.6. A bounded lattice L = [ L, ⊕, ⊙ ] is said to be comple-

∆
mented ←→ ∀a ∈ L ∃b ∈ L b is a complement of a.
7.4 Boolean Algebra

Definition 7.4.1. A bounded, distributive, complemented lattice is called
a boolean algebra. B = [ B, ⊕, ⊙, , 0, 1 ] denotes a boolean algebra with a
is the complement of a, 0 and 1 are the universal lower and upper bounds,
respectively.

Example 7.4.1. Let A be a finite set. 2A , ∪, ∩ is a booean algebra 2A , ∪, ∩, , 0, 1 .
7.5 Canonical Expressions in Boolean Alge-

bras
Theorem 7.5.1. Let B be a boolean algebra and x ∈ B. x is join-irreducible
←→ x is an atom.
Remark 7.5.1. Let B = { b1 , b2 , . . . , bn } be the set of all atoms of boolean
algebra B.
i. No two elements of B is comparable.
ii. The join of any subset of B is irredundant.
iii. Any such join represents a unique element of B.
iv. Therefore there is a bijection between 2B and B.
ϕ : B → 2B
a 7→ the subset whose join represents a.
v. ϕ preserves ⊕ and ⊙
ϕ(a ⊕ b) = ϕ(a) ∪ ϕ(b)
ϕ(a ⊙ b) = ϕ(a) ∩ ϕ(b)
ϕ(a) = ϕ(a).
Theorem 7.5.2 (Stone representation). A boolean algebra B = [ B, ⊕, ⊙, , 0, 1 ]
of finite length is isomorphic to 2B .
Theorem 7.5.3. The Hasse diagram of a boolean algebra with n atoms is
the n-cube.
Theorem 7.5.4. A boolean algebra with n atoms has 2n elements.
Remark 7.5.2. A boolean algebra B is entirely represented by n where n is
the number of atoms. Bn denotes one such algebra.
Part IV
Number Systems
83
Chapter 8
Number Systems
8.1 Natural Numbers

Definition 8.1.1 (Natural Numbers, (Peano Axioms)). The set of natural
numbers is a set N that satisfies the following five axioms:
P1. ∃0 ∈ N.
P2. ∀n ∈ N ∃s(n) ∈ N. (s(n) is called the successor of n).
P3. ∀n ∈ N, s(n) 6= 0.
P4. ∀m, n ∈ N [s(m) = s(n) −→ m = n].
P5. ∀A ⊆ N [0 ∈ A ∧ ∀n (n ∈ A −→ s(n) ∈ A) −→ A = N].
Remark 8.1.1. These axioms are called Peano axioms [Gal89]. Note that s
is a function given as s : N → N.
0 zero 0
s(0) one 1
Remark 8.1.2. is called and represented by
s(s(0)) two 2
··· ··· ···
Question 8.1.1. Does there exist such a set?
Question 8.1.2. Is it unique? That is, if N1 and N2 are sets satisfying the
Peano axioms, then are N1 and N2 isomorphic?
∆
Definition 8.1.2. The predecessor of n, p(n), is p(n) = m ←→ s(m) = n.
Definition 8.1.3 (Addition).

+ : N × N → N defined as:
85
86 CHAPTER 8. NUMBER SYSTEMS
(
n, m = 0,
n+m=
s(n) + p(m), otherwise.
Remark 8.1.3. n + m is called the sum of n and m.
Definition 8.1.4 (Multiplication).

× : N × N → N defined as:
(
0, m = 0,
n×m=
n + n × p(m), otherwise.
Remark 8.1.4. n × m is called the product of n and m.
Definition 8.1.5 (Ordering).

≤ : N × N → {T, F } defined as:
(
T, if m = 0,
m ≤ n means
p(m) ≤ p(n), otherwise.
Question 8.1.3. Define exponentiation nm .

[N, +]
Question 8.1.4. What kind of algebraic structure is [N, ×] ?
[N, +, ×]
8.2 Integers
Definition 8.2.1. Consider the relation ∼ on N×N defined as ∀(a, b), (c, d) ∈
N × N [(a, b) ∼ (c, d) ←→ a + d = b + c]
Example 8.2.1. Some elements of the relation ∼ are the followings:

· · · (0, 2) ∼ (1, 3) (0, 1) ∼ (1, 2) (0, 0) ∼ (1, 1) (1, 0) ∼ (2, 1) (2, 0) ∼ (3, 1) · · ·
· · · (0, 2) ∼ (2, 4) (0, 1) ∼ (2, 3) (0, 0) ∼ (2, 2) (1, 0) ∼ (3, 2) (2, 0) ∼ (4, 2) · · ·
··· ··· ··· ··· ··· ··· ···
Theorem 8.2.1. The relation ∼ is an equivalence relation on N × N. More-
over, the set of equivalence classes, N × N/ ∼, is the set
N × N/ ∼= { [ ( n, 0 ) ] | n ∈ N } ∪ { [ ( 0, n ) ] | n ∈ N ∧ n 6= 0 }
8.2. INTEGERS 87
Proof. Let [ ( a, b ) ] , [ ( c, d ) ] , [ ( e, f ) ] ∈ N × N/ ∼.
1. [ ( a, b ) ] ∼ [ ( a, b ) ], since a + b = b + a. So ∼ is reflexive.
2. [ ( a, b ) ] ∼ [ ( c, d ) ] −→ [ ( c, d ) ] ∼ [ ( a, b ) ], since a + d = b + c. So ∼
is symmetric.
3. If [ ( a, b ) ] ∼ [ ( c, d ) ] ∧ [ ( c, d ) ] ∼ [ ( e, f ) ], then a + d = b + c and
c + f = d + e. Adding the two a + d + c + f = b + c + d + e, then
a + f = b + e. Hence [ ( a, b ) ] ∼ [ ( e, f ) ]. So ∼ is transitive.
Therefore ∼ is an equivalence relation on N × N.
Example 8.2.2. Some equivalence classes of N × N/ ∼ are:
···
[ ( 2, 0 ) ] = { ( n + 2, n ) | n ∈ N }
[ ( 1, 0 ) ] = { ( n + 1, n ) | n ∈ N }
[ ( 0, 0 ) ] = { ( n, n ) | n ∈ N }
[ ( 0, 1 ) ] = { ( n, n + 1 ) | n ∈ N }
[ ( 0, 2 ) ] = { ( n, n + 2 ) | n ∈ N }
···
Definition 8.2.2 (Integers). The set N × N/ ∼ is the set of integers and is
denoted by Z.
Definition 8.2.3 (Addition and Multiplication in Z). Let [ ( a, b ) ] , [ ( c, d ) ] ∈
Z. Define + : Z × Z → Z and × : Z × Z → Z
[ ( a, b ) ] + [ ( c, d ) ] = [ ( a + c, b + d ) ]
[ ( a, b ) ] × [ ( c, d ) ] = [ ( ac + bd, ad + bc ) ]
Theorem 8.2.2. ∀x ∈ Z ∃x′ ∈ Z [x + x′ = x′ + x = 0]. Denote x′ by −x.
Remark 8.2.1. x = [ ( a, b ) ] −→ −x = [ ( b, a ) ]
[Z, +]
Question 8.2.1. What kind of algebraic structure is [Z, ×] ?
[Z, +, ×]
Definition 8.2.4. Z+ = { [ ( n, 0 ) ] | n ∈ N \ { 0 } } is called the set of pos-
itive integers. Z− = { [ ( 0, n ) ] | n ∈ N \ { 0 } } is called the set of negative
integers.
88 CHAPTER 8. NUMBER SYSTEMS
Definition 8.2.5 (Ordering in Z).

Let x, y ∈ Z
∆
• x is less than y, denoted by x < y, ←→ y − x = y + (−x) ∈ Z+ .
∆
• x is less or equal to y, denoted by x ≤ y ←→ (x < y ∨ x = y).

cially [PY73, Ros07, Men08, TZ82, Gal89]. Class of CMPE220 of Fall 2008
did the initial LaTeX draft of hand written notes.
Chapter 9
Division
9.1 Division
Definition 9.1.1 (Division).
∆
Let d, n ∈ Z. d divides n ←→ ∃c ∈ Z n = cd.
d factor or divisor n
is a of .
n multiple d
Notation. If d divides n, we write d | n. If d does not divide n, we write

d ∤ n.
Theorem 9.1.1. Let d, n, m, a, b ∈ Z.

i. n | n (reflexivity)
ii. d | n ∧ n | m −→ d | m (transitivity)
iii. d | n ∧ d | m −→ d | (an + bm) (linearity)
iv. d | n −→ ad | an (multiplication)
v. ad | an ∧ a 6= 0 −→ d | n (cancellation)
vi. 1 | n (1 divides every integer)
vii. n | 0 (every integer divides 0)
viii. 0 | n −→ n = 0 (0 divides only 0)
ix. d | n ∧ n 6= 0 −→ | d | ≤ | n |
x. d | n ∧ n | d −→ | d | = | n |
xi. d | n ∧ d 6= 0 −→ (n/d) | n
Remark 9.1.1.
i. The expression an + bm is called a linear combination of n and m.
89
90 CHAPTER 9. DIVISION
ii. Every common divisor of n and m can be written as a linear combination

of n and m.
Due to linearity d | n ∧ d | m −→ d | (n + m) and d | (nm).
Question 9.1.1. Prove that d | n ∧ d | m −→ d | (nm) using linearity.
Theorem 9.1.2 (The Division Algorithm).
Let n ∈ Z, d ∈ Z+ . Then there are unique q, r ∈ Z with 0 ≤ r < d such that
n = qd + r.
Definition 9.1.2.
Let n = qd + r as in the division algorithm.
d divisor
n dividend
is called
q quotient q = n div d
r remainder r = n mod d
The division algorithm is given as Algorithm 1. A trace of the algorithm
for n = 13, d = 3 is given in Example 9.1.1.
Algorithm 1: The Division Algorithm

Input: Dividend n > 0 and divisor d > 0
Output: Quotient q and remainder r where 0 ≤ r < d
1 begin
2 q←0
3 while n ≥ d do
4 q ←q+1
5 n← n−d
6 end
7 r←n
8 end
Example 9.1.1. 3 divides 13. That is, n = 13, d = 3.

n d q r
13 3 0
10 1
7 2
4 3
1 4
4 1
9.2. PRIME NUMBERS 91
9.2 Prime Numbers

∆
Definition 9.2.1. Let n ∈ Z+ . n > 1 is called prime ←→ The only positive
divisors of n are 1 and n. If n is not prime, then n is called composite.
Notation. Prime numbers are usually denoted by p, p′ , pi , q, q ′, qi .
Example 9.2.1. There are 4 primes less than 10. There are 25 prime numbers
less than 100 which are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53,
59, 61, 67, 71, 73, 79, 83, 89, and 97. So for 40 % of the numbers between
1 and 10 are prime where as only 25 % of the numbers between 1 and 100
are prime. The primes becomes sparse as the numbers grow. There are 168,
that is 17 %, prime numbers less than 1000.
Theorem 9.2.1. Every integer n > 1 is either a prime number or a product
of prime numbers.
Proof. Use induction on n. As an induction base n = 2 is a prime. Assume
that it is true for all the numbers m where 1 < m < n, that is ∀m ∈
Z [1 < m < n] m is either a prime or a product of primes.
We want to prove that it is true for n, too. Consider n.
i. Case: n is prime. Then we are done.
ii. Case: n is not prime. Then there must be a positive divisor d that
devides n, that is, ∃d ∈ Z(d > 0 ∧ d 6= 1 ∧ d 6= n)∃c ∈ Zn = cd. Since
both 1 < c < n and 1 < d < n, by the induction hypothesis they are
either prime or a product of primes. Therefore their product n should
be a product of primes.
Theorem 9.2.2 (Euclid).

There are infinitely many prime numbers.
Remark 9.2.1. The proof of the theorem is given in Elements by Euclid (300
BC).
Notation. Let P be the set of prime numbers.
Theorem 9.2.3. p ∈ P ∧ p | ab −→ p | a ∨ p | b. More generally,
p ∈ P ∧ p | a1 a2 · · · an −→ ∃i ∈ { 1, . . . , n } p | ai .
Theorem 9.2.4 (The Fundamental Theorem of Arithmetic).
Every integer n > 1 can be written uniquely as a product of nondecreasing
primes.
Example 9.2.2.
2=2 6=2·3 30 = 2 · 3 · 5
4 = 2 · 2 = 22 12 = 2 · 2 · 3 = 22 · 3 720 = 2 · 2 · 2 · 2 · 3 · 3 · 5 = 24 · 32 · 51
Remark 9.2.2.
i. Given an integer n > 1, it is not easy to decide whether n is prime.
ii. There is no known formula that generates primes only.
iii. Prime numbers of the form 2p − 1, where p ∈ P, are called Mersenne
primes. As of 2009, there are 47 Mersenne primes known. The largest
is 243,112,609 − 1 [Wik09].
n
iv. Numbers in the form of Fn = 22 + 1 where n ∈ N are called Fermat
numbers. F0 = 3, F1 = 5, F2 = 17, F3 = 257, F4 = 65, 537 are all prime
but Euler (1732) found that F5 = 232 + 1 = 641 × 6, 700, 417 is not
prime. Beyond F5 no Fermat primes have been found [Apo].
+
√ Let n ∈ Z is composite. Then there is a prime divisor p
Theorem 9.2.5.
of n and p ≤ n.
Definition 9.2.2. Let π(x) be the number of primes p satisfying 2 ≤ p ≤ x.
Remark 9.2.3. The density of primes drops as the numbers grow.

n 101 102 103
Number of primes in {2, 3, · · · , n} 4 25 168
Percentage of primes in {2, 3, · · · , n} 40% 25% 17%
Theorem 9.2.6 (The Prime Number Theorem (Hadamard + Vallee Poussin,

1896)).
π(x) log x
lim =1
x→∞ x
Corollary 9.2.7 (Goldbach’s Conjecture (1742)).

Every even integer n > 2 is the sum of two primes.
Definition 9.2.3 (Twin Primes).

If p and p + 2 are primes, they are called twin primes.
Theorem 9.2.8 (The Twin Prime Conjecture).

There are infinitely many twin primes.
9.3. COMMON DIVISORS AND MULTIPLES 93
9.3 Common Divisors and Multiples

Definition 9.3.1 (Common Divisor).
∆
Let a, b ∈ Z. d ∈ Z+ is called a common divisor of a and b. ←→ d |
a ∧ d | b. Let cd(a, b) be the set of all common divisors of a and b.
Remark 9.3.1. ∀a, b ∈ Z [1 ∈ cd(a, b)]. So, cd(a, b) 6= ∅.
Theorem 9.3.1. ∀a, b ∈ Z ∃d ∈ Z+ such that d ∈ cd(a, b) ∧ ∃x, y ∈ Z (d =
ax + by). Moreover, ∀k ∈ cd(a, b) [k | d].
Theorem 9.3.2. ∀a, b ∈ Z ∃!d ∈ Z with the following properties:
i. d ≥ 0
ii. d ∈ cd(a, b)
iii. ∀e ∈ cd(a, b) −→ e | d.
Proof. By Theorem 9.3.1 there is at least one d satisfying (ii) and (iii). Note
that −d also satisfies these conditions. Suppose d′ also satisfies (ii) and (iii),
then d | d′ and d′ | d, so | d | = | d′ |. Hence there is exactly one d ≥ 0
satisfying both (ii) and (iii).
Definition 9.3.2 (Greatest Common Divisor). The number d in Theo-
rem 9.3.2 is called the greatest common divisor (gcd) of a and b and denoted
by a D b or gcd(a, b).
Remark 9.3.2. a D b is the operator notation, gcd(a, b) is the function nota-
tion of the greatest common divisor.
Theorem 9.3.3. The gcd has the following properties:
i. a D b = b D a (commutativity)
ii. a D (b D c) = (a D b) D c (associativity)
iii. | a | (b D c) = (ab) D (ac) (distributivity)
iv. a D 1 = 1 D a = 1
v. a D 0 = 0 D a = | a |
Definition 9.3.3. If a D b = 1, then a and b are said to be relatively prime,
denoted by a ⊥ b.
Remark 9.3.3. a ⊥ b ←→ ∃x, y ∈ Z xa + yb = 1.
Theorem 9.3.4 (Euclid’s lemma).
a | bc ∧ a ⊥ b −→ a | c.
Proof. Since a ⊥ b we can write 1 = ax + by. Therefore c = cax + cby. Since

a | cax and a | bc, a | (cax + cby). Hence a | c.
Theorem 9.3.5. p ∈ P ∧ p ∤ a −→ p D a = 1
Theorem 9.3.6. a and b are relatively prime. ←→ 6 ∃p ∈ P [p | a ∧ p | b].
Example 9.3.1. Due to unique prime factorization, a positive integer can be
represented as a vector where ith entry of the vector is the power of the ith
prime number in the prime factorization of the number.
n prime factors vector
10 21 × 30 × 51 × 70 × 110 × · · · [ 10100 · · · ]
12 22 × 31 × 50 × 70 × 110 × · · · [ 21000 · · · ]
63 20 × 32 × 50 × 71 × 110 × · · · [ 02010 · · · ]
Consider the dot product of the corresponding vectors. The corresponding
vectors are perpendicular if the numbers are relatively prime:
[ 10100 · · · ] · [ 02010 · · · ] = 0 −→ 10 ⊥ 63.
[ 10100 · · · ] · [ 21000 · · · ] = 2 6= 0 −→ 10 6⊥ 12.
Question 9.3.1. What is the dimension of this vector space?
Definition 9.3.4. Let a, b ∈ Z+ . The smallest m ∈ Z+ with a | m and
b | m is called the least common multiple of a and b, denoted by lcm(a, b).
Remark 9.3.4. A more proper approach would be the approach of the great-
est common divisor: First define the set of common multiples, denoted by
cm(a, b). Then show that cm(a, b) 6= ∅ since ab ∈ cm(a, b). Finally, show
that there is the least element in cm(a, b).
Theorem 9.3.7. Let [ ai ] and [ bi ] be the vector representations of a and b.
Then Y min{a ,b } Y max{a ,b }
i i i i
gcd(a, b) = pi and lcm(a, b) = pi
i i
where pi is the ith prime number in the vector representation.
9.4 Modular Arithmetic

Reminder 9.4.1. The division algorithm of Theorem 9.1.2 states that for
n ∈ Z, d ∈ Z+ there exist unique q, r ∈ Z with n = qd + r and 0 ≤ r < d.
Note that r = a mod d and q = n div d.
9.4. MODULAR ARITHMETIC 95
Definition 9.4.1. Let a, b ∈ Z and m ∈ Z+ . a is said to be congruent to b

∆
modulo m, denoted by a ≡ b (mod m). ←→ m | (a − b). If a and b are
not congruent modulo m, then a 6≡ b (mod m).
Theorem 9.4.1. a ≡ b (mod m) ←→ a mod m = b mod m.
Theorem 9.4.2. a ≡ b (mod m) ←→ ∃k ∈ Z [a = b + km].
Theorem 9.4.3. Let m ∈ Z+ and a, b, c, d ∈ Z.

a ≡ b (mod m) ∧ c ≡ d (mod m)
−→ a + c ≡ b + d (mod m) ∧ ac ≡ bd (mod m).
∆
Definition 9.4.2. The congruence class of a modulo m is defined as [a]m =
{ n ∈ Z | ∃k ∈ Zn = a + km }
Theorem 9.4.4. ∀x, y ∈ [a]m x ≡ y (mod m)
Theorem 9.4.5. Let a, b, c, d ∈ Z and m ∈ Z+ (m > 1). If a ≡ b (mod m)

and c ≡ d (mod m) then
a) a + c ≡ b + d (mod m)
b) ac ≡ bd (mod m)
c) ∀x ∈ Z, ax ≡ bx (mod m)
d) ∀n ∈ Z+ , an ≡ bn (mod m).
————– @HB ————–
Application 9.4.1.
i. Hashing Functions.
ii. Pseudorandom Numbers.
iii. Cryptology.
Acknowledgment. These notes are based on various books such as
[PY73, Ros07, Gal89] but especially [Apo].
Part V
Combinatorics
97
Chapter 10
Counting
10.1 Motivation
Counting the number of different ways of satisfying a condition is important
in science including Probability, Statistical Physics and, of course, Computer
Science. Theory of Algorithms in Computer Science deals with finding an
algorithm which has the minimum number of steps. Then one needs to know
what is the possible number of steps.
Example 10.1.1.
i. How many vertices in a complete binary tree?
ii. How many steps are needed in order to traverse a binary tree?
iii. If you have n items, how many comparisons do you need to make in
order to sort them?
Question 10.1.1.
i. Suppose there are 3 balls looks like the same but one of them is different
in weight only. How many comparisons in weight does it needed to figure
out the different one?
ii. The same question for 12 balls?
Example 10.1.2. Consider a room filled with air. The room divided into two
halves. You are sitting in one of the halves. What is the possibility that all
the molecules would be in the other half. Our every day observations says
that that does not happen frequently. If that happens frequently enough,
you would be suffocated. What is the probability that it happens, if the
number of molecules in the room is n where
i. n = 2?
99
100 CHAPTER 10. COUNTING
ii. n = 8?
iii. n is in the order of Avogadro number, that is n ≈ 1024 ?
iv. What is you estimate of n if the room is 4 × 5 × 3 in meters?
Assume that air is an ideal gas where molecules are free to move without any
interaction from each other.
This chapter deals with finite sets. Let A and B be finite sets. Let
| A | = α and | B | = β. Since A is finite, the elements of A can be listed as
an α-tuple (a1 , a2 , . . . , aα ). This ordering is used for the following proofs.
Definition 10.1.1 (Factorial).
Let n ∈ N.
i. 0! = 1
ii. (n + 1)! = n!(n + 1).
Remark 10.1.1. Use of factorial is quite old. One of the earliest use of fac-
torials is in the proof of prime numbers are infinite given by Euclid around
300BC. The proof is based on the idea that there must be a prime between
n and n! + 1.
Definition 10.1.2 (Factorial Power).
Let n, r ∈ Z+ .
∆
nr = (n + 0) (n + 1)(n + 2) · · · (n + (r − 1)),
∆
nr = (n − (r − 1)) · · · (n − 2)(n − 1) (n − 0).
nr and nr are called rising factorial power and falling factorial power and
are read as n to the r rising and n to the r falling, respectively.
Remark 10.1.2. Notice that
n!
nr = .
(n − r)!
The notation of the rising and falling factorial power is due to [GKP98]
Definition 10.1.3 (The set of bits).
∆
B = { 0, 1 }.
10.2 Cardinality: Finite and Infinite Sets

Numbers such as integers or reals are infinitely many. Then how do you
represent them in computers? The number of bits in a register of a typical
10.2. CARDINALITY: FINITE AND INFINITE SETS 101
computer is usually 32 bits. Therefore the number of different bit patterns

that can be obtained using 32-bit is 232 . This is a quite big number but
clearly not big enough to represent integers.
The real numbers are represented in computer by means of floating point
arithmetic but we have the same representation problem since the set of real
numbers is also infinite.
Do we really have the same problem?
Definition 10.2.1. Let A and B be sets. A and B are said to be of the
∆
same cardinality, denoted by | A | = | B | , ←→ There is a bijection from
A to B.
n ∆
Definition 10.2.2. Im = { m, m + 1, . . . , n } where m, n ∈ Z and m ≤ n.
∆
Definition 10.2.3. A set A is called finite ←→ A has the same cardinality
of I1n for some n ∈ N.
Notation 10.2.1. The cardinality of Z+ is denoted by ℵ0 , read as aleph null.
∆
That is, ℵ0 = | Z+ |.
∆
Definition 10.2.4. A set A is called countable ←→ A is finite or A has
the same cardinality of Z+ .
∆
Definition 10.2.5. A set A is called uncountable ←→ A is not countable.
Example 10.2.1 (Hilbert’s Hotel). Infinite sets have unintuitive properties.
Hilbert provide a very nice story about a hotel with countably infinite rooms.
Suppose the hotel is completely full and the officer at the reception is good
in mathematics.
One person arrives. The receptionist asks every person in room number
k to move the the room number k + 1. By doing that the room number 1
becomes empty and the new comer gets it.
This time countably infinite group of people arrives. The receptionist asks
every one in room number k to move the the room number 2k. By doing
so all the rooms with odd numbers become empty. So the kth person of the
new group gets the room with number 2k + 1.
Theorem 10.2.1. | N | = ℵ0 .
Proof. Define f : N → Z+ such that f (n) = n + 1. Since f is a bijection
(left as exercise), | N | =| Z+ | .
Theorem 10.2.2. | E | = ℵ0 and | O | = ℵ0 where E, O are even and odd

natural numbers, respectively.
Proof. Define f : N → E such that f (n) = 2n and g : N → O such that

g(n) = 2n + 1. Since f and g are bijections (left as exercise), | E | =| N | and
| O | =| N | .
Theorem 10.2.3. | Z− | = ℵ0 .
Proof. Define f : Z+ → Z− such that f (n) = −n. Since f is a bijection (left

as exercise), | Z− | =| Z+ | .
Theorem 10.2.4. | Z | = ℵ0 .
Proof. Define f : N → Z such that


−k, n = 2k, k 6= 0, k ∈ N

f (n) = 0, n=0


k, n = 2k + 1, k 6= 0, k ∈ N.
Since f is a bijection, | Z | =| N | .
Theorem 10.2.5. | Q+ | = ℵ0 .
Proof.
↓q→p 1 2 3 4 5 6 ···
1 1 1 1 1 1
1 1 2 3 4 5 6
···
2 2 2 2 2 2
2 1 2 3 4 5 6
···
3 3 3 3 3 3
3 1 2 3 4 5 6
···
4 4 4 4 4 4
4 1 2 3 4 5 6
···
5 5 5 5 5 5
5 1 2 3 4 5 6
···
6 6 6 6 6 6
6 1 2 3 4 5 6
···
··· ··· ··· ··· ··· ··· ··· ···
Define f : N → Q+ such that f (n) =?1 . Since f is a bijection, | Q+ | =
| N |.
Theorem 10.2.6. | Q | = ℵ0 .
1
How to define this function?
10.2. CARDINALITY: FINITE AND INFINITE SETS 103
Proof. Let f : Z+ → Q+ be a bijection. There is such a bijection since

| Z+ | = | Q+ |. Define q : Z → Q using f : Z+ → Q+ as

+
−f (z), −z ∈ Z

q(z) = 0, z=0


f (z), z ∈ Z+ .
Since q is a bijection, | Q | = | Z |.
Summary 10.2.1. ℵ0 = | Z+ | = | N | = | E | = | O | = | Z | = | Z− | = | Q |.
Remark 10.2.1. So far it seems that there is only one kind of infinity, that is
ℵ0 . Note that these sets are countable, that is, there is a bijection from N to
them.
Theorem 10.2.7 (Cantor’s diagonalization).

| [0, 1) | =
6 ℵ0 where [0, 1) = { x ∈ R | 0 ≤ x < 1 }.
Proof. Assume that | [0, 1) | = ℵ0 . Then we can make a list of elements of

[0, 1). All the real numbers in [0, 1) have the decimal expansion of the form
0.d1 d2 d3 . . . . Let xk ∈ [0, 1) be the kth real number in the list. Construct a
new real number y in such a way that the kth digit of y would be different
that the kth digit of the xk . y is in [0, 1) since its decimal expansion is in the
proper form. Yet, y is not in the list because for every k, y is different than
xk in the kth digit since its kth digit is different than dk . This contradicts
the assumption that such a list can be made. If such a list cannot be made
that the set [0, 1) is not countable.
Remark 10.2.2. The set [0, 1) is uncountable.
10.2.1 Hierarchy of Infinities

It seams that there is one type of infinity which is ℵ0 . Cantor showed that
there are actually infinitely many infinities.
6 |2A |.
Theorem 10.2.8 (Cantor’s Theorem). Let A be a set. Then |A| =
In other words “No set is the same size as its power set”.
We show that mapping f from A to 2A is not a surjection, therefore f is
not a bijection.
Suppose f : A −→ 2A . Define B = {x ∈ A | x ∈ / f (x)}. Clearly B ⊆ A.

A
This means B ∈ 2 .
We claim that ∀x ∈ A f (x) 6= B, that is B ∈
/ f (A). If the claim is correct,
that means f cannot map into B. Hence f is not a surjection. Therefore f
cannot be a bijection.
There is no bijection from A to 2A . Therefore |A| =
6 |2A |.
Theorem 10.2.9. ∀x ∈ A f (x) 6= B, that is B ∈

/ f (A).
Proof. Suppose ∃b ∈ A f (b) = B. Ask if b ∈ B?
i) b ∈ B case: By definition of B, b ∈
/ f (b). Since f (b) = B, we have
b∈/ B. Contradiction.
ii) b ∈
/ B case: Since f (b) = B, this means b ∈
/ f (b). This means b ∈ B
since B is defined so. Contradiction.
So we obtain b ∈ B ⇔ b ∈ / B. This contradiction means ¬∃b ∈ A f (b) = B.

That is ∀b ∈ A f (b) 6= B. The theorem is proved.
Remark 10.2.3. Using the Theorem 10.2.8 we can obtain infinitely many
infinities based on N. Let N0 = N. Then |2N | =
6 |N|. We can extent this as
follows:
N1 = 2N0 |N1 | =
6 |N0 |
Define N2 = 2N1 . Then |N2 | = 6 |N1 | .
... ...
Remark 10.2.4. The set of real numbers also produces an other chain of
infinities as follows: Let R0 = R. Then |2R | =
6 |R|. We can extent this as
follows:
R1 = 2R0 |R1 | =
6 |R0 |
Define R2 = 2R1 . Then |R2 | = 6 |R1 | .
... ...
Question 10.2.1. Are the hierarchies of N0 , N1 , . . . and R0 , R1 , . . . related or
different?
10.3 The Number of Ways

Suppose there are n1 ways to go from A to B and n2 ways to go from C to D.
10.3. THE NUMBER OF WAYS 105
) ) (
◦ A n1 5 B ◦ ) ) (
5 ◦ C n2 5 D ◦.
5
10.3.1 The Product Rule

Remark 10.3.1. Let A and B be finite sets where | A | = α and | B | = β.
Theorem 10.3.1 (The Product Rule).

Suppose A − B and C − D are connected in serial. The number of different
ways to go from to △ is n1 × n2 .
) ) ( ) ) )
A n1 5 B ◦ C n2 5 D △.
5 5
Theorem 10.3.2 (The number of elements of cartesian product).

Let A be finite set. Then | An | = | A |n .
Proof. By induction on n using the product rule.
Corollary 10.3.3 (The number of bit strings of length n).

Let Bn be the the set of bit strings of length n where B = { 0, 1 }. Then
| Bn | = 2n .
Theorem 10.3.4 (The number of truth tables).

n
There are 22 different truth tables for propositions in n variables.
Proof. There are 2n rows in a truth table of n variables. For each row,
n
one can assign two choices, namely F or T. Hence there are 22 different
assignments.
The following theorem will be proved in steps.

Theorem 10.3.5 (The number of various type of functions).

functions βα
injections βα
The number of surjections from A to B is ? .
bijections β!
partial functions (β + 1)α

Proof. The number of functions from A to B, that is B A = | B || A | .
Since A is finite, the elements of A can be listed as (a1 , a2 , . . . , aα ). Use this
ordering of elements:
a1 ∈ A β f (a1 ) ∈ B
a ∈A β f (a2 ) ∈ B
For 2 , there are different choices for .
... ... ...
aa ∈ A β f (aa ) ∈ B
By product rule, there are ββ . . . β = β α different ways.
Proof. The number of injections from A to B is β α .
If | A | > | B |, then there is no injection from A to B. So consider the case
of | A | ≤ | B |. Since A is finite, the elements of A can be listed. Use this
ordering of elements:
a1 ∈ A β−0 f (a1 ) ∈ B
a ∈A β−1 f (a2 ) ∈ B
For 2 , there are different choices for .
... ... ...
aα ∈ A β − (α − 1) f (aα ) ∈ B
By product rule, there are (β − 0)(β − 1) . . . (β − (α − 1)) = β α different
ways.
Example 10.3.1. A common approach to counting is to define a bijection to
a set whose cardinality is already known.
We prove that the number of bit strings of length n is | Bn | = 2n by
defining a bijection to B{ 1,2,...,n } whose cardinality is 2n . Consider the set
B{ 1,2,...,n } of functions from { 1, 2, . . . , n } to B. Define a function
f : B{ 1,2,...,n } → { 0, 1 }n
g 7→ (b1 , b2 , . . . , bα )
where g ∈ B{ 1,2,...,n } and bi = g(i), i ∈ { 1, 2, . . . , n }.

f is a bijection (proof?). Therefore

| Bn | = B{ 1,2,...,n } = | B || { 1,2,...,n } | = 2n .
10.3. THE NUMBER OF WAYS 107
Remark 10.3.2. IPv4 is the currently used protocol for the Internet in which
every device on the Internet should have a unique ID. IPv4 uses 32-bit IDs
which is usually written as four numbers separated by dots as in the case of
127.0.0.1. Therefore 232 devices can be connected to the Internet at a given
time. Although it is a very big number, it is not big enough for the demand
of the future. IPv6 is planned to use 128-bit ID’s.
Theorem 10.3.6 (The number of subsets).

Let A be a finite set. Then 2A = 2| A | = 2α .
Proof. Use α-tuple (a1 , a2 , . . . , aα ) of A. Define a function
f : 2A → Bα
A 7→ (b1 , b2 , . . . , bα )
(
1, ai ∈ A,
where A ∈ 2A and bi = .
0, ai ∈
/ A.

f is a bijection (proof?). Therefore 2A = | Bα | = 2α = 2| A | .
Theorem 10.3.7. Let A1 , A2 , . . . , An be finite sets. Then | A1 × A2 × . . . × An | =

| A1 | | A2 | · · · | An |
10.3.2 The Sum Rule

Theorem 10.3.8 (The Sum Rule).
Suppose A − B and C − D is connected in parallel. The number of different
ways to go from to △ is n1 + n2 .
) ) (
8 ◦ A n1 5 B ◦
5
( )
◦ ◦H △
& ) ) (
◦ C n2 5 D ◦
5
Theorem 10.3.9. Let A1 , A2 , . . . , An be finite disjoint sets. Then
| A1 ∪ A2 ∪ . . . ∪ An | = | A1 | + | A2 | + . . . + | An | .
Example 10.3.2. Suppose a computer system requires a password which is 6

to 8 characters long, where each character is an uppercase letter or a digit.
Each password must contain at least one digit.
How many different passwords are there?
Ans. Let P denotes the total number of passwords. Let P6 , P7 , P8 denote
the number of passwords of length 6, 7, 8, respectively. By sum rule P =
P6 + P7 + P8 .
P6 = | { all strings of letters and digits of length 6 } | − | { all strings of letters of length 6 } |

= { A, B, . . . , Z, 0, 1, . . . , 9 }6 − { A, B, . . . , Z }6
= (26 + 10)6 − 266
= 366 − 266 .
Similarly P7 = 367 − 267 and P8 = 368 − 268 . Then
P = P6 +P7 +P8 = 366 −266 +367 −267 +368 −268 = 366 (1+36+362)−266 (1+26+262).
10.3.3 The Inclusion-Exclusion Rule

Suppose A − B and C − D is connected in parellel but n3 of ways from A to
B are common ways from C to D. The number of different ways to go from
to △ is n1 + n2 − n3 .
) ) (
8 ◦ A n1 5 B ◦
5
( ( ( ( ( ( )
◦ ◦ ◦ n3 6
6
◦ ◦ ◦H △
& ) ) (
◦ C n2 5 D ◦
5
10.4. THE PIGEONHOLE PRINCIPLE 109
Theorem 10.3.10. Let A1 and A2 be finite sets. Then
| A1 ∪ A2 | = | A1 | + | A2 | − | A1 ∩ A2 | .
Example 10.3.3. What is the number of 8-bit strings starting with 1 or ending
with 00. Let A = { (b1 , b2 , . . . , bn ) ∈ B8 | b1 = 1 ∨ (bn−1 = 0 ∧ bn = 0) }.
A is the set of 8-bit strings starting with 1 or ending with 00.
| A | =?
A1... starting with 1
Ans. Let A...00 be the 8-bit strings ending with 00 .
A1...00 starting with 1 and ending with 00
Then | A | = | A1... ∪ A...00 | = | A1... | + | A...00 | − | A1... ∩ A...00 | where A1... ∩
A...00 = A1...00 .
| A1... | = | B8−1 | = 27 , | A...00 | = | B8−2 | = 26 and | A1...00 | = | B8−3 | = 25 .
Therefore | A | = | A1... | + | A...00 | − | A1...00 | = 27 + 26 − 25 = 25 (22 + 21 − 1).
Theorem 10.3.11. Let P be the set of partial functions from A to B. Then
| P | = (β + 1)α .
Proof. Let B = B ∪ { b0 } where b0 ∈ / B. Let p ∈ P. Define set Ap =
{ a ∈ A | p(a) is not defined }. Then define function p∗ : A → B such that
(
p(a), a ∈ A\Ap ,
p∗ (a) =
b0 , a ∈ Ap .
Note that p∗ is a function. Then define function f as
f : P → BA (10.1)
p 7→ p∗ (10.2)

f is a bijection (proof ?). Hence | P | = BA = | B || A | = (β + 1)α
10.4 The Pigeonhole Principle

Theorem 10.4.1 (The Pigeonhole Principle).
If k + 1 or more objects are placed into k boxes, then there is at least one box
containing 2 or more objects.
Theorem 10.4.2. Among any n + 1 positive integers not exceeding 2n, there
must be an integer that divides one of the other integers.
Table 10.1: Summary of Counting Methods

ordered unordered
n+r−1

with repetition nr
n! n
P(n,r) r n! nr
without repetition P(n, r) = (n−r)! = nr r
= r! = (n−r)!r! = r!
Theorem 10.4.3 (The Generalized Pigeonhole Principle).

If n objects are placed into k boxes, then there is at least one box containing
at least ⌈ n/k ⌉ objects.
Theorem 10.4.4. Let A and B be finite sets and f : A → B be a function.

If | A | > | B |, then f cannot be an injection.
Proof. Assume that f is an injection. Then f maps each a ∈ A into different

b ∈ B. Since | A | > | B | by pigeonhole principle, ∃a1 , a2 ∈ A [f (a1 ) = f (a2 ) = b]
for some b ∈ B. Hence f cannot be injective.
Example 10.4.1. Let Ai = (xi , yi) i = 1, 2, . . . , 5 be a set of five distinct points

with integer coordinates in the xy-plane.
Show that the midpoints of the line joining at least one pair of these
points have integer coordinates.
x +x y +y
Ans. i 2 j , i 2 j is the coordinate of the mid point of Ai and Aj . Notice
that in order to have its coordinates integer, xi + xj and yi + yj should be
both even. For (xi , yi ) pair there are four boxes, these are (O,O), (O,E),
(E,O), (E,E) where E and O represent even and odd numbers, respectively.
Since there are five points, by the pigeonhole principle, two of them should
be in the same box. Take these two points. Their mid point has integer
coordinates since xi + xj and yi + yj are even numbers.
10.5 Counting Methods: Permutation, Com-

bination and Others
Many counting problems can be put into the following form:
There are n objects. Select r of them (r ≤ n). Then the result depends
on the following questions as given in Table 10.5:
i. Is an item can be reselected? That is, is repetition allowed?
10.5. COUNTING METHODS 111
ii. Is order of items important?

Definition 10.5.1. Let A be any finite set. A permutation σ of A is a
bijection from A to itself.
Remark 10.5.1. If | A | = n, then it is represented as

a1 a2 · · · an
σ= = ai1 ai2 · · · ain
ai1 ai2 · · · ain
where f (aj ) = aij with i, j, ij ∈ { 1, . . . , n }.

Definition 10.5.2. The number of distinct subsets with r elements that can
be chosen
from a set with n elements is called binomial coefficient, denoted
by nr , and is pronounced “n choose r”.
Theorem 10.5.1. For n, r ∈ N, the binomial coefficients satisfy the follow-
ing recurrence relation:
i.
n n
= =1
0 n
ii.
n n−1 n−1
= + for 0 < r < n.
r r r−1
Remark 10.5.2. Note that Theorem 10.5.1 leads to the famous Pascal’s tri-
angle.
1 2 3 4 5 6 7 8 9 10
1 1 1 1 1 1 1 1 1 1 1
2 1 2 3 4 5 6 7 8 9
3 1 3 6 10 15 21 28 36
4 1 4 10 20 35 56 84
5 1 5 15 35 70 126
6 1 6 21 56 126
7 1 7 28 84
8 1 8 36
9 1 9
10 1
The numbers in the first column are the natural numbers. The numbers
in the second and the third columns are called the triangular and tetrahedral
numbers, respectively. The nth triangular number is simply the sum of the
first n integers. The tetrahedral numbers are the sums of the triangular
numbers.
History of binomial coefficients and Pascal’s triangle goes way back than
Pascal. The Pythagoreans considered the triangular numbers around 540
BC. The Greek mathematicians investigated tetrahedral numbers at the be-
ginning of 200 BC. The binomial numbers as coefficients of (a + b)n appeared
in the works of mathematicians in China around 1100. Hindu mathemati-
cians began to encounter the binomial coefficients in combinatorial problems
in 1150s. Pascal puts his triangle in 1665.
Theorem 10.5.2. For n, r ∈ N and r ≤ n,
nr

n n!
= = .
r (n − r)!r! r!
Theorem 10.5.3.
n n
= .
r n−r
Example 10.5.1. Let A be a set with n elements. We want to count the
number of distinct subsets of the set A that have exactly r elements.
Example 10.5.2. Consider { a, b, c, d, e }.
i. How many different words of length 3?
Ans. 5 × 5 × 5 = 53 = 125. Note that each f ∈ A{ 1,2,3 } give a different
word.
ii. How many different words of length 3 if no letter is allowed to repeat?
Ans. 5 × 4 × 3 = 53 = 60. Note that each f ∈ A{ 1,2,3 } where f is an
injection gives a different word.
iii. How many different words of length 3 if the order of letters is not im-
portant?
Ans. There are 53 wordswith order. Each letter combination is counter
3
3! = 6 times. So 53! = 53 = 10
iv. How many different words of length 3 if letters are allowed to repeat
but the order of the letters is not important?
Ans.
aaa bbb ccc ddd eee 1234567
3 - - - - 0001111
2 - 1 - - 0011011
- 1 - 1 1 1011010
2 1 - - - 0010111
10.5. COUNTING METHODS 113
Notice that problemis equivalent to selecting 3 balls out of 5 different

boxes. Hence 5+3−1
3
.
Example 10.5.3. How many bit strings of length n contains exactly r 1’s?
Ans. r positions out of n positions are selected and set to 1. The remain-
ing n− r positions are set to 0. The order of r positions is not important.
So nr .
Example 10.5.4. How many ways are there for 8 men and 5 women to stand
in a line so that no two women stand next to each other?
Ans. There are 9 positions
separated by men so that no two women stand
next to each other. So 95 = 126.
men 1 2 3 4 5 6 7 8
women 1 2 3 4 5 6 7 8 9
Example 10.5.5.
i. How many solutions does the equation x1 + x2 + x3 = 11 have, where
x1 , x2 , x3 ∈ N?
Ans. Note that since 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 = 11 the
pattern 11/1111/11111 which corresponds
to 2+4+5 is a solution. So
11+3−1
the number of solutions is 2
.
ii. The same question with constraint x1 ≥ 1, x2 ≥ 2, x3 ≥ 3?
Ans. Pick 1 of type 1, 2 of type 2, and 3 of type 3. Then there are
5+3−1
additional 5 selections out of 3 item types. So 5
.
Example 10.5.6. How many ways are there to place 10 indistinguishable balls
into 8 distinguishable bins? (Consider atoms. Electrons are indistinguish-
able. The energy levels of an atom are distinguishable.)
Ans. Rephrase the problem as 10 balls and 7 separators. So 10+8−1 7
.
Example 10.5.7. Suppose that S is a set with n elements. How many ordered
pairs (A, B) are there such thatA and B are subsets with A ⊆ B?
Ans. { A, B r A, S r B } is a partition of S. So any a ∈ S should belong
to one of them. Since S is finite, one can list its elements as (s1 , s2 , . . . , sn ).
Let 
0, si ∈ A,

bi = 1, si ∈ B r A,


2, si ∈ S r B.
Then for any (b1 , b2 , . . . , bn ) ∈ { 0, 1, 2 }n , define A = { si | bi = 0 } and B =
{ si | bi = 0 ∨ bi = 1 }, hence A ⊆ B. Notice that we define a bijection
between the set of ternary n-tuples { 0, 1, 2 }n ) and our set of (A, B) pairs.
So the number is equal to the number of ternary n-tuples, that is 3n .
10.6 Supplementary Materials

10.6.1 Some Useful Sequences
A great source of sequences is so called The On-Line Encyclopedia of Integer
Sequences (OEIS) [Slo09]) available at
http://www.research.att.com/∼njas/sequences/Seis.html.
It is a catalog of more than 150000 sequences. It is a great source for com-
binatorics.
Definition 10.6.1. The Stirling number , S(n, k) is the number of ways to
partition a set of cardinality n into exactly k nonempty subsets.
Definition 10.6.2. The nth Bell number , Bn is the number of partitions of
a set with n members, or equivalently, the number of equivalence relations
on it. (Sequence A000110 in [Slo09]). It is named in honor of Eric Temple
Bell.
n

10.6.2 Approximations for n! and r
There is no closed form of n!. Therefore calculating n! for large n is not
easy. It takes to much computation. Some approximations are usually used
instead.
Approximations for n!
Stirling provided an approximation for n! in 1730. Stirling’s approximation
is quite good for n ≫ 1 [Rei67, Mac03]. Even as small values as n = 10, the
error is less than 1%.
n! = 1 × 2 × · · · × n
ln n! = ln 1 + ln 2 + · · · + ln n
Z n
≈ ln xdx = [x ln x − x|n1 = n ln n − n + 1
1
≈ n ln n − n
n
n! ≈ en ln n−n = eln n e−n = nn e−n .
10.6. SUPPLEMENTARY MATERIALS 115
With the next order of correction, it is:
√
n! ≈ nn e−n 2πn
1
ln n! ≈ n ln n − n + ln(2πn).
2
A better approximation is:
√ n n √ n n
2πn e1/(12n+1) < n! < 2πn e1/12n .
e e
n

Approximations for r
n

Using approximations for n!, r
is obtained:

n n!
=
r (n − r)!r!

n
ln = ln n! − ln(n − r)! − ln r!
r
≈ n ln n − n
− ((n − r) ln(n − r) − (n − r))
− (r ln r − r)
= n ln n − (n − r) ln(n − r) − r ln r
= ln nn ln(n − r)(n−r) ln r r
nn
= ln .
(n − r)(n−r) r r

n nn
log2 = log2
r (n − r)(n−r) r r
n(n−r) nr
= log2
(n − r)(n−r) r r
n−r n r
n
= log2 + log2
n−r r
n n
= (n − r) log2 + r log2
n−r r
(n − r) n r n
=n log2 + log2
n n−r n r
!
(n − r) 1 r 1
=n log2 (n−r) + log2 r
n n n
n
!
r 1 r 1
=n 1− log2 r
+ log2 r
n 1− n n n
r
= n H2 .
n
where the binary entropy function, H2 (x), is given as
H2 (x) = −x log2 x − (1 − x) log2 (1 − x)

1 1
= x log2 + (1 − x) log2 .
x (1 − x)

cially [Ros07].
10.7 Problems
Q10 [20 points]

Suppose that S is a set with n elements. How many ordered pairs (A, B) are
there such that A and B are subsets of S with A ⊆ B? [Hint: Show that
each element of S belongs to A, B r A, or S r B.]
Solution.
10.7. PROBLEMS 117
Let A and B subsets of S with A ⊆ B.
∀s ∈ S [s ∈ S] tautology
⇔∀s ∈ S [(s ∈ B) ⊕ (s ∈ S − B)] since B ⊆ S ⇒ S = B ∪ (S − B)
and B ∩ (S − B) = ∅
⇔∀s ∈ S [((s ∈ A) ⊕ (s ∈ B − A)) ⊕ (s ∈ S − B)] since A ⊆ B ⇒ B = A ∪ (B − A)
and A ∩ (B − A) = ∅
Hence, for every s ∈ S there are three mutually disjoint alternatives: s

belongs to either A or B r A, or S r B. Since the choice for different elements
are independent from each other, the result can be found by the rule of
product. The number of ordered pairs is
3| · 3 ·{z· · · · 3} = 3n .
n times
Suppose that S is a set with n elements. How many ordered pairs (A, B)
are there such that A and B are subsets of S with A ⊆ B? [Hint: Show that
each element of S belongs to A, B r A, or S r B.]
Solution.
Let A and B subsets of S with A ⊆ B.
∀s ∈ S [s ∈ S] tautology
⇔∀s ∈ S [(s ∈ B) ⊕ (s ∈ S − B)] since B ⊆ S ⇒ S = B ∪ (S − B)
and B ∩ (S − B) = ∅
⇔∀s ∈ S [((s ∈ A) ⊕ (s ∈ B − A)) ⊕ (s ∈ S − B)] since A ⊆ B ⇒ B = A ∪ (B − A)
and A ∩ (B − A) = ∅
Hence, for every s ∈ S there are three mutually disjoint alternatives: s

belongs to either A or B r A, or S r B. Since the choice for different elements
are independent from each other, the result can be found by the rule of
product. The number of ordered pairs is
3| · 3 ·{z· · · · 3} = 3n .
n times
Q11 [20 points]

Show that a subset of a countable set is also countable.
Solution.
Lat A ⊆ B. If A is finite by definition it is countable.

Suppose A is infinite. We define a bijection from N to A as follows: Since
B is countable there is a bijection from N to B. Using this bijection we can
make a list of elements of B. Use this list, drop all elements that are not in
A. This will be a new list which contains only the elements of A. Define a
function f : N → A as f (n) 7→ an where an is the nth elements of A in the
new list. This is a bijection since for any n ∈ N there is a unique an ∈ A.
and vice versa.
Q12 [20 points]

Definition 10.7.1. A function f : A → A is said to have a fixed point if
there exists x ∈ A such that f (x) = x.
Let A = {1, 2, ....n} for some n ∈ N. How many one-to-one functions

f : A → A have at least one fixed point?
Solution.
The number of one-to-one functions, which have at least one fixed point,
can be computed by subtracting the number of one-to-one functions, which
does not have any fixed points, from the number of all one-to-one functions.
The number of all one-to-one functions f : A → A is n!
A function which does not have any fixed point is a derangement. The
number of derangements of a set with n element is Dn where:

1 1 1 n 1
Dn = n! 1 − + − + .... + (−1) .
1! 2! 3! n!
Hence the answer is n! − Dn

10.7. PROBLEMS 119
Q13 [20 points]

Show that a subset of a countable set is also countable.
Solution.
Let A be a countable set and B be a subset of A.
i) If A is finite, then B should be finite too since |B| ≤ |A|. Hence B is
countable.
ii) If A is not finite, then there exists a bijection f : A −→ N. If B is finite,
it is countable. For infinite B we can list its elements as follows:
b1 = f −1 (min{ f (b) | b ∈ B })
b2 = f −1 (min{ f (b) | b ∈ B − {b1 } })
b3 = f −1 (min{ f (b) | b ∈ B − {b1 , b2 } })
... = .......
bn = f −1 (min{ f (b) | b ∈ B − {b1 , b2 , ....., bn−1 } })
This is equivalent to saying that we are listing B’s elements in the same order
as they are listed by f . Hence, B is countable.
Q14 [20 points]
Solution.
Chapter 11
Recurrence
11.1 Motivation
11.2 Recurrence Equations
11.3 Problems
Q15 [20 points]
Markov chains are powerful models that are often used in Computer Science.
In one application of Markov models is the population dynamics where there
are two types A and B in competition with populations nA and nB where
the total population nA + nB is constant. So if type A increases by one,
type B should decreases by one. Then, the state i of the system can be
represented by the population of A, that is, i = nA . Hence there are N + 1
states represented by 0, 1, · · · , N. If the system is in state i, then it moves
to state i − 1 and i + 1 with probabilities pi,i−1 and pi,i+1 , respectively. Then
with probability 1 − (pi,i−1 + pi,i+1 ) it stays in i. The states 0 and N are
absorbing states. When the system gets in one of these, there is no way to
leave them, i.e. p0,1 = pN −1,N = 0 and p0,0 = pN,N = 1.
Assuming pi,i−1 = pi,i+1 = a, one obtains the following recurrence equa-
tion:
x0 = 0,
xi = axi+1 + (1 − 2a)xi + axi−1 , ∀i 0 < i < N,
xN = 1.
121
122 CHAPTER 11. RECURRENCE
Solve this recurrence relation.
Solution.
The characteristic equation of xi = axi+1 +(1−2a)xi +axi−1 is ar 2 −2ar+a =
0. ar 2 − 2ar + a = a(r 2 − 2r + 1) = a(r − 1)2 . Since r = 1 is the root with
multiplicity 2, the solution would be xi = (β0 + β1 i)r i = β0 + β1 i.
Use boundry conditions to find the values of β0 and β1 .
x0 = 0 = β0 + β1 0 = β0 . So β0 = 0.
xN = 1 = β0 + β1 N = β1 N. So β1 = 1/N.
Finally, the solution is xi = i/N for i = 0, 1, · · · , N.
Q16 [20 points]

Let { an } and { bn } be two sequences whose terms are coupled as
an+1 = α1 an + β1 bn
bn+1 = α2 an + β2 bn
where α1 , α2 , β1 , β2 ∈ R and ∆ = α1 β2 − α2 β1 6= 0.
Solve an and bn when a0 = C and b0 = D.
Solution.
The degenerated case is when α1 = 0 and β1 = 0. In this case the sequences
are not coupled and they are solved separately. That is, an = c1 α1n and
bn = c1 β2n .
Consider the non-degenarated case. Assume β1 6= 0. Then
1
bn = (an+1 − α1 an ) (11.1)
β1
1
bn+1 = (an+2 − α1 an+1 ). (11.2)
β1
Substituting bn and bn+1 into the second relation, we obtain
0 = bn+1 − α2 an − β2 bn
1 β2
⇒0 = (an+2 − α1 an+1 ) − α2 an − (an+1 − α1 an )
β1 β1
⇒ 0 = (an+2 − α1 an+1 ) − β1 α2 an − β2 (an+1 − α1 an )
⇒ 0 = an+2 + (−α1 − β2 )an+1 + (−α2 β1 + α1 β2 )an
11.3. PROBLEMS 123
Let A1 = −α1 − β2 and A0 = −α2 β1 + α1 β2 . Then an+2 + A1 an+1 + A0 an = 0.

By change of index an + A1 an−1 + A0 an−2 = 0. Use characteristic root
technique to solve an . Once an is obtained as an = f (an−1 , an−2 ), use Eq 11.1.
Q17 [20 points]
Solution.
124 CHAPTER 11. RECURRENCE
Part VI
Graphs
125
Chapter 12
Graphs
12.1 Introduction
Graph is a very powerful representation used in many disciplines including
Computer Science, Management, Physics and of course Mathematics. Inter-
actions, relations of objects are usually represented by a graph.
On the other hand, graphs are used for social entertainment. Remember
questions such as “can you draw this without removing your pencil from the
paper” as in Fig. 12.1.
Example 12.1.1. Consider www, web pages and links. A web page has links
to other web pages. A web page a can have many links to page b but there
may be no link from b to a. Your web page probably have a link to google.com
but you would be very lucky if home page of google.com has a link to your
web page.
Figure 12.1: Envelope
127
128 CHAPTER 12. GRAPHS
A web page can have a link to an item in itself. Long web pages have
internal links to headings in it.
12.2 Graphs
Definition 12.2.1 (Multigraph).
A Multigraph G = ( V, A, ϕ ) consists of a nonempty set V of vertices, a set
A of arcs and a function ϕ : A → V × V
Remark 12.2.1.
• V is nonempty but A could be empty. So, a single vertex with no arcs is
the most simple graph.
• arcs will be denoted by Greek letters.
−−−→
• arc −
→
α = (u, v) if ϕ(−
→α ) = (u, v).
• Function ϕ is in general not an injection. So it is possible that ϕ(−
→
αi ) =
ϕ(−
→
αj ) = (u, v) for −
→
αi 6= −
→. Hence, two vertices can be connected more
α j
−−−→
than once, and therefore (u, v) representation of arcs becomes ambiguous.
Definition 12.2.2 (Multiplicity).

Multiplicity of (u, v) = | ϕ−1 ((u, v)) |.
Definition 12.2.3 (Simple Graph).

A simple graph is a multigraph G = ( V, A, ϕ ) such that ϕ is an injection.
Remark 12.2.2. Multiplicity of any ordered pair (u, v) is at most 1. Therefore

(u, v) is sufficient to denote the arc. Hence a simple graph can be represented
as G = (V, ϕ) where ϕ is a relation on V .
Remark 12.2.3. A multigraph G can be represented as G = (V, ϕ) where V
is the vertex set, ϕ : V × V → N is the function expressing the multiplicity
of (v1 , v2 ).
Example 12.2.1.
α1
  path: α1 α3 α2
1 2 1 0 0
v1 gs 0 0 1 0 0 simple path: α4 α2 α1 α5
α6 α2
  elementary: α6 α4
1 0 0 0 0
α5  
α3 0 0 0 0 1 circuit: α3 α2
v2 w 3
' v3 0 0 0 0 0 loop: α1
α4
v4 α7 + v5
12.2. GRAPHS 129
Definition 12.2.4 (Path).

−−−→
Let G = ( V, A, ϕ ) be a multigraph. Given an arc (u, v) ∈ A, u is called the
origin, v is called terminus. A path P of G is a sequence of arcs − →−
α →
0 α1 . . .
such that for every pair, αi , αi+1 , the origin of αi+1 is the terminus of −
−
→ −−→ −−→ →
αi .
Definition 12.2.5.
arc a simple path
A path which does not traverse the same twice is called
vertex an elementary path
.
Definition 12.2.6. Circuit is a finite path such that the origin of the first
one coincides with the terminus of the last.
Definition 12.2.7. Simple circuit is a circuit which is a simple path.
Question 12.2.1. Define elementary circuit.
Definition 12.2.8. The number of arcs in a finite path is called the order
of the path.
Definition 12.2.9. A circuit of order 1 is called loop.
12.2.1 Reachability and Strong-Connectedness

∆
Definition 12.2.10. v is said to be reachable from u ∈ G = ( V, A, ϕ ) ←→
u = v or there is a path from u to v.
Definition 12.2.11. Simple graph G∗ associated with G is the simple graph

obtained by eliminating all but one of the arcs if the multiplicity is more
than 1.
Remark 12.2.4.
i. Connection array MG∗ of G∗ has only 0s and 1s.
ii. [MG∗ ]ij = 1 means there is an arc from vi to vj .
Definition 12.2.12. Power of a relation on A.

(
ρρk−1 k > 1,
ρk =
ρ k = 1.
Remark 12.2.5.
• Mρk+1 = Mρ Mρk = (Mρ )k+1
• ρρk = ρk ρ
Theorem 12.2.1. Let G = ( V, ρ ) be a simple graph describing ρ.
There is a path of order n from u to v ←→ (u, v) ∈ ρn .
Remark 12.2.6. Given a simple graph G = ( V, ρ ), the array (Mρ )k describes

the relation on V : “there is at least one path of order exactly k”. In other
words, [(Mρ )k ]ij = 1 ←→ there is at least one path of order k from vi to vj .
Reachability for G∗ = ( V, ρ ) can be obtained by Algorithm 2 where
| V | = n.
Algorithm 2: Reachability
Input: Dividend n > 0 and divisor d > 0
Output: Quotient q and remainder r, 0 ≤ r < d
/* reachability for G∗ = (V, ρ) */
/* where | V | = n */
1 begin
2 M(G) ← Mρ
3 for k = 2 to n − 1 do
4 M(G) = M(G) + Mρk
5 end
6 end
Definition 12.2.13. G is a multigraph and G∗ is the associated simple

graph.
The reachability array M(G) of G is defined as
(
1, there is at least one k for which [Mρk ]ij = 1 where 1 ≤ k ≤ n − 1,
[M(G)]ij =
0, otherwise.
Remark 12.2.7. [M(G)]ij = 1 ←→ there is a path from vi to vj in G.
∆
Definition 12.2.14. A multigraph is said to be strongly connected ←→
there is a path from vi to vj for all vi , vj ∈ V .
12.2. GRAPHS 131
Definition 12.2.15. G = [V, A, ϕ] is a multigraph, { V1 , V2 } dichotomy of

V . The set of arcs from vertices of V1 to vertices of V2 is called the cut-set
of G relative to the dichotomy { V1 , V2 }.
Example 12.2.2.
a)Is it strongly connected? No, there is no way to v1 .
v1  
1 |||
| 3 0 1 0 1
||
8 2
0 0 0 1
~|| MG∗ = 
v2X Bs /3' v4 0 1 0 0
BB 4 |
BB 5 9 ||| 0 1 1 0
B |
6 BB |
~|w | 10
7
v3 M(G) = MG∗
    
0 1 0 1 0 1 0 1 0 1 0 1
0 0 0 1 0 0 0 1 0 0 0 1

MG2 = ∨ 
0 1 0 0  0 1 0 0 0 1
 0 0
0 1 1 0 0 1 1 0 0 1 1 0
     
0 1 0 1 0 1 1 1 0 1 1 1
0 0 0 1  0
  1 1 0  0
  1 1 1
=
0 ∨ = 
1 0 0  0 0 0 1  0 1 0 1
0 1 1 0 0 1 0 1 0 1 1 1
    
0 1 1 1 0 1 0 1 0 1 1 1
0 1 1 1 0 0 0 1 0 1 1 0

MG3 = ∨ 
0 1 0 1  0 1 0 0 0 0
 0 1
0 1 1 1 0 1 1 0 0 1 0 1
     
0 1 1 1 0 1 1 1 0 1 1 1
0 1 1 1  0
  1 0 1  0
  1 1 1
=
0 ∨ = 
1 0 1  0 1 1 0  0 1 1 1
0 1 1 1 0 1 1 1 0 1 1 1
 
0 1 1 1
0 1 1 1
MG∗ = ... = 
0
 not strongly connected.
1 1 1
0 1 1 1
b) use V0 = { { v1 , v4 } , { v2 , v3 } } as an example.
Then the cut-set relative to V0 is { α1 , α8 , α9 , α10 }.
Example 12.2.3.
Theorem 12.2.2. G = [V, A, ϕ] is strongly connected ←→ for every di-

chotomy { V1 , V2 }, the cut-set is non empty.
12.2. GRAPHS 133
, 0/1
1/0 q0 l
GFED
@ABC q
, GFED
@ABC
1
Y
1/0
1/1 0/0
q2 t
GFED
@ABC
T
0/0
Figure 12.2: State transition diagram
Figure 12.3: Linked list
12.2.2 Application of Multigraphs
• Graphs are used to represent state transition of finite state machines

Fig. 12.2.
• Many data structures are represented as graphs Fig. 12.3, Fig. 12.4, Fig. 12.5.
• Some other systems are also represented by graphs Fig. 12.6.
• Computer networks
• Interconnecting networks
• Parallel architectures
• Graph algorithms
Figure 12.4: B-tree

Figure 12.5: Circular queue
Figure 12.6: Flow chart

12.3. UNDIRECTED GRAPHS 135
12.3 Undirected Graphs

If the relation is symmetric: • h (
• ≡ • •
Definition 12.3.1 (Multiple undirected graph).
A multiple undirected graph G = ( V, E, ϕ ) consists of a set V of vertices, a
set E of edges and a function ϕ from E to the set of unordered pairs in V .
Notation. If ϕ(α) =< u, v > we write (u, v).
Definition 12.3.2. For (u, v) ∈ E, u and v are called terminals.
Definition 12.3.3. A chain is a sequence of edges (v0 , v1 )(v1 , v2 )(v2 , v3 ) · · · (vn−1 , vn ).

A simple chain if no edge is repeated.
An elementary chain if no vertices is repeated.
A cycle if v0 = vn
A simple cycle ≡ simple chain + cycle.
∆
Definition 12.3.4. G = ( V, E, ϕ ) is connected ←→ ∀v1 , v2 ∈ V [there is
a chain between v1 and v2 ].
Definition 12.3.5. Let G be an undirected graph. The corresponding ad-

joint multigraph, GA , is obtained by replacing each edge by a pair of opposite
arcs.
Definition 12.3.6 (Subgraph).

G′ = ( V ′ , E ′ , ϕ′ ) is called a subgraph of G = ( V, E, ϕ ) if V ′ ⊆ V , E ′ ⊆ E
and E ′ consists of all the edges in E joining vertices in V ′ . If E ′ is a subset
of all the edges in E joining vertices in V ′ , then G′ is called partial subgraph.
Definition 12.3.7. A component G′ of G is a connected subgraph such that

no vertex in V ′ is connected to a vertex in V \ V ′ in G.
Theorem 12.3.1. Let G be an undirected multigraph.

G is connected
←→ GA is strongly connected.
←→ “something similar to cut-set theorem”.
←→ G has only one component.
Theorem 12.3.2. A connected undirected simple graph with | V | = n ≥ 1,

must have at least n − 1 edges.
Definition 12.3.8. Let G = ( V, E, ϕ ) be connected. A vertex v is called a

cut-point if the subgraph obtained by deleting it is not connected.
Theorem 12.3.3. v is a cut-point ←→ there exist vertices u and w such
that every chain connecting u and w passes through v.
Example 12.3.1. i. A simple chain which is not an

1 elementary chain: 4, 9, 11, 10, 5.
a NNN
?>=<
89:; 89:;
?>=<
b
NNN 2
ppppp ii. A simple cycle: 9, 10, 11 or 1, 6,
NN pp
3 4NNN
NNN pp5
p 6 13, 12, 3.
ppp
NN ppp iii. Is G connected? Yes.
c
89:;
?>=< 7 89:;
?>=<
d= 8 e
89:;
?>=<
== iv. How many components does G
=
9 10== have? 1.
==

f
@ABC
GFED 11 g
89:;
?>=<
12 13
89:;
?>=<
h
Example 12.3.2. Show that a finite graph with n vertices is connected ←→

every pair of vertices is connected by a chain of order ≤ n − 1.
⇒ part: G = [V, E, φ] is connected, then there is a chain between u and

v. We need to show that the order of the chain ≤ n − 1. Suppose the or-
der ≥ n. Then a vertex is repeated in the chain, hence the chain contains a
cycle. Remove the cycle. This process can be repeated until the order ≤ n−1.
⇐ part: If every vertex pair is connected, then by definition G is con-

nected.
∆
Definition 12.3.9. A simple undirected graph is said to be bipartite ←→
its vertices can be partitioned into two disjoint sets V1 and V2 so that every
edge has one terminal vertex in each.
Theorem 12.3.4. G is bipartite ←→ there is a cut-set which contains all
the edges.
Proof. ⇒ part: G is a bipartite, then use V1 and V2 , each edge has one
terminal in V1 and other in V2 . ⇒ the cut-set of V1 , V2 contains all the edges.
⇐ part: All the edges in the cut-set of V1 , V2 ⇒ each edge has one terminal
12.4. PATH PROBLEMS 137
vertex in V1 , the other in V2 . ⇒ G is bipartite.
Remark 12.3.1.
a.= 1 Applications of bipartite graphs

..== • classical 3 house, 3 utility problem
.. ===
. =
.. = • optimum matching problems
b == ... 2 • heterosexual relations
== .
===...
=
c 3

d
12.4 Path Problems

Definition 12.4.1. For a multigraph G:
indegree terminate
of a vertex v is the number of axes on v.
outdegree originated
Definition 12.4.2. For an undirected multigraph G, degree of a vertex v is
the number of edges incident on v.
Definition 12.4.3. isolated vertex is a vertex of degree 0.

Eularian chain
Definition 12.4.4. An an undirected multigraph is a
Eularian cycle
chain
that uses every edge once and only once.
cycle
Theorem 12.4.1. An undirected multigraph without isolated vertices has an
Eulerian cycle ←→ it is connected and contains no vertices of odd degree.
Theorem 12.4.2. G = [V, E, ϕ] without isolated vertices has an Eulerian

chain ←→ it is connected and contains exactly two vertices of odd degrees.
Hamilton path path
Definition 12.4.5. An in a multigraph is a
Hamilton circuit circuit
which passes through each of the vertices exactly once.
Definition 12.4.6. A multigraph is complete if every point of vertices is

joined by at least one arc.
Theorem 12.4.3. Every complete multigraph contains a Hamiltonian path.
shortest path algorithm pp77. Read 2.4.1, 2.4.2, 2.4.3
Question
P 12.4.1. G =P[V, A, α]. d+ (v) = indegree(v), d− (v) = outdegree(v).
Show v∈V d+ (v) = v∈V d− (v) = | A |.
Theorem 12.4.4. There is even number of vertices which have odd degrees
in an undirected multigraph.
12.5 Planarity and Coloration

Application. Consider printed circuit boards (PCB) used in electronic de-
vices. Legs of integrated circuits (IC) are electrically connected by means
of channels of the PCB. While channel run on PCB, they should not cross
each other. If they do, short circuits occur. So drawing channels without
crossing each other becomes an importing issue. Very same problem occurs
in the integrated circuit production. In this case electronic components such
as resistors, transistors are structures on a silicon wafer. There is channels
on silicon to connect them electrically. This is problem can be converted to
the problem of drawing a graph on a plane or planarity of graphs.
Definition 12.5.1. A finite undirected multigraph is planar if it can be
drawn on a plane in such a way that no two of its edges intersect except,
possibly, at vertices.
Definition 12.5.2. An undirected multigraph G = (V, E, ϕ) is said to be
∆
n-colorable ←→ ∃f, f : V → { 1, 2, . . . , n } such that if (u, v) ∈ E then
f (u) 6= f (v).
Theorem 12.5.1 (The Four-color Theorem).
Every planar graph is 4-colorable.
Definition 12.5.3. Minimum number n for which an undirected multigraph
is n-colorable is called the chromatic number of the graph.
Theorem 12.5.2. If the maximum degree of vertices is n, then the chromatic
number is less than or equal to n + 1.
12.6. TREE 139
Theorem 12.5.3. An undirected multigraph is 2-colorable ←→ it contains

no cycles of odd length.
Theorem 12.5.4. A tree is 2-colorable.
Definition 12.5.4. Let G be a connected planar graph. A region of G is

a domain of the plane surrounded by edges of the graph such that any two
points in it can be joined by a line not crossing any edge. The edges touching
a region contain a simple cycle called the contour of the region. Two regions
are said to be adjacent if the contours of the two regions have at least one
edge in common.
Theorem 12.5.5 (Euler Formula).

If a connected planar graph has ν vertices, e edges and r regions then ν − e +
r = 2.
Theorem 12.5.6. If G is a connected simple graph without loops, and has

ν vertices, e edges and r regions,
then 23 r ≤ e ≤ 3ν − 6.
K3,3 K5
Theorem 12.5.7 (Kuratowski).

An undirected multigraph is planar
←→ it contains no partial subgraphs of either K3,3 or K5 .
12.6 Tree
Definition 12.6.1. A tree is a connected undirected graph with no cycles.
A tree of an isolated vertex is called degenerated tree.
Theorem 12.6.1. Let G = [V, E, α] and G is a nondegenerated tree.

←→ every pair of vertices is connected by one and only one chain
←→ G is connected but deletion of an edge makes it disconnected

←→ G has no cycles and if an edge is added, one and only one cycle is
formed.
Theorem 12.6.2. A nondegenerated tree contains at least two vertices of
degree 1.
Theorem 12.6.3. G = [V, E, α] with | V | = n ≥ 1
G is a tree
←→ G contains no cycle and has n-1 edges
←→ G is connected and has n-1 edges
Definition 12.6.2 (Spanning Tree).

A spanning tree of a connected undirected graph G = [V, E, α] is a tree
′ ′ ′ ′
T = [V, E , α] where E ⊆ E and α is the restriction of α to E .
Remark 12.6.1. There may be many spanning trees for G.

Definition 12.6.3. A minimal spanning tree is a spanning tree which has
minimum number of edges.1
12.6.1 Minimal Spanning Tree Algorithm
Algorithm 3: The Minimal Spanning Tree Algorithm

1 begin
/* minimal spanning tree algorithm here */
2 end
12.6.2 Rooted Tree

Definition 12.6.4. A rooted tree R is a directed graph obtained by specifying
as the root a special vertex v and each chain between v and some u is replaced
by a path from v to u. The order of the path from v to u is called the level
of u. For every arc (− u,−→
w), u and w are a predecessor-successor pair. Any
vertex whose outdegree is 0 is called a leaf .
1
@HB correct this
12.6. TREE 141
Remark 12.6.2. Rooted trees are classical representations for hierarchical

structures.
• organization charts
• procedures in programming languages
• algebra of commutative operations
• scope of variables in procedural programming languages
Definition 12.6.5. An oriented rooted tree is a rooted tree such that the set
of arcs issuing from any vertex is an ordered set.
Representation
Example 12.6.1. Huffmann coding s

a coding technique which is optimum
in mean coding length.

cially [PY73, Ros07, TZ82, Gal89].
12.7 Problems
Q18 [20 points]
P
Suppose d1 , d2 , . . . , dn ∈ Z+ with ni=1 di = 2n − 2. Show that there is a tree
that has n vertices with degree sequence d1 , d2 , . . . , dn .
Solution.
Note that ∀i [di > 0]. Use induction on the number of vertices n.
Case n = 1. Since 2n − 2 = 0, the degree sequence is d1 = 0 only. A
degenerated tree with one vertex satisfies the proposition. Note that d1 = 0
does not actually satisfy the rule that di > 0. So the question should have
one more condition such as n > 1. Hence induction should start from n = 2.
Induction Base. n = 2. Since 2n − 2 = 2, the degree sequence can only
be d1 = 1, d2 = 1. A tree with 2 vertices connected by an edge satisfies it.
Induction. Assume that it is true for n ≥ 2. Then show that is must be
true for n + 1.
Consider a degree sequence d1 , d2 , . . . , , dn , dn+1 . If we can show that
there exist vertices vk of degree dk = 1 and vℓ of degree dℓ > 1, then we
can construct such tree as follows: Reindex d1 , d2 , . . . , dn−1 , dn , dn+1 so that
we have dn > 1 and dn+1 = 1. Hence, dn − 1 > 0. By induction hypotesis,
there exists a corresponding tree T with n vertices for the degree sequence
d1 , d2 , . . . , dn−1 , dn − 1. Obtain a new tree T ′ by add vertex vn+1 to T by
connecting vn+1 to vn . The degree sequence of T ′ becomes d1 , d2, . . . , , dn −
1 + 1, dn+1 = 1.
Existence P
P of dk = 1. Suppose ∀i ∈ { 1, 2, P.n. . , n } [di > 1]. Then di ≥ 2,
n n
so i=1 di ≥ i=1 2 = 2n > 2n − 2. Since i=1 di = 2n − 2, there must be
at lease one vertex with dk < 2, that is dk = 1. Pn
Pn Existence of d ℓ > 1. Suppose
Pn ∀i ∈ { 1, 2, . . . , n } [d i = 1]. Then i=1 di =
i=1 1 = n < 2n − 2. Since i=1 di = 2n − 2, There must be at lease one
vertex with dk > 1.
Q19 [20 points]

Let G = [V, E] be a simple, undirected and connected graph which does not
contain any self-loops. Prove that G is a bipartite graph if and only if G
12.7. PROBLEMS 143
does not contain any cycle of odd length.
Solution.
(⇒ Part) Let G = [V, E] be a loop-free simple, undirected, connected and

bipartite graph with V = V1 ∪ V2 .
Let C = {{v1 , v2 }, {v2 , v3 }, {v3 , v4 }, . . . , {vn , v1 }, } be a cycle in G. Let v1 ∈
V1 . (The proof for v1 ∈ V2 is similar.) Since G is a bipartite graph vi and vi+1
must belong to different sets V1 and V2 . Hence, the sequence v1 −v2 ....−vn −v1
is an alternating sequence between the edges of V1 and V2 . For this sequence
to start and end with the same vertex there must be odd number of vertices
in this sequence. Hence, the number of edges on C must be even.
(⇐ Part) Let G = [V, E] be a loop-free simple, undirected and connected

graph with no cycles of odd length. Let x ∈ V , and
V1 = {v ∈ V | the length of a shortest path between x and v is odd} and
V2 = {w ∈ V | the length of a shortest path between x and w is even}.
Note that
i) x ∈ V2
ii) V1 ∩ V2 = ∅
iii) V1 ∪ V2 = V
Claim: each edge {a, b} ∈ E has one vertex in V1 and the other vertex in V2 .
To prove this claim suppose that there exists an edge e = {a, b} ∈ E
with a 6= b and a, b ∈ V1 . (The proof for a, b ∈ V2 is similar) Let Ea =
{{a, v1 }, {v1 , v2 }, . . . , {vm−1 , x}} be the m edges in a shortest path from a to
x and let Eb = {{b, v1 ′ }, {v1 ′ , v2 ′ }, . . . , {vn−1 ′ , x}} be the n edges in a shortest
path from b to x. m and n are both odd since a, b ∈ V1 .
If {v1 , v2 , . . . , vm−1 } ∩ {v1 ′ , v2 ′ , . . . , vm−1 ′ } = ∅, then the set of edges C1 =
{{a, b}} ∪ Ea ∪ Eb is a cycle of odd length in G.
Otherwise, let w(6= x) be the first vertex where the paths come together and
let
C2 = {{a, b}}∪{{a, v1 }, {v1 , v2 }, . . . , {vi, w}}∪{{b, v1 ′ }, {v1 ′ , v2 ′ }, . . . , {vj ′ , w}}
for some 1 ≤ i ≤ m − 1 and 1 ≤ j ≤ n − 1.
Then either C2 or C1 − C2 is a cycle of odd-length in G.
Q20 [20 points]
Solution.
Bibliography
[Apo] Tom M. Apostol. Introduction to Analytic Number Theory.

Springer-Verlag.
[Gal89] Steven Galovich. Introduction to Mathematical Structures. Har-

court Brace Jovanovich, Inc., 1989.
[GKP98] Ronald L. Graham, Donald E. Knuth, and Oren Patashnik. Con-

crete Mathematics: A Foundation for Computer Science. Addison-
Wesley, 1998.
[Hol60] Paul Holmos. Naive Set Theory. Van Nastrand, 1960.
[LP98] Rudolf Lidl and Gunter Pilz. Applied Abstract Algebra. Springer,
1998.
[Mac03] David MacKay. Information Theory,Inference, and Learning. Cam-

bridge University Press, 2003.
[Men08] Eliott Mendelson. Number Systems and the Foundation of Analysis.

Dover, 2008.
[Nes09] Ali Nesin. Mathematige Giris: III. Sayma. Nesin Yayincilik, 2009.
[PY73] Franco P. Preparata and Raymond T. Yeh. Introduction to Discrete

Structures. Addison-Wesley, 1973.
[Rei67] Frederick Reif. Berkeley Physics: Statistical Physics. McGraw-Hill,

1967.
[Ros07] Kenneth H. Rosen. Discrete Mathematics and its Applications.

McGraw-Hill, 2007.
145
146 BIBLIOGRAPHY
[Slo09] N. J. A. Sloane. The On-Line Encyclopedia of Integer Sequences

(OEIS), 2009.
[Str94] Steven H. Strogatz. Nonlinear Dynamics and Chaos. Perseus Books

Publishing, 1994.
[TZ82] Gaisi Takeuti and Wilson M. Zaring. Introduction to Axiomatic

Set Theory. Springer-Verlag, 1982.
[Wik09] Wikipedia. Mersenne Prime, 2009.

BIBLIOGRAPHY 147
.
148 BIBLIOGRAPHY
The Notation Index
(a1 , a2 ), 21 { a1 , a2 , . . . }, 19
(a1 , a2 , . . . , an ), 21
A = B, 20 { a , P (a) }19
AΓE30F B, 23 A, 19
A ∩ B, 22
A ∪ B, 22 B, 19
A 6= B, 20
A ⊕ B, 23
A ⊂ B, 20
A ⊆ B, 20
A × B, 21
An , 21
A1 × A2 × · · · × An , 21
∅, 19
| A |, 20
C, 6
N, 6
Q+ , 6
Q− , 6
Q≥0 , 6
Q≤0 , 6
Q, 6
R+ , 6
R− , 6
R≥0 , 6
R, 6
Z+ , 6
Z− , 6
Z≥0 , 6
Z≤0 , 6
Z, 6
A, 23
a ∈ A, 19
a∈ / A, 19
A
2 , 20
THE CONCEPTS INDEX 149
The Concepts Index
Ba , 26 antisymmetric, 5
F , 12
M ⊤ , 26 bi-implication, 15
Mα , 24 biconditional statement, 14
Mβ ⊙ Mα , 25 bijection, 28
T , 12 binary relation, 24
[M]ij , 24 boolean n-tuple, 13
α−1 , 26 boolean domain, 13
β ◦ α, 25 cardinality, 20
f : A → B, 27 Cartesian product, 21
B A , 27 codomain, 27
∃xφ(x), 11 complement, 23, 26
∀xφ(x), 11 composition, 25
p̄, 14 compound propositions, 14
B, 13 concept, 19
Z+ , 5 conclusion, 15
¬p, 14 conditional statement, 14
α, 26 conjunction, 14
φ ←→ ψ, 12 constant-False, 14
a α b, 24 constant-True, 14
p ⇐⇒ q, 17 contingency, 16
p ←→ q, 14 contradiction, 16
p −→ q, 14 contrapositive, 15
p ∧ q, 14 converse, 15
p ∨ q, 14
p ≡ q, 17 difference, 23
p ⊕ q, 14 disjoint, 23
=, 21 disjunction, 14
cod f , 27 domain, 27
dom f , 27 dyadic, 13
ran f , 27
element, 19
=⇒ , 11 empty set, 19
equal, 20, 21
a=b, 12 equivalent, 15
150 BIBLIOGRAPHY
even, 5 power set, 20

exclusive or, 14 product, 25
existentially, 11 proper subset, 20
extension, 28 proposition, 12
propositional operator, 13
f, 26
f(a), 27 range, 27
f(C), 27 reflexive, 5
finite, 20 relation
function, 26 boolean matrix multiplication,
partial, 26 25
complement, 26
hypothesis, 15 composition, 25
inverse, 26
identity, 14
transpose, 26
if-and-only-if, 15
restriction, 28
iff, 15
implication, 15 set, 19
infinite, 20 a ∈ A, 19
injection, 28 a∈/ A, 19
intersection, 22 disjoint, 23
inverse, 15, 26 element, 19
membership, 19
logically equivalent, 12, 17 representation, 19
set, 19
membership, 19
set operations
monadic, 13
complement, 23
negation, 14 difference, 23
negation of p, 14 intersection, 22
new concept, 5 symmetric difference, 23
not equal, 20 union, 22
subset, 20
odd, 5 surjection, 28
ordered n-tuple, 21 symmetric, 5
ordered pairs, 21 symmetric difference, 23
partial function, 26 tautology, 16

permutation, 28 transitive, 5
power of a set, 21 transpose, 26
THE CONCEPTS INDEX 151
truth table, 13
truth value, 12
union, 22
universally, 11
unordered n-tuple, 19
well-formed formula (wff), 10

Discrete Mathematics: Haluk Bingol February 21, 2012

Uploaded by

Copyright:

Available Formats

Discrete Mathematics: Haluk Bingol February 21, 2012

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Discrete Mathematics: Haluk Bingol February 21, 2012

Uploaded by

Copyright:

Available Formats

Discrete Mathematics

February 21, 2012

3 Sets, Relations, and Functions 21

5 Partial Ordering, Lattice 47

10.5 Counting Methods . . . . . . . . . . . . . . . . . . . . . . . . 110

Note that in plain English we use the form “A is called B if A satis-

1.3 Similar statements

In order to emphasize the differences of such cases the following notation

1.4 Set of Numbers

“Bertrand Russell Mathematica OR Kurt -philosopher”

2.2.1 Well-formed formula

Definition 2.2.1 (well-formed formula (wff)).

2.2.2 Logical Axioms

2.2.3 Rules of Inference

Definition 2.2.2 (Logically Equivalence).

2.3 Propositional Logic

Notation. Propositions are represented by lower case letters such as p, r, q.

2.3.1 Compound Propositions

Table 2.1: Boolean functions of one variable

Table 2.2: Boolean functions of two variables

Definition 2.3.3. An n-operand truth table is a table that assigns a boolean

Definition 2.3.10. Two compound propositions φ(x1 , x2 , . . . , xn ) and ψ(x1 , x2 , . . . , xn )

Remark 2.3.5. The biconditional, p ←→ q, is an operator. The equivalence

Definition 2.3.11. Let p −→ q.

Translating English sentences

of the rest of the story which can be represented as q(p1 , p2 , . . . , pn ). In

Boolean search. Search in web.

2.4 Propositional Equivalence

Table 2.3: The laws of logic

Definition 2.4.2 (Logically Equivalence).

Acknowledgment. These notes are based on various books but especially

b) Using rules of inference provide a formal proof for

1. ∀x [S(x) ∨ Q(x)] Premise

Sets, Relations, and Functions

Remark 3.1.1. We do not define set, element, and membership properly.

Definition 3.1.2. The empty set, denoted ∅, has no elements in it.

Example 3.1.2. { 1, 2, 3 } = { 2, 1, 3 }. Order of elements is not important.

Definition 3.1.4 (Subset).

Remark 3.1.4. This definition of infinity needs elaboration.

Definition 3.1.6 (Power Set).

Definition 3.1.8 (Cartesian Product).

3.1.2 Set Operations

(a) Union. (b) Intersection.

(c) Set difference. (d) Symmetric set differ-

Figure 3.1: Set operations.

Remark 3.1.7. Set operations can be visualized by Venn diagrams as in

Definition 3.1.13. Let C = { A1 , A2 , . . . , An } be a collection of sets.

Definition 3.1.15 (Set Difference).

Definition 3.2.1 (Matrix). An array of numbers with n rows and m columns

Using the orderings of

3.2.1 Composition of Relations

Remark 3.2.5. Binary matrix

Theorem 3.2.2 (Associativity).

Corollary 3.2.3 (Associativity).

Definition 3.2.5 (Inverse of a Binary Relation). The inverse of a binary

Definition 3.2.6. The transpose of a matrix, denoted by M ⊤ , is defined as

Theorem 3.2.4. Mα−1 = (Mα )⊤ .

Theorem 3.2.5. [α ◦ β]−1 = β −1 ◦ α−1 .

Theorem 3.2.6. Mᾱ = 1 − Mα where 1 is matrix of all 1s.