Introduction to

Discrete Mathematics:
Computer Science

Ham Karim
Department of Mathematics
Royal University of Phnom Penh

Giving lecture at the Institute of Technology of Cambodia (ITC)

October 13, 2011

ii

© 2011 by Ham Karim

Permission is granted to copy, distribute and/or modify this document under the
terms of the GNU Free Documentation License, Version 1.2 or any later version
published by the Free Software Foundation; with no Invariant Sections, no Front-
Cover Texts, and no Back-Cover Texts. A copy of the license is included in the
appendix entitled “GNU Free Documentation License”.

A current version can always be found via abstract.pugetsound.edu.

 Contents

1 LOGIG and PROOFS 1

1 Logic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1 Propositions, connectives . . . . . . . . . . . . . . . . . . . . 1
1.2 Truth table . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3 Tautology, Contradiction, Contingency . . . . . . . . . . . . . 3
1.4 Logical Equivalence . . . . . . . . . . . . . . . . . . . . . . . 4
1.5 Formulas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.6 Gates of Formulas . . . . . . . . . . . . . . . . . . . . . . . . 8
1.7 Predicates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.8 Quantifiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.9 Generalized De Morgan Laws . . . . . . . . . . . . . . . . . . 11
2 Proofs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.1 Mathematical Systems . . . . . . . . . . . . . . . . . . . . . . 11
2.2 Methods of Proof . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.3 Arguments, Rules of Inference . . . . . . . . . . . . . . . . . . 13

2 Language of Mathematics 19
1 Set Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.1 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.2 Venn Diagrams . . . . . . . . . . . . . . . . . . . . . . . . . . 20
1.3 Set Operations . . . . . . . . . . . . . . . . . . . . . . . . . . 20
1.4 Counting with Venn Diagrams . . . . . . . . . . . . . . . . . 22
1.5 Properties of Sets . . . . . . . . . . . . . . . . . . . . . . . . . 23
1.6 Generalized Union and Intersection . . . . . . . . . . . . . . . 24
1.7 Partitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
1.8 Ordered Pairs, Cartesian Product . . . . . . . . . . . . . . . . 24
2 Sequences and strings . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.1 Sequences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.2 Sum and Product Notation . . . . . . . . . . . . . . . . . . . 27
2.3 Strings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3 Relations and properties of relations . . . . . . . . . . . . . . . . . . 27
4 Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
4.1 Correspondences . . . . . . . . . . . . . . . . . . . . . . . . . 27

iii
iv

4.2 Representations of Relations . . . . . . . . . . . . . . . . . . 28

4.3 Inverse Relation . . . . . . . . . . . . . . . . . . . . . . . . . 29
4.4 Composition of Relations . . . . . . . . . . . . . . . . . . . . 29
4.5 Properties of Binary Relations . . . . . . . . . . . . . . . . . 30
4.6 Partial Orders . . . . . . . . . . . . . . . . . . . . . . . . . . 30
4.7 Hasse diagrams . . . . . . . . . . . . . . . . . . . . . . . . . . 31
4.8 Equivalence Relations . . . . . . . . . . . . . . . . . . . . . . 31
4.9 Equivalence Classes, Quotient Set, Partitions . . . . . . . . . 31
5 Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
5.1 Types of Functions . . . . . . . . . . . . . . . . . . . . . . . . 34
5.2 Identity Function . . . . . . . . . . . . . . . . . . . . . . . . . 34
5.3 Function Composition . . . . . . . . . . . . . . . . . . . . . . 34
5.4 Inverse Function . . . . . . . . . . . . . . . . . . . . . . . . . 35
5.5 Operators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

3 Counting Methods 37
1 Mathematical induction . . . . . . . . . . . . . . . . . . . . . . . . . 37
1.1 Principle of Mathematical Induction . . . . . . . . . . . . . . 37
1.2 Strong Form of Mathematical Induction . . . . . . . . . . . . 39
1.3 The Well-Ordering Principle . . . . . . . . . . . . . . . . . . 39
2 Recurrence Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
2.1 First Order Recurrence Relations . . . . . . . . . . . . . . . . 40
2.2 Second Order Recurrence Relations . . . . . . . . . . . . . . . 41
3 Basic Principle of Counting . . . . . . . . . . . . . . . . . . . . . . . 43
3.1 The Rule of Sum . . . . . . . . . . . . . . . . . . . . . . . . . 43
3.2 The Rule of Product . . . . . . . . . . . . . . . . . . . . . . . 43
3.3 The Inclusion-Exclusion Principle . . . . . . . . . . . . . . . . 43
4 Combinatorics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
4.1 Permutations . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
4.2 Combinations . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
5 Generalized Permutations and Combinations . . . . . . . . . . . . . 45
5.1 Permutations with Repeated Elements . . . . . . . . . . . . . 45
5.2 Combinations with Repetition . . . . . . . . . . . . . . . . . 45
6 Binomial Coefficients . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
6.1 Binomial Theorem . . . . . . . . . . . . . . . . . . . . . . . . 46
6.2 Properties of Binomial Coefficients . . . . . . . . . . . . . . . 47
6.3 Pascal’s Triangle . . . . . . . . . . . . . . . . . . . . . . . . . 47
7 The Pigeonhole Principle . . . . . . . . . . . . . . . . . . . . . . . . 48
7.1 The Pigeonhole Principle . . . . . . . . . . . . . . . . . . . . 48
 COURSE SYLLABUS
COURSE NAME : Introduction to Discrete Mathematics: Computer Science

CREDITS : 2 (32h)

PREREQUISITES : General Mathematics: 1st year

TOPICS OF THE COURSE

1. Logic and proofs
• Propositions, connectives, truth tables
• Conditional propositions
• De Morgan’s Law and Quantifiers
• Proofs
2. Language of Mathematics
• Sets and operation on sets
• Sequences and strings
• Number systems
• Relations and properties of relations
• Functions
3. Counting Methods
• Multiplication and addition principles
• Permutation vs combination
• Binomial coefficients and Pascal triangle
• Pigeonhole principle
4. Cryptography and Number Theory
• Cryptography and Modular Arithmetic
• Inverses and GCDs
• The RSA Cryptosystem
• Details of the RSA Cryptosystem
Mid-term
5. Graph Theory
• Graph definition, nodes, edges, etc.
• Types of graphs
• Paths, cycles, sub-graphs, vertex degree, components
• Euler, Hamiltonian cycles
• Graph representation
• Isomorphism of graphs
6. Trees
• Tree definition, free tree vs rooted tree, vertex levels, tree height, etc
• Applications of trees
• Tree terminology
 • Spanning trees (Prim’s and Kruskal’s algorithms)
• Binary trees and tree traversals
• Isomorphism of trees
Final exam

Class meets: Friday 1:00-5:00 PM (if not 7:00-11:00 AM for alter.) in Room ???

Lecturer: Ham Karim, MSc. (PhD Candidate)

Office: Department of Mathematics, RUPP, Office 113B

E-mail: ham.karim at rupp.edu.kh

Tel: 097 740 6123/015 906 123

TEXT BOOK: • Discrete Mathematics and Its Applications, TheMcGraw-

Hill Companies, 5th Edition, by Kenneth H. Rosen;
• Discrete Mathematics for Computer Scientists, Addison-Wesley, by Cliff
Stein, Robert Drysdale, Kenneth Bogart

COVERED TOPICS: Chapters: 1, 2, 5, 7, 8, 9 and 10 and Chapter: 2 (second

reference)

GRADING: • Attendance: 10%

• Home works & Quizzes: 20%
• Midterm: 20%
• Final: 50%
 Chapter 1
LOGIG and PROOFS

In this chapter, we will cover some basic points of logic and then fundamental
methods of proof are also focused. The contents of the chapter are as follows:

• Propositions, connectives, truth tables

• Conditional propositions

• De Morgan’s Law and Quantifiers

• Proofs

This chapter is not meant to be a complete enumeration of all possible proof tech-
niques. Its philosophy is that you will learn more about proofs by reading, watching,
and attempting proofs than by an extended study of the logical rules behind proofs.
As such, some examples of proofs can help you read and do proofs if we reflect on
their structure and discuss what constitutes a proof. Thus, we first develop a lan-
guage that will allow us to talk about proofs, and then this kind of language can
be described the logical structure of a proof.

1 Logic
1.1 Propositions, connectives

Definition 1.1 (Statement or Proposition) A proposition is a declarative

sentence that is either true or false, but not both.

For instance, the following are propositions:

• “Phnom Penh is in Cambodia” −→ (true),

• “Sun rises in the east” −→ (false),

• “2 < 4” −→ (true),

• “4 = 7” −→ (false).

1
2 CHAPTER 1. LOGIG AND PROOFS

However the following are not propositions: “what is your name?” (this is a ques-
tion), “do your homework” (this is a command), “this sentence is false” (neither
true nor false), “x is an even number” (it depends on what x represents), “Socrates”
(it is not even a sentence). The truth or falsehood of a proposition is called its truth
value, represented by 1 or T for “Truth” and 0 or F for “False”.

Logical Connectives: Connectives are used for making compound propositions.

There are basic used connectives as presented in the following table: (here, let p
and q represent given propositions):

Name Represented Meaning

Negation ∼p “not p”
Conjunction p∧q “p and q”
Disjunction p∨q “p or q (or both)”
Exclusive Or p⊕q “either p or q, but not both”
Implication p⇒q “if p then q”
Biconditional p⇔q “p if and only if q”
NOT and AND (NAND) p ↑ q or (p NAND q) “NAND of p and q” or ∼ (p ∧ q)
NOT and OR (NOR) p ↓ q or (p NOR q) “NOR of p and q” or ∼ (p ∨ q)

Table 1.1: Connectives and their meaning

1.2 Truth table

The truth value of a compound proposition depends only on the value of its com-
ponents. We can summarize the meaning of the connectives in the following truth
table:

p q ∼p ∼q p∧q p∨q p⊕q p→q p↔q p↑q p↓q

T T F F T T F T T F F
T F F T F T T F F T F
F T T F F T T T F T F
F F T T F F F T T T T

Table 1.2: summarizing of truth table for basic connectives

Note: Remember that connective ∨, a non-exclusive or, i.e., p ∨ q is false when

both p and q are false, but ↓ translates conversely. For ∧, it is true, whenever,
both p and q are true, but ↑ means contrarily. On the other hand, ⊕ represents an
exclusive or, i.e., p ⊕ q is true only when exactly one of p and q is true.
1. LOGIC 3

Definition 1.2 (Conditional Propositions) A proposition of the form “if p

then q” or “p implies q”, represented by “p ⇒ q” is called a conditional propo-
sition.

For instance: “if Sao is from Battambang then Sok is from Phnom Penh”. The
proposition p, “Sao is from Battambang”, is called hypothesis or antecedent, and
the proposition q, “Sok is from Phnom Penh”, is the conclusion or consequence.

Note: Statement “p ⇒ q” is true always except when p is true and q is false.

Example 1. Consider the following sentences, they are true:

• “if 2 < 4 then Phnom Penh is in Cambodia” (true −→ true),

• “if London is in Denmark then 2 < 4” (false −→ true),

• “if 4 = 7 then London is in Denmark” (false −→ false).

However the following one is false: “if 2 < 4 then London is in Denmark” (true −→
false). ■
To consider a proposition “p ⇒ q”, it seem a bit strange that it is true when
p is false, regardless of the truth value of q. This will become clearer when we
study predicates such as “if x is a multiple of 4 then x is a multiple of 2”. That
implication is obviously true, although for the particular case x = 3 it becomes “if
3 is a multiple of 4 then 3 is a multiple of 2”.

Definition 1.3 (Biconditional) The proposition p ⇔ q, read “p if and only

if q”, is called biconditional. It is true precisely when p and q have the same
truth value, i.e., they are both true or both false.

1.3 Tautology, Contradiction, Contingency

Definition 1.4 (Tautology, Contradiction and Contingency):

1. A proposition is said to be a tautology if its truth value is T for any

assignment of truth values to its components.

2. A proposition is said to be a contradiction if its truth value is F for any

assignment of truth values to its components.

3. A proposition that is neither a tautology nor a contradiction is called a

contingency.

Example 2. Consider the following truth table:

4 CHAPTER 1. LOGIG AND PROOFS

p ∼p p∨∼p p∧∼p
T F T F
T F T F
F T T F
F T T F

Table 1.3: Truth table of tautology and contradiction statement

1.4 Logical Equivalence

We know that the compound propositions p ⇒ q and ∼ p ∨ q have the same truth
values:

p q ∼p ∼p∨q p⇒q
T T F T T
T F F F F
F T T T T
F F T T T

Table 1.4: Logically equivalent

When two compound propositions have the same truth values no matter what
truth value their constituent propositions have, they are called logical equiva-
lence. For instance p ⇒ q and ∼ p ∨ q are logically equivalent, we, then, write it
as:

p⇒q ≡ ∼p∨q

Note that that two propositions A and B are logically equivalentprecisely when
A ⇐⇒ B is a tautology.

Example 3. The following propositions are logically equivalent:

∼ (p ∨ q) ≡ ∼p∧∼q
∼ (p ∧ q) ≡ ∼p∨∼q

We can check it by examining their truth tables:

1. LOGIC 5

p q ∼p ∼q p∨q ∼ (p ∨ q) ∼p∧∼q p ∧q ∼ (p ∧ q) ∼p∨∼q

T T F F T F F T F F
T F F T T F F F T T
F T T F T F F F T T
F F T T F T T F T T

Table 1.5: Truth table of De Morgan’s Laws

Example 4.he following propositions are logically equivalent:

p⇔q ≡ (p ⇒ q) ∧ (q ⇒ p)

Again, this can be checked with the truth tables:

p q p⇒q q⇒p (p ⇒ q) ∧ (q ⇒ p) p⇔q

T T T T T T
T F F T F F
F T T F F F
F F T T T T

Table 1.6: Logical equivalence of Bicondition

■
Exercise: Check the following logical equivalences:

∼ (p ⇒ q) ≡ p∧ ∼ q
p⇒q ≡ ∼ q ⇒∼ p
∼ (p ⇔ q) ≡ p⊕q

Definition 1.5 (Converse). The converse of a conditional proposition p ⇒ q

is the proposition q ⇒ p.

(Contrapositive). The contrapositive of a conditional proposition p ⇒ q is the

proposition ∼ q ⇒∼ p.

As we have seen, the biconditional proposition is equivalent to the conjunction

of a conditional proposition an its converse.

p⇔q ≡ (p ⇒ q) ∧ (q ⇒ p)
6 CHAPTER 1. LOGIG AND PROOFS

So, for instance, saying that “John is married if and only if he has a spouse” is
the same as saying “if John is married then he has a spouse” and “if he has a spouse
then he is married”. Note that the converse is not equivalent to the given condi-
tional proposition, for instance “if John is from Chicago then John is from Illinois”
is true, but the converse “if John is from Illinois then John is from Chicago” may
be false.

On the other hand, the contrapositive of “if John is from Chicago then John is
from Illinois” is “if John is not from Illinois then John is not from Chicago”. Thus,
they are logically equivalent.

Equivalence Name
p∧T ≡p Identity laws
p∨F ≡p
p∨T≡T Domination laws
p∧F≡F
p∨p≡p Idenpotent laws
p∧p≡p
∼ (∼ p) ≡ p Double negation law
p ∨q ≡q ∨p Commutative laws
p ∧q ≡q ∧p
(p ∨ q) ∨ r ≡ p ∨ (q ∨ r) Association laws
(p ∧ q) ∧ r ≡ p ∧ (q ∧ r)
p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r) Distributive laws
p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)
∼ (p ∧ q) ≡ ∼ p∨ ∼ q De Morgan’s laws
∼ (p ∨ q) ≡ ∼ p∧ ∼ q
p ∨ (p ∧ q) ≡ p Absorption laws
p ∧ (p ∨ q) ≡ p
p∨∼p≡T Negation laws
p∧∼p≡F

Table 1.7: Logical equivalences’ laws

Question: (A merge sort program) Joe and Mary have each written an algorithm
for a function that takes two sorted lists, List1 and List2, of lengths m and n,
respectively, and merges them into a third list, List3. Part of Mary’s algorithm is
as follows:
(1) if ((i + j <= m + n) && (i <= m) && ((j > n)
1. LOGIC 7

Logical Equivalences of “⇒”

p ⇒ q ≡∼ p ∨ q
p ⇒ q ≡∼ q ⇒∼ q
Logical Equivalences of “⇔”
p ∨ q ≡∼ p ⇒ q
p ⇔ q ≡ (p ⇒ q) ∧ (q ⇒ p)
p ∧ q ≡∼ (p ⇒∼ q)
p ⇔ q ≡∼ p ⇔∼ g
∼ (p ⇒ q) ≡ p∧ ∼ q
p ⇔ q ≡ (p ∧ q) ∨ (∼ p∧ ∼ q)
(p ⇒ q) ∧ (p ⇒ r) ≡ p ⇒ (q ∧ r)
∼ (p ⇔ q) ≡ p ⇔∼ q
(p ⇒ r) ∧ (q ⇒ r) ≡ (p ∨ q) ⇒ r
(p ⇒ q) ∨ (p ⇒ r) ≡ p ⇒ (q ∨ r)
(p ⇒ r) ∨ (q ⇒ r) ≡ (p ∧ q) ⇒ r

Table 1.8: More rule on logical equivalences

||(List1[i] <= List2[j])))

(2) List3[k] = List1[i]
(3) i = i + 1
(4) else
(5) List3[k] = List2[j]
(6) j = j + 1
(7) k = k + 1

The corresponding part of Joe’s algorithm is

(1) if (((i + j <= m + n) && (i <= m) && (j > n))

|| ((i + j <= m + n) && (i <= m) && (List1[i] <= List2[j])))
(2) List3[k] = List1[i]
(3) i = i + 1
(4) else
(5) List3[k] = List2[j]
(6) j = j + 1
(7) k = k + 1

Do Joe’s and Mary’s algorithms do the same thing? (Explain logically)

Example 5.

i) Show that ∼ (p ∨ (∼ p ∧ q)) and ∼ p ∧ ∼ q are logically equivalent.

ii) Show that (p ∧ q) ⇒ (p ∨ q) is a tautology.

Solution:
8 CHAPTER 1. LOGIG AND PROOFS

1.5 Formulas
More complicated propositional expressions, formulas or well-formed formulas,
can be built from the proposition letters using the propositional connectives and
parentheses. When we say ϕ = (p ∧ q) ⇒ r, we mean that ϕ is the string of symbols
(p ∧ q) ⇒ r. Consider the following formulas, whether the conclusion is necessarily
true:
(i.) ψ = (p ∧ q) ⇒ r, means “If p and q are both true, then r is also true.”
(ii.) ψ1 = (p ∨ q) ⇒ r, means “If p or q (or both) is true, then r is also true.”
(iii.) ψ2 = (p ⇒ r) ⇒ ((p ∧ q) ⇒ r), means “Suppose that if p is T , then r is T .
Then, if p and q are both T , then r is T .”

Example 6. Translate the following sentences into a formula in propositional logic:

“If Mr. Holmes told the truth and Mr. Watson did not hear anything, then it cannot
be both that the butler did it and that the butler returned to his hotel room that night.”
■

Proof:
ϕ = (p ∧ q) ⇒ (∼ (r ∧ s))

Definition 1.6 A formula is any string of symbols that is formed using the
following rules:

Base cases: Every proposition letter is a formula. T and F are formulas.

Closure rules: Let ϕ be a formula. Then, (∼ ϕ) is a formula. For formulas ϕ

and ψ, we have (ϕ ∧ ψ), (ϕ ∨ ψ), (ϕ ⇒ ψ), and (ϕ ⇔ ψ) are formulas.

1.6 Gates of Formulas

Basically, computer memory has two states, identified as the two logical values or
boolean values of T and F . Computer operations are thought of as being composed
of operations on these boolean values and, hence, as operations of propositional
logic. In describing computer circuits, a specialized notation for propositional logic
is used. As such, special physical devices, called Gates, implement the ∧, ∨, and ∼
operations. A set of gates to represent a circuit is called a combinatorial circuit
or combinatorial network. By common consent, the basic gates are represented
by the following notations.

p p p
. p∧q . p∨q p . ∼p . p⊕q
q q q

p p
. p↑q . p↓q
q q

Figure 1.1: Notation of logical gates

1. LOGIC 9

Example 7.

i) A combinatorial circuit is, roughly, the analogue of a formula. Boolean

circuit notation for the formula

(p ∧ q) ∧ r

is shown as follows:

p p∧q
q

(p ∧ q) ∧ r
r
.
Figure 1.2: AND gates

ii) For the formula

(p ∧ p) ∧ p
instead of having three separate p’s, the gate to represent it should has one
line that splits, as shown in the following figure:

p∧p

p (p ∧ p) ∧ p

Figure 1.3: AND gates with common input

Note: Since gates are used to describe computer circuits that will be implemented
in a device or printed on a chip, it is common to represent more than one formula
in the same diagram.

1.7 Predicates

Definition 1.7 A predicate or propositional function1 is a statement containing

variables.

Example 8.or instance “x + 2 = 7”, “X is American”, “x < y”, “p is a prime

number” are predicates.
The truth value of the predicate depends on the value assigned to its variables. ■
10 CHAPTER 1. LOGIG AND PROOFS

In above example, if we replace x with 1 in the predicate “x + 2 = 7” we obtain

“1 + 2 = 7”, which is false, but if taking x = 5 we get “5 + 2 = 7”, which is true.
We represent a predicate by a letter followed by the variables enclosed between
parenthesis: P (x), Q(x, y), etc. An example for P (x) is a value of x for which P (x)
is true. Conversely, it is a value of x for which P (x) is false. So, 5 is an example
for “x + 2 = 7”, while 1 is a counterexample.

Each variable in a predicate is assumed to belong to a domain (or universe)

of discourse, for instance in the predicate “n is an odd integer”; n represents an
integer, so the domain of discourse of n is the set of all integers. In “X is American”
we may assume that X is a human being, so in this case the domain of discourse is
the set of all human beings 2 .

1.8 Quantifiers
Given a predicate P (x), the statement “for some x, P (x)” or “there is some x such
that P (x)”, written as “∃x, P (x)”, has a definite truth value, so it is a proposition.
For instance, if P (x) is “x + 2 = 7” with the integers as domain of discourse, then
∃x, P (x) is true, since there is indeed an integer, say 5, such that P (5) is a true
statement. Yet, if Q(x) is “2x = 7” and the domain of discourse is still the integers,
then ∃x, Q(x) is false. On the other hand, ∃x, Q(x) would be true if x ∈ Q. The
symbol ∃ is called the existential quantifier.

With the same sense, the sentence “for all x, P (x)” or “for any x, P (x)” or “for
every x, P (x)” or “for each x, P (x)”, written as “∀x, P (x)”, has a definite truth
value. For instance, if P (x) is “x + 2 = 7” and the domain of discourse is the inte-
gers, then ∀x, P (x) is false. However, if Q(x) represents “(x + 1)2 = x2 + 2x + 1”
then “∀x, Q(x)” is true. The symbol ∀ is called the universal quantifier.

If multi-variables are used in a predicate, it is possible to use several quantifiers

at the same time, for instance “∀x ∀y ∃z, P (x, y, z)”, the same as “for all x and all
y there is some z such that P (x, y, z)”.

Remark:
∀x ∃y, P (x, y) ̸= ∃y ∀x, P (x, y)

Example 9. If x and y represent human beings and P (x, y) represents “x is

married to y”, then “∀x ∃y, P (x, y)” means that everybody is married to someone,
but “∃y ∀x, P (x, y)” means that there is someone to whom everybody else is married
(an extreme form of polygamy!..). ■
A predicate can be partially quantified, e.g. “∀y ∃y, P (x, y, z, t)”, where x and
y, here are variables quantified, are called bound variables, and the rest, z and t
are called free variables. A partially quantified predicate is still a predicate, but
depending on fewer variables.
2
Usually all variables occurring in predicates along a reasoning are supposed to belong to the
same domain of discourse, but in some situations (as in the so called many-sorted logics) it is
possible to use different kinds of variables to represent different types of objects belonging to
different domains of discourse. For instance in the predicate “σ is a string of length n” the variable
σ represents a string, while n represents a natural number, so the domain of discourse of σ is the
set of all strings, while the domain of discourse of n is the set of natural numbers.
2. PROOFS 11

1.9 Generalized De Morgan Laws

If “∃x, P (x)” is false then there is no value of x for which P (x) is true, or in other
words, P (x) is always false. Hence,
( )
∼ ∃x, P (x) ≡ ∀x, ∼ P (x)
On the other hand, if “∀x, P (x)” is false then it is not true that for every x, P (x)
holds, hence for some x, P (x) must be false. Thus:
( )
∼ ∀x, P (x) ≡ ∃x, ∼ P (x)
This two rules can be applied in successive steps to find the negation of a more
complex quantified statement, for instance:

( ) ( )
∼ ∃x ∀y, p(x, y) ≡ ∀x ∼ ∀y, P (x, y) ≡ ∀x ∃y, ∼ P (x, y)

Example 10. Write formally the statement “for every real number there is a
greater real number”. Write the negation of that statement. ■

2 Proofs
2.1 Mathematical Systems
A Mathematical System consists of:

1. Axioms: propositions that are assumed true.

2. Definitions: used to create new concepts from old ones.

3. Undefined terms: corresponding to the primitive concepts of the system

(for instance in set theory the term “set” is undefined).

A theorem is a proposition that can be proved to be true. An argument that

establishes the truth of a proposition is called a proof.

2.2 Methods of Proof

Direct Proof: we assume the hypothesis together with axioms and other theorems
previously proved and we derive the conclusion from them.

Example 1. Prove that if x > 2 and y > 3 then x + y > 5. ■

Answer: Assuming x > 2 and y > 3 and adding the inequalities term by term, we,
then, get:
x+y >2+3=5

Indirect Proof or Proof by Contrapositive: it consists of proving the contra-

positive of the desired implication, i.e., instead of proving p ⇒ q, we prove
∼ q ⇒∼ p.
12 CHAPTER 1. LOGIG AND PROOFS

Example 2. Prove that if x + y > 5 then x > 2 or y > 3 . ■

Answer:
( ) that x + y > 5 ⇒ (x > 2) ∨ (y >
We must prove ( 3). Thus, we must
) proof
∼ (x > 2) ∨ (y > 3) ⇒ ∼ (x + y > 5). We have: ∼ (x > 2) ∨ (y > 3) is the
same as (x ≤ 2) ∧ (y ≤ 3), so adding both inequalities we get x + y ≤ 5, which is
the same as ∼ (x + y > 5).

Proof by Contradiction: in a proof by contradiction, we assume the hypotheses

and the negation of the conclusion, and try to derive a contradiction, i.e., a
proposition of the form r ∧ ∼ r.

Example 3. Prove by contradiction that if x + y > 5 then either x > 2 or y > 3.

■

Answer: We assume the hypothesis x + y > 5. From here we must conclude that
x > 2 or y > 3. Assume to the contrary that “x > 2 or y > 3” is false, so x ≤ 2
and y ≤ 3. Adding those inequalities, we get x + y ≤ 2 + 3 = 5, which contradicts
the hypothesis x + y > 5. From here, we conclude that the assumption “x ≤ 2 and
y ≤ 3” cannot be right, so “x > 2 or y > 3” must be true.

Note: See its difference. In an indirect proof, we prove an implication of the form
p ⇒ q by proving the contrapositive ∼ q ⇒∼ p. In a proof by contradiction, we
prove an statement s (which may or may not be an implication); by assuming ∼ s
and deriving a contradiction. In fact, proofs by contradiction are more general than
indirect proofs

√
Example 4. Prove by contradiction that 2 is not a rational number. ■

√ √
Answer: Assume that 2 is rational, i.e., 2 = a/b, where a and b are integers
and the fraction is written in least terms. We have,

2 = a2 /b2

hence
2b2 = a2

Since the left hand side is even, then a2 is even, but this implies that a itself is
even, so a = 2a′ . Hence:
2b2 = 4a′2

and simplifying:
b2 = 2a′2

This implies that b2 is even, so b is even: b = 2b′ . Consequently, a/b = 2a′ /2b′ =
a′ /b′ , which is contradicting the hypothesis that a/b was in least terms.
2. PROOFS 13

2.3 Arguments, Rules of Inference

Argument: is a sequence of propositions p1 , p2 , · · · , pn called hypotheses (or premises)
followed by a proposition q called conclusion. An argument is usually written as:

p1
p2
..
.
pn
∴ q
The argument is called valid if q is true whenever p1 , p2 , · · · , pn are true; oth-
erwise it is called invalid.

Rules of inference: are certain simple arguments known to be valid and used to
make a proof step by step. In logic, a rule of inference, is the act of making a conclu-
sion relied on the form of premises interpreted as a function which takes premises,
analyses their syntax, and returns a conclusion (or conclusions). Common
rules of inference are cited as follows:

i). Modus Ponens: commonly called as Rule of Detachment (in Latin for the
way that affirms by affirming) or implication elimination is a valid, simple
argument form. It is a very common rule of inference, and takes the following
form:

p⇒q
p
∴ q

To check whether it is valid, we must examine the following truth table:

p q p⇒q p q
T T T T T
T F F T F
F T T F T
F F T F F

Example 5. Consider the following argument:

”If roses are red and violets are blue, then sugar is sweet and so are
you.”
”Roses are red and violets are blue.”

”Therefore, sugar is sweet and so are you.” ■

14 CHAPTER 1. LOGIG AND PROOFS

ii). Modus Tollens: (or modus tollendo tollens in Latin) means the way that
denies by denying), which has the following argument form:

p⇒q
∼q
∴ ∼p

p q p⇒q ∼p ∼q
T T T F F
T F F F T
F T T T F
F F T T T

Example 6. Consider following proposition:

”If the watch-dog detects an intruder, the dog will bark.”
”The dog did not bark.”

Therefore, no intruder was detected by the watch-dog. ■

iii). Addition: (or Disjunction Introduction) :

p
∴ p∨q

Example 7. Consider:

Socrates is a man.

Therefore (either or both of) Socrates is a man, or pigs are flying in

formation over the English Channel. ■

iv). Simplification: (or Conjunction Elimination) :

p∧q
∴ p

Example 8.

It’s raining and it’s pouring.

Therefore it’s raining. ■

2. PROOFS 15

v). Conjunction: is the inference that, if p is true, and q is true, then the
conjunction p ∧ q is true.

p
q
∴ p∧q

Example 9. Consider:

If it’s true that it’s raining, and it’s true that I’m inside, then it’s true
that ”it’s raining and I’m inside”. ■

vi). Hypothetical Syllogism:

p⇒q
q⇒r
∴ p⇒r

Example 10. Consider the following statements:

If I do not wake up, then I cannot go to work.

If I cannot go to work, then I will not get paid.

Therefore, if I do not wake up, then I will not get paid.

■

vii). Disjunctive Syllogism:

p∨q
∼p
∴ q

Example 11. Consider the following statements:

Either I will choose soup or I will choose salad.

I will not choose soup.

Therefore, I will choose salad. ■

viii). Resolution:
16 CHAPTER 1. LOGIG AND PROOFS

p∨q
∼p∨r
∴ q∨r

Example 12. Consider the following statements:

“It is cold or raining” and “It is not cold or it is snowing” are true, then it is
raining or snowing. ■

Exercises

1. Use the truth tables to determine whether the following logical equivalences are
correct:

1. p ∧ (q ⊕ r) ≡ (p ∧ q) ⊕ (p ∧ r)

2. (p ⊕ q) ⊕ r ≡ p ⊕ (q ⊕ r)

3. (p ⇒ q) ⇒ r ≡ p ⇒ (q ⇒ r)

4. (p ⊕ q) ⊕ r ≡ (p ⇔ q) ⇔ r

5. p ⇒ (q ⇒ r) ≡ (p ∧ q) ⇒ r

2. Consider the following statements:

1. ∀x∀y, (x2 < y)

2. ∀x∃y, (x < y)

3. ∃x∀y, (x < y 2 )

4. ∃x∃y, (x ≤ y)
Determine their truth value assuming that the universe of discourse is:

1. The set of all integers.

2. The set of positive integers.

3. The set of negative integers.

4. The set A = {1, 2, 3, . . . , 10}

3. Let C(x, y) means that student x is enrolled in class y, where the domain for
x consists of all students in your school and the domain for y consists of all classes
being given at your school. Express each of these statements by a simple English
sentence.

1. C(Randy Goldberg, CS 252)

EXERCISES 17

2. ∃x, C(x, Math 695)

3. ∃y, C(Carol Sitea, y)

( )
4. ∃x, C(x, Math 222) ∧ C(x, CS 252)
( ( ))
5. ∃x∃y∀z, (x ̸= y) ∧ C(x, z) ⇒ C(y, z)
( ( ))
6. ∃x∃y∀z, (x ̸= y) ∧ C(x, z) ⇔ C(y, z)

4. Consider the following premises (hypothesis):

1. If A is red then B is green.

2. If C is red then D is green.

3. A is red or C is red.

4. B is not green.
Use a formal argument to prove that D is green (write it in three columns con-
taining respectively a label (no.), a compound proposition and a reason).

5. Find a counterexample, if possible, to these universally quantified statements,

where the domain for all variables consists of all integers.

1. ∀x∀y, (x2 = y 2 ⇒ x = y)

2. ∀x∃y, (y 2 = x)

3. ∀x∀y, (xy ≥ x)

4. ∀x∃y, (y 2 − x < 100)

6. Let a, b, c be integers satisfying a2 + b2 = c2 . Give a proof, by using a contra-

diction, that abc must be even.

7. Show that each of these conditional statements is a tautology by using (i) truth
tables and (ii) logical equivalence properties (without construct their truth tables)

1. [∼ p ∧ (p ∨ q)] ⇒ q

2. [(p ⇒ q) ∧ (q ⇒ r)] ⇒ (p ⇒ r)

8. Prove the following:

1. There exists a pair of consecutive integers such that one is a perfect square
and the other one is a perfect cube.

2. The product of two of the numbers: 651000 −82001 + 3177 , 791212 −92399 +
22001 ,
and 244493 −58192 + 71777 is nonnegative. (Do not try to evaluate these
numbers!).
18
 Chapter 2
Language of Mathematics

1 Set Theory
1.1 Definition
A Set is a collection of objects, called elements of the set. A set can be represented
by listing its elements between braces, such as A = {1, 2, 3, 4, 5}. The symbol ∈
is used to express that an element is (or belongs to) a set, for instance 3 ∈ A. Its
negation is represented by ∈,
/ e.g. 7 ∈ / A. If the set is finite, its number of elements
is represented by |A| or card(A), e.g. in above example, we get |A| = 5.

Some important sets are the following:

1. N = {1, 2, 3, · · · } = the set of natural numbers.

2. Z = {· · · , −3, −2, −1, 0, 1, 2, 3, · · · } = the set of integers.

{ }
3. Q = pq | p, q ∈ Z, q ̸= 0 and pq in the least form = the set of rational
numbers.

4. R =] − ∞, +∞[ = the set of real numbers.

5. C = {a + ib | a, b ∈ R} = the set of complex numbers

If S is one of those sets, then we also use the following notations:
1. S+ = set of positive elements in S, for instance
Z+ = {1, 2, 3, · · · } = the set of positive integers.

2. S− = set of negative elements in S, for instance

Z− = {−1, −2, −3, · · · } = the set of negative integers.

3. S∗ = set of elements in S excluding zero, for instance R∗ = the set of non zero
real numbers.
Set-builder notation. An alternative way to define a set, called set-builder nota-
tion, is by stating a property (predicate) P(x) verified by exactly its elements, for
instance A = {x ∈ Z | 1 ≤ x ≤ 5} = “set of integers x such that 1 ≤ x ≤ 5” — i.e.,
A = {1, 2, 3, 4, 5}.

19
20 CHAPTER 2. LANGUAGE OF MATHEMATICS

In general: A = {x ∈ U | P(x)}, where U is the universe of discourse in which

the predicate P(x) must be interpreted, or A = {x | P(x)}, if the universe of dis-
course for P(x) is implicitly understood. In set theory the term universal set is
often used in place of “universe of discourse” for a given predicate.

Principle of Extension: Two sets are equal if and only if they have the same
elements, i.e.: ( )
A = B ≡ ∀x x ∈ A ⇔ x ∈ B (2.1)
Subset: We say that A is a subset of set B, or A is contained in B, and we
represent it “A ⊆ B”, if all elements of A are in B, e.g., if A = {a, b, c} and
B = a, b, c, d, e then A ⊆ B.
A is a proper subset of B, represented “A ⊂ B”, if A ⊆ B but A ̸= B, i.e.,
there is some element in B which is not in A.

Empty Set: A set with no elements is called empty set (or null set, or void set),
and is represented by ∅ or {}.

Remark: A set can be an element

{ of another set } (which is not the same as being a
subset!). For instance if A = 1, a, {3, t}, {1, 2, 3} and B = {3, t}, then obviously
B is an element of A, i.e., B ∈ A.

Power Set: The collection of all subsets of a set A is called the power set of A,
and represented by P(A). For instance, if A = {1, 2, 3}, then
{ }
P(A) = ∅, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, A

1.2 Venn Diagrams

Venn diagrams are graphic representations of sets as enclosed areas in the plane.
For instance, in figure 2.1, the closed curve represents the universal set (the set of
all elements considered in a given problem) and the shaded region represents a set
A.

Figure 2.1: Venn diagram of a set A

1.3 Set Operations

Intersection: Given common elements of two sets, then
{ }
A∩B= x | x∈A∧x∈B (2.2)
1. SET THEORY 21

U
B

A∩B
Figure 2.2: The intersection of two sets A and B

Union: The set of elements that belong to either of two sets, then
{ }
A∪B= x | x∈A∨x∈B (2.3)

U
B
A

A ∪ B

Figure 2.3: The union of two sets A and B

Complement: The set of elements (in the universal set) that do not belong to a
given set, represented by Ac or A
{ }
Ac = x ∈ U | x ∈
/A (2.4)

Figure 2.4: The complement of a set A

Difference: The set of elements that belong to a set but not to another:
{ }
A\B= x | x∈A∧x∈ / B =A∩B (2.5)
22 CHAPTER 2. LANGUAGE OF MATHEMATICS

A
B

A\B
B\A

Figure 2.5: The difference between set A and B

Symmetric Difference: Given two sets, their symmetric difference is the set of
elements that belong to either one or the other set but not both:
{ }
A⊕B= x | x∈A⊕x∈B (2.6)

It can be expressed also in the following way:

A ⊕ B = (A ∪ B) \ (A ∩ B) = (A \ B) ∪ (B \ A)

1.4 Counting with Venn Diagrams

A Venn diagram with n sets intersecting in the most general way divides the plane
into 2n regions. If we have information about the number of elements of some
portions of the diagram, then we can find the number of elements in each of the
regions and use that information for obtaining the number of elements in other
portions of the plane.

Example 1. Let A, B and C be the sets of students taking Mathematics courses,

Physics courses and Computer Science courses respectively in a university. Assume
|A| = 300, |B| = 350, |C| = 450, |A ∩ B| = 100, |A ∩ C| = 150, |B ∩ C| = 75, |A ∩
B ∩ C| = 10. How many students are taking exactly one of those courses?

A
B

60 90 185

10

140 65

235
C

Figure 2.6: Counting with Venn diagram

Proof: The number of students taking exactly one of those courses is 60 + 185 +
235 = 480.

■
 1. SET THEORY 23

1.5 Properties of Sets

The set operations verify the following properties:
1. Associative Laws:
A ∪ (B ∪ C) = (A ∪ B) ∪ C (2.7)
A ∩ (B ∩ C) = (A ∩ B) ∩ C (2.8)

2. Commutative Laws:
A∪B = B∪A (2.9)
A∩B = B∩A (2.10)

3. Distributive Laws:
A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C) (2.11)
A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C) (2.12)

4. Identity Laws:
A∪∅ = A (2.13)
A∩U = A (2.14)

5. Complement Laws:
A∪A = U (2.15)
A∩A = ∅ (2.16)

6. Idempotent Laws:
A∪A = A (2.17)
A∩A = A (2.18)

7. Bound Laws:
A∪ U = U (2.19)
A∩∅ = ∅ (2.20)

8. Absorption Laws:
A ∪ (A ∩ B) = A (2.21)
A ∩ (A ∪ B) = A (2.22)

9. Involution Law:
A = A (2.23)

10. 0/1 Laws:

∅ = U (2.24)
U = ∅ (2.25)

11. De Morgan’s Laws:

A∪B = A∩B (2.26)
A∩B = A∪B (2.27)
24 CHAPTER 2. LANGUAGE OF MATHEMATICS

1.6 Generalized Union and Intersection

Given a collection of sets A1 , A2 , ..., An , their union is defined as the set of elements
that belong to at least one of the sets
∪
n { }
An = A1 ∪ A2 ∪ · · · ∪ An = x | ∃k (x ∈ An ) . (2.28)
k=1

Analogously, their intersection is the set of elements that belong to all the sets
simultaneously:
∩
n { }
An = A1 ∩ A2 ∩ · · · ∩ An = x | ∀k (x ∈ An ) . (2.29)
k=1

These definitions can {be applied to infinite } collections of sets as well. For in-
stance assume that Sn = kn | k = 2, 3, 4, · · · = set of multiples of n greater than
n. Then,
∞
∪
Sn = S2 ∪ S3 ∪ S4 ∪ · · · = {4, 6, 8, 9, 10, 12, 14, 15, · · · }
k=2
= set of composite positive integers

1.7 Partitions
A partition of a set X is a collection S of non overlapping non-empty subsets of X
whose union is the whole X. Thus, X1 , X2 , . . . , Xn is a partition of X if and only
if  n
 ∪
 Xk = X where Xk ̸= ∅
k=1 (2.30)

 X ∩ X = ∅ for all i ̸= j
i j

For instance a partition of X = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} could be

{ }
S = {1, 2, 4, 8}, {3, 6}, {5, 7, 9, 10}

Note: Given a partition S of a set X, every element of X belongs to exactly one

member of S.

Example 2. The division } Z into

{ of the integers { even and odd}numbers is a partition:
S = {E, O}, where E = 2n | n ∈ Z , O = 2n + 1 | n ∈ Z ■

Example 3. The{ divisions of} Z in negative integers, positive integers and zero is a
partition: S = Z+ , Z− , {0} ■

1.8 Ordered Pairs, Cartesian Product

An ordinary pair {a, b} is a set with two elements. In a set the order of the elements
is irrelevant, so {a, b} = {b, a}. If the order of the elements is relevant, then we use
a different object called ordered pair, represented (a, b). Now (a, b) ̸= (b, a) (unless
a = b). In general (a, b) = (a′ , b′ ) iff a = a′ and b = b′ .
2. SEQUENCES AND STRINGS 25

Given two sets A, B, their Cartesian product A × B is the set of all ordered
pairs (a, b) such that a ∈ A and b ∈ B:
{ }
A×B = (a, b) | (a ∈ A) ∧ (b ∈ B) (2.31)

B
b7 b b b b b b b b b

b6 b b b b b b b b b

b5 b b b b b b b b b

b4 b b b b b b b b b

b3 b b b b b b b b b

b2 b b b b b b b b b

b1 (a1 , b1 )
b b b b b b b b b

a1 a2 a3 a4 a5 a6 a7 a8 a9 A

Figure 2.7: Cartesian product of sets A and B

Analogously, we can define triples or 3-tuples (a, b, c), 4-tuples (a, b, c, d), · · · ,
n-tuples (a1 , a2 , · · · , an ), and the corresponding 3-fold, 4-fold, · · · , n-fold Cartesian
products:

∏
n { }
Ak = (a1 , . . . , an ) | (a1 ∈ A1 ) ∧ . . . ∧ (an ∈ An ) (2.32)
k=1

Remark: In case of all the sets in a Cartesian product are the same, then we can
use an exponent, such as : A2 = A × A, A3 = A × A × A, etc. In general:

An = A × A × . . . × A (2.33)
| {z }
n−times
∏
n
{ }
= A= (a1 , a2 , . . . , an ) | ∀k ∈ Nn : ak ∈ A
k=1

An example of Cartesian product is the real plane R2 , where R is the set of real
numbers (R is sometimes called real line).

2 Sequences and strings

2.1 Sequences
A sequence is an (usually infinite) ordered list of elements.

Example 1.
26 CHAPTER 2. LANGUAGE OF MATHEMATICS

i). The sequence of positive integers:

1, 2, 3, 4, . . . , n, . . .

ii). The sequence of positive even integers:

2, 4, 6, 8, . . . , 2n, . . .

iii). The sequence of powers of 2:

1, 2, 4, 8, 16, ..., n2 , ...

iv). The sequence of Fibonacci numbers (each one is the sum of the two pre-
vious ones):
0, 1, 1, 2, 3, 5, 8, 13, ...

v). The reciprocals of the positive integers:

1 1 1 1
1, , , , ···, , ···
2 3 4 n

In general the elements of a sequence are represented with an indexed letter,

say s1 , s2 , s3 , ..., sn , .... The sequence itself can be defined by giving a rule, e.g.:
sn = 2n + 1 is the sequence:
3, 5, 7, 9, ...

Here we are assuming that the first element is s1 , but we can start at any value
of the index that we want, for instance if we declare s0 to be the first term, the
previous sequence would become:

1, 3, 5, 7, 9, ...

The sequence is symbolically represented {sn } or {sn }∞

n=1 .

If sn ≤ sn+1 for every n the sequence is called increasing. If sn ≥ sn+1 , then

it is called decreasing. For instance sn = 2n + 1 is increasing: 3, 5, 7, 9, ..., while
sn = 1/n is decreasing: 1, 12 , 31 , 14 , . . ..

If we remove elements from a sequence we obtain a subsequence. E.g., if we

remove all odd numbers from the sequence of positive integers:

1, 2, 3, 4, 5...,

we get the subsequence consisting of the even positive integers:

2, 4, 6, 8, ...
3. RELATIONS AND PROPERTIES OF RELATIONS 27

2.2 Sum and Product Notation

In order to abbreviate sums and products the following notations are used:

1. Sum (or sigma) notation:

∑
n
ak = am + am+1 + am+2 + . . . + an (2.34)
k=m

2. Product notation:
∏
n
ak = am × am+1 × am+2 × . . . × an (2.35)
k=m

Example 2. Assume an = 2n + 1, then ■

∏6 ∑6
Answer: n=3 an = 9009, n=3 an = 40

2.3 Strings
Given a set A, a string over A is a finite ordered list of elements of A.

Example 3. If A = {a, b, c}, then the following are strings over A : aba, aaaa, bba,
etc ■
Note: If repetitions exist, a superscripts can be replaced them, for instance:
a2 b3 ac2 a3 = aabbbaccaaa, (ab)3 = ababab, etc

The length of a string is its number of elements, e.g., |abaccbab| = 8, |a2 b7 a3 c6 | =

18.

The string with no elements is called null string, represented λ. Its length is
zero, i.e, |λ| = 0.

The set of all strings over A is represented A∗ . The set of no null strings over
A (i.e., all strings over A except the null string) is represented by A+

Given two strings α and β over A, the string consisting of α followed by β is

called the concatenation of α and β. For instance if α = abac and β = baaab then
αβ = abacbaaab.

3 Relations and properties of relations

4 Functions
4.1 Correspondences
Suppose that to each element of a set A we assign some elements of another set
B. For instance, A = N, B = Z, and to each element x ∈ N we assign all elements
y ∈ Z such that y 2 = x.
28 CHAPTER 2. LANGUAGE OF MATHEMATICS

1 1
2
3 -1
4 2
5
6 7 -2
9 3
8
-3
10
N Z
√
Figure 2.8: Correspondence of x 7→ ± x

This operation is called a correspondence.

Remark: A correspondence (or a relation between two sets) of sets A and B is

any subset of the Cartesian product A × B of the sets.

4.2 Representations of Relations

Arrow diagrams: Venn diagrams and arrows can be used for representing rela-
tions between given sets. As an example, figure 2.9 represents the relation from
A = {a, b, c, d} to B = {1, 2, 3, 4} given by R = {(a, 1), (b, 1), (c, 2), (c, 3)}. In the
diagram an arrow from x to y means that x is related to y. This kind of graph
is called directed graph or digraph.

a
1
b
2
c
3
d
4

A
B
Figure 2.9: Correspondence of R

Another example is given in diagram 2.10, which represents the divisibility rela-
tion on the set A = {1, 2, 3, 4, 5, 6, 7, 8, 9}.
4. FUNCTIONS 29

1
4

3 2
5

7
6 8

A
Figure 2.10: Binary relation of divisibility of set A

Matrix of a Correspondence: Another way of representing a relation R from

A to B is with a matrix. Its rows are labeled with the elements of A, and its
columns are labeled with the elements of B. If a ∈ A and b ∈ B then we write
1 in row a column b if aRb, otherwise we write 0. For instance the relation
R = {(a, 1), (b, 1), (c, 2), (c, 3)} from A = {a, b, c, d} to B = {1, 2, 3, 4} has the
following matrix:

1 2 3 4
a ⃝
1 0 0 0
 
 
b ⃝1 0 0 0 
 
 
c 0 ⃝
1 ⃝
1 0 
 
d 0 0 0 0

4.3 Inverse Relation

Given a relation R from A to B, the inverse of R, denoted R−1 , is the relation
from B to A defined as:
bR−1 a ⇐⇒ aRb
For instance, if R is the relation “being a son or daughter of”, then R−1 is the
relation “being a parent of”.

4.4 Composition of Relations

Let A , B and C be three sets. Given a relation R from A to B and a relation S
from B to C , then the composition S ◦ R of relations R and S is a relation from
A to C defined by:
( )
a S ◦ R c ⇐⇒ ∃ some b ∈ B | aRb and bSc
For instance, if R is the relation “to be the father of”, and S is the relation “to
be married to”, then S ◦ R is the relation “to be the father in law of”.
30 CHAPTER 2. LANGUAGE OF MATHEMATICS

R S

A B C

S ◦R

4.5 Properties of Binary Relations

A binary relation R on A is called:

1. Reflexive: if for all x ∈ A, xRx. For instance on Z the relation “equal to”
(=) is reflexive.

2. Transitive: if for all x, y, z ∈ A, xRy and yRz implies xRz. For instance
equality (=) and inequality (<) on Z are transitive relations.

3. Symmetric: if for all x, y ∈ A, xRy) =⇒ yRx. For instance on Z, equality

(=) is symmetric, but strict inequality (<) is not.

4. Antisymmetric: if for all x, y ∈ A, xRy and yRx implies x = y. For instance,

non-strict inequality (≤) on Z is antisymmetric.

4.6 Partial Orders

A partial order, or simply, an order on a set A is a binary relation “≤” on A with
the following properties:

i). Reflexive: for all x ∈ A, x ≤ x.

( )
ii). Antisymmetric: for all x, y ∈ A, (x ≤ y) ∧ (y ≤ x) =⇒ x = y.
( )
iii). Transitive: for all x, y, z ∈ A, (x ≤ y) ∧ (y ≤ z) =⇒ x ≤ z.

Example 1.

i). The non-strict inequality (≤) in Z.

ii). Relation of divisibility on Z+ : a|b ⇐⇒ ∃k, b = ak.
iii). Set inclusion (⊆) on P(A) (the collection of subsets of a given set A ).

■
4. FUNCTIONS 31

4.7 Hasse diagrams

A Hasse diagram is a graphical representation of a partially ordered set in which
each element is represented by a dot (node or vertex of the diagram). Its imme-
diate successors are placed above the node and connected to it by straight line
segments. As an example, figure 2.11 represents the Hasse diagram for the relation
of divisibility on {1, 2, 3, 4, 5, 6, 7, 8, 9}.
Question: How does the Hasse diagram look for a totally ordered set?
bc
8 bc
9
5bc 7
bc

bc 4 6
bc

2 bc 3 bc

bc
1
Figure 2.11: Hasse diagram for divisibility

4.8 Equivalence Relations

An equivalence relation on a set A is a binary relation “∼” on A with the following
properties:
i). Reflexive: for all x ∈ A, x ∼ x.
ii). Symmetric: for all x, y ∈ A, x ∼ y =⇒ y ∼ x.
iii). Transitive: for all x, y, z ∈ A, (x ∼ y) ∧ (y ∼ z) =⇒ x ∼ z.

Example 2.
• On Z, the equality (=) is an equivalence relation.

• On Z, define x ≡ y (mod 2) (“x is congruent to y modulo 2”) iff x−y is even.

■

4.9 Equivalence Classes, Quotient Set, Partitions

Given an equivalence relation ∼ on a set A , and an element x ∈ A, the set
of elements of A related to x are called the equivalence class of x, represented
[x] = {y ∈ A | y ∼ x}. Element x is said to be a representative of class [x].
The collection of equivalence classes, represented A/∼ = {[x] | x ∈ A}, is called
quotient set of A by ∼.

Example 3. Find the equivalence classes on Z with the relation of congruence

modulo 2. ■
32 CHAPTER 2. LANGUAGE OF MATHEMATICS

One of the main properties of an equivalence relation on a set A is that the

quotient set, i.e. the collection of equivalence classes, is a partition of A . Recall
that a partition of a set A is a collection of non-empty subsets A1 , A2 , A3 , . . . of A
which are pairwise disjoint and whose union equals A :

1). Ai ∩ Aj = ∅ for i ̸= j,
∪
2). k Ak = A

Example 4. In Z with the relation of congruence modulo 2 (call it “∼ 2”), there are
two equivalence classes: the set E of even integers and the set O of odd integers. The
quotient set of Z by the relation “∼ 2” of congruence modulo 2 is Z/ ∼ 2 = {E, O}.
We see that it is in fact a partition of Z, because E ∩ O = ∅, and Z = E ∪ O. ■
Exercise: Let m be an integer greater than or equal to 2. On Z we define the
relation x ≡ y (mod m) ⇔ m|(y−x) (i.e., m divides exactly y−x). Prove that it is
an equivalence relation. What are the equivalence classes? How many are there?

Exercise: On the Cartesian product Z× Z∗ , we define the relation (a, b)R(c, d) ⇔

ad = bc. Prove that R is an equivalence relation. Would it still be an equivalence
relation if we extend it to Z × Z?

5 Functions
A function or mapping f from a set A to a set B, denoted f : A → B, is a
correspondence in which to each element x of A corresponds exactly one element
y = f (x) of B . See (figure 2.12).

b
f b

b b

b
b

b b

b
b
b
b

b b

A B
Figure 2.12: Diagram of a function

Sometimes we represent the function with a diagram like this:

f : A −→ B
x 7−→ y

or
f
A −−→ B
x 7−→ y

For instance, the following represents the function from Z to Z defined by f (x) =
2x + 1:
5. FUNCTIONS 33

f : Z −→ Z
x 7−→ 2x + 1

The element y = f (x) is called the image of x, and x is a preimage of y. For

instance, if f (x) = 2x + 1 then f (7) = 2·7 + 1 = 15. The set A is the domain of f ,
and B is its codomain. If A′ ⊂ A, the image of A′ by f is f (A′ ) = {f (x)| x ∈ A′ },
i.e., the subset of B consisting of all images of elements of A′ . The subset f (A) of
B consisting of all images of elements of A is called the range of f . For instance,
the range of f (x) = 2x + 1 is the set of all integers of the form 2x + 1 for some
integer x, i.e., all odd numbers.

Example 1. Two useful functions from R to Z are the following:

i). The floor function:

⌊x⌋ = greatest integer less than or equal to x

ii). The ceiling function:

⌈x⌉ = least integer greater than or equal to x

Example 2. The modulus operator is the function mod : Z × Z+ → Z defined by:

x mod y = remainder when x is divided by y

Definition 2.1 (Graph:) The graph of a function f : A → B is the subset of

A × B defined by { }
G(f ) = (x, f (x)) | x ∈ A

Example 3. Consider the graph of function: f : R → R

Figure 2.13: Graph of function y = x2

■
34 CHAPTER 2. LANGUAGE OF MATHEMATICS

5.1 Types of Functions

1). One-to-One or Injective: A function f : A → B is called one-to-one or
injective if each element of B is the image of at most one element of A :

∀x1 , x2 ∈ A, f (x1 ) = f (x2 )) ⇐⇒ x1 = x2

2). Onto or Surjective: A function f : A → B is called onto or surjective if every

element of B is the image of some element of A :

∀y ∈ B, ∃x ∈ A such that y = f (x)

3). One-To-One Correspondence or Bijective: A function f : A → B is said to

be a one-to-one correspondence, or bijective, or a bijection, if it is one-to-one
and onto.

5.2 Identity Function

Given a set A , the function 1A : A → A defined by 1A (x) = x for every x in A
is called the identity function for A .

5.3 Function Composition

Given two functions f : A → B and g : B → C, the composite
( ) function of f and g
is the function g ◦ f : A → C defined by (g ◦ f )(x) = g f (x) for every x in A :

g◦f

A f B g C
( )
x y = f (x) z = g(y) = g f (x)

Example 4. If A = B = C = Z, f (x) = x + 1, g(x) = x2 , then (g ◦ f )(x) =

f (x)2 = (x + 1)2 . Also (f ◦ g)(x) = g(x) + 1 = x2 + 1 (i.e, the composition of
functions is not commutative in general). ■
Some properties of function composition are the following:
1). If f : A → B is a function from A to B , then

f ◦ 1A = 1B ◦ f = f

f g h
2). Function composition is associative A −
→B→ − C−
→ D, we have
( ) ( )
h◦ g◦f = h◦g ◦f

Function iteration: If f : A → A is a function from A to A , then it makes sense

to compose it with itself: f 2 = f ◦ f .

Example 5. If f : Z → Z is f (x) = 2x + 1, then f 2 (x) = 2(2x + 1) + 1 = 4x + 3. ■

Analogously, we can define f 3 = f ◦ f ◦ f , and so on, f n = f ◦ . . . ◦ f .
| {z }
(n−times)
5. FUNCTIONS 35

5.4 Inverse Function

If f : A → B is a bijective function, its inverse is the function f −1 : B → A such
that f −1 (y) = x if and only if f (x) = y.

The arrow diagram of f −1 is the same as the arrow diagram of f but with all
arrows reversed.

A characteristic property of the inverse function is that

f −1 ◦ f = 1A and f ◦ f −1 = 1B

Example 6. If f : Z → Z is defined by f (x) = x + 3, then its inverse is f −1 (x) =

x−3. ■

5.5 Operators
A function from A × A to A is called a binary operator on A . For instance the
addition of integers is a binary operator + : Z × Z → Z. In the usual notation
for functions the sum of two integers x and y would be represented +(x, y). This
is called prefix notation. The infix notation consists of writing the symbol of the
binary operator between its arguments, i.e, x + y (this is the most common). There
is also a postfix notation consisting of writing the symbol after the arguments: xy+.

Another example of binary operator on Z is (x, y) 7→ x · y.

A monary or unary operator on A is a function from A to A . For instance

the change of sign x 7→ −x on Z is a unary operator on Z. An example of unary
operator on R∗ is x 7→ 1/x.
36
 Chapter 3
Counting Methods

1 Mathematical induction
Many properties of positive integers can be proved by mathematical induction.

1.1 Principle of Mathematical Induction

Let P be a property of positive integers such that:

37
38 CHAPTER 3. COUNTING METHODS
1. MATHEMATICAL INDUCTION 39

1.2 Strong Form of Mathematical Induction

Let P be a property of positive integers such that:

1. Basis Step: P(1) is true, and

2. Inductive Step: if P(k) is true for all 1 ≤ k ≤ n then P(n + 1) is true.

Then P(n) is true for all positive integers.

1.3 The Well-Ordering Principle

Every nonempty set of positive integers has a smallest element.
40 CHAPTER 3. COUNTING METHODS

2 Recurrence Relations
Here we look at recursive definitions under a different point of view. Rather than
definitions they will be considered as equations that we must solve. The point is
that a recursive definition is actually a definition when there is one and only one ob-
ject satisfying it, i.e., when the equations involved in that definition have a unique
solution. Also, the solution to those equations may provide a closed-form (explicit)
formula for the object defined.

The recursive step in a recursive definition is also called a recurrence relation.

We will focus on k th -order linear recurrence relations, which are of the form:

C0 xn + C1 xn−1 + C2 xn−2 + · · · + Ck xn−k = bn

where C0 ̸= 0. If bn = 0 the recurrence relation is called homogeneous. Other-

wise it is called non-homogeneous. The basis of the recursive definition is also called
initial conditions of the recurrence. So, for instance, in the recursive definition of
the Fibonacci sequence, the recurrence is:

2.1 First Order Recurrence Relations

The homogeneous case can be written in the following way:

xn = rxn−1 (n > 0); x0 = A

Its general solution is

xn = Arn ,
2. RECURRENCE RELATIONS 41

which is a geometric sequence with ratio r.

The non-homogeneous case can be written in the following way:

xn = rxn−1 + cn ; (n > 0); x0 = A

Using the summation notation, its solution can be expressed like this:

∑
n
xn = Arn + ck rn−k
k=1

We examine two particular cases. The first one is

xn = rxn−1 + c; (n > 0); x0 = A

where c is a constant. The solution is

∑
n
rn−1
n
xn = Ar + c rn−k = Arn + c , if r ̸= 1,
r−1
k=1

and
xn = A + cn, if r=1

Example 1. Example: Assume that a country with currently 100 million people
has a population growth rate (birth rate minus death rate) of 1% per year, and it
also receives 100 thousand immigrants per year (which are quickly assimilated and
reproduce at the same rate as the native population). Find its population in 10
years from now. (Assume that all the immigrants arrive in a single batch at the
end of the year.) ■

xn = 1.01xn −1 + 100, 000 (n > 0); x0 = 100, 000, 000.

Thus,
x10 = 110, 462, 317

2.2 Second Order Recurrence Relations

Now we look at the recurrence relation
42 CHAPTER 3. COUNTING METHODS
3. BASIC PRINCIPLE OF COUNTING 43

3 Basic Principle of Counting

3.1 The Rule of Sum
If a task can be performed in m ways, while another task can be performed in
n ways, and the two tasks cannot be performed simultaneously, then performing
either task can be accomplished in m + n ways.

In Set Theory, the rule of sum is determined as: If A and B are disjoint sets
(A ∩ B = ∅) then
n(A ∪ B) = n(A) + n(B)

Example 1. If a class has 30 male students and 25 female students, then the class
has 30 + 25 = 45 students. ■

3.2 The Rule of Product

If a task can be performed in m ways and another independent task can be per-
formed in n ways, then the combination of both tasks can be performed in mn
ways.

As such, the rule of product in Set Theory: Let A × B be the Cartesian product
of sets A and B. Then:
n(A × B) = n(A).n(B)

Example 2. Assume that a license plate contains two letters followed by three
digits. How many different license plates can be printed? ■

Proof: Each letter can be printed in 26 ways, and each digit can be printed in
10 ways, so 26.26.10.10.10 = 676000 different plates can be printed.

Example 3. Given a set A with m elements and a set B with n elements, find the
number of functions from A to B . ■

3.3 The Inclusion-Exclusion Principle

The inclusion-exclusion principle generalizes the rule of sum to non-disjoint sets.
In general, for arbitrary (but finite) sets A, B:

n(A ∪ B) = n(A) + n(B) − n(A ∩ B)

Example 4. Assume that in a university with 1000 students, 200 students are
taking a course in mathematics, 300 are taking a course in physics, and 50 students
are taking both. How many students are taking at least one of those courses? ■
For three sets the following formula applies:

n(A ∪ B ∪ C) = n(A) + n(B) + n(C) − n(A ∩ B) − n(A ∩ C)−

n(B ∩ C) + n(A ∩ B ∩ C)
44 CHAPTER 3. COUNTING METHODS

and for an arbitrary union of sets:

n(A1 ∩ A2 ∩ . . . An ) = s1 − s2 + s3 − s4 + . . . ± sn

where sk = sum of the cardinalities of all possible k−fold intersections of the

given sets.

4 Combinatorics
4.1 Permutations
Assume that we have n objects. Any arrangement of any k of these objects in
a given order is called a permutation of size k. If k = n then we call it just a
permutation of the n objects.

Example 1. The permutations of the letters a, b, c are the following: abc, acb, bac,
bca, cab, cba. The permutations of size 2 of the letters a, b, c, d are: ab, ac, ad, ba, bc, bd,
ca, cb, cd, da, db, dc. ■
Note that the order is important. Given two permutations, they are considered
equal if they have the same elements arranged in the same order.

We find the number P(n, k) of permutations of size k of n given objects in the

following way: The first object in an arrangement can be chosen in n ways, the
second one in n − 1 ways, the third one in n − 2 ways, and so on, hence:
n!
P(n, k) = n × (n − 1) × . . . (n − k + 1) =
| {z } (n − k)!
(k−factors)

where n! = 1 × 2 × 3 × . . . × n is called “n factorial”.

| {z }
(n−factors)
The number P(n, k) of permutations of n objects is

P(n, n) = n!

By convention 0! = 1.

Example 2. There are 3! = 6 permutations of the 3 letters a, b, c. The number of

permutations of size 2 of the 4 letters a, b, c, d is P(4, 2) = 4 × 3 = 12. ■

Example 3. Given a set A with m elements and a set B with n elements, find the
number of one-to-one functions from A to B. ■

4.2 Combinations
Assume that we have a set A with n objects. Any subset of A of size r is called a
combination of n elements taken r at a time.

Example 4. The combinations of the letters a, b, c, d, e taken 3 at a time are:

abc, abd, abe, acd, ace, ade, bcd, bce, bde, cde, where two combinations are considered
identical if they have the same elements regardless of their order. ■
5. GENERALIZED PERMUTATIONS AND COMBINATIONS 45

The number of subsets of size r in a set A with n elements is:

n!
C(n, r) =
r!(n−r)!
( )
The symbol nr , read as “n choose r”, is often used instead of C(n, r).
One way to derive the formula for C(n, r) is the following. Let A be a set with
n objects. In order to generate all possible permutations of size r of the elements
of A we must:

(i) take all possible subsets of size r in the set A, and

(ii) permute the k elements in each subset in all possible ways.

Task (i) can be performed in C(n, r) ways, and task (ii) can be performed in
P(r, r) ways. By the product rule we have P(n, r) = C(n, r) × P(r, r), hence

P(n, r) n!
C(n, r) = =
P(r, r) r!(n−r)!

5 Generalized Permutations and Combinations

5.1 Permutations with Repeated Elements
Assume that we have an alphabet with k letters and we want to write all possible
words containing n1 times the first letter of the alphabet, n2 times the second letter,
…, nk times the k−th letter. How many words can we write? We call this number
P(n; n1 , n2 , . . . , nk ), where n = n1 + n2 + . . . + nk .

Example 1. With 3 a’s and 2 b’s we can write the following 5−letter words:
aaabb, aabab, abaab, baaab, aabba, ababa, baaba, abbaa, babaa, bbaaa. ■
We may solve this problem in the following way, as illustrated with the example
above. Let us distinguish the different copies of a letter with subscripts: a1 a2 a3 b1 b2 .
Next, generate each permutation of this five elements by choosing 1) the position
of each kind of letter, then 2) the subscripts to place on the 3 a’s, then 3) these
subscripts to place on the 2 b’s. Task 1) can be performed in P(5; 3, 2) ways, task
2) can be performed in 3! ways, task 3) can be performed in 2!. By the product
rule we have 5! = P(5; 3, 2) × 3! × 2!, hence P(5; 3, 2) = 5!/3!2!.
In general the formula is:

n!
P(n; n1 , n2 , . . . , nk ) =
n1 !n2 ! . . . nk !

5.2 Combinations with Repetition

Assume that we have a set A with n elements. Any selection of r objects from
A, where each object can be selected more than once, is called a combination of n
objects taken r at a time with repetition.

Example 2. The combinations of the letters a, b, c, d taken 3 at a time with repeti-

tion are: aaa, aab, aac, aad, abb, abc, abd, acc, acd, add, bbb, bbc, bbd, bcc, bcd, bdd, ccc,
ccd, cdd, ddd. ■
46 CHAPTER 3. COUNTING METHODS

Two combinations with repetition are considered identical if they have the same
elements repeated the same number of times, regardless of their order.
Note that the following are equivalent:
(i) The number of combinations of n objects taken r at a time with repetition.
(ii) The number of ways r identical objects can be distributed among n distinct
containers.
(iii) The number of nonnegative integer solutions of the equation:

x1 + x2 + . . . + xn = r

Example 3. Assume that we have 3 different (empty) milk containers and 7 quarts
of milk that we can measure with a one quart measuring cup. In how many ways
can we distribute the milk among the three containers? ■

Proof: We solve the problem in the following way. Let x1 , x2 , x3 be the quarts
of milk to put in containers number 1, 2 and 3 respectively. The number of possible
distributions of milk equals the number of non negative integer solutions for the
equation x1 + x2 + x3 = 7. Instead of using numbers for writing the solutions,
we will use strokes, so for instance we represent the solution x1 = 2, x2 = 1, x3 =
4, or2 + 1 + 4, like this: || + | + ||||. Now, each possible solution is an arrangement( of
)
7 strokes and 2 plus signs, so the number of arrangements is P(9; 7, 2) = 7!2! 9!
= 97 .

The general solution is:

( )
(n + r − 1)! n+r−1
P(n + r − 1; r, n − 1) = =
r!(n − 1)! r

6 Binomial Coefficients
6.1 Binomial Theorem
The following identities can be easily checked:

(x + y)0 = 1
(x + y)1 = x + y
(x + y)2 = x2 + 2xy + y 2
(x + y)3 = x3 + 3x2 y + 3xy 2 + y 3

They can be generalized by the following formula, called the Binomial Theorem:
∑n ( )
n n n−k k
(x + y) = x y
k
k=0
( ) ( ) ( )
n n n n−1 n n−2 2
= x + x y+ x y + ...+
0 1 2
( ) ( )
n n−1 n n
xy + y
n−1 n
6. BINOMIAL COEFFICIENTS 47

We can find this formula by writing

(x + y)n = (x + y) × (x + y) × . . . × (x + y)
| {z }
(n−factors)

expanding, and grouping terms of the form xa y b . Since there are n factors of
the form (x + y), we have a + b = n, hence the terms must be of the form xn−k y k .
The coefficient of xn−k y k will be equal to the number of ways in which we can select
the y from any ( )the x from the remaining n − k factors), which
( )k of the factors (and
is C(n, k) = nk . The expression nk is often called binomial coefficient.

Example 1. Prove the following:

n ( )
∑ ∑
n ( )
n n k n
=2 and (−1) =0
k k
k=0 k=0

6.2 Properties of Binomial Coefficients

The binomial coefficients have the following properties:
( ) ( n )
i. nk = n−k
( ) (n ) ( n )
ii. n+1
k+1 = k + k+1
( )
The first property follows easily from nk = k!(n−k)!
n!
.
The second property can be proved by ( choosing
) a distinguished element a in a
set A of n + 1 elements. The set A has n+1 k+1 subsets of size k + 1. Those subsets
can be partitioned into two classes: that of the subsets containing a, and that of the
subsets not containing a. The number ( ) of subsets containing a equals the number
of subsets of A − {a} of size k, i.e., nk . The number( of subsets
) not containing a is
n
the number of subsets of A − {a} of size k + 1, i.e., k+1 . Using the sum principle
( ) (n ) ( n )
we find that in fact n+1
k+1 = k + k+1 .

6.3 Pascal’s Triangle

The properties shown in the previoussection allow us to compute binomial coeffi-
cients in a simple way. Look at the following triangular arrangement of binomial
coefficients:
(0)
0
(1 ) (1)
0 1
(2) (2) (2 )
0 1 2
(3) (3 ) (3) (3 )
0 1 2 3
(4 ) (4) (4) (4 ) (4)
0 1 2 3 4

We notice that each binomial coefficient on this arrangement must be the sum
( ) of
the two closest binomial coefficients on the line above it. This together with n0 =
48 CHAPTER 3. COUNTING METHODS

(n )
n = 1, allows us to compute very quickly the values of the binomial coefficients
on the arrangement:

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1

This arrangement of binomial coefficients is called Pascal’s Triangle1 .

7 The Pigeonhole Principle

7.1 The Pigeonhole Principle
The pigeonhole principle is used for proving that a certain situation must actually
occur. It says the following: If n pigeonholes are occupied by m pigeons and m > n,
then at least one pigeonhole is occupied by more than one pigeon2 .
Example: In any given set of 13 people at least two of them have their birthday
during the same month. Example: Let S be a set of eleven 2-digit numbers. Prove
that S must have two elements whose digits have the same difference (for instance
in S = 10, 14, 19, 22, 26, 28, 49, 53, 70, 90, 93, the digits of the numbers 28 and 93
have the same difference: 8 − 2 = 6, 9 − 3 = 6.) Answer: The digits of a two-digit
number can have 10 possible differences (from 0 to 9). So, in a list of 11 numbers
there must be two with the same difference.
Example: Assume that we choose three different digits from 1 to 9 and write all
permutations of those digits. Prove that among the 3-digit numbers written that
way there are two whose difference is a multiple of 500. Answer: There are 9 · 8
· 7 = 504 permutations of three digits. On the other hand if we divide the 504
numbers by 500 we can get only 500 possible remainders, so at least two numbers
give the same remainder, and their difference must be a multiple of 500. Exercise:
Prove that if we select n + 1 numbers from the set S = 1, 2, 3, . . . , 2n, among
the numbers selected there are two such that one is a multiple of the other one.

1
Although it was already known by the Chinese in the XIV century
2
The Pigeonhole Principle (Schubfachprinzip) was first used by Dirichlet in Number Theory.
The term pigeonhole actually refers to one of those old-fashioned writing desks with thin vertical
wooden partitions in which to file letters.