CIS160

Mathematical Foundations of
Computer Science
Some Notes

Jean Gallier
Department of Computer and Information Science
University of Pennsylvania
Philadelphia, PA 19104, USA
e-mail: jean@cis.upenn.edu

�c Jean Gallier
Please, do not reproduce without permission of the author

December 15, 2009

2
Contents

1 Mathematical Reasoning, Proof Princi-

ples and Logic 7
1.1 Problems, Motivations . . . . . . . . . . . 7
1.2 Inference Rules, Deductions, The Proof
Systems Nm⇒ and N G ⇒ m . . . . . . . . . . 19
1.3 Adding ∧, ∨, ⊥; The Proof Systems
Nc⇒,∧,∨,⊥ and N G ⇒,∧,∨,⊥
c . . . . . . . . . 46
1.4 Clearing Up Differences Between Rules In-
volving ⊥ . . . . . . . . . . . . . . . . . . 71
1.5 De Morgan Laws and Other Rules of Clas-
sical Logic . . . . . . . . . . . . . . . . . 80
1.6 Formal Versus Informal Proofs; Some Ex-
amples . . . . . . . . . . . . . . . . . . . 85
1.7 Truth Values Semantics for Classical Logic 103
1.8 Adding Quantifiers; The Proof Systems
Nc⇒,∧,∨,∀,∃,⊥, N G ⇒,∧,∨,∀,∃,⊥
c . . . . . . . . 113
1.9 First-Order Theories . . . . . . . . . . . . 148
1.10 Basics Concepts of Set Theory . . . . . . 166
3
4 CONTENTS

2 Relations, Functions, Partial Functions 193

2.1 What is a Function? . . . . . . . . . . . . 193
2.2 Ordered Pairs, Cartesian Products, Rela-
tions, etc. . . . . . . . . . . . . . . . . . . 203
2.3 Induction Principles on N . . . . . . . . . 219
2.4 Composition of Relations and Functions . 241
2.5 Recursion on N . . . . . . . . . . . . . . . 245
2.6 Inverses of Functions and Relations . . . . 250
2.7 Injections, Surjections, Bijections, Permu-
tations . . . . . . . . . . . . . . . . . . . 258
2.8 Direct Image and Inverse Image . . . . . . 268
2.9 Equinumerosity; Pigeonhole Principle;
Schröder–Bernstein . . . . . . . . . . . . . 274
2.10 An Amazing Surjection: Hilbert’s Space
Filling Curve . . . . . . . . . . . . . . . . 298
2.11 Strings, Multisets, Indexed Families . . . . 302

3 Graphs, Part I: Basic Notions 319

3.1 Why Graphs? Some Motivations . . . . . 319
3.2 Directed Graphs . . . . . . . . . . . . . . 324
3.3 Path in Digraphs; Strongly Connected Com-
ponents . . . . . . . . . . . . . . . . . . . 336
3.4 Undirected Graphs, Chains, Cycles, Con-
nectivity . . . . . . . . . . . . . . . . . . 362
3.5 Trees and Arborescences . . . . . . . . . . 380
CONTENTS 5

3.6 Minimum (or Maximum) Weight Spanning

Trees . . . . . . . . . . . . . . . . . . . . 389

4 Some Counting Problems; Multinomial

Coefficients 401
4.1 Counting Permutations and Functions . . 401
4.2 Counting Subsets of Size k; Multinomial
Coefficients . . . . . . . . . . . . . . . . . 407
4.3 Some Properties of the Binomial Coefficients423
4.4 The Inclusion-Exclusion Principle . . . . . 446

5 Partial Orders, Equivalence Relations, Lat-

tices 459
5.1 Partial Orders . . . . . . . . . . . . . . . 459
5.2 Lattices and Tarski’s Fixed Point Theorem 478
5.3 Well-Founded Orderings and Complete In-
duction . . . . . . . . . . . . . . . . . . . 487
5.4 Unique Prime Factorization in Z and GCD’s502
5.5 Equivalence Relations and Partitions . . . 521
5.6 Transitive Closure, Reflexive and Transi-
tive Closure . . . . . . . . . . . . . . . . 533
5.7 Fibonacci and Lucas Numbers; Mersenne
Primes . . . . . . . . . . . . . . . . . . . 536
5.8 Distributive Lattices, Boolean Algebras, Heyt-
ing Algebras . . . . . . . . . . . . . . . . 570
6 CONTENTS
Chapter 1

Mathematical Reasoning, Proof

Principles and Logic

1.1 Problems, Motivations

Problem 1. Find formulae for the sums

1 + 2 + 3 + ··· + n = ?
12 + 22 + 32 + · · · + n2 = ?
13 + 23 + 33 + · · · + n3 = ?
············
1k + 2k + 3k + · · · + nk = ?

Jacob Bernoulli (1654-1705) discovered the formulae listed

below:

7
8 CHAPTER 1. MATHEMATICAL REASONING, PROOF PRINCIPLES AND LOGIC

If
Sk (n) = 1k + 2k + 3k + · · · + nk
then
S0(n) = 1n
1 1
S1(n) = n2 + n
2 2
1 3 1 1
S2(n) = n + n2 + n
3 2 6
1 1 1
S3(n) = n4 + n3 + n2
4 2 4
1 1 1 1
S4(n) = n5 + n4 + n3 − n
5 2 3 30
1 6 1 5 5 4 1
S5(n) = n + n + n − n2
6 2 12 12
1 1 1 1 1
S6(n) = n7 + n6 + n5 − n3 + n
7 2 2 6 42
1 1 7 7 1
S7(n) = n8 + n7 + n6 − n4 + n2
8 2 12 24 12
1 1 2 7 2 1
S8(n) = n9 + n8 + n7 − n5 + n3 − n
9 2 3 15 9 30
1 10 1 9 3 7 1 3
S9(n) = n + n + n8 − n6 + n4 − n2
10 2 4 10 2 20
1 11 1 10 5 9 1 5
S10(n) = n + n + n − n7 + n5 − n3 + n
11 2 6 2 66

Is there a pattern?
What are the mysterious numbers
1 1 1 1 1 5
1 0 − 0 0 − 0 ?
2 6 30 42 30 66
1.1. PROBLEMS, MOTIVATIONS 9

The next two are

691
0 −
2730
Why?

It turns out that the answer has to do with the Bernoulli

polynomials, Bk (x), with
� k � �
k k−i i
Bk (x) = x B,
i=0
i

where the B i are the Bernoulli numbers.

There are various ways of computing the Bernoulli num-

bers, including some recurrence formulae.

Amazingly, the Bernoulli numbers show up in very differ-

ent areas of mathematics, in particular, algebraic topol-
ogy!
10 CHAPTER 1. MATHEMATICAL REASONING, PROOF PRINCIPLES AND LOGIC

Figure 1.1: Funny spheres (in 3D)

Figure 1.2: A plane (granite slab!)

Problem 2. Prove that a sphere and a plane in 3D have

the same number of points.

More precisely, find a one-to-one and onto mapping of the

sphere onto the plane (a bijection)

Actually, there are also bijections between the sphere and

a (finite) rectangle, with or without its boundary!
1.1. PROBLEMS, MOTIVATIONS 11

Problem 3. Counting the number of derangements of

n elements.

A permutation of the set {1, 2, . . . , n} is any one-to-one

function, f , of {1, 2, . . . , n} into itself. A permutation is
characterized by its image: {f (1), f (2), . . . , f (n)}.

For example, {3, 1, 4, 2} is a permutation of {1, 2, 3, 4}.

It is easy to show that there are n! = n · (n − 1) · · · 3 · 2

distinct permutations of n elements.

A derangements is a permutation that leaves no element

fixed, that is, f (i) �= i for all i.

{3, 1, 4, 2} is a derangement of {1, 2, 3, 4} but

{3, 2, 4, 1} is not a derangement since 2 is left fixed.

What is the number of derangements, pn, of n elements?

12 CHAPTER 1. MATHEMATICAL REASONING, PROOF PRINCIPLES AND LOGIC

The number pn/n! can be interpreted as a probability.

Say n people go to a restaurant and they all check their

coat. Unfortunately, the cleck loses all the coat tags.
Then, pn/n! is the probability that nobody gets her or
his coat back!
1 1
Interestingly, pn/n! has limit e ≈ 3 as n goes to infinity,
a surprisingly large number.
1.1. PROBLEMS, MOTIVATIONS 13

1 2 3 4

5 6 7 8 9

10 11 12 13 14 15

16 17 18 19

Figure 1.3: An undirected graph modeling a city map

Problem 4. Finding strongly connected components

in a directed graph.

The undirected graph of Figure 1.3 represents a map of

some busy streets in a city.

The city decides to improve the traffic by making these

streets one-way streets.

However, a good choice of orientation should allow one

to travel between any two locations. We say that the
resulting directed graph is strongly connected .
14 CHAPTER 1. MATHEMATICAL REASONING, PROOF PRINCIPLES AND LOGIC

1 2 3 4

5 6 7 8 9

10 11 12 13 14 15

16 17 18 19

Figure 1.4: A choice of one-way streets

A possibility of orienting the streets is shown in Figure

1.4.

Is the above graph strongly connected?

If not, how do we find its strongly connected compo-

nents?

How do we use the strongly connected components to find

an orientation that solves our problem?
1.1. PROBLEMS, MOTIVATIONS 15

card 2 card 1
d2
d3
card n
dn+1

Figure 1.5: Stack of overhanging cards

Problem 5. The maximum overhang problem.

How do we stack n cards on the edge of a table, respecting

the law of gravity, and achieving a maximum overhang.

We assume each card is 2 units long.

Is it possible to achieve any desired amount of overhang

or is there a fixed bound?

How many cards are needed to achieve an overhang of d

units?
16 CHAPTER 1. MATHEMATICAL REASONING, PROOF PRINCIPLES AND LOGIC

Problem 6. Ramsey Numbers

A version of Ramsey’s Theorem says that for every pair,

(r, s), of positive natural numbers, there is a least positive
natural number, R(r, s), such that for every coloring of
the edges of the complete (undirected) graph on R(r, s)
vertices using the colors blue and red , either there is a
complete subgraph with r vertices whose edges are all
blue or there is a complete subgraph with s vertices whose
edges are all red .

So, R(r, r), is the smallest number of vertices of a com-

plete graph whose edges are colored either blue or red
that must contain a complete subgraph with r vertices
whose edges are all of the same color.
1.1. PROBLEMS, MOTIVATIONS 17

Figure 1.6: Left: A 2-coloring of K5 with no monochromatic K3 ; Right: A 2-coloring of K6

with several monochromatic K3 ’s

The graph shown in Figure 1.6 (left) is a complete graph

on 5 vertices with a coloring of its edges so that there is
no complete subgraph on 3 vertices whose edges are all
of the same color.

Thus, R(3, 3) > 5.

There are
215 = 32768
2-colored complete graphs on 6 vertices. One of these
graphs is shown in Figure 1.6 (right).

It can be shown that all of them contain a triangle whose

edges have the same color, so R(3, 3) = 6.
18 CHAPTER 1. MATHEMATICAL REASONING, PROOF PRINCIPLES AND LOGIC

The numbers, R(r, s), are called Ramsey numbers.

It turns out that there are very few numbers r, s for

which R(r, s) is known because the number of colorings
of a graph grows very fast! For example, there are
243×21 = 2903 > 102490 > 10270
2-colored complete graphs with 43 vertices, a huge num-
ber!

In comparison, the universe is only approximately 14 bil-

lions years old, namely 14 × 109 years old.

For example, R(4, 4) = 18, R(4, 5) = 25, but R(5, 5) is

unknown, although it can be shown that
43 ≤ R(5, 5) ≤ 49.

Finding the R(r, s), or, at least some sharp bounds for
them, is an open problem.