DM23 LNss-tablet
DM23 LNss-tablet
Departement Informatik
Diskrete
Mathematik
Ueli Maurer
Herbstsemester 2023
Vorwort
1 Die Mathematik der Informatik sollte demnach einfacher verständlich sein als die kontinuier-
liche Mathematik (z.B. Analysis). Sollte dies dem Leser ab und zu nicht so erscheinen, so ist es
vermutlich lediglich eine Frage der Gewöhnung.
2 Die Numerik befasst sich unter anderem mit dem Thema der (in einem Computer unvermeid-
baren) diskreten Approximation reeller Grössen und den daraus resultierenden Problemen wie z.B.
numerische Instabilitäten.
Das Teilgebiet der Mathematik, das sich mit diskreten Strukturen befasst,
heisst diskrete Mathematik. Der Begriff “diskret” ist zu verstehen als endlich oder
abzählbar unendlich. Viele Teilbereiche der diskreten Mathematik sind so wichtig,
dass sie vertieft in einer eigenen Vorlesung behandelt werden. Dazu gehören
die Theorie der Berechnung, also die Formalisierung der Begriffe Berechnung
und Algorithmus, welche in der Vorlesung “Theoretische Informatik” behan-
delt wird, sowie die diskrete Wahrscheinlichkeitstheorie. Eine inhaltliche Ver-
wandtschaft besteht auch zur Vorlesung über Algorithmen und Datenstruktu-
ren.
In dieser Lehrveranstaltung werden die wichtigsten Begriffe, Techniken und
Resultate der diskreten Mathematik eingeführt. Hauptziele der Vorlesung sind
nebst der Behandlung der konkreten Themen ebenso die adäquate Modellie-
rung von Sachverhalten, sowie das Verständnis für die Wichtigkeit von Ab-
straktion, von Beweisen und generell der mathematisch-präzisen Denkweise,
die auch beim Entwurf von Softwaresystemen enorm wichtig ist. Zudem wer-
den einige Anwendungen diskutiert, z.B. aus der Kryptografie, der Codierungs-
theorie oder der Algorithmentheorie. Diskrete Mathematik ist ein sehr breites
Gebiet. Entsprechend unterschiedliche Ansätze gibt es auch für den Aufbau ei-
ner Vorlesung über das Thema. Mein Ziel bei der Konzipierung dieser Lehr-
veranstaltung war es, speziell auf Themen einzugehen, die in der Informatik
wichtig sind, sowie dem Anspruch zu genügen, keine zentralen Themen der
diskreten Mathematik auszulassen. Ausnahmen sind die Kombinatorik und die
Graphentheorie, die früher als Kapitel 4 und 5 dieses Skriptes erschienen, in der
letzten Studienplanrevision aber in andere Vorlesungen verschoben wurden.
Die sechs Kapitel sind
Viele Beispiele werden nur an der Tafel oder in den Übungen behandelt. Die
Vorlesung und die Übungen bilden einen integralen Bestandteil der Lehrveran-
staltung und des Prüfungsstoffes. Es gibt kein einzelnes Buch, das den ganzen
Stoff der Lehrveranstaltung behandelt. Aber unten folgt eine Liste guter Bücher,
die als Ergänzung dienen können. Sie decken aber jeweils nur Teile der Vorle-
sung ab, gehen zum Teil zu wenig tief, oder sind zu fortgeschritten im Vergleich
zur Vorlesung.
iv
• K. H. Rosen, Discrete Mathematics and its Applications, fourth edition,
McGraw-Hill.
• A. Steger, Diskrete Strukturen, Band 1, Springer Verlag.
• M. Aigner, Diskrete Mathematik, Vieweg.
• J. Matousek, J. Nesetril, Discrete Mathematics, Clarendon Press.
• I. Anderson, A First Course in Discrete Mathematics, Springer Verlag.
• U. Schöning, Logik für Informatiker, Spektrum Verlag, 5. Auflage, 2000.
• M. Kreuzer and S. Kühling, Logik für Informatiker, Pearson Studium,
2006.
v
Contents
Vorwort iii
vii
2.3.6 Tautologies and Satisfiability . . . . . . . . . . . . . . . . . 22
2.3.7 Logical Circuits * . . . . . . . . . . . . . . . . . . . . . . . . 23
2.4 A First Introduction to Predicate Logic . . . . . . . . . . . . . . . . 23
2.4.1 Predicates . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.4.2 Functions and Constants . . . . . . . . . . . . . . . . . . . . 24
2.4.3 The Quantifiers ∃ and ∀ . . . . . . . . . . . . . . . . . . . . 24
2.4.4 Nested Quantifiers . . . . . . . . . . . . . . . . . . . . . . . 25
2.4.5 Interpretation of Formulas . . . . . . . . . . . . . . . . . . . 26
2.4.6 Tautologies and Satisfiability . . . . . . . . . . . . . . . . . 27
2.4.7 Equivalence and Logical Consequence . . . . . . . . . . . . 27
2.4.8 Some Useful Rules . . . . . . . . . . . . . . . . . . . . . . . 28
2.5 Logical Formulas vs. Mathematical Statements . . . . . . . . . . . 28
2.5.1 Fixed Interpretations and Formulas as Statements . . . . . 28
2.5.2 Mathematical Statements about Formulas . . . . . . . . . . 29
2.6 Some Proof Patterns . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.6.1 Composition of Implications . . . . . . . . . . . . . . . . . 30
2.6.2 Direct Proof of an Implication . . . . . . . . . . . . . . . . . 30
2.6.3 Indirect Proof of an Implication . . . . . . . . . . . . . . . . 30
2.6.4 Modus Ponens . . . . . . . . . . . . . . . . . . . . . . . . . 31
2.6.5 Case Distinction . . . . . . . . . . . . . . . . . . . . . . . . . 31
2.6.6 Proofs by Contradiction . . . . . . . . . . . . . . . . . . . . 32
2.6.7 Existence Proofs . . . . . . . . . . . . . . . . . . . . . . . . . 34
2.6.8 Existence Proofs via the Pigeonhole Principle . . . . . . . . 34
2.6.9 Proofs by Counterexample . . . . . . . . . . . . . . . . . . 36
2.6.10 Proofs by Induction . . . . . . . . . . . . . . . . . . . . . . 36
viii
3.2.6 Constructing Sets from the Empty Set . . . . . . . . . . . . 46
3.2.7 A Construction of the Natural Numbers . . . . . . . . . . . 47
3.2.8 The Power Set of a Set . . . . . . . . . . . . . . . . . . . . . 48
3.2.9 The Cartesian Product of Sets . . . . . . . . . . . . . . . . . 48
3.3 Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
3.3.1 The Relation Concept . . . . . . . . . . . . . . . . . . . . . 49
3.3.2 Representations of Relations . . . . . . . . . . . . . . . . . 50
3.3.3 Set Operations on Relations . . . . . . . . . . . . . . . . . . 51
3.3.4 The Inverse of a Relation . . . . . . . . . . . . . . . . . . . . 51
3.3.5 Composition of Relations . . . . . . . . . . . . . . . . . . . 52
3.3.6 Special Properties of Relations . . . . . . . . . . . . . . . . 53
3.3.7 Transitive Closure . . . . . . . . . . . . . . . . . . . . . . . 55
3.4 Equivalence Relations . . . . . . . . . . . . . . . . . . . . . . . . . 55
3.4.1 Definition of Equivalence Relations . . . . . . . . . . . . . 55
3.4.2 Equivalence Classes Form a Partition . . . . . . . . . . . . 56
3.4.3 Example: Definition of the Rational Numbers . . . . . . . 57
3.5 Partial Order Relations . . . . . . . . . . . . . . . . . . . . . . . . . 58
3.5.1 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
3.5.2 Hasse Diagrams . . . . . . . . . . . . . . . . . . . . . . . . . 59
3.5.3 Combinations of Posets and the Lexicographic Order . . . 61
3.5.4 Special Elements in Posets . . . . . . . . . . . . . . . . . . . 61
3.5.5 Meet, Join, and Lattices . . . . . . . . . . . . . . . . . . . . 63
3.6 Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
3.7 Countable and Uncountable Sets . . . . . . . . . . . . . . . . . . . 65
3.7.1 Countability of Sets . . . . . . . . . . . . . . . . . . . . . . . 65
3.7.2 Between Finite and Countably Infinite . . . . . . . . . . . . 66
3.7.3 Important Countable Sets . . . . . . . . . . . . . . . . . . . 67
3.7.4 Uncountability of {0, 1}∞ . . . . . . . . . . . . . . . . . . . 69
3.7.5 Existence of Uncomputable Functions . . . . . . . . . . . . 70
4 Number Theory 72
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
4.1.1 Number Theory as a Mathematical Discipline . . . . . . . 72
4.1.2 What are the Integers? . . . . . . . . . . . . . . . . . . . . . 73
4.2 Divisors and Division . . . . . . . . . . . . . . . . . . . . . . . . . . 74
4.2.1 Divisors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
ix
4.2.2 Division with Remainders . . . . . . . . . . . . . . . . . . . 74
4.2.3 Greatest Common Divisors . . . . . . . . . . . . . . . . . . 75
4.2.4 Least Common Multiples . . . . . . . . . . . . . . . . . . . 77
4.3 Factorization into Primes . . . . . . . . . . . . . . . . . . . . . . . . 77
4.3.1 Primes and the Fundamental Theorem of Arithmetic . . . 77
4.3.2 Proof of the Fundamental Theorem of Arithmetic * . . . . 78
4.3.3 Expressing gcd and lcm . . . . . . . . . . . . . . . . . . . . 79
4.3.4 Non-triviality of Unique Factorization * . . . . . . . . . . . 79
4.3.5 Irrationality of Roots * . . . . . . . . . . . . . . . . . . . . . 80
4.3.6 A Digression to Music Theory * . . . . . . . . . . . . . . . . 80
4.4 Some Basic Facts About Primes * . . . . . . . . . . . . . . . . . . . 81
4.4.1 The Density of Primes . . . . . . . . . . . . . . . . . . . . . 81
4.4.2 Remarks on Primality Testing . . . . . . . . . . . . . . . . . 82
4.5 Congruences and Modular Arithmetic . . . . . . . . . . . . . . . . 83
4.5.1 Modular Congruences . . . . . . . . . . . . . . . . . . . . . 83
4.5.2 Modular Arithmetic . . . . . . . . . . . . . . . . . . . . . . 84
4.5.3 Multiplicative Inverses . . . . . . . . . . . . . . . . . . . . . 86
4.5.4 The Chinese Remainder Theorem . . . . . . . . . . . . . . 87
4.6 Application: Diffie-Hellman Key-Agreement . . . . . . . . . . . . 88
5 Algebra 91
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
5.1.1 What Algebra is About . . . . . . . . . . . . . . . . . . . . . 91
5.1.2 Algebraic Structures . . . . . . . . . . . . . . . . . . . . . . 91
5.1.3 Some Examples of Algebras . . . . . . . . . . . . . . . . . . 92
5.2 Monoids and Groups . . . . . . . . . . . . . . . . . . . . . . . . . . 92
5.2.1 Neutral Elements . . . . . . . . . . . . . . . . . . . . . . . . 93
5.2.2 Associativity and Monoids . . . . . . . . . . . . . . . . . . 93
5.2.3 Inverses and Groups . . . . . . . . . . . . . . . . . . . . . . 94
5.2.4 (Non-)minimality of the Group Axioms . . . . . . . . . . . 95
5.2.5 Some Examples of Groups . . . . . . . . . . . . . . . . . . . 96
5.3 The Structure of Groups . . . . . . . . . . . . . . . . . . . . . . . . 97
5.3.1 Direct Products of Groups . . . . . . . . . . . . . . . . . . . 97
5.3.2 Group Homomorphisms . . . . . . . . . . . . . . . . . . . . 98
5.3.3 Subgroups . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
5.3.4 The Order of Group Elements and of a Group . . . . . . . 99
x
5.3.5 Cyclic Groups . . . . . . . . . . . . . . . . . . . . . . . . . . 100
5.3.6 Application: Diffie-Hellman for General Groups . . . . . 101
5.3.7 The Order of Subgroups . . . . . . . . . . . . . . . . . . . . 101
5.3.8 The Group Z∗m and Euler’s Function . . . . . . . . . . . . . 102
5.4 Application: RSA Public-Key Encryption . . . . . . . . . . . . . . 104
5.4.1 e-th Roots in a Group . . . . . . . . . . . . . . . . . . . . . . 105
5.4.2 Description of RSA . . . . . . . . . . . . . . . . . . . . . . . 105
5.4.3 On the Security of RSA * . . . . . . . . . . . . . . . . . . . . 107
5.4.4 Digital Signatures * . . . . . . . . . . . . . . . . . . . . . . . 107
5.5 Rings and Fields . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
5.5.1 Definition of a Ring . . . . . . . . . . . . . . . . . . . . . . . 108
5.5.2 Units and the Multiplicative Group of a Ring . . . . . . . . 109
5.5.3 Divisors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
5.5.4 Zerodivisors and Integral Domains . . . . . . . . . . . . . 110
5.5.5 Polynomial Rings . . . . . . . . . . . . . . . . . . . . . . . . 111
5.5.6 Fields . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
5.6 Polynomials over a Field . . . . . . . . . . . . . . . . . . . . . . . . 115
5.6.1 Factorization and Irreducible Polynomials . . . . . . . . . 115
5.6.2 The Division Property in F [x] . . . . . . . . . . . . . . . . . 117
5.6.3 Analogies Between Z and F [x], Euclidean Domains * . . . 118
5.7 Polynomials as Functions . . . . . . . . . . . . . . . . . . . . . . . 119
5.7.1 Polynomial Evaluation . . . . . . . . . . . . . . . . . . . . . 119
5.7.2 Roots . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
5.7.3 Polynomial Interpolation . . . . . . . . . . . . . . . . . . . 120
5.8 Finite Fields . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
5.8.1 The Ring F [x]m(x) . . . . . . . . . . . . . . . . . . . . . . . 121
5.8.2 Constructing Extension Fields . . . . . . . . . . . . . . . . 123
5.8.3 Some Facts About Finite Fields * . . . . . . . . . . . . . . . 125
5.9 Application: Error-Correcting Codes . . . . . . . . . . . . . . . . . 126
5.9.1 Definition of Error-Correcting Codes . . . . . . . . . . . . . 126
5.9.2 Decoding . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
5.9.3 Codes based on Polynomial Evaluation . . . . . . . . . . . 128
6 Logic 130
6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130
6.2 Proof Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
xi
6.2.1 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
6.2.2 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133
6.2.3 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
6.2.4 Proof Systems in Theoretical Computer Science * . . . . . . 136
6.3 Elementary General Concepts in Logic . . . . . . . . . . . . . . . . 136
6.3.1 The General Goal of Logic . . . . . . . . . . . . . . . . . . . 137
6.3.2 Syntax, Semantics, Interpretation, Model . . . . . . . . . . 137
6.3.3 Syntax . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
6.3.4 Semantics . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138
6.3.5 Connection to Proof Systems * . . . . . . . . . . . . . . . . 139
6.3.6 Satisfiability, Tautology, Consequence, Equivalence . . . . 139
6.3.7 The Logical Operators ∧, ∨, and ¬ . . . . . . . . . . . . . . 140
6.3.8 Logical Consequence vs. Unsatisfiability . . . . . . . . . . 142
6.3.9 Theorems and Theories . . . . . . . . . . . . . . . . . . . . 142
6.4 Logical Calculi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
6.4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
6.4.2 Hilbert-Style Calculi . . . . . . . . . . . . . . . . . . . . . . 144
6.4.3 Soundness and Completeness of a Calculus . . . . . . . . . 145
6.4.4 Some Derivation Rules . . . . . . . . . . . . . . . . . . . . . 146
6.4.5 Derivations from Assumptions . . . . . . . . . . . . . . . . 147
6.4.6 Connection to Proof Systems * . . . . . . . . . . . . . . . . 148
6.5 Propositional Logic . . . . . . . . . . . . . . . . . . . . . . . . . . . 148
6.5.1 Syntax . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148
6.5.2 Semantics . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149
6.5.3 Brief Discussion of General Logic Concepts . . . . . . . . . 149
6.5.4 Normal Forms . . . . . . . . . . . . . . . . . . . . . . . . . 150
6.5.5 The Resolution Calculus for Propositional Logic . . . . . . 152
6.6 Predicate Logic (First-order Logic) . . . . . . . . . . . . . . . . . . 156
6.6.1 Syntax . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156
6.6.2 Free Variables and Variable Substitution . . . . . . . . . . . 156
6.6.3 Semantics . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157
6.6.4 Predicate Logic with Equality . . . . . . . . . . . . . . . . . 159
6.6.5 Some Basic Equivalences Involving Quantifiers . . . . . . 159
6.6.6 Substitution of Bound Variables . . . . . . . . . . . . . . . 160
6.6.7 Normal Forms . . . . . . . . . . . . . . . . . . . . . . . . . 161
6.6.8 Derivation Rules . . . . . . . . . . . . . . . . . . . . . . . . 162
xii
xiii
1
1.2. Discrete Mathematics: A Selection of Teasers 2
the form of calculations (e.g. calculating the wing profile for an airplane).
In contrast, in Computer Science, mathematical reasoning often happens
in the form of a derivation (or, more mathematically stated, a proof). For
example, understanding a computer program means to understand it as
a well-defined discrete mathematical object, and making a desirable state-
ment about the program (e.g. that it terminates within a certain number
of steps) means to prove (or derive) this statement. Similarly, the state-
ment that a system (e.g. a block-chain system) is secure is a mathematical
statement that requires a proof.
k 2 ≡3 1
discussed in this section, for example the interpolation of a polynomial, computation modulo a
number n, Euclid’s algorithm for computing greatest common divisors, or matrices.
3 Chapter 1. Introduction and Motivation
Hence we have P (k) = 0 for all k with k ≡3 0 (i.e.,4 the k divisible by 3).5
The case k = 4 can be solved easily by finding a solution for each of the three
types of squares (corner, edge, interior of board) that could be marked. Hence
we have proved P (4) = 1. This proof type will later be called a proof by case
distinction.
For the case k = 5 one can prove that P (5) = 0 by showing that there is (at
least) a square which, when marked, leaves an area not coverable by L-shapes.
Namely, if one marks a square next to the center square, then it is impossible to
cover the remaining area by L-shapes. This proof type will later be called a proof
by counterexample.
We have P (6) = 0 because 6 is divisible by 3, and hence the next interesting
case is k = 7. The reader can prove as an exercise that P (7) = 1. (How many
cases do you have to check?)
The question of interest is, for a general k, whether P (k) = 1 or P (k) = 0.
But one can prove (explained in the lecture) that
P (k) = 1 =⇒ P (2k) = 1,
i.e., that if the statement is true for some k, then it is also true for two times k.
This implies that P (2i ) = 1 for any i and also that P (7 · 2i ) = 1 for any i. Hence
we have P (8) = 1, and P (9) = 0, leaving P (10) and P (11) as the next open
cases. One can also prove the following generalization of the above-stated fact:
We point out that, already in this first example, we understand the reasoning
leading to the conclusion P (k) = 0 or P (k) = 1 as a proof.
Example 1.2. Consider the following simple method for testing primality. Prove
or disprove that an odd number n is a prime if and only if 2n−1 divided by n
yields remainder 1, i.e., if
2n−1 ≡n 1.
One can easily check that 2n−1 ≡n 1 holds for the primes n = 3, 5, 7, 11, 13 (and
many more). Moreover, one can also easily check that 2n−1 6≡n 1 for the first odd
composite numbers n = 9, 15, 21, 25, etc. But is the formula a general primality
test? The solution to this problem will be given in Chapter 4.
Example 1.3. The well-known cancellation law for real numbers states that if
ab = ac and a 6= 0, then b = c. In other words, one can divide both sides by
a. How general is this law? Does it hold for the polynomials over R, i.e., does
4 “i.e.”,
the abbreviation of the Latin “id est”, should be read as “that is” (German: “das heisst”).
5 Thefact that the equation k 2 ≡p 1 has two solutions modulo p, for any prime p, not just for
p = 3, will be obvious once we understand that computing modulo p is a field (see Chapter 5) and
that every element of a field has either two square roots or none.
1.3. Abstraction: Simplicity and Generality 4
a(x)b(x) = a(x)c(x) imply b(x) = c(x) if a(x) 6= 0? Does it hold for the integers
modulo m, i.e., does ab ≡m ac imply b ≡m c if a 6= 0? Does it hold for the
permutations, when multiplication is defined as composition of permutations?
What does the condition a 6= 0 mean in this case? Which abstraction lies behind
the cancellation law? This is a typical algebraic question (see Chapter 5).
Example 1.4. It is well-known that one can interpolate a polynomial a(x) =
ad xd + ad−1 xd−1 + · · · a1 x + a0 of degree d with real coefficients from any d + 1
values a(αi ), for distinct α1 , . . . , αd+1 . Can we also construct polynomials over a
finite domain (which is of more interest and use in Computer Science), keeping
this interpolation property?
For example, consider computation modulo 5. There are 53 = 125 polyno-
mials a2 x2 + a1 x + a0 of degree 2 because we can freely choose three coefficients
from {0, 1, 2, 3, 4}. It is straight-forward (though cumbersome) to verify that if
we fix any three evaluation points (for example 0, 2, and 3), then the polyno-
mial is determined by the values at these points. In other words, two different
polynomials p and q result in distinct lists (p(0), p(2), p(3)) and (q(0), q(2), q(3))
of polynomial values. What is the general principle explaining this? For the
answer and applications, see Chapter 5.
a a
the larger integer is divided by the smaller integer, and the pair of integers is
replaced by the pair consisting of the smaller integer and the remainder of the
division. This step is repeated until the remainder is 0. The greatest common
divisor is the last non-zero remainder.
Essentially the same algorithm works for two polynomials a(x) and b(x), say
with integer (or real) coefficients, where the size of a polynomial is defined to
be its degree. In which sense are integer numbers and polynomials similar? At
which level of abstraction can they be seen as instantiations of the same abstract
concept? As we will see in Chapter 5, the answer is that they are both so-called
Euclidean domains, which is a special type of a so-called integral domain, which in
turn is a special case of a ring.
Chapter 2
Mathematical Reasoning,
Proofs, and a First Approach
to Logic
1 The term “theorem” is usually used for an important result, whereas a lemma is an interme-
diate, often technical result, possibly used in several subsequent proofs. A corollary is a simple
consequence (e.g. a special case) of a theorem or lemma.
7
2.1. Mathematical Statements 8
• 71 is a prime number.
• If p is a prime number, then 2p − 1 is also a prime number.
• Every natural number is the sum of at most four square numbers. (Exam-
ple: 22 = 42 + 22 + 12 + 12 and 74 = 62 + 52 + 32 + 22 .)
• Every even natural number greater than 2 can be expressed as the sum of
two primes.3 For example, 108 = 37 + 71 and 162 = 73 + 89.
• Any n lines ℓ1 , . . . , ℓn in the plane, no two of which are parallel, intersect
in one point (see Example 2.4).
• For the chess game there exists a winning strategy for the player making
the first move (playing “white”).
The first statement is easily shown to be true. The second statement is false,
and this can be proved by giving a counter-example: 11 is prime but 211 − 1 =
2047 = 23 ·89 is not prime.4 The third statement is true but by no means obvious
(and requires a sophisticated proof). The fourth statement is not known to be
true (or false). The fifth statement is false. The sixth statement is not known to
be true (or false).
Example 2.1. Consider the following statement which sounds like a statement
of interest in Computer Science: “There is no algorithm for factoring any n-
bit integer in n3 steps”. This is not a precise mathematical statement because
its truth (namely the complexity of the best algorithm) generally depends on
the particular computational model one is considering. A goal of Theoretical
Computer Science (TCS) is therefore to define precise models of computation
and the complexity of algorithms, allowing to make such claims precise.
If one makes a statement, say S, for example in the context of these lecture
notes, there can be two different meanings. The first meaning is that by stating
it one claims that S is true, and the second meaning is simply to discuss the
statement itself (for example as an assumption), independently of whether it is
true or not. We should try to distinguish clearly between these two meanings.
• Negation: S is false.
• And: S and T are (both) true.
• Or: At least one of S and T is true.
• Implication: If S is true, then T is true.
• “4 is even” is false.
• 4 is an even number and 71 is a prime number.
• 5 is an even number and 71 is a prime number.
• 5 is an even number or 71 is a prime number.
The first statement is false because “4 is even” is true. The second statement is
true because both statements “4 is an even number” and “71 is a prime number”
are true. In contrast, the third statement is false because the statement “5 is an
even number” is false. However, the fourth statement is again true because
“71 is a prime number” is true and hence it is irrelevant whether “5 is an even
number” is true or false.
For the first three types of statements, there is no particular notation used
in mathematics.5 However, interestingly, for the fourth type (implication) there
exists a notation that is often used, namely
S =⇒ T.
We point out that S =⇒ T does not express any kind of causality like “because S
is true, T is also true” (but see the discussion in Section 2.2.3).
Similarly, S ⇐⇒ T means that S is true if and only if T is true. This can
equivalently be stated as “S implies T and T implies S.”
5 Note that, when introducing logic and its symbols, we will for example use the symbol ∧ for
the logical “and” of two formulas, but we avoid using the symbols of logic outside of logic. Thus,
in order to avoid confusion, we avoid writing something like S ∧ T for “S and T .”
2.2. The Concept of a Proof 10
• Program P terminates (i.e., does not enter an infinite loop) for all inputs.
• Program P terminates within k computation steps for all inputs.
• Program P computes f (x) for every input x, where f is a function of in-
terest.
• Algorithm A solves problem S within accuracy ǫ.
• The error probability of file transmission system F in a file transmission is
at most p (where p can be a function of the file length).
• The computer network C has the property that if any t links are deleted,
every node is still connected with every other node.
• Encryption scheme E is secure (for a suitable definition of security).
• Cryptocurrency system C operates correctly as long as a majority of the
involved nodes behave honestly, even if all the other nodes behave arbi-
trarily maliciously.
• Database system D provides data privacy (for a suitable definition of pri-
vacy).
That this is true can even be easily seen without doing a calculation, by prov-
ing a more general claim of which the above one is a special case:
Claim: n is not prime =⇒ 2n − 1 is not prime.6
Proof: If n is not a prime, then (by definition of prime numbers) n = ab with
a > 1 and a < n. Now we observe that 2a − 1 divides 2ab − 1:
b−1
X
2ab − 1 = (2a − 1) 2ia = (2a − 1) 2(b−1)a + 2(b−2)a + · · · + 2a + 1
i=0
n is prime =⇒ 2n − 1 is prime
is a false statement, even though it may appear at first sight to follow from the
above claim. However, we observe that if S =⇒ T is true, then generally it does
not follow that if S is false, then T is false.
Example 2.3. An integer n is called a square if n = m · m for some integer m.
Prove that if a and b are squares, then so is a · b.
Example 2.4. Claim: Any n lines ℓ1 , . . . , ℓn in the plane, no two of which are
parallel, intersect in one point (i.e., have one point in common).
Proof: The proof proceeds by induction.8 The induction basis is the case n = 2:
Any two non-parallel lines intersect in one point. The induction hypothesis is
that any n lines intersect in one point. The induction step states that then this
must be true for any n+1 lines. The proof goes as follows. By the hypothesis, the
n lines ℓ1 , . . . , ℓn intersect in a point P . Similarly, the n lines ℓ1 , . . . , ℓn−1 , ℓn+1
intersect in a point Q. The line ℓ1 lies in both groups, so it contains both P and
Q. The same is true for line ℓn−1 . But ℓ1 and ℓn−1 intersect at a single point,
hence P = Q. This is the common point of all lines ℓ1 , . . . , ℓn+1 .
in depth.
.
9 This notation is not standard and only used in these lecture notes. The symbol =⇒ is intention-
ally chosen very close to the symbol =⇒ to allow someone not used to this to easily overlook the
difference.
13 Chapter 2. Math. Reasoning, Proofs, and a First Approach to Logic
A proof based on several implications often has a more general form: The
implications do not form a linear sequence but a more general configuration,
where each implication can assume several of the already proved statements.
For example, one can imagine that in order to prove a given statement T , one
starts with two (known to be) true statements S1 and S2 and then, for some
statements S3 , . . . , S7 , proves the following six implications:
.
• S1 =⇒ S3 ,
.
• S1 =⇒ S4 ,
.
• S2 =⇒ S5 ,
.
• S3 and S5 =⇒ S6 ,
.
• S1 and S4 =⇒ S7 , as well as
.
• S6 and S7 =⇒ T .
Example 2.6. In the lecture we demonstrate the proof of Example 2.2 in the
above format, making every intermediate statement explicit.
if the reasoning is clear. An informal proof is often easier to read than a pedantic
formal proof.
However, a proof, like every mathematical object, can be made rigorous and
formally precise. This is a major goal of logic (see Section 2.2.7 and Chapter 6).
There are at least three (related) reasons for using a more rigorous and formal
type of proof.
• Prevention of errors. Errors are quite frequently found in the scientific lit-
erature. Most errors can be fixed, but some can not. In contrast, a com-
pletely formal proof leaves no room for interpretation and hence allows to
exclude errors.
• Precision and deeper understanding. Informal proofs often hide subtle steps.
A formal proof requires the formalization of the arguments and can lead
to a deeper understanding (also for the author of the proof).
Logic (see Chapter 6) defines the syntax of a language for expressing statements
and the semantics of such a language, defining which statements are true and
which are false. A logical calculus allows to express and verify proofs in a purely
syntactic fashion, for example by a computer.
• Proof sketch or proof idea: The non-obvious ideas used in the proof are
described, but the proof is not spelled out in detail with explicit reference
to all definitions that are used.
• Complete proof: The use of every definition is made explicit. Every proof
step is justified by stating the rule or the definition that is applied.
• Formal proof: The proof is entirely phrased in a given proof calculus.
Proof sketches are often used when the proof requires some clever ideas and
the main point of a task or example is to describe these ideas and how they fit
together. Complete proofs are usually used when one systematically applies the
definitions and certain logical proof patterns, for example in our treatments of
relations and of algebra. Proofs in the resolution calculus in Chapter 6 can be
considered to be formal proofs.
2.3. A First Introduction to Propositional Logic 16
Definition 2.4.
(i) The negation (logical NOT) of a propositional symbol A, denoted as ¬A, is
true if and only if A is false.
(ii) The conjunction (logical AND) of two propositional symbol A and B, de-
noted A ∧ B, is true if and only if both A and B are true.
(iii) The disjunction (logical OR) of two propositional symbols A and B, de-
noted A ∨ B, is true if and only if A or B (or both) are true.12
The logical operators are functions, where ¬ is a function {0, 1} → {0, 1} and
∧ and ∨ are functions {0, 1} × {0, 1} → {0, 1}. These functions can be described
by function tables, as follows:
A B A∧B A B A∨B
A ¬A 0 0 0 0 0 0
0 1 0 1 0 0 1 1
1 0 1 0 0 1 0 1
1 1 1 1 1 1
Logical operators can also be combined, in the usual way of combining func-
tions. For example, the formula
A ∨ (B ∧ C)
11 These values 1 and 0 are not meant to be the corresponding numbers, even though the same
A B A→B
0 0 1
0 1 1
1 0 0
1 1 1
Note that A → B is true if and only if A implies B. This means that when A
is true, then also B is true. Note that A → B is false if and only if A is true and
B is false, or, stated differently, if B is false despite that A is true. A → B can be
understood as an alternative notation for ¬A ∨ B, which has the same function
table.
Example 2.7. Consider the following sentence: If student X reads the lecture
notes every week and solves the exercises (A), then student X will get a good
grade in the exam (B). This is an example of an implication A → B. Saying that
A → B is true does not mean that A is true and it is not excluded that B is true
2.3. A First Introduction to Propositional Logic 18
even if A is false, but it is excluded that B is false when A is true. Let’s hope the
statement A → B is true for you : -) .
A B A↔B
0 0 1
0 1 0
1 0 0
1 1 1
Definition 2.6. Two formulas F and G (in propositional logic) are called equiva-
lent, denoted as F ≡ G, if they correspond to the same function, i.e., if the truth
values are equal for all truth assignments to the propositional symbols appear-
ing in F or G.
For example, it is easy to see that ∧ and ∨ are commutative and associative,
i.e.,
A∧B ≡ B∧A and A∨B ≡ B∨A
as well as
A ∧ (B ∧ C) ≡ (A ∧ B) ∧ C.
Because of this equivalence, we introduce the notational convention that such
unnecessary parentheses can be dropped:.
A ∧ B ∧ C ≡ A ∧ (B ∧ C).
Similarly we have
A ∨ (B ∨ C) ≡ (A ∨ B) ∨ C
and can write A ∨ B ∨ C instead, and we also have
¬(¬A) ≡ A.
Let us look at some equivalences involving more than one operation, which
are easy to check. The operator ∨ can be expressed in terms of ¬ and ∧, as
follows:
¬(A ∨ B) ≡ ¬A ∧ ¬B,
which also means that A ∨ B ≡ ¬(¬A ∧ ¬B). In fact, ¬ and ∧ are sufficient to
express every logical function (of propositional logic). Similarly we have
¬(A ∧ B) ≡ ¬A ∨ ¬B.
The following example shows a distributive law for ∧ and ∨. Such laws will
be discussed more systematically in Chapter 6.
2.3. A First Introduction to Propositional Logic 20
Lemma 2.1.
1) A ∧ A ≡ A and A ∨ A ≡ A (idempotence);
2) A ∧ B ≡ B ∧ A and A ∨ B ≡ B ∨ A (commutativity of ∧ and ∨);
3) (A ∧ B) ∧ C ≡ A ∧ (B ∧ C) and (A ∨ B) ∨ C ≡ A ∨ (B ∨ C) (associativity);
4) A ∧ (A ∨ B) ≡ A and A ∨ (A ∧ B) ≡ A (absorption);
5) A ∧ (B ∨ C) ≡ (A ∧ B) ∨ (A ∧ C) (first distributive law);
6) A ∨ (B ∧ C) ≡ (A ∨ B) ∧ (A ∨ C) (second distributive law);
7) ¬¬A ≡ A (double negation);
8) ¬(A ∧ B) ≡ ¬A ∨ ¬B and ¬(A ∨ B) ≡ ¬A ∧ ¬B (de Morgan’s rules).
F |= G,
if for all truth assignments to the propositional symbols appearing in F or G,
the truth value of G is 1 if the truth value of F is 1.
Intuitively, if we would interpret the truth values 0 and 1 as the numbers 0
and 1 (which we don’t!), then F |= G would mean F ≤ G (as functions).
Example 2.11. A ∧ B |= A ∨ B.
Example 2.12. Comparing the truth tables of the two formulas (A ∧ B) ∨ (A ∧ C)
and ¬B → (A ∨ C) one can verify that
(A ∧ B) ∨ (A ∧ C) |= ¬B → (A ∨ C).
14 German: (logische) Folgerung, logische Konsequenz
21 Chapter 2. Math. Reasoning, Proofs, and a First Approach to Logic
Example 2.13. The following logical consequence, which the reader can prove
as an exercise, captures a fact intuitively known to us, namely that implication
is transitive:15
(A → B) ∧ (B → C) |= A → C.
We point out (see also Chapter 6) that two formulas F and G are equivalent
if and only if each one is a logical consequence of the other, i.e.,16
F ≡G ⇐⇒ F |= G and G |= F.
as well as
F ∧ (G ∧ H) ≡ (F ∧ G) ∧ H
for any real numbers a, b, and c. Therefore, for any arithmetic expressions f , g,
and h, we have
(f + g) · h = (f · h) + (g · h).
(F → G) ∧ (G → H) |= F → H
Example 2.15. The formulas A∨(¬A) and (A∧(A → B)) → B are tautologies.
One often wants to make statements of the form that some formula F is a
tautology. As stated in Definition 2.8, one also says “F is valid” instead of “F is
a tautology”.
F ∨ ¬F ≡ ⊤ and F ∧ ¬F ≡ ⊥.
The following lemmas state two simple facts that follow immediately from
the definitions. We only prove the second one.
Proof. The lemma has two directions which we need to prove. To prove the
first direction (=⇒), assume that F → G is a tautology. Then, for any truth
assignment to the propositional symbols, the truth values of F and G are either
both 0, or 0 and 1, or both 1 (but not 1 and 0). In each of the three cases it
holds that G is true if F is true, i.e., F |= G. To prove the other direction (⇐=),
assume F |= G. This means that for any truth assignment to the propositional
symbols, the truth values of G is 1 if it is 1 for F . In other words, there is no
17 German: Tautologie
18 German: allgemeingültig
19 German: erfüllbar
23 Chapter 2. Math. Reasoning, Proofs, and a First Approach to Logic
truth assignment such that the truth value of F is 1 and that of G is 0. This
means that the truth value of F → G is always 1, which means that F → G is a
tautology.
2.4.1 Predicates
Let us consider a non-empty set U as the universe in which we want to reason.
For example, U could be the set N of natural numbers, the set R of real numbers,
the set {0, 1}∗ of finite-length bit-strings, or a finite set like {0, 1, 2, 3, 4, 5, 6}.
Definition 2.10. A k-ary predicate24 P on U is a function U k → {0, 1}.
Similarly, one can naturally define the unary predicates even(x) and odd(x).
For any universe U with an order relation ≤ (e.g. U = N or U = R), the
binary (i.e., k = 2) predicate less(x, y) can be defined as
1 if x < y
less(x, y) =
0 else.
x + 3 < x + 5.
This is a true statement for every value x in U . In the next section we see how
we can express this as a formula.
Definition 2.11. For a universe U and predicate P (x) we define the following
logical statements:25
∀x P (x) stands for: P (x) is true for all x in U .
∃x P (x) stands for: P (x) is true for some x in U , i.e.,
there exists an x ∈ U for which P (x) is true.
More generally, for a formula F with a variable x, which for each value x ∈ U is
either true or false, the formula ∀x F is true if and only if F is true for all x in
U , and the formula ∃x F is true if and only if F is true for some x in U .
25 Inthe literature one also finds the notations ∀x: P (x) and ∀x. P (x) instead of ∀x P (x), and
similarly for ∃.
25 Chapter 2. Math. Reasoning, Proofs, and a First Approach to Logic
The name of the variable x is irrelevant. For example, the formula ∃x (x+5 =
3) is equivalent to the formula ∃y (y + 5 = 3). The formula could be stated in
words as: “There exists a natural number (let us call it y) which, if 5 is added
to it, the result is 3.” How the number is called, x or y or z, is irrelevant for the
truth or falsity of the statement. (Of course the statement is false; it would be
true if the universe were the integers Z.)
Sometimes one wants to state only that a certain formula containing x is
true for all x that satisfy a certain condition. For example, to state that x2 ≥ 25
whenever x ≥ 5, one can write
∀x (x ≥ 5) → (x2 ≥ 25) .
∀x ≥ 5 : (x2 ≥ 25).
Example 2.19. For the universe of the natural numbers, U = N, the predicate
prime(x) can be defined as follows:29
def
prime(x) ⇐⇒ x > 1 ∧ ∀y ∀z (yz = x) → ((y = 1) ∨ (z = 1)) .
26 But note that ∀x (x ≥ 0) is false for the universe U = R.
27 We don’t do this.
28 German: verschachtelt
def
29 We use the symbol “⇐⇒” if the object on the left side is defined as being equivalent to the object
on the right side.
2.4. A First Introduction to Predicate Logic 26
Example 2.20. Fermat’s last theorem can be stated as follows: For universe
N \ {0},30
¬ ∃ x ∃y ∃z ∃n (n ≥ 3 ∧ xn +y n = z n ) .
Example 2.21. The statement “for every natural number there is a larger prime”
can be phrased as
∀x ∃y y > x ∧ prime(y)
and means that there is no largest prime and hence that there are infinitely many
primes.
If the universe is N, then one sometimes uses m, n, or k instead of x and y.
The above formula could hence equivalently be written as
∀m ∃n n > m ∧ prime(n) .
Example 2.22. Let U = R. What is the meaning of the following formula, and
does it correspond to a true statement?
∀x x = 0 ∨ ∃y (xy = 1)
Example 2.23. What is the meaning of the following formula, and for which
universes is it true (or false)?
∀x ∀y (x < y) → ∃z((x < z) ∧ (z < y))
even multiple copies of the quantifier. For example one writes ∃xyz instead of ∃x ∃y ∃z. We will
not use such a convention in this course.
27 Chapter 2. Math. Reasoning, Proofs, and a First Approach to Logic
is a tautology, or valid.
Example 2.24. Recall Example 2.22. The formula can be written in an equivalent
form, as:
∀x x = 0 ∨ ∃y (xy = 1) ≡ ∀x ¬(x = 0) → ∃y (xy = 1) .
The order of identical quantifiers does not matter, i.e., we have for example:
∃x∃y P (x, y) ≡ ∃y∃x P (x, y) and ∀x∀y P (x, y) ≡ ∀y∀x P (x, y).
∀x P (x) |= ∃x P (x).
It holds because if P (x) is true for all x in the universe, then it is also true for
some (actually an arbitrary) x. (Recall that the universe is non-empty.)
Some more involved examples of equivalences and logical consequences are
stated in the next section.
31 We will see in Chapter 6 that predicate logic also involves function symbols, and an interpreta-
tion also instantiates the function symbols by concrete functions.
2.5. Logical Formulas vs. Mathematical Statements 28
since if P (x) is true for all x and also Q(x) is true for all x, then P (x) ∧ Q(x) is
true for all x, and vice versa. Also,32
∃x P (x) ∧ Q(x) |= ∃x P (x) ∧ ∃x Q(x)
since, no matter what P and Q actually mean, any x that makes P (x)∧Q(x) true
(according to the left side) also makes P (x) and Q(x) individually true. But, in
contrast, ∃x (P (x) ∧ Q(x)) is not a logical consequence of ∃x P (x) ∧ ∃x Q(x), as
the reader can verify. We can write
We also have:
¬∀x P (x) ≡ ∃x ¬P (x)
and
¬∃x P (x) ≡ ∀x ¬P (x).
The reader can prove as an exercise that
∃y ∀x P (x, y) |= ∀x ∃y P (x, y)
but that
∀x ∃y P (x, y) 6|= ∃y ∀x P (x, y).
Proof. F |= G states that for every interpretation, if F is true (for that interpre-
tation), then also G is true (for that interpretation). Therefore, if F is true for
every interpretation, then also G is true for every interpretation, which is state-
ment (2.1).
Lemma 2.5. (A → B) ∧ (B → C) |= A → C.
Lemma 2.6. ¬B → ¬A |= A → B.
Proof. One can actually prove the stronger statement, namely that ¬B → ¬A ≡
A → B, simply by examination of the truth table which is identical for both
formulas ¬B → ¬A and A → B.
√
Example 2.26. Prove the following claim: If x > 0 is irrational,
√ then also x is
irrational. The indirect proof proceeds by assuming that x is not irrational and
33 Recall Section 2.1.2.
31 Chapter 2. Math. Reasoning, Proofs, and a First Approach to Logic
showing that then x is also not irrational. Here “not irrational” means rational,
i.e., we prove √
x is rational =⇒ x is rational
√ √
Assume hence that x is rational, i.e., that x = m/n for m, n ∈ Z. This means
that x = m2 /n2 , i.e., x is the quotient of two natural numbers (namely m2 and
n2 ) and thus is rational. This completes the proof of the claim.
More informally, one proves for a complete list of cases that the statement S
holds in all the cases.
The soundness of this principle is explained by the following lemma of
propositional logic.
Lemma 2.8. For every k we have
(A1 ∨ · · · ∨ Ak ) ∧ (A1 → B) ∧ · · · ∧ (Ak → B) |= B.
Proof. For a fixed k (say k = 2) one can verify the statement by examination
of the truth table. The statement for general k can be proved by induction (see
Section 2.6.10).
2.6. Some Proof Patterns 32
Note that for k = 1 (i.e., there is only one case), case distinction corresponds
to the modus ponens discussed above.
Example 2.27. Prove the following statement S: The 4th power of every natural
number n, which is not divisible by 5, is one more than a multiple of 5.
To prove the statement, let n = 5k + c, where 1 ≤ c ≤ 4. Using the usual
binomial formula (a + b)4 = a4 + 4a3 b + 6a2 b2 + 4ab3 + b4 we obtain:
n4 = (5k + c)4 = 54 k 4 + 4 · 53 k 3 c + 6 · 52 k 2 c2 + 4 · 5kc3 + c4 .
Each summand is divisible by 5, except for the last term c4 . The statement S is
hence equivalent to the statement that c4 is one more than a multiple of 5, for
1 ≤ c ≤ 4.
This statement S can be proved by case distinction, i.e., by considering all
four choices for c. For c = 1 we have c4 = 1, which is trivially one more than a
multiple of 5. For c = 2 we have c4 = 16, which is also one more than a multiple
of 5. The same is true for c = 3 where c4 = 81 and for c = 4 where c4 = 256.
This concludes the proof.
With a few insights from number theory and algebra we will see later that
the above statement holds when 5 is replaced by any odd prime number.
In many cases, the proof steps appear in a different order: One starts from
assuming that S is false, derives statements from it until one observes that one
of these statements is false (i.e., is the statement T in the above description). In
this case, the fact that T is false (step 2) is obvious and requires no proof.
The soundness of this principle is explained by the following lemma of
propositional logic which can again be proved by comparing the truth tables
of the involved formulas.
Lemma 2.9. (¬A → B) ∧ ¬B |= A.
Since ¬A → B is equivalent to A ∨ B, the principle of a proof by contradic-
tion can alternatively be described as follows: To prove S, one proves for some
statement T that either S or T is true (or both) and that T is false. This is justified
because we have
(A ∨ B) ∧ ¬B |= A.
33 Chapter 2. Math. Reasoning, Proofs, and a First Approach to Logic
√
Example 2.28. We discuss the classical proof of three statement that 2 is irra-
tional. (This is the statement S to be proved.) Recall (from basic number theory)
that a number a is rational if and only if a = m/n (i.e., m = an) for two relatively
prime34 integers m and n (i.e., with gcd(m, n) = 1).35
The proof by contradiction starts by assuming that S is false and deriving,
from this assumption, a false statement T . In the following derivation we may
use formulas as a compact way of writing statements, but the derivation itself
is “normal” mathematical reasoning and is not to be understood as a formula-
based logical reasoning.36
. √
S is false ⇐⇒ 2 is rational
.
⇐⇒ ∃m ∃n m2 = 2n2 ∧ gcd(m, n) = 1
.
m2 = 2n2 =⇒ m2 is even
.
=⇒ m is even
.
=⇒ 4 divides m2
.
=⇒ 4 divides 2n2 (also using m2 = 2n2 )
.
=⇒ 2 divides n2
.
=⇒ n is even
.
=⇒ gcd(m, n) ≥ 2 (also using that m is even)
Hence we have
∃m ∃n m2 = 2n2 ∧ gcd(m, n) = 1
.
=⇒ ∃m ∃n m2 = 2n2 ∧ gcd(m, n) ≥ 2 ∧ gcd(m, n) = 1 .
| {z }
false for arbitrary m and n
| {z }
statement T , which is false
34 German: teilerfremd
35 gcd(m, n) denotes the greatest common divisor of m and n (see Section 4.2.3).
36 We can write ⇐⇒.
if the implication holds in both directions, but it would be sufficient to always
. .
replace ⇐⇒ by =⇒.
2.6. Some Proof Patterns 34
Example 2.29. Prove that there exists a prime37 number n such that n − 10 and
n + 10 are also primes, i.e., prove
∃n prime(n) ∧ prime(n − 10) ∧ prime(n + 10) .
| {z }
Sn
To prove this, consider an arbitrary but fixed number m and consider the state-
ments Sp parameterized by p: There exists a prime p greater than m, i.e., such
that prime(p) ∧ p > m is true.
To prove this, we use the known fact (which has been proved) that every
natural number n ≥ 2 has at least one prime divisor. We consider the specific
number m! + 1 (where m! = 2 · 3 · · · (m − 1) · m). We observe that for all k in
the range 2 ≤ k ≤ m, k does not divide m! + 1. In particular, no prime smaller
than m divides m! + 1. Because m! + 1 has at least one prime divisor, there exists
a prime p greater than m which divides m! + 1. Hence there exists a prime p
greater than m.39
equal to m! + 1.
40 German: Schubfachprinzip
41 This principle is often described as follows: If there are more pigeons than pigeon holes, then
there must be at least one pigeon hole with more than one pigeon in it. Hence the name of the
principle.
35 Chapter 2. Math. Reasoning, Proofs, and a First Approach to Logic
Theorem 2.10. If a set of n objects is partitioned into k < n sets, then at least one of
these sets contains at least ⌈ nk ⌉ objects.42
Proof. The proof is by contradiction. Suppose that all sets in the partition have
at most ⌈ nk ⌉ − 1 objects. Then the total number of objects is at most k ⌈ nk ⌉ − 1 ,
which is smaller than n because
l n m n n
k −1 < k +1 −1 = k = n.
k k k
Example 2.31. Claim: Among 100 people, there are at least nine who were born
in the same month. The claim can be equivalently stated as an existence claim:
Considering any 100 people, there exists a month in which at least nine of them
have their birthday.
Proof. Set n = 100 and k = 12, and observe that ⌈100/12⌉ = 9.
Example 2.32. Claim: In any subset A of {1, 2, . . . , 2n} of size |A| = n + 1, there
exist distinct a, b ∈ A such that a | b (a divides b).43
For example, in the set {2, 3, 5, 7, 9, 10} we see that 3 | 9.
Proof. We write every ai ∈ A as 2ei ui with ui odd. There are only n possible
values {1, 3, 5, . . . , 2n − 1} for ui . Thus there must exist two numbers ai and aj
with the same odd part (ui = uj ). Therefore one of them has fewer factors 2
than the other and must hence divide it.
(iℓ , dℓ ) that can occur. Thus the pigeonhole principle guarantees that there must
be two indices s < t with (is , ds ) = (it , dt ). But this leads to a contradiction.
Because the numbers are distinct, either as < at or as > at . If as < at , then,
since is = it , an increasing subsequence of length it + 1 can be built starting
at position s, taking as followed by the increasing subsequence beginning at at .
This is a contradiction. A similar contradiction is obtained if as > at .
Proof by induction:
1. Basis step.44 Prove P (0).
2. Induction step. Prove that for any arbitrary n we have P (n) =⇒ P (n+1).
Theorem 2.11. For the universe N and an arbitrary unary predicate P we have
3.1 Introduction
There seems to be no simpler mathematical concept than a set1 , a collection of
objects. Although intuitively used for a long time,2 the formulation of a set as a
mathematical concept happened as late as the end of the 19th century. For exam-
ple, in 1895 Cantor proposed the following wording: “Unter einer ‘Menge’ ver-
stehen wir jede Zusammenfassung M von bestimmten wohlunterschiedenen
Objekten unserer Anschauung oder unseres Denkens (welche die ‘Elemente’
von M genannt werden) zu einem Ganzen”.
39
3.1. Introduction 40
This calls for a precise mathematical treatment with clear definitions, lemmas,
and proofs. The need for such a precise treatment also becomes obvious when
considering Russell’s paradox discussed below.
ematician, but also politically active as a pacifist. Because of his protests against World War I he
was dismissed from his position at Trinity College in Cambridge and imprisoned for 6 months. In
1961, at the age of 89, he was arrested again for his protests against nuclear armament. In 1950 he
received the Nobel Prize for literature.
41 Chapter 3. Sets, Relations, and Functions
The problem with Cantor’s intuitive set theory is that, because it was not
clearly axiomatized, it makes the following apparently innocent (yet false) as-
sumption. Whenever one specifies a precise condition (i.e., a logical predicate
P ), allowing to distinguish between objects that satisfy the predicate and ob-
jects that don’t, then {x | P (x)}, the set of objects satisfying the predicate is
well-defined. Russell proposed the set
R = {A | A ∈
/ A}
of sets that are not elements of themselves. Note that there seems to be nothing
wrong with a set being an element of itself. For example, the set of sets contain-
ing at least 10 elements seems to be an element of itself, as it contains more than
10 elements. Similarly, the set of sets containing at most 10 elements is not an
element of itself.
Either R ∈ R or R ∈ / R. If R ∈ R, then by the definition of R, this implies
R∈ / R, a contradiction. Thus the only alternative is R ∈ / R. But again, by the
definition of R, this implies R ∈ R, again a contradiction. In other words, R ∈ R
if and only if R ∈ / R, a paradox that requires an explanation.
The problem, subsequently addressed by Zermelo’s axiomatization, is the
following: While for any set B and predicate P , {x ∈ B | P (x)} is actually a
well-defined set, {x | P (x)} is not. We must have a set to begin with before being
able to create new sets by selecting the elements satisfying a certain condition. In
other words, the universe U of objects one has in mind when writing {x | P (x)}
is not itself a set.4
and develops a theory (set theory) based on these axioms. There are indeed
several different (but related) axiom systems for set theory, and it is beyond the
scope of this course to discuss set theory in a formal sense.5 However, we will
informally introduce some of these properties/axioms in order to arrive at a
sufficiently precise treatment of sets.
When writing formulas, it will often be convenient to not only use the usual
logical variable symbols x, y, etc., but to use in the same formula symbols like A,
B, etc. This is convenient because it makes the formulas look closer to how set
theory is usually informally discussed. However, whether we use the symbol x
or A for a set is not mathematically relevant.
def
Definition 3.2. A = B ⇐⇒ ∀x (x ∈ A ↔ x ∈ B).
We postulate7 that if a is a set, then the set containing exactly (and only) a
exists, and is usually denoted as {a}. Similarly, for any finite list of sets, say a, b,
and c, the set containing exactly these elements exists and is usually denoted as
{a, b, c}.
Since a set is specified by its elements, we can conclude that if two sets, each
containing a single element, are equal, then the elements are equal. This can be
stated as a lemma (in set theory), and it actually requires a proof.
descriptions, including {1, 2, 3}, {3, 1, 2}, {1, 1 + 1, 1 + 1 + 1}, etc. All these descriptions refer to
the same set.
7 In axiomatic set theory this is guaranteed by appropriate axioms.
43 Chapter 3. Sets, Relations, and Functions
element, namely a, that is contained in the first set, but not in the second. Thus
we have proved that a 6= b =⇒ {a} = 6 {b}. According to Definition 2.14, this
proves {a} = {b} =⇒ a = b.
Note that, in contrast, {a, b} = {c, d} neither implies that a = c nor that b = d.
In a set, say {a, b}, there is no order of the elements, i.e.,
def
(a, b) = (c, d) ⇐⇒ a = c ∧ b = d.
Example 3.1. This example shows that one can model ordered pairs by using
only (unordered) sets?8 This means that the sets corresponding to two ordered
pairs must be equal if and only if the ordered pairs are equal. A first approach is
def
to define (a, b) = {a, {b}}. However, this definition of an ordered pair fails be-
cause one could not distinguish whether the set {{b}, {c}} denotes the ordered
pair ({b}, c) or the ordered pair ({c}, b). The reader can verify as an exercise that
the following definition is correct:
def
(a, b) = {{a}, {a, b}}.
3.2.3 Subsets
The following lemma states an alternative way for capturing the equality of
sets, via the subset relation. In fact, this is often the best way to prove that two
sets are equal.
Proof. The proof first makes use (twice) of Definition 3.3, then uses the fact from
predicate logic that ∀F ∧ ∀G ≡ ∀(F ∧ G), then uses the fact from propositional
8 We
briefly address this question, although we will not make use of this later and will continue
to think about ordered pairs and lists in a conventional sense and with conventional notation.
3.2. Sets and Operations on Sets 44
logic that (C → D)∧(D → C) ≡ C ↔ D,9 and then makes use of Definitions 3.2.
For any sets A and B we have the following equivalences of statements about A
and B:
.
(A ⊆ B) ∧ (B ⊆ A) ⇐⇒ ∀x (x ∈ A → x ∈ B) ∧ ∀x (x ∈ B → x ∈ A)
.
⇐⇒ ∀x (x ∈ A → x ∈ B) ∧ (x ∈ B → x ∈ A)
.
⇐⇒ ∀x (x ∈ A ↔ x ∈ B)
.
⇐⇒ A = B
The next lemma states that the subset relation is transitive (a term discussed
later). The proof is left as an exercise.
A ⊆ B ∧ B ⊆ C =⇒ A ⊆ C.
The above definition can be extended from two to several sets, i.e., to a set
(or collection) of sets. Let A be a non-empty set of sets, with finite or infinite
cardinality. The only restriction on A is that its elements must be sets. Then we
define the union of all sets in A as the set of all x that are an element of at least
one of the sets in A:
[ def
A = {x| x ∈ A for some A ∈ A}.
Similarly, we define the intersection of all sets in A as the set of all x that are an
element of every set in A:
\ def
A = {x| x ∈ A for all A ∈ A}.
9 Here we use C and D rather than A and B to avoid confusion because A and B are used here
to denotes sets.
45 Chapter 3. Sets, Relations, and Functions
Typically, the sets (elements) in a set A of sets are indexed by some index
set I: A = {Ai | i ∈ I}. In this
T case, one S
also writes {Ai }i∈I , and for the intersec-
tion and union one writes i∈I Ai and i∈I Ai , respectively.
Definition 3.5. The difference of sets B and A, denoted B\A is the set of elements
of B without those that are elements of A:
def
B \ A = {x ∈ B| x ∈
/ A}.
Theorem 3.4. For any sets A, B, and C, the following laws hold:
Idempotence: A ∩ A = A;
A ∪ A = A;
Commutativity: A ∩ B = B ∩ A;
A ∪ B = B ∪ A;
Associativity: A ∩ (B ∩ C) = (A ∩ B) ∩ C;
A ∪ (B ∪ C) = (A ∪ B) ∪ C;
Absorption: A ∩ (A ∪ B) = A;
A ∪ (A ∩ B) = A;
Distributivity: A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C);
A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C);
Consistency: A ⊆ B ⇐⇒ A ∩ B = A ⇐⇒ A ∪ B = B.
Proof. The proof is straight-forward and exploits the related laws for logical op-
erations. For example, the two associative laws are implied by the associativity
of the logical AND and OR, respectively. The proof is left as an exercise.
Lemma 3.5. There is only one empty set (which is often denoted as ∅ or {}).10
Proof. Let ∅ and ∅′ both be arbitrary empty sets. Since both are empty, every
element that is in ∅ (namely none) is also in ∅′ , and vice versa. This means
according to Definition 3.2 that ∅ = ∅′ , which means that there is only one
empty set.
Proof. The proof is by contradiction: Assume that there is a set A for which
∅ 6⊆ A. This means that there exists an x for which x ∈ ∅ but x ∈ / A. But such
an x cannot exist because ∅ contains no element, which is a contradiction.
The above is a valid proof. Just to illustrate (as an example) that the same proof
could be made more formal and more precise we can write the proof as follows,
making use of logical transformation rules for formulas with quantifiers. Let A
be an arbitrary (but fixed) set. The proof is by contradiction (see Definition 2.17),
where the statement S to be proved is ∅ ⊆ A and as the statement T we choose
¬∀x (x ∈/ ∅), which is false because it is the negation of the definition of ∅. The
proof that the negation of S implies T (step 3 in Definition 2.17) is as follows:
.
¬(∅ ⊆ A) ⇐⇒ ¬∀x (x ∈ ∅ → x ∈ A) (def. of ∅ ⊆ A)
.
⇐⇒ ∃x ¬(x ∈ ∅ → x ∈ A) (¬∀x F ≡ ∃x ¬F )
.
⇐⇒ ∃x ¬(¬(x ∈ ∅) ∨ x ∈ A) (def. of →)
.
⇐⇒ ∃x (x ∈ ∅ ∧ ¬(x ∈ A)) (de Morgan’s rule)
.
=⇒ ∃x (x ∈ ∅) ∧ ∃x ¬(x ∈ A) (∃x (F ∧ G) |= (∃xF ) ∧ (∃xG))
.
=⇒ ∃x (x ∈ ∅) (F ∧ G implies F )
.
⇐⇒ ¬∀x ¬(x ∈ ∅). (¬∀x F ≡ ∃x ¬F )
.
⇐⇒ ∅ is not the empty set (Definition 3.6)
∅, i.e., {∅} 6= ∅. Note that |{∅}| = 1 while |∅| = 0. One can thus define a whole
sequence of such sets:
Note that, except for the empty set, all these sets have cardinality 1.
Example 3.3. A few other sets constructed from the empty set are:
A = {∅, {∅}},
B = {{∅, {∅}}}, and
C = {∅, {∅}, {∅, {∅}}}.
Their cardinalities are |A| = 2, |B| = 1, and |C| = 3. Also, A ⊆ C and B ⊆ C.
def
s(n) = n ∪ {n}.
For example, we have 1 = s(0) and 2 = s(1). We note that |0| = 0, |1| = 1,
|2| = 2, |3| = 3, . . ., and, more generally, that |s(n)| = |n| + 1.
An operation + on these sets 0, 1, 2, 3, . . ., which corresponds to addition of
numbers, can be defined recursively as follows:
def def
m+0 = m and m+s(n) = s(m+n).
One can also define a multiplication operation and prove that these operations
satisfy the usual laws of the natural numbers (commutative, associative, and
distributive laws).
3.2. Sets and Operations on Sets 48
Definition 3.7. The power set of a set A, denoted P(A), is the set of all subsets
of A:11
def
P(A) = {S| S ⊆ A}.
For a finite set with cardinality k, the power set has cardinality 2k (hence the
name ‘power set’ and the alternative notation 2A ).
Example 3.5. P({a, b, c}) = {∅, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}} and
|P({a, b, c})| = 8.
Example 3.6. We have
P(∅) = {∅},
P({∅}) = {∅, {∅}},
P({∅, {∅}}) = {∅, {∅}, {{∅}}, {∅, {∅}}},
{1, 7, 9} ∈ P(N).
Definition 3.8. The Cartesian product A × B of two sets A and B is the set of
all ordered pairs with the first component from A and the second component
from B:
A × B = (a, b) a ∈ A ∧ b ∈ B .
For finite sets, the cardinality of the Cartesian product of some sets is the
product of their cardinalities: |A × B| = |A| · |B|.
Example 3.7. Prove or disprove the following statements:
(i) ∅ × A = ∅ .
(ii) A × B = B × A .
More generally, the Cartesian product of k sets A1 , . . . , Ak is the set of all lists
of length k (also called k-tuples) with the i-th component from Ai :
We point out that the Cartesian product is not associative, and in particular
×3i=1 Ai 6= (A1 × A2 ) × A3 .
3.3 Relations
Relations are a fundamental concept in discrete mathematics and Computer Sci-
ence. Many special types of relations (e.g., equivalence relations, order relations,
and lattices) capture concepts naturally arising in applications. Functions are
also a special type of relation.
Definition 3.9. A (binary) relation ρ from a set A to a set B (also called an (A, B)-
relation) is a subset of A × B. If A = B, then ρ is called a relation on A.
Example 3.12. The relation {(x, y)| x2 + y 2 = 1} on R is the set of points on the
unit circle, which is a subset of R × R.
Example 3.13. For any set S, the subset relation (⊆) is a relation on P(S).
Example 3.14. Two special relations from A to B are the empty relation (i.e., the
empty set ∅) and the complete relation A × B consisting of all pairs (a, b).
Definition 3.10. For any set A, the identity relation on A, denoted idA (or simply
id), is the relation idA = {(a, a)| a ∈ A}.
2
Relations on a finite set are of special interest. There are 2n different rela-
tions on a set of cardinality n. (Why?)
The relation concept can be generalized from binary to k-ary relations for
given sets A1 , . . . , Ak . A k-ary relation is a subset of A1 × · · ·× Ak . Such relations
play an important role in modeling relational databases. Here we only consider
binary relations.
Example 3.15. Let A = {a, b, c, d} and B = {q, r, s, t, u}, and consider the re-
lation ρ = {(a, r), (a, s), (a, u), (b, q), (b, s), (c, r), (c, t), (c, u), (d, s), (d, u)}. The
matrix representation is
q r s t u
a 0 1 1 0 1
b 1 0 1 0 0
Mρ =
c 0 1 0 1 1
d 0 0 1 0 1
where the rows and columns are labeled by the elements of A and B, respec-
tively.
Example 3.16. For the set A = {1, 2, 3, 4, 5}, the relations =, ≥, and ≤ correspond
to the identity matrix,13 the lower triangular matrix, and the upper triangular
matrix, respectively.
13 The identity relation (=) on any finite set corresponds to the identity matrix.
51 Chapter 3. Sets, Relations, and Functions
def
ρ◦σ = (a, c) ∃b (a, b) ∈ ρ ∧ (b, c) ∈ σ .
Proof. We use the short notation ρσ instead of ρ ◦ σ. The claim of the lemma,
ρ(σφ) = (ρσ)φ, states an equality of sets, which can be proved by proving that
each set is contained in the other (see Section 3.2.3). We prove ρ(σφ) ⊆ (ρσ)φ;
the other inclusion is proved analogously. Suppose that (a, d) ∈ ρ(σφ). We
need to prove that (a, d) ∈ (ρσ)φ. For illustrative purposes, We provide two
formulations of this proof, first as a text and then in logical formulas.
Because (a, d) ∈ ρ(σφ), there exists b such that (a, b) ∈ ρ and (b, d) ∈ σφ.
The latter implies that there exists c such that (b, c) ∈ σ and (c, d) ∈ φ. Now,
(a, b) ∈ ρ and (b, c) ∈ σ imply that (a, c) ∈ ρσ, which together with (c, d) ∈ φ
implies (a, d) ∈ (ρσ)φ.
Now comes the more formal version of the same proof, where the justifica-
tion for each step is omitted:16
.
(a, d) ∈ ρ(σφ) =⇒ ∃b (a, b) ∈ ρ ∧ (b, d) ∈ σφ
.
=⇒ ∃b (a, b) ∈ ρ ∧ ∃c (b, c) ∈ σ ∧ (c, d) ∈ φ
.
=⇒ ∃b∃c (a, b) ∈ ρ ∧ (b, c) ∈ σ ∧ (c, d) ∈ φ
.
=⇒ ∃b∃c (a, b) ∈ ρ ∧ (b, c) ∈ σ ∧ (c, d) ∈ φ
.
=⇒ ∃c∃b (a, b) ∈ ρ ∧ (b, c) ∈ σ ∧ (c, d) ∈ φ
.
=⇒ ∃c ∃b (a, b) ∈ ρ ∧ (b, c) ∈ σ ∧ (c, d) ∈ φ
.
=⇒ ∃c (a, c) ∈ ρσ ∧ (c, d) ∈ φ
.
=⇒ (a, d) ∈ (ρσ)φ.
16 The justifications should be obvious, except perhaps for the following fact from predicate logic
(explained in Chapter 6) used several times in the proof: ∃x(F ∧ G) ≡ F ∧ ∃xG if x does not appear
in F .
53 Chapter 3. Sets, Relations, and Functions
Example 3.22. Consider the ownership relation π and the parenthood relation φ
as above. Then the relation φπ from H to O can be interpreted as follows: a φπ b
if and only if person a has a child who owns object b.
Example 3.23. If φ is the parenthood relation on the set H of humans, then the
relation φ2 is the grand-parenthood relation.17
Lemma 3.8. Let ρ be a relation from A to B and let σ be a relation from B to C. Then
the inverse ρc
σ of ρσ is the relation σ
bρb.
Example 3.24. The relations ≤, ≥, and | (divides) on Z \ {0} are reflexive, but
the relations < and > are not.
17 Note that the notation φ2 is actually ambiguous; it could also denote the Cartesian product
necessarily irreflexive.
3.3. Relations 54
a ρ b ∧ b ρ c =⇒ a ρ c
Proof. The “if” part of the theorem (⇐=) follows from the definition of compo-
sition: If a ρ b and b ρ c, then a ρ2 c. Therefore also a ρ c since ρ2 ⊆ ρ.20 This
20 In set-theoretic notation: (a, c) ∈ ρ2 ∧ ρ2 ⊆ ρ =⇒ (a, c) ∈ ρ.
55 Chapter 3. Sets, Relations, and Functions
means transitivity.
Proof of the “only if” part (=⇒): Assume that ρ is transitive. To show that ρ2 ⊆ ρ,
assume that a ρ2 b for some a and b. We must prove that a ρ b. The definition
of a ρ2 b states that there exists c such that a ρ c and c ρ b. Transitivity of ρ
thus implies that a ρ b, which concludes the proof.
Example 3.30. Consider the set P of all convex polygons. We can think of them
as being given as pieces of paper. By cutting a piece into two pieces with a
straight cut one can obtain new polygons. Let be the relation defined as fol-
lows: a b if and only if with a single straight-line cut (or no cut) one can ob-
tain b from a. Moreover, consider the covering relation ⊒, where a ⊒ b if and
only if a can completely cover b (if appropriately positioned). It is easy to see
that ⊒ is reflexive, anti-symmetric, and transitive21 whereas is only reflexive
and antisymmetric. Note that ⊒ is the transitive closure of .
Definition 3.20. For an equivalence relation θ on a set A and for a ∈ A, the set
of elements of A that are equivalent to a is called the equivalence class of a and is
denoted as [a]θ :22
def
[a]θ = {b ∈ A| b θ a}.
Example 3.32. The equivalence classes of the relation ≡3 are the sets
Example 3.33. Consider the set R2 of points (x, y) in the plane, and consider the
relation ρ defined by (x, y) ρ (x′ , y ′ ) ⇐⇒ x + y = x′ + y ′ . Clearly, this relation is
reflexive, symmetric, and transitive. The equivalence classes are the set of lines
in the plane parallel to the diagonal of the second quadrant.
Lemma 3.10. The intersection of two equivalence relations (on the same set) is an
equivalence relation.
Consider any partition of a set A and define the relation ≡ such that two
elements are ≡-related if and only if they are in the same set of the partition. It
is easy to see that this relation is an equivalence relation. The following theorem
states that the converse also holds. In other words, partitions and equivalence
relations capture the same (simple) abstraction.
22 When the relation θ is understood, we can drop the subscript θ.
23 A singleton is a set with one element.
57 Chapter 3. Sets, Relations, and Functions
Proof. Since a ∈ [a] for all a ∈ A (reflexivity of θ), the union of all equivalence
classes is equal to A. It remains to prove that equivalence classes are disjoint.
This is proved by proving, for any fixed a and b, that
a θ b =⇒ [a] = [b]
and
a 6 θ b =⇒ [a] ∩ [b] = ∅.
To prove the first statement we consider an arbitrary c ∈ [a] and observe that
.
c ∈ [a] ⇐⇒ c θ a (def. of [a])
.
=⇒ c θ b (use a θ b and transitivity)
.
⇐⇒ c ∈ [b] (def. of [b].)
Note that c ∈ [a] =⇒ c ∈ [b] (for all c ∈ A) is the definition of [a] ⊆ [b]. The state-
ment [b] ⊆ [a] is proved analogously but additionally requires the application of
symmetry. (This is an exercise.) Together this implies [a] = [b].
The second statement is proved by contradiction. Suppose it is false24 , i.e.,
a 6 θ b and [a] ∩ [b] 6= ∅, i.e., there exists some c ∈ [a] ∩ [b], which means that c θ a
and c θ b. By symmetry we have a θ c and thus, by transitivity, we have a θ b,
a contradiction. (As an exercise, the reader can write this proof as a sequence of
implications.)
(c, d) ∼ (e, f ). Then ad = bc and cf = de, and thus adcf = bcde. Canceling d
(which is 6= 0) gives
acf = bce.
We have to consider the cases c 6= 0 and c = 0 separately. If c 6= 0, then c can be
canceled, giving af = be. If c = 0, then a = 0 since d 6= 0 but ad = bc. Similarly,
e = 0, and thus we also have af = be. Therefore ∼ is transitive and hence an
equivalence relation.
To every equivalence class [(a, b)] we can associate the rational number a/b
(b 6= 0). It is easy to see that all pairs (u, v) ∈ [(a, b)] correspond to the same ra-
tional number, and two distinct rational numbers correspond to distinct equiv-
alence classes. Thus25
def
Q = Z × (Z\{0}) ∼.
if and only if the ratio is the same. But actually, this is the definition of the rational numbers. If the
reader is surprised, he or she is challenged to come up with a simpler definition.
26 German: Ordnungsrelation
27 Partial orders are often denoted by ≤ or by a similar symbol like or ⊑.
59 Chapter 3. Sets, Relations, and Functions
Example 3.38. The covering relation on convex polygons (see Example 3.30) is
a partial order.
For a partial order relation we can define the relation a ≺ b similar to how
the relation < is obtained from ≤:
def
a ≺ b ⇐⇒ a b ∧ a 6= b.
Definition 3.24. For a poset (A; ), two elements a and b are called comparable28
if a b or b a; otherwise they are called incomparable.
Definition 3.25. If any two elements of a poset (A; ) are comparable, then A is
called totally ordered (or linearly ordered) by .
Example 3.39. (Z; ≤) and (Z; ≥) are totally ordered posets (or simply totally
ordered sets), and so is any subset of Z with respect to ≤ or ≥. For instance,
({2, 5, 7, 10}; ≤) is a totally ordered set.
Example 3.40. The poset (P(A); ⊆) is not totally ordered if |A| ≥ 2, nor is the
poset (N; |).
Definition 3.27. The Hasse diagram of a (finite) poset (A; ) is the directed graph
whose vertices are labeled with the elements of A and where there is an edge
from a to b if and only if b covers a.
The Hasse diagram is a graph with directed edges. It is usually drawn such
that whenever a ≺ b, then b is placed higher than a. This means that all arrows
are directed upwards and therefore can be omitted.
Example 3.42. The Hasse diagram of the poset ({2, 3, 4, 5, 6, 7, 8, 9}; |) is shown
in Figure 3.1 on the left.
28 German: vergleichbar
29 German: überdecken
3.5. Partial Order Relations 60
Example 3.43. A nicer diagram is obtained when A is the set of all divisors of
an integer n. The Hasse diagram of the poset ({1, 2, 3, 4, 6, 8, 12, 24}; |) is shown
in Figure 3.1 in the middle.
{a,b,c}
24
8 12
8 {a,c}
{a,b} {b,c}
6 9 4 6
4 {a} {b} {c}
2 3
2 3 5 7 1 {}
Figure 3.1: The Hasse diagrams of the posets ({2, 3, 4, 5, 6, 7, 8, 9}; |),
({1, 2, 3, 4, 6, 8, 12, 24}; |), and (P({a, b, c}); ⊆).
Example 3.44. The Hasse diagram of the poset (P({a, b, c}); ⊆) is shown in Fig-
ure 3.1 on the right.
Example 3.45. For the two Hasse diagrams in Figure 3.2, give a realization as
the divisibility poset of a set of integers.
Example 3.46. Consider the covering30 relation on the convex polygons dis-
cussed in Example 3.30. A polygon a is covered by a polygon b if b can be
placed on top of a such that a disappears completely. Are there sets of six poly-
gons resulting in a poset with the left (or right) Hasse diagram in Figure 3.2?
30 The term “cover” is used here in a physical sense, not in the sense of Definition 3.26.
61 Chapter 3. Sets, Relations, and Functions
The proof is left as an exercise. The reader can verify that when replacing ∧
by ∨, the resulting relation is in general not a partial order relation.
A more interesting order relation on A × B is defined in the following theo-
rem, whose proof is left as an exercise.
Theorem 3.13. For given posets (A; ) and (B; ⊑), the relation ≤lex defined on A×B
by
def
(a1 , b1 ) ≤lex (a2 , b2 ) ⇐⇒ a1 ≺ a2 ∨ (a1 = a2 ∧ b1 ⊑ b2 )
31
is a partial order relation.
The relation ≤lex is the well-known lexicographic order of pairs, usually con-
sidered when both posets are identical. The lexicographic order ≤lex is useful
because if both (A; ) and (B; ⊑) are totally ordered (e.g. the alphabetical order
of the letters), then so is the lexicographic order on A × B (prove this!).
The lexicographic order can easily be generalized to the k-tuples over some
alphabet Σ (denoted Σk ) and more generally to the set Σ∗ of finite-length strings
over Σ. The fact that a total order on the alphabet results in a total order on Σ∗
is well-known: The telephone book has a total order on all entries.
Definition 3.29. Let (A; ) be a poset, and let S ⊆ A be some subset of A. Then
1. a ∈ A is a minimal (maximal) element of A if there exists no b ∈ A with b ≺ a
(b ≻ a).32
2. a ∈ A is the least (greatest) element of A if a b (a b) for all b ∈ A.33
3. a ∈ A is a lower (upper) bound34 of S if a b (a b) for all b ∈ S.35
4. a ∈ A is the greatest lower bound (least upper bound) of S if a is the greatest
(least) element of the set of all lower (upper) bounds of S.36
31 Recall def
that for a partial order we can define the relation ≺ as a ≺ b ⇐⇒ a b ∧ a 6= b.
def
32 The relations and ≻ are defined naturally by a b ⇐⇒ b a and a ≻ b ⇐⇒ def
b ≺ a.
3.5. Partial Order Relations 62
Example 3.47. Consider the poset ({2, 3, 4, 5, 6, 7, 8, 9}; |) shown in Figure 3.1. It
has no least or greatest elements, but 2, 3, 5, and 7 are minimal elements, and 5,
6, 7, 8 and 9 are maximal elements. The number 2 is a lower bound (actually the
greatest lower bound) of the subset {4, 6, 8}, and the subset {4, 9} has no lower
(nor upper) bound.
Example 3.48. The poset ({1, 2, 3, 4, 6, 8, 12, 24}; |) shown in Figure 3.1 has both
a least (1) and a greatest (24) element. The subset {8, 12} has the three lower
bounds 1, 2, and 4, and 4 is the greatest lower bound of {8, 12}. Actually, this
poset is special in that any set of elements has a greatest lower bound and a least
upper bound. How can glb(S) and lub(S) be defined?
Example 3.49. The poset (P({a, b, c}); ⊆) shown in Figure 3.1 has both a least
element, namely ∅, and a greatest element, namely {a, b, c}.
Example 3.50. In the poset (Z+ ; |), 1 is a least element but there is no greatest
element.
Note that every totally ordered finite poset is well-ordered. The property of
being well-ordered is of interest only for infinite posets. The natural numbers N
are well-ordered by ≤. Any subset of the natural numbers is also well-ordered.
More generally, any subset of a well-ordered set is well-ordered (by the same
order relation).
33 Note that a least or a greatest element need not exist. However, there can be at most one least
element, as suggested by the word “the” in the definition. This follows directly from the antisym-
metry of . If there were two least elements, they would be mutually comparable, and hence must
be equal.
34 German: untere (obere) Schranke
35 Note that the definitions of the least element and of a lower bound differ only in that a lower
bound can be outside of the considered subset S (and therefore need not be unique).
36 Note that for a poset (A; ) and a subset S ⊆ A, restricting to S results in a poset (S; ).
37 German: wohlgeordnet
38 The least element is defined naturally (see Definition 3.29).
63 Chapter 3. Sets, Relations, and Functions
Definition 3.31. Let (A; ) be a poset. If a and b (i.e., the set {a, b} ⊆ A) have a
greatest lower bound, then it is called the meet of a and b, often denoted a ∧ b.
If a and b have a least upper bound, then it is called the join of a and b, often
denoted a ∨ b.
Definition 3.32. A poset (A; ) in which every pair of elements has a meet and
a join is called a lattice39 .
Example 3.51. The posets (N; ≤), (N \ {0}; | ), and (P(S); ⊆) are lattices, as the
reader can verify.
Example 3.52. The poset ({1, 2, 3, 4, 6, 8, 12, 24}; |) shown in Figure 3.1 is a lat-
tice. The meet of two elements is their greatest common divisor, and their join
is the least common multiple. For example, 6 ∧ 8 = 2, 6 ∨ 8 = 24, 3 ∧ 4 = 1, and
3 ∨ 4 = 12. In contrast, the poset ({2, 3, 4, 5, 6, 7, 8, 9}; |) is not a lattice.
3.6 Functions
The concept of a function is perhaps the second most fundamental concept in
mathematics (after the concept of a set). We discuss functions only now, after
having introduced relations, because functions are a special type of relation, and
several concepts defined for relations (e.g. inversion and composition) apply to
functions as well.
43
Definition 3.34. The set of all functions A → B is denoted as B A .
One can generalize the function concept by dropping the first condition (to-
tally defined), i.e., allowing that there can exist elements a ∈ A for which f (a) is
not defined.
def
f (S) = {f (a) | a ∈ S}.
Definition 3.37. The subset f (A) of B is called the image (or range) of f and is
also denoted Im(f ).
def
f −1 (T ) = {a ∈ A| f (a) ∈ T }.
Example 3.54. Consider again the function f (x) = x2 . The preimage of the
interval [4, 9] is [−3, −2] ∪ [2, 3].
43 This notation is motivated by the fact that if A and B are finite, then there are |B||A| such
functions.
44 German: Bild
45 German: Urbild
65 Chapter 3. Sets, Relations, and Functions
Definition 3.40. For a bijective function f , the inverse (as a relation, see Defini-
tion 3.11) is called the inverse function46 of f , usually denoted as f −1 .
Example 3.55. Consider again the function f (x) = x3 + 3 and g(x) = 2x2 + x.
Then g ◦ f (x) = 2(f (x))2 + f (x) = 2x6 + 13x3 + 21.
Proof. This is a direct consequence of the fact that relation composition is asso-
ciative (see Lemma 3.7).
Definition 3.42.
(i) Two sets A and B equinumerous48 , denoted A ∼ B, if there exists a bijection
A → B.
(ii) The set B dominates the set A, denoted A B, if A ∼ C for some subset
C ⊆ B or, equivalently, if there exists an injective function A → B.
(iii) A set A is called countable49 if A N, and uncountable50 otherwise.51
Lemma 3.15. 52
(i) The relation ∼ is an equivalence relation.
(ii) The relation is transitive: A B ∧ B C =⇒ A C.
(iii) A ⊆ B =⇒ A B.
Theorem 3.16. A B ∧ B A =⇒ A ∼ B.
Proof. A statement of the form “if and only if” has two directions. To prove the
direction ⇐=, note that if A is finite, then it is countable, and also if A ∼ N, then
A is countable.
To prove the other direction (=⇒), we prove that if A is countable and infinite,
then A ∼ N. According to the definition, A N means that there is a bijection
f : A → C for a set C ⊆ N. For any infinite subset of N, say C, one can define a
bijection g : C → N as follows. According to the well-ordering principle, there
exists a least element of C, say c0 . Define g(c0 ) = 0. Define C1 = C \ {c0 }.
Again, according to the well-ordering principle, there exists a least element of
C1 , say c1 . Define g(c1 ) = 1. This process can be continued, defining inductively
a bijection g : C → N. Now g ◦ f is a bijection A → N, which proves A ∼ N.
def
Theorem 3.18. The set {0, 1}∗ = {ǫ, 0, 1, 00, 01, 10, 11, 000, 001, . . .} of finite binary
sequences is countable.54
Proof. We could give an enumeration of the set {0, 1}∗, i.e., a bijection be-
tween {0, 1}∗ and N, but to prove the theorem it suffices to provide an injection
{0, 1}∗ → N, which we define as follows. We put a “1” at the beginning of the
string and then interpret it as an natural number using the usual binary repre-
sentation of the natural numbers. For example, the string 0010 is mapped to the
number 18.55
Theorem 3.19. The set N×N (= N2 ) of ordered pairs of natural numbers is countable.
m = n − 2t , where t > 0 is the smallest integer such that t+1 2 > n. This cor-
responds to the enumeration of the pairs (k, m) along diagonals with constant
sum k + m. More concretely, we enumerate the pairs as follows: (0, 0), (1, 0),
(0, 1), (2, 0), (1, 1), (0, 2), (3, 0), (2, 1), (1, 2), (0, 3), (4, 0), (3, 1), · · ·. It is easy to
see that this is a bijection N → N2 , hence N2 is countable.
where we first encode the length |a| of a and then append a and b.
Corollary 3.20. The Cartesian product A × B of two countable sets A and B is count-
able, i.e., A N ∧ B N =⇒ A × B N.
Proof. Every rational number can be represented uniquely as a pair (m, n) where
m ∈ Z, n ∈ N \ {0}, and where m and n are relatively prime. Hence Q Z × N.
According to Example 3.56, Z is countable, i.e., Z N. Thus, according to
Corollary 3.20, Z × N N. Hence, using transitivity of , we have Q N (i.e.,
Q is countable).
The next theorem provides some other important sets that are countable.
Proof. Statement (i) can be proved by induction. The (trivial) induction basis is
that A1 = A is countable. The induction step shows that if An is countable, then
also An+1 ∼ An × A is countable. This follows from Corollary 3.20 because both
An and A are countable.
We omit the proof of (ii).
We now prove (iii), which implies (i), and hence gives an alternative proof
for (i). We define an injection A∗ → {0, 1}∗. This is achieved by using an ar-
bitrary injection f : A → {0, 1}∗ and defining the natural injection g : A∗ →
({0, 1}∗)∗ as follows: For a sequence of length n in A∗ , say (a1 , . . . , an ), we let
g(a1 , . . . , an ) = f (a1 ), . . . , f (an ) ,
i.e., each element in the sequence is mapped separately using f . Now it only
remains to demonstrate an injection ({0, 1}∗)∗ → {0, 1}∗, which can be achieved
as follows.56 We replace every 0-bit in a sequence by 00 and every 1-bit by 01,
which defines a (length-doubling) injection {0, 1}∗ → {0, 1}∗. Then we con-
catenate all obtained expanded sequences, always separated by 11. This is an
injection because the separator symbols 11 can be detected and removed and
the extra 0’s can also be removed. Hence a given sequence can be uniquely de-
composed into the component sequences, and hence no two sequences of binary
(component) sequences can result in the same concatenated sequence.
Example 3.58. We illustrate the above injection ({0, 1}∗)∗ → {0, 1}∗ by an ex-
ample. Consider the sequence (0100, 10111, 01, 1) of bit-sequences. Now 0100
is mapped to 00010000, 10111 is mapped to 0100010101, etc. and the final con-
catenated sequence is 000100001101000101011100011101, which can uniquely be
decomposed into the original four sequences.
Definition 3.43. Let {0, 1}∞ denote the set of semi-infinite binary sequences or,
equivalently, the set of functions N → {0, 1}.
56 Notethat a simple concatenation of the sequences does not work because the concatenated
sequences can not uniquely be decomposed into the original sequences, i.e., this is not an injection.
3.7. Countable and Uncountable Sets 70
def
f (i) = βi,0 , βi,1 , βi,2 , βi,3 , . . . .
Let b be the complement of a bit b ∈ {0, 1}. We define a new semi-infinite binary
sequence α as follows:
def
α = β0,0 , β1,1 , β2,2 , β3,3 , . . . .
57 Here we make use of Theorem 3.17 which implies that {0, 1}∞ is countable if and only if such
a bijection exists.
58 A subtlety, which is not a problem in the proof, is that some real numbers have two representa-
tions as bit-strings. For example, the number 0.5 has representations 10000000 · · · and 0111111 · · ·.
71 Chapter 3. Sets, Relations, and Functions
In fact, essentially all such functions are uncomputable. Those that are com-
putable are rare exceptions. For example, the function prime : N → {0, 1} is
computable.
Is there a specific uncomputable function? A prominent example is the so-
called Halting problem defined as follows: Given as input a program (encoded
as a bit-string or natural number) together with an input (to the program), de-
termine whether the program will eventually stop (function value 1) or loop
forever (function value 0) on that input. This function is uncomputable. This is
usually stated as: The Halting problem is undecidable.
This theorem can also be proved by a diagonalization argument similar to
the one above. The theorem has far-reaching consequences in theoretical and
practical Computer Science. It implies, for example, that it is impossible to write
a program that can verify (in the most general case) whether a given program
satisfies its specification, or whether a given program contains malicious parts.
Chapter 4
Number Theory
4.1 Introduction
Number theory is one of the most intriguing branches of mathematics. For a
long time, number theory was considered one of the purest areas of mathemat-
ics, in the sense of being most remote from having applications. However, since
the 1970’s number theory has turned out to have intriguing and unexpected
applications, primarily in cryptography.
In this course we discuss only some basic number-theoretic topics that have
applications in Computer Science. In addition to the rich applications, a sec-
ond reason for discussing the basics of number theory in a course in Computer
Science is as a preparation for the chapter on algebra (Chapter 5).
72
73 Chapter 4. Number Theory
Example 4.3. The recent proof of the Catalan conjecture by Preda Mihailescu,
who worked at ETH Zürich, is another break-through in number theory. This
theorem states that the equation am − bn = 1 has no other integer solutions but
32 − 23 = 1 (for m, n ≥ 2).
Theorem 4.1 (Euclid). For all integers a and d 6= 0 there exist unique integers q and
r satisfying
a = dq + r and 0 ≤ r < |d|.
Here a is called the dividend, d is called the divisor, q is called the quotient, and
r is called the remainder. The remainder r is often denoted as Rd (a) or sometimes
as a mod d.
Proof. We carry out this proof in a detailed manner, also to serve as an example
of a systematic proof.
We define S to be the set of possible nonnegative remainders:
def
S = {s| s ≥ 0 and a = dt + s for some t ∈ Z}.
We prove the following three claims by first proving 1), then proving that 1)
implies 2), and then proving that 2) implies 3).
1) S is not empty.
2) S contains an r < |d|.
3) The r of claim 2) is unique.
2 German: Teiler
3 German: Vielfaches
4 One can prove that it is unique.
5 German: Rest
75 Chapter 4. Number Theory
Proof of 1): We use case distinction and prove the statement for three cases (one
of which is always satisfied):
Case 1: a ≥ 0. Then a = d0 + a and hence a ∈ S.
Case 2: a < 0 and d > 0. Then a = da + (1 − d)a and thus (1 − d)a ∈ S since
(1 − d)a ≥ 0 because both (1 − d) and a are ≤ 0.
Case 3: a < 0 and d < 0. Then a = d(−a) + (1 + d)a and thus (1 + d)a ∈ S since
(1 + d)a ≥ 0 because both (1 + d) and a are ≤ 0.
Proof that 1) implies 2): Because S is not empty, it has a smallest element
(due to the well-ordering principle), which we denote by r. We now prove that
r < |d|, by contradiction, i.e., assuming r ≥ |d|. By definition of S we have
a = dq + r for some q. We make a case distinction: d > 0 and d < 0. If d > 0,
then
a = d(q + 1) + (r − |d|),
hence r − |d| ≥ 0 and therefore r − |d| ∈ S, which means that r is not the smallest
element of S, a contradiction. If d < 0, then a = d(q − 1) + (r − |d|), and the same
argument as above shows that r − |d| ∈ S, a contradiction.
Proof that 2) implies 3): It remains to prove that r is unique. We give a proof
only for d > 0; the case d < 0 is analogous and is left as an exercise. The proof
is by contradiction. Suppose that there also exist r′ 6= r with 0 ≤ r′ < |d| and
such that a = dq ′ + r′ for some q ′ . We distinguish the three cases q ′ = q, q ′ < q,
and q ′ > q. If q ′ = q, then r′ = a − dq ′ = a − dq = r, a contradiction since we
assumed r′ 6= r. If q ′ < q, then q − q ′ ≥ 1, so
r′ = a − dq ′ = (a − dq) + d(q − q ′ ) ≥ r + d.
Since r′ ≥ r + d ≥ d, the condition 0 ≤ r′ < |d| is violated, which is a contra-
diction. A symmetric argument shows that q ′ > q also results in a contradic-
tion,
Definition 4.2. For integers a and b (not both 0), an integer d is called a greatest
common divisor6 of a and b if d divides both a and b and if every common divisor
of a and b divides d, i.e., if
d | a ∧ d | b ∧ ∀c (c | a ∧ c | b) → c | d .
The concept of a greatest common divisor applies not only to Z, but to more
general structures (e.g. polynomial rings). If d and d′ are both greatest common
divisors of a and b, then d | d′ and d′ | d. For the integers Z, this means that
d′ = ±d, i.e., there are two greatest common divisors. (But for more general
structures there can be more than two greatest common divisors.)
6 Note that the term “greatest” does not refer to the order relation ≤ but to the divisibility relation.
4.2. Divisors and Division 76
Definition 4.3. For a, b ∈ Z (not both 0) one denotes the unique positive greatest
common divisor by gcd(a, b) and usually calls it the greatest common divisor. If
gcd(a, b) = 1, then a and b are called relatively prime7 .
Proof. It is easy to prove (as an exercise) that every common divisor of m and
n − qm (and therefore also the greatest) is also a common divisor of m and n,
and vice versa.
which is the basis for Euclid’s well-known gcd-algorithm: Start with m < n and
repeatedly replace the pair (m, n) by the pair (Rm (n), m) until the remainder
is 0, at which point the last non-zero number is equal to gcd(m, n).
Definition 4.4. For a, b ∈ Z, the ideal generated by a and b8 , denoted (a, b), is the
set
def
(a, b) = {ua + vb | u, v ∈ Z}.
Similarly, the ideal generated by a single integer a is
def
(a) = {ua | u ∈ Z}.
Lemma 4.4. Let a, b ∈ Z (not both 0). If (a, b) = (d), then d is a greatest common
divisor of a and b.
7 German: teilerfremd
8 German: durch a und b erzeugtes Ideal
77 Chapter 4. Number Theory
Proof. d is a common divisor of a and b since a ∈ (d) and b ∈ (d). To show that d
is a greatest common divisor, i.e., that every common divisor c of a and b divides
d, note that c divides every integer of the form ua + vb, in particular d.
This notion of having only trivial divisors extends to other rings, for example
the ring of polynomials over R. In such a general context, the property is called
irreducible rather than prime. The term prime is in general used for the property
that if p divides a product of elements, then it divides at least one of them (see
Lemma 4.7 below). For the integers, these two concepts are equivalent. The next
lemma states one direction of this equivalence.
The following theorem is called the fundamental theorem of arithmetic.
Theorem 4.6. Every positive integer can be written uniquely (up to the order in which
factors are listed) as the product of primes.11
Proof. The proof is by induction on n. The claim is trivially true for n = 1 (induction
basis). Suppose it is true for some general n (induction hypothesis). To prove the claim
for n + 1 (induction step), suppose that p | x1 · · · xn+1 . We let y := x1 · · · xn (and hence
p | yxn+1 ) and look at the two cases p | y and p6 | y separately. If p | y, then p | xi for
some 1 ≤ i ≤ n, due to the induction hypothesis, and we are done. If p6 | y, then, since p
has no positive divisor except 1 and p, we have gcd(p, y) = 1. By Corollary 4.5 there are
integers u and v such that up + vy = 1. Hence we have
Because p divides both terms (uxn+1 )p and v(yxn+1 ) in the sum on the right side, it
follows that it also divides the sum, i.e., p | xn+1 , which concludes the proof.
Proof. We first need to prove that a factorization into primes exists and then that it is
unique.
The existence is proved by contradiction. Every prime can obviously be factored into
primes. Let n be the smallest positive integer which has no prime factorization. Since
it can not be a prime, we have n = km with 1 < k, m < n. Since both k and m can be
factored into primes, so can km = n, a contradiction. Hence there is no smallest n that
cannot be factored into primes, and therefore every n ≥ 1 can be factored into primes.
To prove the uniqueness of the prime factorization, suppose towards a contradiction
that an integer n can be factored in two (possibly different) ways as a product of primes,
where the primes p1 , . . . , pr and also the primes q1 , . . . , qs are put in an increasing order
and where we have written products of identical primes as powers (here ai > 0 and
11 Note that 1 has zero prime factors, which is allowed.
79 Chapter 4. Number Theory
bi > 0). Then for every i, pi | n and thus pi | q1b1 q2b2 · · · qsbs . Hence, by Lemma 4.7,
pi | qj for some j and, because qj is a prime and pi > 1, we have pi = qj . Similarly for
every j, qj = pi for some i. Thus the set of primes are identical, i.e., r = s and pi = qi
for 1 ≤ i ≤ r. To show that the corresponding exponents ai and bi are also identical,
suppose that ai < bi for some i. We can divide both expressions by pai i , which results
in two numbers that are equal, yet one is divisible by pi while the other is not. This is
impossible since if two numbers are equal, then they have the same divisors.
Example 4.6. Consider now a slightly twisted version of the Gaussian integers:
√ √
Z[ −5] = {a + b 5i | a, b ∈ Z}.
Like the Gaussian integers, this set is closed with respect to addition and multiplication
(of complex numbers). For example,
√ √ √
(a + b 5i)(c + d 5i) = ac − 5bd + (bc + ad) 5i.
√
The only units in Z[ −5] are 1 and −1. One can check√easily, by ruling √ out all possible
divisors with smaller norm, that the elements 2, 3, 1 + 5i, and 1 − 5i are irreducible.
The element 6 can be factored in two different ways into irreducible elements:
√ √
6 = 2 · 3 = (1 + 5i)(1 − 5i).
Note that this proof is simpler and more general than the proof given in Example 2.28
because there we have not made use of the unique prime factorization of the integers.
approximating the minor third, major third, fourth, and fifth astonishingly well.
One can view these relations also as integer approximations. For example, we have
531′ 441 = 312 ≈ 219 = 524′ 288, which implies that ( 23 )12 ≈ 27 , i.e., 12 fifths are approxi-
mately seven octaves.
√
A piano for which every half-tone has the same frequency ratio, namely 12 2, is called
a well-tempered15 piano. The reason why music is a pleasure, despite its theoretically
unavoidable inaccuracy, is that our ear is trained to “round tones up or down” as needed.
Proof. To arrive at a contradiction, suppose Q that the set of primes is finite, say P =
{p1 , . . . , pm }. Then the number n = m i=1 p i + 1 is not divisible by any of the primes
p1 , . . . , pm and hence n is either itself a prime, or divisible by a prime not in {p1 , . . . , pm }.
In either case, this contradicts the assumption that p1 , . . . , pm are the only primes.
Theorem 4.10. Gaps between primes can be arbitrarily large, i.e., for every k ∈ N there exists
n ∈ N such that the set {n, n + 1, · · · , n + k − 1} contains no prime.
Example 4.7. The largest gap between two primes below 100 is 8. Which are these
primes?
There exists a huge body of literature on the density and distribution of primes. We
only state the most important one of them.
Definition 4.7. The prime counting function π : R → N is defined as follows: For any real
x, π(x) is the number of primes ≤ x.
15 German: wohltemperiert
4.4. Some Basic Facts About Primes * 82
The following theorem proved by Hadamard and de la Vallée Poussin in the 19th
century states that the density of primes ≤ x is approximately 1/ ln(x). This shows that
if one tries to find a large (say 1024 bit) prime, for instance for cryptographic purposes,
then a randomly selected odd integer has reasonable chances of being prime. Much more
precise estimates for π(x) are known today.
π(x) ln(x)
Theorem 4.11. lim = 1.
x→∞ x
Two of the main open conjectures on prime numbers are the following:
Conjecture 4.1. There exist infinitely many twin primes, i.e., primes p for which also
p + 2 is prime.
Conjecture 4.2 (Goldbach). Every even number greater than 2 is the sum of two primes.
Proof.√If n is composite,
√ it has a divisor a with
√ 1<√ a < n. Hence n = ab for b > 1. Either
a ≤ n√ or b ≤ n since otherwise ab > n · n = n. Hence n has a divisor √ c with
1 < c ≤ n. Either c is prime or, by Theorem 4.6, has a prime divisor d < c ≤ n.
For large integers, trial-division up to the square root is hopelessly inefficient. Let us
briefly discuss the algorithmic problem of testing primality.
Primes are of great importance in cryptography. In many applications, one needs to
generate very large primes, with 1024 or even 2048 bits. In many cases, the primes must
remain secret and it must be infeasible to guess them. They should therefore be selected
uniformly at random from the set of primes in a certain interval, possibly satisfying some
further restrictions for security or operational reasons.
Such primes can be generated in three different ways. The first approach is to select
a random (odd) integer from the given interval (e.g. [101023 , 101024 − 1]) and to apply
a general primality test. Primality testing is a very active research area. The record
in general primality testing is around 8.000 decimal digits and required sophisticated
techniques and very massive computing power. As a celebrated theoretical breakthrough
(with probably little practical relevance), it was proved in 2002 that primality testing is
in P, i.e., there is a worst-case polynomial-time algorithm for deciding primality of an
integer.16
The second approach is like the first, but instead of a primality test one performs a
probabilistic compositeness test. Such a test has two outcomes, “composite” and “pos-
sibly prime”. In the first case, one is certain that the number is composite, while in the
16 M. Agrawal, N. Kayal, and N. Saxena, PRIMES is in P, Annals of Mathematics vol. 160, pp. 781–
793.
83 Chapter 4. Number Theory
other case one has good chances that the number is a prime, without being certain. More
precisely, one can fix a (very small) probability ǫ (e.g. ǫ = 10−100 ) and then perform
a test such that for any composite integer, the probability that the test does not output
“composite” is bounded by ǫ.
A third approach is to construct a prime together with a proof of primality. As we
might see later, the primality of an integer n can be proved if one knows part of the
factorization of n − 1.
def
a ≡m b ⇐⇒ m | (a − b).
Example 4.10. We have 23 ≡7 44 and 54321 ≡10 1. Note that a ≡2 b means that
a and b are either both even or both odd.
Example 4.11. If a ≡2 b and a ≡3 b, then a ≡6 b. The general principle underly-
ing this example will be discussed later.
The above examples 4.8 and 4.9 make use of the fact that if an equality holds
over the integers, then it must also hold modulo 2 or, more generally, modulo
any modulus m. In other words, for any a and b,
a = b =⇒ a ≡m b (4.1)
4.5. Congruences and Modular Arithmetic 84
for all m, i.e., the relation ≡m is reflexive (a ≡m a for all a). It is easy to verify
that this relation is also symmetric and transitive, which was already stated in
Chapter 3:
The implication (4.1) can be turned around and can be used to prove the
inequality of two numbers a and b:
a 6≡m b =⇒ a 6= b.
The following lemma shows that modular congruences are compatible with
the arithmetic operations on Z.
a + c ≡m b + d and ac ≡m bd.
Proof. We only prove the first statement and leave the other proof as an exercise.
We have m | (a − b) and m | (c − d). Hence m also divides (a − b) + (c − d) =
(a + c) − (b + d), which is the definition of a + c ≡m b + d.
f (a1 , . . . , ak ) ≡m f (b1 , . . . , bk ).
Example 4.12. Is n = 84877 · 79683 − 28674 · 43879 even or odd? The answer
is trivial and does not require the computation of n. The product of two odd
numbers is odd, the product of an even and an odd numbers is even, and the
difference of an odd and an even number is odd. Thus n is odd.
(i) a ≡m Rm (a).
(ii) a ≡m b ⇐⇒ Rm (a) = Rm (b).
The above lemma together with Lemma 4.14 implies that if in a computation
involving addition and multiplication one is interested only in the remainder of
the result modulo m, then one can compute remainders modulo m at any in-
termediate step (thus keeping the numbers small), without changing the result.
This is referred to as modular arithmetic.
Proof. By Lemma 4.16 (i) we have ai ≡m Rm (ai ) for all i. Therefore, using
Corollary 4.15 we have f (a1 , . . . , ak ) ≡m f (Rm (a1 ), . . . , Rm (ak )). Thus, using
Lemma 4.16 (ii) we obtain the statement to be proved.
Example 4.13. Compute 7100 modulo 24. We make use of the fact that 72 =
49 ≡24 1. Thus R24 (7100 ) = R24 ((72 )50 ) = R24 (R24 (72 )50 ) = R24 (150 ) =
R24 (1) = 1.
Example 4.15. A similar test can be performed for m = 11. R11 (n) can be com-
puted by adding the decimal digits of n with alternating sign modulo 11. This
test, unlike that for m = 9, detects the swapping of digits.
Example 4.16. The larger m, the more likely it is that a calculation error is de-
tected. How could one implement a similar test for m = 99, how for m = 101?
ax ≡m b.
ax ≡m 1
x ≡ m1 a 1
x ≡ m2 a 2
...
x ≡ mr a r
Mi Ni ≡mk 0.
Therefore
r
X
ai M i N i ≡ mk ak
i=1
satisfies all the congruences. In order to prove uniqueness, observe that for two
solutions x′ and x′′ , x′ − x′′ ≡mi 0 for all i, i.e., x′ − x′′ is a multiple of all the mi
and hence of lcm(m1 , . . . , mr ) = M . Thus x′ ≡M x′′ .
The Chinese Remainder Theorem has several applications. When one is in-
terested in a computation modulo M , then the moduli mi can be viewed as a
coordinate system. One can project the numbers of interest modulo the mi , and
perform the computation in the r projections (which may be more efficient than
computing directly modulo M ). If needed at the end, one can reconstruct the
result from the projections.
Example 4.19. Compute R35 (21000 ). We can do this computation modulo 5 and
modulo 7 separately. Since 24 ≡5 1 we have 21000 ≡5 1. Since 23 ≡7 1 we have
21000 ≡7 2. This yields 21000 ≡35 16 since 16 is the (unique) integer x ∈ [0, 34]
with x ≡5 1 and x ≡7 2.
as (a version of) the discrete logarithm problem. The security of the Diffie-Hellman
protocol is based on this asymmetry in computational difficulty. Such a func-
tion, like x 7→ Rp (g x ), is called a one-way function: it is easy to compute in one
direction but computationally very hard to invert.21
The prime p and the basis g (e.g. g = 2) are public parameters, possibly
generated once and for all for all users of the system. The protocol is symmetric,
i.e., Alice and Bob perform the same operations. The exchange of the so-called
public keys yA and yB must be authenticated, but not secret.22 It is easy to see that
Alice and Bob end up with the same value kAB = kBA which they can use as
a secret key for encrypting subsequent communication.23 In order to compute
kAB from yA and yB , an adversary would have to compute either xA or xB ,
which is believed to be infeasible.
yA := Rp (g xA ) yB := Rp (g xB )
yA
✲
yB
✛
xA xB
kAB := Rp (yB ) kBA := Rp (yA )
xA
kAB ≡p yB ≡p (g xB )xA ≡p g xA xB ≡p kBA
to KAB .
24 A padlock with a key corresponds to a so-called trapdoor one-way function which is not consid-
ered here.
4.6. Application: Diffie-Hellman Key-Agreement 90
Alice Bob
insecure channel
x x
A A
yA=g A yB=g B B B
xA xB
yA
A
yB B
xx xx
B
kAB=g B A kBA=g A B
B
A
A
Figure 4.2: Mechanical analog of the Diffie-Hellman protocol.
interlocked. For the adversary, this is impossible without breaking open one of
the locks.
Another famous (and more widely used) public-key cryptosystem, the so-
called RSA-system invented in 1977 and named after Rivest, Shamir and Adle-
man25 , will be discussed later. Its security is based on the (conjectured) compu-
tational difficulty of factoring large integers.
Algebra
5.1 Introduction
5.1.1 What Algebra is About
In a nutshell, algebra is the mathematical study of structures consisting of a set
and certain operations on the set. Examples are the integers Z, the rational num-
bers Q, and the set of polynomials with coefficients from some domain, with the
respective addition and multiplication operations. A main goal in algebra is to
understand the properties of such algebraic systems at the highest level of gen-
erality and abstraction. For us, an equally important goal is to understand the
algebraic systems that have applications in Computer Science.
For instance, one is interested in investigating which properties of the inte-
gers are responsible for the unique factorization theorem. What do the integers,
the polynomials with rational or real coefficients, and several other structures
have in common so that the unique factorization theorem holds? Why does it
not hold for certain other structures?
The benefit of identifying the highest level of generality and abstraction is
that things often become simpler when unnecessary details are eliminated from
consideration, and that a proof must be carried out only once and applies to all
structures captured at the given level of generality.
91
5.2. Monoids and Groups 92
Operations with arity 1 and 2 are called unary and binary operations, respec-
tively. An operation with arity 0 is called a constant; it is a fixed element from
the set S, for instance the special element 1 in Z. In many cases, only binary
operations are actually listed explicitly,
Definition 5.3. A left [right] neutral element (or identity element) of an algebra
hS; ∗i is an element e ∈ S such that e ∗ a = a [a ∗ e = a] for all a ∈ S. If
e ∗ a = a ∗ e = a for all a ∈ S, then e is simply called neutral element.
Lemma 5.1. If hS; ∗i has both a left and a right neutral element, then they are equal.
In particular hS; ∗i can have at most one neutral element.
Proof. Suppose that e and e′ are left and right neutral elements, respectively.
Then, by definition, e ∗ e′ = e′ (considering e as a left neutral element), but also
e ∗ e′ = e (considering e′ as a right neutral element). Thus e′ = e.
Example 5.4. The empty sequence ǫ is the neutral element of hΣ∗ ; |i, where Σ∗
is the set of sequences over the alphabet Σ and | denotes concatenation of se-
quences.
Note that up to now, and also in the next section, we do not yet pay attention
to the fact that some operations are commutative. In a sense, commutativity is
less important than associativity.
Some standard examples of associate operations are addition and multipli-
cation in various structures: Z, N, Q, R, and Zm .
Example 5.7. For a set A, the set AA of functions A → A form a monoid with re-
spect to function composition. The identity function id (defined by id(a) = a for
all a ∈ A) is the neutral element. According to Lemma 3.7, relation composition,
and therefore also function composition, is associative. The algebra hAA ; ◦, idi is
thus a monoid.
Lemma 5.2. In a monoid hM ; ∗, ei, if a ∈ M has a left and a right inverse, then they
are equal. In particular, a has at most one inverse.
Proof. Let b and c be left and right inverses of a, respectively, i.e., we have b ∗ a =
e and a ∗ c = e, Then
b = b ∗ e = b ∗ (a ∗ c) = (b ∗ a) ∗ c = e ∗ c = c,
Example 5.8. Consider again hAA ; ◦, idi. A function f ∈ AA has a left inverse
only if it is injective, and it has a right inverse only if it is surjective. Hence f has
an inverse f −1 if and only if f is bijective. In this case, f ◦ f −1 = f −1 ◦ f = id.
5 or simply left [right] inverse.
95 Chapter 5. Algebra
Definition 5.7. A group is an algebra hG; ∗,b, ei satisfying the following axioms:
G1 ∗ is associative.
G2 e is a neutral element: a ∗ e = e ∗ a = a for all a ∈ G.
G3 Every a ∈ G has an inverse element b a, i.e., a ∗ b
a=ba ∗ a = e.
We can write hG; ∗i (or simply G if ∗ is understood) instead of hG; ∗,b, ei. If
the operation ∗ is called addition (+) [multiplication (·)], then the inverse of a is
denoted −a [a−1 or 1/a] and the neutral element is denoted 0 [1].
Some standard examples of groups are hZ; +, −, 0i, hQ; +, −, 0i, hQ \
{0}; ·,−1 , 1i, hR; +, −, 0i, hR \ {0}; ·,−1 , 1i, and hZm ; ⊕, ⊖, 0i.
We summarize a few facts we encountered already earlier for the special case
of the integers Z. The group is the right level of abstraction for describing these
facts. The proofs are left as exercises.
Lemma 5.3. For a group hG; ∗,b, ei, we have for all a, b, c ∈ G:
c
(i) (b
a) = a.
(ii) ad
∗ b = bb ∗ b
a.
(iii) Left cancellation law: a ∗ b = a ∗ c =⇒ b = c.
(iv) Right cancellation law: b ∗ a = c ∗ a =⇒ b = c.
(v) The equation a ∗ x = b has a unique solution x for any a and b.
So does the equation x ∗ a = b.
= b a∗b
a ∗ (a ∗ (b b
a)) (G1)
= b a) ∗ b
a ∗ ((a ∗ b b
a) (G1)
a ∗ (e ∗ b
= b b
a) (G3)
b
a ∗ e) ∗ b
= (b a (G1)
a∗b
= b b
a (G2’)
= e (G3’, i.e., def. of right inverse of b
a)
Example 5.10. Recall that the sequences with concatenation and the empty se-
quence as the neutral element form a non-commutative monoid. This is not a
group because inverses cannot be defined (except for the empty sequence).
Example 5.12. Let Sn be the set of n! permutations of n elements, i.e., the set
of bijections {1, . . . , n} → {1, . . . , n}. A bijection f has an inverse f −1 . Sn is a
subset of the set of functions {1, . . . , n} → {1, . . . , n}. It follows from the asso-
ciativity of function composition that the composition of permutations is also
associative. The group hSn ; ◦,−1 , idi is called the symmetric group on n elements.
Sn is non-abelian for n ≥ 3.
permuted. Consider the four reflections with respect to one of the two mid-
dle parallels or one of the two diagonals. The closure under composition of
these four elements also includes the four rotations by 0◦ (the neutral element),
by 90◦ , 180◦, and by 270◦ . These 8 elements (reflections and rotations) form a
group, which we denote by S✷ . It is called the symmetry group of the square. If
the vertices of the square are labeled A, B, C, D, then these eight geometric op-
erations each corresponds to a permutation of the set {A, B, C, D}. For example,
the rotation by 90◦ corresponds to the permutation (A, B, C, D) → (B, C, D, A).
Note that the set of four rotations also form a group, actually a subgroup of the
above described group and also a subgroup of the group of permutations on
{A, B, C, D}.7
Example 5.14. It is left as an exercise to figure out the symmetry group of the
three-dimensional cube.
Definition 5.9. The direct product of n groups hG1 ; ∗1 i , . . . , hGn ; ∗n i is the alge-
bra
hG1 × · · · × Gn ; ⋆i,
where the operation ⋆ is component-wise:
Lemma 5.4. hG1 × · · ·× Gn ; ⋆i is a group, where the neutral element and the inversion
operation are component-wise in the respective groups.
Example 5.15. Consider the group hZ5 ; ⊕i × hZ7 ; ⊕i. The carrier of the group is
Z5 × Z7 . The neutral element is (0, 0). If we denote the group operation by ⋆,
[
then we have (2, 6) ⋆ (4, 3) = (1, 2). Also, (2, 6) = (3, 1). It follows from the
Chinese remainder theorem that hZ5 ; ⊕i × hZ7 ; ⊕i is isomorphic to hZ35 ; ⊕i, a
concept introduced in the following subsection.
7 We point out that one can consider the described operations also as bijections of the real plane,
i.e., as functions R2 → R2 .
5.3. The Structure of Groups 98
Definition 5.10. For two groups hG; ∗,b, ei and hH; ⋆,e, e′ i, a function ψ : G → H
is called a group homomorphism if, for all a and b,
We use the symbol e for the inverse operation in the group H. The proof of
the following lemma is left as an exercise:
Lemma 5.5. A group homomorphism ψ from hG; ∗,b, ei to hH; ⋆,e, e′ i satisfies
(i) ψ(e) = e′ ,
(ii) ψ(b g for all a.
a) = ψ(a)
Example 5.16. The group hZ6 ; ⊕i × hZ10 ; ⊕i is isomorphic to hZ2 ; ⊕i × hZ30 ; ⊕i.
The isomorphism ψ : Z6 × Z10 → Z2 × Z30 is easily checked to be given by
ψ((a, b)) = (a′ , b′ ) where a′ ≡2 a (i.e., a′ = R2 (a)) and b′ is given by b′ ≡3 a and
b′ ≡10 b (where the Chinese remainder theorem can be applied).
We give two familiar examples of relevant homomorphisms that are not iso-
morphisms.
Example 5.18. If one considers the three-dimensional space R3 with vector ad-
dition, then any projection on a plane through the origin or a line through the
origin are homomorphic images of R3 . A special case is the projection onto an
axis of the coordinate system, which abstracts away all but one coordinate.
5.3.3 Subgroups
For a given algebra, for example a group or a ring (see Section 5.5), a subalgebra
is a subset that is by itself an algebra of the same type, i.e., a subalgebra is a sub-
set of an algebra closed under all operations. For groups we have specifically:
Example 5.20. For any group hG; ∗,b, ei, there exist two trivial subgroups: the
subset {e} and G itself.
Example 5.21. Consider the group Z12 (more precisely hZ12 ; ⊕, ⊖, 0i). The
following subsets are all the subgroups: {0}, {0, 6}, {0, 4, 8}, {0, 3, 6, 9},
{0, 2, 4, 6, 8, 10}, and Z12 .
Example 5.22. The set of symmetries and rotations discussed in example 5.13,
denoted S✷ , constitutes a subgroup (with 8 elements) of the set of 24 permuta-
tions on 4 elements.
• a0 = e,
• an = a · an−1 for n ≥ 1, and
• an = (a−1 )|n| for n ≤ −1.
Example 5.23. The order of 6 in hZ20 ; ⊕, ⊖, 0i is 10. This can be seen easily since
60 = 10 · 6 is the least common multiple of 6 and 20. The order of 10 is 2, and we
note that 10 is self-inverse.
Example 5.24. The order of any axial symmetry in the group S✷ (see exam-
ple 5.13) is 2, while the order of the 90◦ -rotation (and also of the 270◦-rotation)
is 4.
Example 5.26. Consider the group S5 of permutations on the set {1, 2, 3, 4, 5}.
What is the order of the permutations described by (1, 2, 3, 4, 5) → (3, 1, 2, 4, 5),
by (1, 2, 3, 4, 5) → (1, 2, 3, 5, 4), and by (1, 2, 3, 4, 5) → (2, 3, 1, 5, 4)?
Proof. Since G is finite, we must have ar = as = b for some r and s with r < s
(and some b). Then as−r = as · a−r = b · b−1 = e.
Definition 5.13. For a finite group G, |G| is called the order of G.9
am = aRord(a) (m) .
Definition 5.14. For a group G and a ∈ G, the group generated by a, denoted hai,
is defined as
def
hai = {an | n ∈ Z}.
8 German: Ordnung
9 Note that the term “order” has two different (but related) meanings.
101 Chapter 5. Algebra
It is easy to see that hai is a group, actually the smallest subgroup of a group
G containing the element a ∈ G. For finite groups we have
def
hai = {e, a, a2 , . . . , aord(a)−1 }.
Being cyclic is a special property of a group. Not all groups are cyclic! A
cyclic group can have many generators. In particular, if g is a generator, then so
is g −1 .
Example 5.27. The group hZn ; ⊕i is cyclic for every n, where 1 is a generator.
The generators of hZn ; ⊕i are all g ∈ Zn for which gcd(g, n) = 1, as the reader
can prove as an exercise.
Example 5.28. The additive group of the integers, hZ; +, −, 0i, is an infinite
cyclic group generated by 1. The only other generator is −1.
Theorem 5.7. A cyclic group of order n is isomorphic to hZn ; ⊕i (and hence abelian).
Proof. Let G = hgi be a cyclic group of order n (with neutral element e). The
bijection Zn → G : i 7→ g i is a group isomorphism since i ⊕ j 7→ g i+j =
gi ∗ gj .
Theorem 5.8 (Lagrange). Let G be a finite group and let H be a subgroup of G. Then
the order of H divides the order of G, i.e., |H| divides |G|.
Corollary 5.9. For a finite group G, the order of every elements divides the group order,
i.e., ord(a) divides |G| for every a ∈ G.
Corollary 5.11. Every group of prime order10 is cyclic, and in such a group every
element except the neutral element is a generator.
Proof. Let |G| = p with p prime. For any a, the order of the subgroup hai divides
p. Thus either ord(a) = 1 or ord(a) = p. In the first case, a = e and in the latter
case G = hai.
def
Definition 5.16. Z∗m = {a ∈ Zm | gcd(a, m) = 1}.
ϕ(pe ) = pe−1 (p − 1)
since exactly every pth integer in Zpe contains a factor p and hence ϕ(pe ) =
pe−1 (p − 1) elements contain no factor p. For a ∈ Zm we have gcd(a, m) = 1 if
and only if gcd(a, pei i ) = 1 for i = 1, . . . , r. Since the numbers pei i are pairwise
relatively prime, the Chinese remainder theorem implies that there is a one-
to-one correspondence between elements of Zm and lists (a1 , . . . , ar ) with ai ∈
Zpei i . Hence, using the above, there is also a one-to-one correspondence between
Qr
elements of Z∗m and lists (a1 , . . . , ar ) with ai ∈ Z∗pei . There are i=1 (pi − 1)piei −1
i
such lists.
Example 5.30. In Z∗18 = {1, 5, 7, 11, 13, 17} we have 5 ⊙ 13 = 11 and 11−1 = 5
since 11 ⊙ 5 = 1 (i.e., R18 (11 · 5) = 1).
Y
11 Alternatively, 1
ϕ(m) could be defined as ϕ(m) = m · 1− .
p
p|m
p prime
5.4. Application: RSA Public-Key Encryption 104
Now we obtain the following simple but powerful corollary to Theorem 5.8.
Corollary 5.14 (Fermat, Euler). For all m ≥ 2 and all a with gcd(a, m) = 1,
aϕ(m) ≡m 1.
ap−1 ≡p 1.
Proof. This follows from Corollary 5.10 for the group Z∗m of order ϕ(m).
The special case for primes was known already to Fermat.12 The general
case was proved by Euler, actually before the concept of a group was explicitly
introduced in mathematics.
We state the following theorem about the structure of Z∗m without proof. Of
particular importance and interest is the fact that Z∗p is cyclic for every prime p.
propriate. To test whether a number n is prime one chooses a base a and checks whether an−1 ≡n 1.
If the condition is violated, then n is clearly composite, otherwise n could be a prime. Unfortunately,
it is not guaranteed to be a prime. In fact, there are composite integers n for which an−1 ≡n 1 for
all a with gcd(a, n) = 1. (Can you find such an n?) For more sophisticated versions of such a
probabilistic test one can prove that for every composite n, the fraction of test values for which the
corresponding condition is satisfied is at most 1/4. Thus, by repeating the test sufficiently many
times, the confidence that n is prime can be increased beyond any doubt. This is useful in practice,
but it does not provide a proof that n is prime.
13 R. L. Rivest, A. Shamir, and L. Adleman, A method for obtaining digital signatures and public-
key cryptosystems, Communications of the ACM, Vol. 21, No. 2, pp. 120–126, 1978.
105 Chapter 5. Algebra
they can authenticate each other’s public keys (respectively the Diffie-Hellman
values). Moreover, the RSA system can be used as a digital signature scheme
(see below). RSA was the first cryptographic system offering this important
functionality.
Theorem 5.16. Let G be some finite group (multiplicatively written), and let e ∈ Z be
relatively prime to |G| (i.e. gcd(e, |G|) = 1). The function x 7→ xe is a bijection and
the (unique) e-th root of y ∈ G, namely x ∈ G satisfying xe = y, is
x = yd ,
ed ≡|G| 1.
which means that the function y 7→ y d is the inverse function of the function
x 7→ xe (which is hence a bijection). The under-braced term is equal to 1 because
of Corollary 5.10.
When |G| is known, then d can be computed from ed ≡|G| 1 by using the
extended Euclidean algorithm No general method is known for computing e-th
roots in a group G without knowing its order. This can be exploited to define a
public-key cryptosystem.
Generate
primes p and q
n=p·q
f = (p−1)(q−1)
select e
n, e plaintext
d ≡f e−1 ✲ m ∈ {1, . . . , n − 1}
c ciphertext
m = Rn (cd ) ✛ c = Rn (me )
Figure 5.1: The naı̈ve RSA public-key cryptosystem. Alice’s public key is the
pair (n, e) and her secret key is d. The public key must be sent to
Bob via an authenticated channel. Bob can encrypt a message, rep-
resented as a number in Zn , by raising it to the eth power modulo n.
Alice decrypts a ciphertext by raising it to the dth power modulo n.
can be computed only if the prime factors p and q of n are known.14 The (public)
encryption transformation is defined by
m 7→ c = Rn (me ),
c 7→ m = Rn (cd ),
ed ≡(p−1)(q−1) 1.
s ∈ Z∗n would be a legitimate signature, and hence forging a signature would be trivial.
5.5. Rings and Fields 108
Lemma 5.17. For any ring hR; +, −, 0, ·, 1i, and for all a, b ∈ R,
(i) 0a = a0 = 0.
(ii) (−a)b = −(ab).
(iii) (−a)(−b) = ab.
(iv) If R is non-trivial (i.e., if it has more than one element), then 1 6= 0.
addition follows from the remaining ring axioms. The stated ring axioms are hence not minimal.
The word “commutative” in (i) could be dropped.
109 Chapter 5. Algebra
Definition 5.19. The characteristic of a ring is the order of 1 in the additive group
if it is finite, and otherwise the characteristic is defined to be 0 (not infinite).
Example 5.38. The ring of Gaussian integers (see Example 4.5) contains four
units: 1, i, −1, and −i. For example, the inverse of i is −i.
Lemma 5.18. For a ring R, R∗ is a multiplicative group (the group of units of R).
Proof. We need to show that R∗ is closed under multiplication, i.e., that for
u ∈ R∗ and v ∈ R∗ , we also have uv ∈ R∗ , which means that uv has an in-
verse. The inverse of uv is v −1 u−1 since (uv)(v −1 u−1 ) = uvv −1 u−1 = uu−1 = 1.
R∗ also contains the neutral element 1 (since 1 has an inverse). Moreover, the
associativity of multiplication in R∗ is inherited from the associativity of multi-
plication in R (since elements of R∗ are also elements of R and the multiplication
operation is the same).
21 This also follows from commutativity of multiplication, but the proof shows that the statement
5.5.3 Divisors
In the following R denotes a commutative ring.
Definition 5.22. For ring elements a and b (not both 0), a ring element d is called
a greatest common divisor of a and b if d divides both a and b and if every common
divisor of a and b divides d, i.e., if
d | a ∧ d | b ∧ ∀c (c | a ∧ c | b) → c | d .
25 Recall that this definition was already stated as Definition 4.1 for the special case of integers.
26 German: Teiler
27 German: Vielfaches
28 German: Nullteiler
29 German: Integritätsbereich
30 i.e., 1 6= 0
111 Chapter 5. Algebra
and thus, because a 6= 0 and there are no zero-divisors, we must have c+(−c′ ) =
0 and hence c = c′ .
max(d,d′ )
X
a(x) + b(x) = (ai + bi ) xi ,
i=0
where here and in the following coefficients with index greater than the degree
are understood to be 0. The product of a(x) and b(x) is defined as33
d+d ′
i
! d+d ′ !
X X X X
i
a(x)b(x) = ak bi−k x = au bv xi
i=0 k=0 i=0 u+v=i
d+d′
= + · · · + (a0 b2 + a1 b1 + a2 b0 )x2 + (a0 b1 + a1 b0 )x + a0 b0 .
ad b d ′ x
Pi P
The i-th coefficient of a(x)b(x) is k=0 ak bi−k = u+v=i au bv , where the sum
is over all pairs (u, v) for which u + v = i as well as u ≥ 0 and v ≥ 0.
The degree of the product of polynomials over a ring R is, by definition, at
most the sum of the degrees. It is equal to the sum if R is an integral domain,
which implies that the highest coefficient is non-zero: ad bd′ 6= 0 if ad 6= 0 and
bd′ 6= 0.
Example 5.42. Consider the ring Z7 and let a(x) = 2x2 +3x+1 and b(x) = 5x+6.
Then
a(x) + b(x) = 2x2 + (3 + 5)x + (1 + 6) = 2x2 + x
and
a(x)b(x) = (2 · 5)x3 + (3 · 5 + 2 · 6)x2 + (1 · 5 + 3 · 6)x + 1 · 6 = 3x3 + 6x2 + 2x + 6.
Proof. We need to prove that the conditions of Definition 5.18 (i.e., the ring ax-
ioms) are satisfied for R[x], assuming they are satisfied for R. We first observe
that since multiplication in R is commutative, so is multiplication in R[x].
Condition (i) requires that R[x] is an abelian group with respect to (poly-
nomial) addition. This is obvious from the definition of addition. Associativ-
ity and commutativity of (polynomial) addition are inherited from associativ-
ity and commutativity of addition in R (because R is a ring). The neutral el-
ement is the polynomial 0, and the inverse in the group (i.e., the negative) of
P P
a(x) = di=0 ai xi is −a(x) = di=0 (−ai )xi .
Condition (ii) requires that R[x] is a monoid with respect to (polynomial)
multiplication. The polynomial 1 is the neutral element, which is easy to see.
That multiplication is associative can be seen as follows. Let a(x) and b(x) as
P ′′
above, and c(x) = di=0 ci xi . Using the above definition of a(x)b(x), we have
′
d+d
X +d′′ Xi X
a(x)b(x) c(x) = au bv ci−j xi
i=0 j=0 u+v=j
33 Note
P ′
that, for example, the highest coefficient d+d
k=0 ak bi−k is in the formula defined as a sum
of d + d′ + 1 terms, but all but one of them (namely for k = d) are zero.
113 Chapter 5. Algebra
d+d ′
+d′′
!
X X
= (au bv )cw xi .
i=0 u+v+w=i
If one computes a(x) b(x)c(x) , one arrives at the same expression, by mak-
ing use of associativity of multiplication in R, i.e., the fact that (au bv )cw =
au (bv cw ) = au bv cw .
Condition (iii), the distributive law, can also be shown to follow from the
distributive law holding for R.
Lemma 5.22.
(i) If D is an integral domain, then so is D[x].
(ii) The units of D[x] are the constant polynomials that are units of D: D[x]∗ = D∗ .
Example 5.43. Lemma 5.22 implies that for an integral domain D, the set D[x][y]
of polynomials in y with coefficients in D[x], is also an integral domain. One can
also view the elements of D[x][y] as polynomials in two indeterminates, denoted
D[x, y].
5.5.6 Fields
Example 5.44. Q, R, and C are fields, but Z and R[x] (for any ring R) are not
fields.
Proof. This follows from our earlier analysis of Z∗p , namely that Zp \ {0} is a
multiplicative group if and only if p is prime.
In the following we denote the field with p elements by GF(p) rather than
Zp . As explained later, “GF” stands for Galois field. Galois discovered finite
fields around 1830.
34 German: Körper
5.5. Rings and Fields 114
Fields are of crucial importance because in a field one can not only add,
subtract, and multiply, but one can also divide by any nonzero element. This
is the abstraction underlying many algorithms like those for solving systems of
linear equations (e.g. by Gaussian elimination) or for polynomial interpolation.
Also, a vector space, a crucial concept in mathematics, is defined over a field,
the so-called base field. Vector spaces over R are just a special case.
Example 5.45. Solve the following system of linear equations over Z11 :
5x ⊕ 2y = 4
2x ⊕ 7y = 9
Solution: Eliminate x by adding 2 times the first and ⊖5 = 6 times the second
equation, resulting in
(2 ⊙ 5 ⊕ 6 ⊙ 2) x + (2 ⊙ 2 ⊕ 6 ⊙ 7) y = 2 ⊙ 4 ⊕ 6 ⊙ 9,
| {z } | {z } | {z }
=0 =2 =7
x = 2−1 ⊙ (9 ⊖ 7 ⊙ y) = 6 ⊙ (9 ⊕ 4 ⊙ 9) = 6 ⊙ 1 = 6.
Later we will describe a few applications of finite fields. Here we give an-
other example of a finite field.
Example 5.46. We describe a field with 4 elements, F = {0, 1, A, B}, by giving
the function tables of addition and multiplication:
+ 0 1 A B · 0 1 A B
0 0 1 A B 0 0 0 0 0
1 1 0 B A 1 0 1 A B
A A B 0 1 A 0 A B 1
B B A 1 0 B 0 B 1 A
This field is not isomorphic to the ring Z4 , which is not a field. We explain the
construction of this 4-element field in Section 5.8.2.
Theorem 5.24. A field is an integral domain.
v = 1v = u−1 uv = u−1 0 = 0,
Definition 5.27. A polynomial a(x) ∈ F [x] is called monic35 if the leading coef-
ficient is 1.
In GF(2)[x] we have
Definition 5.28. A polynomial a(x) ∈ F [x] with degree at least 1 is called irre-
ducible if it is divisible only by constant polynomials and by constant multiples
of a(x).
It follows immediately from the definition (and from the fact that the degrees
are added when polynomials are multiplied) that every polynomial of degree 1
is irreducible. Moreover, a polynomial of degree 2 is either irreducible or the
product of two polynomials of degree 1. A polynomial of degree 3 is either
irreducible or it has at least one factor of degree 1. Similarly, a polynomial of
degree 4 is either irreducible, has a factor of degree 1, or has an irreducible
factor of degree 2.
Irreducibility of a polynomial of degree d can be checked by testing all irre-
ducible polynomials of degree ≤ d/2 as possible divisors. Actually, it suffices to
test only the monic polynomials because one could always multiply a divisor by
a constant, for example the inverse of the highest coefficient. This irreducibil-
ity test is very similar to the primality test which checks all divisors up to the
square root of the number to be tested.
Not only the concepts of divisors and division with remainders (see below)
carries over from Z to F [x], also the concept of the greatest common divisor can
be carried over. Recall that F [x] is a ring and hence the notion of a greatest
common divisor is defined. For the special type of ring F [x], as for Z, one can
single out one of them.
Definition 5.29. The monic polynomial g(x) of largest degree such that g(x) |
a(x) and g(x) | b(x) is called the greatest common divisor of a(x) and b(x), de-
noted gcd(a(x), b(x)).
Example 5.53. Consider GF(2)[x]. Let a(x) = x3 +x2 +x+1 and b(x) = x2 +x+1.
Then gcd(a(x), b(x)) = 1.
117 Chapter 5. Algebra
Theorem 5.25. Let F be a field. For any a(x) and b(x) 6= 0 in F [x] there exist a
unique q(x) (the quotient) and a unique r(x) (the remainder) such that
Proof sketch. We first prove the existence of q(x) and r(x) and then the unique-
ness. If deg(b(x)) > deg(a(x)), then q(x) = 0 and r(x) = a(x). We thus assume
that deg(b(x)) ≤ deg(a(x)). Let a(x) = am xm + · · · and b(x) = bn xn + · · · with
n ≤ m, where “· · ·” stands for lower order terms. The first step of polynomial
division consists of subtracting am bn−1 b(x)xm−n from a(x), resulting in a poly-
nomial of degree at most m − 1.36 Continuing polynomial division finally yields
q(x) and r(x), where deg(r(x)) < deg(b(x)) since otherwise one could still sub-
tract a multiple of b(x).
To prove the uniqueness, suppose that
where deg(r(x)) < deg(b(x)) and deg(r′ (x)) < deg(b(x)). Then
Since deg(r′ (x) − r(x)) < deg(b(x)), this is possible only if q(x) − q ′ (x) = 0, i.e.,
q(x) = q ′ (x), which also implies r′ (x) = r(x).37
In analogy to the notation Rm (a), we will denote the remainder r(x) of the
above theorem by Rb(x) (a(x)).
Example 5.54. Let F be the field GF(7) and let a(x) = x3 + 2x2 + 5x + 4 and
b(x) = 2x2 + x + 1. Then q(x) = 4x + 6 and r(x) = 2x + 5 since
point out that this only holds in an integral domain. (Why?) Recall that a field is an integral domain
(Theorem 5.24).
5.6. Polynomials over a Field 118
The units in Z are 1 and −1 and the units in F [x] are the non-zero constant polyno-
mials (of degree 0). In Z, a and −a are associates.
For a ∈ D one can define one associate to be distinguished. For Z the distinguished
associate of a is |a|, and for a(x) ∈ F [x] the distinguished associate of a(x) is the monic
polynomial associated with a(x). If we consider only the distinguished associates of
irreducible elements, then for Z we arrive at the usual notion of prime numbers.39
We point out that the association relation is closely related to divisibility. The proof
of the following lemma is left as an exercise.
Lemma 5.26. a ∼ b ⇐⇒ a | b ∧ b | a.
There is one more crucial property shared by both integral domains Z and F [x] (for
any field F ), described in the following abstract definition.
One can prove that in a Euclidean domain, the greatest (according to the degree func-
tion) common divisor is well-defined, up to taking associates, i.e., up to multiplication
38 In
other words, p is divisible only by units and associates of p.
39 There is a notion of a prime element of a ring,
which is different from the notion of an irreducible
element, but for the integers Z the two concepts coincide.
119 Chapter 5. Algebra
by a unit. The condition d(r) < d(b) guarantees that the gcd can be computed in the
well-known manner by continuous division. This procedure terminates because d(r)
decreases monotonically in each division step.
The following theorem can be proved in a manner analogous to the proof of the
unique factorization theorem for Z. One step is to show that a Euclidean domain is a
principle ideal domain.
Theorem 5.27. In a Euclidean domain every element can be factored uniquely (up to taking
associates) into irreducible elements.
Example 5.58. Consider the field GF (5) and the polynomial a(x) = 2x3 +3x+1.
Then a(0) = 1, a(1) = 1, a(2) = 3, a(3) = 4, and a(4) = 1.
5.7.2 Roots
Definition 5.33. Let a(x) ∈ R[x]. An element α ∈ R for which a(α) = 0 is called
a root40 of a(x).
Example 5.59. The polynomial x3 − 7x + 6 in R[x] has 3 roots: −3, 1, and 2. The
polynomial x2 + 1 in R[x] has no root. The polynomial (x3 + 2x2 + 5x + 2) in
GF(7)[x] has 2 as its only root. The polynomial (x4 + x3 + x + 1) in GF(2)[x] has
the root 1.
Lemma 5.29. For a field F , α ∈ F is a root of a(x) if and only if x − α divides a(x).
Proof. (=⇒) Assume that α is a root, i.e., a(α) = 0. Then, according to Theo-
rem 5.25, we can write a(x) as
r = a(x) − (x − α)q(x).
Theorem 5.31. For a field F , a nonzero42 polynomial a(x) ∈ F [x] of degree d has at
most d roots.
Proof. To arrive at a contradiction, suppose Qthat a(x) has degree d but e > d
e
roots, say α1 , . . . , αe . Then the polynomial i=1 (x − αi ) divides a(x). Since this
is a polynomial of degree e, a(x) has degree at least e, and hence more than d,
which is a contradiction.
Note that for ui (x) to be well-defined, all constant terms αi − αj in the denomi-
nator must be invertible. This is guaranteed if F is a field since αi − αj 6= 0 for
i 6= j. Note also that the denominator is simply a constant and hence ui (x) is in-
deed a polynomial of degree d. It is easy to verify that ui (αi ) = 1 and ui (αj ) = 0
P
for j 6= i. Thus the polynomials a(x) and d+1 i=1 βi ui (x) agree when evaluated at
any αi , for all i. We note that a(x) has degree at most d.43
It remains to prove the uniqueness. Suppose there is another polynomial
a′ (x) of degree at most d such that βi = a′ (αi ) for i = 1, . . . , d + 1. Then a(x) −
a′ (x) is also a polynomial of degree at most d, which (according to Theorem 5.31)
can have at most d roots, unless it is 0. But a(x) − a′ (x) has indeed the d + 1 roots
α1 , . . . , αd+1 . Thus it must be the 0-polynomial, which implies a(x) = a′ (x).
def
a(x) ≡m(x) b(x) ⇐⇒ m(x) | a(x) − b(x) .
43 The degree can be smaller than d.
5.8. Finite Fields 122
The proof of the following lemma is analogous to the proof that congruence
modulo m is an equivalence relation on Z.
Lemma 5.33. Congruence modulo m(x) is an equivalence relation on F [x], and each
equivalence class has a unique representative of degree less than deg(m(x)).
Example 5.60. Consider R[x] or Q[x]. We have, for example,
5x3 − 2x + 1 ≡3x2 +2 8x3 + 1 ≡3x2 +2 − 16
3 x+1
as one can easily check. Actually, the remainder when 5x3 − 2x + 1 is divided
by 3x2 + 2 is − 16
3 x + 1.
Example 5.61. Consider GF(2)[x]. Example 5.55 can be rephrased as Rx2 +1 (x4 +
x3 + x2 + 1) = x + 1.
def
F [x]m(x) = a(x) ∈ F [x] deg(a(x)) < d .
Proof. We have
F [x]m(x) = ad−1 xd−1 + · · · + a1 x + a0 a0 , . . . , ad−1 ∈ F .
There are q d choices for a0 , . . . , ad−1 .
F [x]m(x) is derived from F [x] in close analogy to how the ring Zm is derived
from the ring Z.
Lemma 5.35. F [x]m(x) is a ring with respect to addition and multiplication mod-
ulo m(x).44
and F [x]m(x) . Each system has an addition and a multiplication operation, and we use the same
symbols “+” and “·” in each case, letting the context decide which one we mean. This should cause
no confusion. The alternative would have been to always use different symbols, but this would
be too cumbersome. Note that, as mentioned above, addition (but not multiplication) in F [x] and
F [x]m(x) are identical.
45 Note that the sum of two polynomials is never reduced modulo m(x) because the degree of the
sum is at most the maximum of the two degrees. In other words, a(x)+ b(x) in F [x] and a(x)+ b(x)
in F [x]m(x) are the same operation when restricted to polynomials of degree less than deg(m(x)).
123 Chapter 5. Algebra
a(x)b(x) ≡m(x) 1
(for a given a(x)) has a solution b(x) ∈ F [x]m(x) if and only if gcd(a(x), m(x)) = 1.
The solution is unique.46 In other words,
F [x]∗m(x) = a(x) ∈ F [x]m(x) gcd(a(x), m(x)) = 1 .
Theorem 5.37. The ring F [x]m(x) is a field if and only if m(x) is irreducible.47
Proof. For an irreducible polynomial m(x), we have gcd(a(x), m(x)) = 1 for all
a(x) 6= 0 with deg(a(x)) < deg(m(x)) and therefore, according to Lemma 5.36,
a(x) is invertible in F [x]m(x) . In other words, F [x]∗m(x) = F [x]m(x) \ {0}. If m(x)
is not irreducible, then F [x]m(x) is not a field because nontrivial factors of m(x)
have no multiplicative inverse.
In Computer Science, the fields of most interest are finite fields, i.e., F [x]m(x)
where F itself is a finite field. But before we discuss finite fields, we illustrate
this new type of field based on polynomial arithmetic using a well-known ex-
ample of an infinite field.
Example 5.62. The polynomial x2 + 1 is irreducible in R[x] because x2 + 1 has no
root in R. Hence, according to Theorem 5.37, R[x]x2 +1 is a field. The elements
of R[x]x2 +1 are the polynomials of degree at most 1, i.e., of the form ax + b.
Addition and multiplication are defined by
and
The last step follows from the fact that Rx2 +1 (x2 ) = −1. The reader may have
noticed already that these addition and multiplication laws correspond to those
of the complex numbers C when ax + b is interpreted as the complex number
b + ai. Indeed, R[x]x2 +1 is simply C or, more precisely, R[x]x2 +1 is isomorphic to
C. In fact, this appears to be the most natural way of defining C.
This example raises a natural question: Can we define other extension fields
of R, or, what is special about C? There are many other irreducible polynomials
of degree 2, namely all those corresponding to a parabola not intersecting with
the x-axis. What is, for example, the field R[x]2x2 +x+1 ? One can show that
R[x]m(x) is isomorphic to C for every irreducible polynomial of degree 2 over
R. Are there irreducible polynomials of higher degree over R? The answer, as
we know, is negative. Every polynomial in R[x] can be factored into a product
of polynomials of degree 1 (corresponding to real roots) and polynomials of
degree 2 (corresponding to pairs of conjugate complex roots). The field C has
the special property that a polynomial of degree d has exactly d roots in C. For
the field R, this is not true. There are no irreducible polynomials of degree > 1
over C.
Note that the “+” in ax + b is in GF(2) (i.e., in Z2 ), and the middle “+” in
(ax + b) + (cx + d) is to be understood in GF(2)[x]x2 +x+1 , i.e., as polynomial
addition. Multiplication is defined by
The last step follows from the fact that Rx2 +x+1 (x2 ) = −x − 1 = x + 1 (since
−1 = 1 in GF(2)). It now becomes clear that this field with 4 elements is that of
Example 5.46. The reader can check that A = x and B = x + 1 works just as well
as A = x + 1 and B = x.
125 Chapter 5. Algebra
+ 0 1 x x+1 x2 x2 + 1 x2 + x x2 + x + 1
0 0 1 x x+1 x2 x2 + 1 x2 + x x2 + x + 1
2
1 0 x+1 x x +1 x2 2
x +x+1 x2 + x
x 0 1 x2 + x 2
x +x+1 x2 x2 + 1
x+1 0 x2 + x + 1 x2 + x 2
x +1 x2
x2 0 1 x x+1
x2 + 1 0 x+1 x
x2 + x 0 1
2
x +x+1 0
Figure 5.2: The addition table for GF(8) constructed with the irreducible poly-
nomial x3 + x + 1.
· 0 1 x x+1 x2 x2 + 1 x2 + x x2 + x + 1
0 0 0 0 0 0 0 0 0
1 1 x x+1 x2 x2 + 1 x2 + x x2 + x + 1
x x2 x2 + x x+1 1 x2 + x + 1 x2 + 1
x+1 x2 + 1 x2 + x + 1 x2 1 x
x2 x2 + x x x2 + 1 1
2
x +1 x2 + x + 1 x+1 x2 + x
x2 + x x x2
x2 + x + 1 x+1
Figure 5.3: The multiplication table for GF(8) constructed with the irreducible
polynomial x3 + x + 1.
(1811–1832).48 In his honor, finite fields are called Galois fields. A field with q elements is
usually denoted by GF(q) (independently of how it is constructed).
Theorem 5.38. For every prime p and every d ≥ 1 there exists an irreducible polynomial of
degree d in GF(p)[x]. In particular, there exists a finite field with pd elements.
The following theorem states that the finite fields we have seen so far, Zp for prime
p and GF(p)[x]m(x) for an irreducible m(x), are all finite fields. There are no other finite
fields. Moreover, one obtains no new finite fields by taking an irreducible polynomial,
′
say of degree d′ , over some extension field GF(pd ), resulting in the field GF(pdd ). Such
a field can always be constructed directly using an irreducible polynomial of degree dd′
over GF(p).
Theorem 5.39. There exists a finite field with q elements if and only if q is a power of a prime.
Moreover, any two finite fields of the same size q are isomorphic.
The last claim justifies the use of the notation GF(q) without making explicit how the
field is constructed. Different constructions yield different representations (naming) of
the field elements, but not different fields. However, it is possible that some representa-
tions are better suited than others for the efficient hardware or software implementation
of the field arithmetic.
Theorem 5.40. The multiplicative group of every finite field GF(q) is cyclic.
Note that the multiplicative group of GF(q) has order q − 1 and has ϕ(q − 1) genera-
tors.
Example 5.65. One can check that the fields GF(22 ) and GF(23 ) have multiplicative
groups of orders 3 and 7, which are both prime. Therefore all elements except 1 (and
0 of course) are generators of the multiplicative group.
general no closed form solution in radicals (while equations of up to fourth degree do). His major
contributions to mathematics were recognized by the leading mathematicians only many years after
his death. He died in a duel at the age of 21. The story goes that he wrote down major parts of his
theory during the last night before the duel.
127 Chapter 5. Algebra
There are two types of problems that can occur in data transmission or when
reading data from a storage medium. First, data can be erased, meaning that
when reading (or receiving) it one realizes that it is missing. Second, data can
contain errors. The second type of problem is more severe because it is not even
known where in a data stream the errors occurred. A good error-correcting
scheme can handle both problems.
Definition 5.36. An (n, k)-error-correcting code over the alphabet A with |A| = q
is a subset of An of cardinality q k .
It is natural to use as the alphabet A = {0, 1}, i.e., to take bits as the basic unit
of information. However, for several reasons (one being the efficiency of encod-
ing and in particular decoding), one often considers larger units of information,
for example bytes (i.e., A = {0, 1}8).
Definition 5.37. The Hamming distance between two strings of equal length over
a finite alphabet A is the number of positions at which the two strings differ.
Example 5.66. The following code is a (5, 2)-code over the alphabet {0, 1}:
5.9.2 Decoding
Theorem 5.41. A code C with minimum distance d is t-error correcting if and only if
d ≥ 2t + 1.
Proof. (⇐=) If any two codewords have Hamming distance at least 2t + 1 (i.e.,
differ in at least 2t+1 positions), then it is impossible that a word (r0 , . . . , rn−1 ) ∈
An could result from two different codewords by changing t positions. Thus if
(r0 , . . . , rn−1 ) has distance at most t from a codeword (c0 , . . . , cn−1 ), then this
codeword is uniquely determined. The decoding function D can be defined to
decode to (one of) the nearest codeword(s) (more precisely, to the information
resulting (by E) in that codeword).
(=⇒) If there are two codewords that differ in at most 2t positions, then there
exists a word (r0 , . . . , rn−1 ) which differs from both codewords in at most t po-
sitions; hence it is possible that t errors can not be corrected.
49 Forexample the list of symbols received after transmission of a codeword over a noisy channel
or read from a storage medium like a CD.
129 Chapter 5. Algebra
Theorem 5.42. Let A = GF(q) and let α0 , . . . , αn−1 be arbitrary distinct elements of
GF(q). Consider the encoding function
E((a0 , . . . , ak−1 )) = a(α0 ), . . . , a(αn−1 ) ,
Proof. The polynomial a(x) of degree k−1 can be interpolated from any k values,
i.e., from any k codeword symbols. If two polynomials agree for k arguments
(or, equivalently, if two codewords agree at k positions), then they are equal.
This means that two different codewords cannot agree at k positions. Hence any
two codewords disagree in at least n − k + 1 positions.
An (n, k)-code over the field GF(2d ) can be interpreted as a binary (dn, dk)-
code (over GF(2)). The minimum distance of this binary code is at least that of
the original code because two different GF(2d )-symbols must differ in at least
one bit (but can of course differ in more than one bit).
Example 5.68. Polynomial codes as described are used for storing information
on Compact Discs. In fact, the coding scheme of CD’s makes use of two different
such codes, but explaining the complete scheme is beyond the scope of this
course on discrete mathematics. The field is GF(28 ) defined by an irreducible
polynomial of degree 8 over GF(2) and the two codes are a (32, 28)-code over
GF(28 ) and a (28, 24)-code over GF(28 ), both with minimum distance 5.
Chapter 6
Logic
6.1 Introduction
In Chapter 2 we have introduced some basic concepts of logic, but the treat-
ment was quite informal. In this chapter we discuss the foundations of logic
in a mathematically rigorous manner. In particular, we clearly distinguish be-
tween the syntax and the semantics of a logic and between syntactic derivations
of formulas and logical consequences they imply. We also introduce the con-
cept of a logical calculus and define soundness and completeness of a calculus.
Moreover, we discuss in detail a concrete calculus for propositional logic, the
so-called resolution calculus.
At a very general level, the goal of logic is to provide a framework for ex-
pressing mathematical statements and for expressing and verifying proofs for
such statements. A more ambitious, secondary goal can be to provide tools for
automatically or semi-automatically generating a proof for a given statement.
A treatment of logic usually begins with a chapter on propositional logic1
(see Section 6.5), followed by a chapter on predicate (or first-order) logic2 (see
Section 6.6), which can be seen as an extension of propositional logic. There are
several other logics which are useful in Computer Science and in mathematics,
including temporal logic, modal logic, intuitionistic logic, and logics for rea-
soning about knowledge and about uncertainty. Most if not all relevant logics
contain the logical operators from propositional logic, i.e., ∧, ∨, ¬ (and the de-
rived operators → and ↔), as well as the quantifiers (∀ and ∃) from predicate
logic.
Our goal is to present the general concepts that apply to all types of log-
ics in a unified manner, and then to discuss the specific instantiations of these
1 German: Aussagenlogik
2 German: Prädikatenlogik
130
131 Chapter 6. Logic
concepts for each logic individually. Therefore we begin with such a general
treatment (see Sections 6.2, 6.3, and 6.4) before discussing propositional and
predicate logic. From a didactic viewpoint, however, it will be useful to switch
back and forth between the generic concepts of Sections 6.2, 6.3, and 6.4 and the
concrete instantiations of Sections 6.5 and 6.6.
We give a general warning: Different treatments of logic often use slightly or
sometimes substantially different notation.3 Even at the conceptual level there
are significant differences. One needs to be prepared to adopt a particular no-
tation used in a particular application context. However, the general principles
explained here are essentially standard.
We also refer to the book by Kreuzer and Kühling and that by Schöning
mentioned in the preface of these lecture notes.
By a statement type we mean for example the class of statements of the form
that a given number n is prime, or the class of statements of the form that a
given graph G has a Hamiltonian cycle (see below), or the class of statements of
the form that a given formula F in propositional logic is satisfiable.
Consider a fixed type of statements. Let S ⊆ Σ∗ be the set of (syntactic
representations of) mathematical statements of this type, and let P ⊆ Σ∗ be the
set of (syntactic representations of) proof strings.4
Every statement s ∈ S is either true or false. The truth function
τ : S → {0, 1}
3 For example, in some treatments the symbol ⇒ is used for →, which can be confusing.
4 Membership in S and also in P is assumed to be efficiently checkable (for some notion of effi-
ciency).
6.2. Proof Systems 132
assigns to each s ∈ S its truth value τ (s). This function τ defines the meaning,
called the semantics, of objects in S.5
An element p ∈ P is either a (valid) proof for a statement s ∈ S, or it is not.
This can be defined via a verification function
φ : S × P → {0, 1},
S = P = {0, 1}∗,
with the understanding that any string in {0, 1}∗ can be interpreted as a state-
ment by defining syntactically wrong statements as being false statements.
5 In the context of logic discussed from the next section onwards, the term semantics is used in a
(PCP). The idea is that the proof can be very long (i.e., exponentially long), but that the verification
only examines a very small random selection of the bits of the proof and nevertheless can decide
correctness, except with very small error probability.
133 Chapter 6. Logic
6.2.2 Examples
Example 6.1. An undirected graph consists of a set V of nodes and a set E of
edges between nodes. Suppose that V = {0, . . . , n − 1}. A graph can then be
described by the so-called adjacency matrix, an n×n-matrix M with {0, 1}-entries,
where Mi,j = 1 if and only if there is an edge between nodes i and j. A graph
with n nodes can hence be represented by a bit-string of length n2 , by reading
out the entries of the matrix row by row.
We are now interested in proving that a given graph has a so-called Hamilto-
nian cycle, i.e., that there is a closed path from node 1 back to node 1, following
edges between nodes, and visiting every node exactly once. We are also inter-
ested in the problem of proving the negation of this statement, i.e., that a given
graph has no Hamiltonian cycle. Deciding whether or not a given graph has a
Hamiltonian cycle is considered a computationally very hard decision problem
(for large graphs).11
To prove that a graph has a Hamiltonian cycle, one can simply provide the
sequence of nodes visited by the cycle. A value in V = {0, . . . , n − 1} can be
represented by a bit-string of length ⌈log2 n⌉, and a sequence of n such numbers
can hence be represented by a bit-string of length n⌈log2 n⌉. We can hence define
S = P = {0, 1}∗.
Now we can let τ be the function defined by τ (s) = 1 if and only if |s| = n2
for some n and the n2 bits of s encode the adjacency matrix of a graph containing
a Hamiltonian cycle. If |s| is not a square or if s encodes a graph without a
Hamiltonian cycle, then τ (s) = 0.12 Moreover, we can let φ be the function
defined by φ(s, p) = 1 if and only if, when s is interpreted as an n × n-matrix
M and when p is interpreted as a sequence of n different numbers (a1 , . . . , an )
with ai ∈ {0, . . . , n − 1} (each encoded by a bit-string of length ⌈log2 n⌉), then
the following is true:
Mai ,ai+1 = 1
for i = 1, . . . , n − 1 and
Man ,a1 = 1.
This function φ is efficiently computable. The proof system is sound because a
graph without Hamiltonian cycle has no proof, and it is complete because every
graph with a Hamiltonian cycle has a proof. Note that each s with τ (s) = 1 has
at least n different proofs because the starting point in the cycle is arbitrary.
Example 6.2. Let us now consider the opposite problem of proving the inex-
istence of a Hamiltonian cycle in a given graph. In other words, in the above
example we define τ (s) = 1 if and only if |s| = n2 for some n and the n2 bits
11 The best known algorithm has running time exponential in n. The problem is actually NP-
complete, a concept that will be discussed in a later course on theoretical Computer Science.
12 Note that τ defines the meaning of the strings in S, namely that they are meant to encode graphs
and that we are interested in whether a given graph has a Hamiltonian cycle.
6.2. Proof Systems 134
Example 6.3. Let again S = P = {0, 1}∗ , and for s ∈ {0, 1}∗ let n(s) de-
note the natural number whose (standard) binary representation is s, with the
convention that leading 0’s are ignored. (For example, n(101011) = 43 and
n(00101) = 5.) Now, let τ be the function defined as follows: τ (s) = 1 if and
only if n(s) is not a prime number. Moreover, let φ be the function defined
by φ(s, p) = 1 if and only if n(s) = 0, or if n(s) = 1, or if n(p) divides n(s) and
1 < n(p) < n(s). This function φ is efficiently computable. This is a proof system
for the non-primality (i.e., compositeness) of natural numbers. It is sound be-
cause every s corresponding to a prime number n(s) has no proof since n(s) 6= 0
and n(s) 6= 1 and n(s) has no divisor d satisfying 1 < d < n(s). The proof sys-
tem is complete because every natural number n greater than 1 is either prime
or has a prime factor q satisfying 1 < q < n (whose binary representation can
serve as a proof).
Example 6.4. Let us consider the opposite problem, i.e., proving primality of
a number n(s) represented by s. In other words, in the previous example we
replace “not a prime” by “a prime”. It is far from clear how one can define a
verification function φ such that the proof system is sound and complete. How-
ever, such an efficiently computable function φ indeed exists. Very briefly, the
proof that a number n(s) (henceforth we simply write n) is prime consists of
(adequate representations of):
1) the list p1 , . . . , pk of distinct prime factors of n − 1,
2) a (recursive) proof of primality for each of p1 , . . . , pk 13
3) a generator g of the group Z∗n .
The exact representation of these three parts of the proof would have to be made
precise, but we omit this here as it is obvious how this could be done.
The verification of a proof (i.e., the computation of the function φ) works as
follows.
required.
135 Chapter 6. Logic
• It is verified that
g n−1 ≡n 1
and, for all i ∈ {1, . . . , k}, that
g (n−1)/pi 6≡n 1.
This proof system for primality is sound because if n is not a prime, then there
is no element of Z∗n of order n − 1 since the order of any element is at most ϕ(n),
which is smaller than n − 1. The proof system is complete because if n is prime,
then GF (n) is a finite field and the multiplicative group of any finite field, i.e.,
Z∗n , is cyclic and has a generator g. (We did not prove this statement in this
course.)15
6.2.3 Discussion
The examples demonstrate the following important points:
• While proof verification must be efficient (in some sense not defined here),
proof generation is generally not (or at least not known to be) efficient. For
example, finding a proof for the Hamiltonian cycle example requires to
find such a cycle, a problem that, as mentioned, is believed to be very
hard. Similarly, finding a primality proof as discussed would require the
factorization of n − 1, and the factoring problem is believed to be hard.
In general, finding a proof (if it exists) is a process requiring insight and
ingenuity, and it cannot be efficiently automated.
• A proof system is always restricted to a certain type of mathematical state-
ment. For example, the proof system of Example 6.1 is very limited in the
sense that it only allows to prove statements of the form “graph G has a
Hamiltonian cycle”.
• Proof verification can in principle proceed in very different ways. The
proof verification method of logic, based on checking a sequence of rule
applications, is (only) a special case.
• Asymmetry of statements and their negation: Even if a proof system exists
for a certain type of statements, it is quite possible that for the negation of
the statements, no proof system (with efficient verification) exists.
15 Actually, a quite efficient deterministic primality test was recently discovered by Agrawal et al.,
and this means that primality can be checked without a proof. In other words, there exists a trivial
proof system for primality with empty proofs. However, this fact is mathematically considerably
more involved than the arguments presented here for the soundness and completeness of the proof
system for primality.
6.3. Elementary General Concepts in Logic 136
6.3.3 Syntax
A logic is defined by the syntax and the semantics. The basic concept in any logic
is that of a formula18 .
Definition 6.4. The syntax of a logic defines an alphabet Λ (of allowed symbols)
and specifies which strings in Λ∗ are formulas (i.e., are syntactically correct).
17 Ina fully computerized system, this must of course be (and indeed is) defined.
18 German: Formel
19 There are logics (not considered here) with more than two truth values, for example a logic with
confidence or belief values indicating the degree of confidence in the truth of a statement.
6.3. Elementary General Concepts in Logic 138
6.3.4 Semantics
Definition 6.5. The semantics of a logic defines (among other things, see below)
a function free which assigns to each formula F = (f1 , f2 , . . . , fk ) ∈ Λ∗ a subset
free(F ) ⊆ {1, . . . , k} of the indices. If i ∈ free(F ), then the symbol fi is said to
occur free in F .20
The same symbol β ∈ Λ can occur free in one place of F (say f3 = β where
3 ∈ free(F )) and not free in another place (say f5 = β where 5 6∈ free(F )).
The free symbols of a formula denote kind of variables which need to be
assigned fixed values in their respective associated domains before the formula
has a truth value. This assignment of values is called an interpretation:
Often (but not in propositional logic), the domains are defined in terms of a
so-called universe U , and the domain for a symbol in Λ can for example be U , or
a function U k → U (for some k), or a function U k → {0, 1} (for some k).
20 The term “free” is not standard in the literature which instead uses special terms for each specific
logic, but as we see later it coincides for the notion of free variables in predicate logic.
21 There may be restrictions for what is an allowed interpretation.
22 German: passend
23 A suitable interpretation can also assign values to symbols β ∈ Λ not occurring free in F .
24 We assume that the set of formulas and the set of interpretations are well-defined.
25 Note that different free occurrences of a symbol β ∈ Λ in F are assigned the same value, namely
ent things, namely for an interpretation as well as for the function induced by the interpretation
which assigns to every formula the truth value (under that interpretation). We nevertheless use the
notation A(F ) instead of σ(F, A) in order to be compatible with most of the literature.
139 Chapter 6. Logic
27 German: erfüllbar
28 Note that the statement that M is satisfiable is not equivalent to the statement that every formula
in M is satisfiable.
29 The symbol ⊥ is not a formula itself, i.e., it is not part of the syntax of a logic, but if used in
30 German: Tautologie
31 German: gültig, allgemeingültig
32 German: (logische) Folgerung, logische Konsequenz
33 The symbol |= is used in two slightly different ways: with a formula (or set of formulas), and
also with an interpretation on the left side. This makes sense because one can consider a set M of
formulas as defining a set of interpretations, namely the set of models for M .
34 More formally, let G be any formula (one of the many equivalent ones) that corresponds to the
Definition 6.16.
A((F ∧ G)) = 1 if and only if A(F ) = 1 and A(G) = 1.
A((F ∨ G)) = 1 if and only if A(F ) = 1 or A(G) = 1.
A(¬F ) = 1 if and only if A(F ) = 0.
Some basic equivalences were already discussed in Section 2.3.2 and are now
stated for any logic that includes the logical operators ∧, ∨, and ¬ :
Proof. The proofs follow directly from Definition 6.16. For example, the claim
35 Alternatively, one could also define → to be a symbol of the syntax, in which case one would
also need to extend the semantics to provide an interpretation for →. This subtle distinction be-
tween notational convention or syntax extension is not really relevant for us. We can simply use the
symbol →.
6.3. Elementary General Concepts in Logic 142
¬(F ∧ G) ≡ ¬F ∨ ¬G follows from the fact that for any suitable interpretation,
we have A(¬(F ∧ G)) = 1 if and only if A(F ∧ G) = 0, and hence if and only if
either A(F ) = 0 or A(G) = 0, i.e., if and only if either A(¬F ) = 1 or A(¬G) = 1,
and hence if and only if A(¬F ∨ ¬G) = 1.
4. Statements about the logic, for example that a certain calculus for the logic
is sound.
To describe the first type of statements, consider a fixed logic, for instance
predicate logic discussed in Section 6.6, and consider a set T of formulas, where
the formulas in T are called the axioms of the theory. Any formula F for which
T |= F
143 Chapter 6. Logic
is called a theorem in theory T . For example, the axioms of group theory are three
formulas in predicate logic, and any theorem in group theory (e.g. Lagrange’s
theorem) is a logical consequence of the axioms.
Consider two theories T and T ′ , where T ′ contains all the axioms of T plus
one or more additional axioms. Then every theorem in T is also a theorem in T ′
(but not vice versa). In the special case where T = ∅, a theorem in T = ∅ is a
tautology in the logic. Tautologies are useful because they are theorems in any
theory, i.e., for any set of axioms.
Example 6.5. The formula ¬∃x∀y P (y, x) ↔ ¬P (y, y) is a tautology in predi-
cate logic, as proved in Section 6.6.9.
As mentioned in Section 6.3.1, the goal of logic is to provide a framework for ex-
pressing and verifying proofs of mathematical statements. A proof of a theorem
should be a purely syntactic derivation consisting of simple and easily verifiable
steps. In each step, a new syntactic object (typically a formula, but it can also be
a more general object involving formulas) is derived by application of a deriva-
tion rule or inference rule, and at the end of the derivation, the desired theorem
appears. The syntactic verification of a proof does not require any intelligence
or “reasoning between the lines”, and it can in particular be performed by a
computer.
Checking a proof hence simply means to execute a program. Like in com-
puter programming, where the execution of a program is a dumb process while
the design of a program is generally an intelligent, sometimes ingenious pro-
cess, the verification of a proof should be a dumb process while devising a proof
is an intelligent, creative, and sometimes ingenious process.
A well-defined set of rules for manipulating formulas (the syntactic objects)
is called a calculus. Many such calculi have been proposed, and they differ in
various ways, for example in the syntax, the semantics, the expressiveness, how
easy or involved it is to write a proof, and how long a proof will be.
When defining a calculus, there is a trade-off between simplicity (e.g. a small
number of rules) and versatility. For a small set of rules, proving even sim-
ple logical steps (like the substitution of a sub-formula by an equivalent sub-
formula) can take a very large number of steps in the calculus.
It is beyond the scope of this course to provide an extensive treatment of
various logical calculi.
6.4. Logical Calculi 144
Definition 6.17. A derivation rule or inference rule36 is a rule for deriving a for-
mula from a set of formulas (called the precondition or premises). We write
{F1 , . . . , Fk } ⊢R G
F1 F2 · · · Fk
(R),
G
where spaces separate the formulas above the bar.
Derivation is a purely syntactic concept. Derivation rules apply to syntac-
tically correct (sets of) formulas. Some derivation rules (e.g. resolution, see
Section 6.5.5) require the formulas to be in a specific format.
Typically such a derivation rule is defined as a rule that involves place-holders
for formulas (such as F and G), which can be instantiated with any concrete
formulas. In order to apply such a rule one must instantiate each place-holder
with a concrete formula.
Example 6.6. Two derivation rules for propositional and predicate logic are
{F ∧ G} ⊢ F and {F, G} ⊢ F ∧ G
36 German: Schlussregel
37 Formally, a derivation rule is a relation from the power set of the set of formulas to the set of
formulas.
145 Chapter 6. Logic
The left rule states that if one has already derived a formula of the form F ∧ G,
where F and G are arbitrary formulas, then one can derive F . The second rule
states that for any two formulas F and G that have been derived, one can also
derive the formula F ∧ G. For example, an application of the right rule yields
{A ∨ B, C ∨ D} ⊢ (A ∨ B) ∧ (C ∨ D),
38 German: Kalkül
39 German: Herleitung
6.4. Logical Calculi 146
Definition 6.21. A derivation rule R is correct if for every set M of formulas and
every formula F , M ⊢R F implies M |= F :
M ⊢R F =⇒ M |= F.
Example 6.7. The two rules of Example 6.6 are correct, but the rule
{F → G, G → F } ⊢ F ∧ G
is not correct. To see this, note that if F and G are both false, then F → G and
G → F are true while F ∧ G is false.
M |= F =⇒ M ⊢K F.
F ⊢ F ∨G F ⊢ G∨F
{F, F → G} ⊢ G {F ∨ G, F → H, G → H} ⊢ H.
Such rules are not necessarily independent. For example, the rule F ∧ G ⊢
G ∧ F could be derived from the above three rules as follows: F can be derived
from F ∧ G and G can also be derived from F ∧ G, resulting in the set {F ∧
G, F, G}. {G, F } is a subset of {F ∧ G, F, G} and hence one of the above rules
yields {G, F } ⊢ G ∧ F .
The last rule discussed above captures case distinction (two cases). It states
that if one knows that F or G is true and that each of them implies H, then we
can conclude H. Such a proof step is in a sense non-constructive because it may
not be known which of F or G is true.
To begin a derivation from the empty set of formulas, one can use any rule
of the form ⊢ F , where F is a tautology. The best-known such rule is
⊢ F ∨ ¬F
called “tertium non datur (TND)” (in English: “there is no third [alternative]”),
which captures the fact that a formula F can only be true or false (in which
case ¬F is true); there is no option in between.42 Another rule for deriving a
tautology is
⊢ ¬(F ↔ ¬F ).
Example 6.8. The following rule can be understood as capturing the principle
of proof by contradiction. (Why?)
{F ∨ G, ¬G} ⊢ F.
Which set of rules constitutes an adequate calculus is generally not clear, but
some calculi have received special attention. One could argue both for a small
set of rules (which are considered the fundamental ones from which everything
else is derived) or for a large library of rules (so there is a large degree of freedom
in finding a short derivation).
F ⊢K G =⇒ |= (F → G).
42 However, in so-called constructive or intuitionistic logic, this rule is not considered correct be-
cause its application does not require explicit knowledge of whether F or ¬F is true.
6.5. Propositional Logic 148
One could therefore also extend the calculus by the new rule
⊢ (F → G),
which is sound. Here F and G can be expressions involving place-holders for
formulas.
Example 6.9. As a toy example, consider the rules ¬¬F ⊢ F and ¬(F ∨G) ⊢ ¬F .
Let H be an arbitrary formula. Using the second rule (and setting F = ¬H) we
can obtain ¬(¬H ∨ G) ⊢ ¬¬H. Thus, using the first rule (and setting F = H) we
can obtain ¬¬H ⊢ H. Hence we have proved ¬(¬H ∨ G) ⊢ H. As usual, this
holds for arbitrary formulas G and H and hence can be understood as a rule.
When stated in the usual form (with place holders F and G, the rule would be
stated as ¬(¬F ∨ G) ⊢ F .
6.5.1 Syntax
6.5.2 Semantics
Recall Definitions 6.5 and 6.6. In propositional logic, the free symbols of a formula
are all the atomic formulas. For example, the truth value of the formula A ∧ B is
determined only after we specify the truth values of A and B. In propositional
logic, an interpretation is called a truth assignment (see below).
F = (A ∧ ¬B) ∨ (B ∧ ¬C)
Theorem 6.4. Every formula is equivalent to a formula in CNF and also to a formula
in DNF.
Given such a formula F , one can use the truth table of F to derive an equiv-
alent formula in DNF, as follows. For every row of the function table evaluating
to 1 one takes the conjunction of the n literals defined as follows: If Ai = 0 in
the row, one takes the literal ¬Ai , otherwise the literal Ai . This conjunction is a
formula whose function table is 1 exactly for the row under consideration (and
0 for all other rows). Then one takes the disjunction of all these conjunctions. F
is true if and only if one of the conjunctions is true, i.e., the truth table of this
formula in DNF is identical to that of F .
Given such a formula F , one can also use the truth table of F to derive an
equivalent formula in CNF, as follows. For every row of the function table eval-
uating to 0 one takes the disjunction of the n literals defined as follows: If Ai = 0
in the row, one takes the literal Ai , otherwise the literal ¬Ai . This disjunction
is a formula whose function table is 0 exactly for the row under consideration
(and 1 for all other rows). Then one takes the conjunction of all these (row-wise)
disjunctions. F is false if and only if all the disjunctions are false, i.e., the truth
table of this formula in CNF is identical to that of F .
Example 6.14. Consider the formula F = (A ∧ ¬B) ∨ (B ∧ ¬C) from above.
The function table is
A B C (A ∧ ¬B) ∨ (B ∧ ¬C)
0 0 0 0
0 0 1 0
0 1 0 1
0 1 1 0
1 0 0 1
1 0 1 1
1 1 0 1
1 1 1 0
We therefore obtain the following DNF
F ≡ (¬A ∧ B ∧ ¬C) ∨ (A ∧ ¬B ∧ ¬C) ∨ (A ∧ ¬B ∧ C) ∨ (A ∧ B ∧ ¬C)
as the disjunction of 4 conjunctions. And we obtain the following CNF
F ≡ (A ∨ B ∨ C) ∧ (A ∨ B ∨ ¬C) ∧ (A ∨ ¬B ∨ ¬C) ∧ (¬A ∨ ¬B ∨ ¬C).
as the conjunction of 4 disjunctions.
Example 6.15. For the formula ¬ (A∧¬B)∨(B∧C) ∨D we derive an equivalent
formula in CNF, using the basic equivalences of Lemma 6.1:
¬ (A ∧ ¬B) ∨ (B ∧ C) ∨ D ≡ ¬(A ∧ ¬B) ∧ ¬(B ∧ C) ∨ D
≡ (¬A ∨ ¬¬B) ∧ (¬B ∨ ¬C) ∨ D
≡ (¬A ∨ B) ∧ (¬B ∨ ¬C) ∨ D
≡ ((¬A ∨ B) ∨ D) ∧ ((¬B ∨ ¬C) ∨ D)
≡ (¬A ∨ B ∨ D) ∧ (¬B ∨ ¬C ∨ D).
In the first step we have used F ∧ G ≡ ¬(¬F ∨ ¬G), which is a direct con-
sequence of rule 8) of Lemma 6.1. In the second step we have applied rule 8)
twice, etc.
Example 6.16. {A, ¬B, ¬D} and {B, C, ¬C, ¬D, E} are clauses, and the empty
set ∅ is also a clause.
The idea behind this definition is that a clause is satisfied by a truth assign-
ment if and only if it contains some literal that evaluates to true. In other words,
a clause stands for the disjunction (OR) of its literals. Likewise, a set K(M ) of
clauses is satisfied by a truth assignment if every clause in K(M ) is satisfied by it.
In other words, a set of clauses stands for the conjunction (AND) of the clauses.
Vk
The set M = {F1 , . . . , Fk } is satisfied if and only if i=1 Fi is satisfied, i.e., if and
only if all clauses in K(M ) are satisfied. Note that the empty clause corresponds to
an unsatisfiable formula and the empty set of clauses corresponds to a tautology.
Note that for a given formula (not necessarily in CNF) there are many equiv-
alent formulas in CNF and hence many equivalent sets of clauses. Conversely,
to a given set K of clauses one can associate many formulas which are, how-
ever, all equivalent. Therefore, one can naturally think of a set of clauses as a
(canonical) formula, and the notions of satisfiability, equivalence, and logical
consequence carry over immediately from formulas to clause sets.
Example 6.17. The clauses {A, ¬B, ¬C} and {¬A, C, D, ¬E} have two resol-
vents: If A is eliminated, we obtain the clause {¬B, ¬C, C, D, ¬E}, and if C
is eliminated, we obtain the clause {A, ¬B, ¬A, D, ¬E}. Note that clauses are
sets and we can write the elements in arbitrary order. In particular, we could
write the latter clause as {A, ¬A, ¬B, D, ¬E}.
It is important to point out that resolution steps must be carried out one by
one; one cannot perform two steps at once. For instance, in the above exam-
ple, {¬B, D, ¬E} is not a resolvent and can also not be obtained by two res-
olution steps, even though {¬B, D, ¬E} would result from {A, ¬B, ¬C} and
{¬A, C, D, ¬E} by eliminating A and ¬C from the first clause and ¬A and C
from the second clause.47
46 For a literal L, ¬L is the negation of L, for example if L = ¬A, then ¬L = A.
47 A simpler example illustrating this is that {{A, B}, {¬A, ¬B}} is satisfiable, but a “double”
resolution step would falsely yield ∅, indicating that {{A, B}, {¬A, ¬B}} is unsatisfiable.
6.5. Propositional Logic 154
{K1 , K2 } ⊢res K,
where equation (6.1) must be satisfied. The resolution calculus, denoted Res,
consists of a single rule:
Res = {res}.
Recall that we write K ⊢Res K if K can be derived from K using a finite num-
ber of resolution steps.49
Lemma 6.5. The resolution calculus is sound, i.e., if K ⊢Res K then K |= K.50
Proof. We only need to show that the resolution rule is correct, i.e., that if K is a
resolvent of clauses K1 , K2 ∈ K, then K is logical consequence of {K1 , K2 }, i.e.,
Let A be an arbitrary truth assignment suitable for {K1 , K2 } (and hence also for
K). Recall that A is a model for {K1 , K2 } if and only if A makes at least one
literal in K1 true and also makes at least one literal in K2 true.
We refer to Definition 6.30 and distinguish two cases. If A(L) = 1, then
A makes at least one literal in K2 \ {¬L} true (since ¬L is false). Similarly, if
A(L) = 0, then A makes at least one literal in K1 \ {L} true (since L is false).
Because one of the two cases occurs, A makes at least one literal in K = (K1 \
{L}) ∪ (K2 \ {¬L}) true, which means that A is a model for K.
Proof. The “if” part (soundness) follows from Lemma 6.5: If K(M ) ⊢Res ∅,
then K(M ) |= ∅, i.e., every model for K(M ) is a model for ∅. Since ∅ has no
model, K(M ) also does not have a model. This means that K(M ) is unsatisfiable.
48 In the literature, one usually does not use the symbol ⊢ in the context of resolution.
49 In the lecture we introduce a natural graphical notation for writing a sequence of resolution
steps.
50 For convenience, the clause K is understood to mean the singleton clause set {K}. In other
words, the truth value of a clause K is understood to be the same the truth value of {K}.
155 Chapter 6. Logic
It remains to prove the “only if” part (completeness with respect to unsatis-
fiability). We need to show that if a clause set K is unsatisfiable, then ∅ can be
derived by some sequence of resolution steps. The proof is by induction over
the number n of atomic formulas appearing in K. The induction basis (for n = 1)
is as follows. A clause set K involving only literals A1 and ¬A1 is unsatisfiable
if and only if it contains the clauses {A1 } and {¬A1 }. One can derive ∅ exactly
if this is the case.
For the induction step, suppose that for every clause set K′ with n atomic
formulas, K′ is unsatisfiable if and only if K′ ⊢Res ∅. Given an arbitrary
clause set K for the atomic formulas A1 , . . . , An+1 , define the two clause sets K0
and K1 as follows. K0 is the clause set for atomic formulas A1 , . . . , An obtained
from K by setting An+1 = 0, i.e.,
• by eliminating all clauses from K containing ¬An+1 (which are satisfied
since ¬An+1 = 1), and
• by eliminating from each remaining clause the literal An+1 if it appears in
it (since having An+1 in it can not contribute to the clause being satisfied).
6.6.1 Syntax
Definition 6.31. (Syntax of predicate logic.)
• A variable symbol is of the form xi with i ∈ N.51
(k)
• A function symbol is of the form fi with i, k ∈ N, where k denotes the
number of arguments of the function. Function symbols for k = 0 are
called constants.
(k)
• A predicate symbol is of the form Pi with i, k ∈ N, where k denotes the
number of arguments of the predicate.
• A term is defined inductively: A variable is a term, and if t1 , . . . , tk are
(k)
terms, then fi (t1 , . . . , tk ) is a term. For k = 0 one writes no parentheses.
• A formula is defined inductively:
(k)
– For any i and k, if t1 , . . . , tk are terms, then Pi (t1 , . . . , tk ) is a for-
mula, called an atomic formula.
– If F and G are formulas, then ¬F , (F ∧ G), and (F ∨ G) are formulas.
– If F is a formula, then, for any i, ∀xi F and ∃xi F are formulas.
Note that the same variable can occur bound and free in a formula. One can
draw the construction tree (see lecture) of a formula showing how a formula is
constructed according to the rules of Definition 6.31. Within the subtree corre-
sponding to ∀x or ∃x, all occurrences of x are bound.
Example 6.18. In the formula
F = Q(x) ∨ ∀y P (f (x, y)) ∧ ∃x R(x, y) ,
the first two occurrences of x are free, the other occurrences are bound. The last
occurrence of y is free, the other occurrences are bound.
Definition 6.33. For a formula F , a variable x and a term t, F [x/t] denotes the
formula obtained from F by substituting every free occurrence of x by t.
6.6.3 Semantics
Recall Definitions 6.5 and 6.6. In predicate logic, the free symbols of a formula are all
predicate symbols, all function symbols, and all occurrences of free variables. An inter-
pretation, called structure in the context of predicate logic, must hence define a
universe and the meaning of all these free symbols.
This definition defines the function σ(F, A) of Definition 6.8. Note that the
definition is recursive not only on formulas (see the second bullet of the defini-
159 Chapter 6. Logic
tion), but also on structures. Namely, A(∀x G) and A(∃x G) are defined in terms
of all structures A[x→u] (G) for u ∈ U . To evaluate the truth value of a formula
F = ∀x G one needs to apply Definition 6.36 recursively, for formula G and all
structures A[x→u] .
The basic concepts discussed in Section 6.3 such as satisfiable, tautology,
model, logical consequence, and equivalence, are now immediately instantiated
for predicate logic.
Note that the syntax of predicate logic does not require nested quantified
variables in a formula to be distinct, but we will avoid such overload of variable
names to avoid any confusion. For example, the formula ∀x (P (x) ∨ ∃y Q(y)) is
equivalent to ∀x (P (x) ∨ ∃x Q(x)).
Lemma 6.7. For any formulas F , G, and H, where x does not occur free in H, we have
1) ¬(∀x F ) ≡ ∃x ¬F ;
2) ¬(∃x F ) ≡ ∀x ¬F ;
3) (∀x F ) ∧ (∀x G) ≡ ∀x (F ∧ G);
4) (∃x F ) ∨ (∃x G) ≡ ∃x (F ∨ G);
5) ∀x ∀y F ≡ ∀y ∀x F ;
6) ∃x ∃y F ≡ ∃y ∃x F ;
7) (∀x F ) ∧ H ≡ ∀x (F ∧ H);
8) (∀x F ) ∨ H ≡ ∀x (F ∨ H);
9) (∃x F ) ∧ H ≡ ∃x (F ∧ H);
10) (∃x F ) ∨ H ≡ ∃x (F ∨ H).
Proof. We only prove statement 7). The other proofs are analogous.
We have to show that every structure A that is a model for (∀x F ) ∧ H is
also a model for ∀x (F ∧ H), and vice versa.
6.6. Predicate Logic (First-order Logic) 160
Therefore ∀x G is true for exactly the same structures for which ∀y G[x/y] is
true.
54 according to the semantics of ∧, see Definition 6.36
161 Chapter 6. Logic
Example 6.22. The formula ∀x ∃y (P (x, f (y)) ∨ Q(g(x), a)) is equivalent to the
formula ∀u ∃v (P (u, f (v)) ∨ Q(g(u), a)) obtained by substituting x by u and y
by v.
Q1 x1 Q2 x2 · · · Qn xn G,
Theorem 6.10. For every formula there is an equivalent formula in prenex form.
Proof. One first transforms the formula into an equivalent formula in rectified
form and then applies the equivalences of Lemma 6.7 move up all quantifiers in
the formula tree, resulting in a prenex form of the formula.
Example 6.23.
¬ ∀x P (x, y) ∧ ∃y Q(x, y, z) ≡ ¬ ∀u P (u, y) ∧ ∃v Q(x, v, z)
≡ ¬∀u P (u, y) ∨ ¬∃v Q(x, v, z)
(1)
≡ ∃u ¬P (u, y) ∨ ¬∃v Q(x, v, z)
(2)
≡ ∃u ¬P (u, y) ∨ ∀v ¬ Q(x, v, z)
(10)
≡ ∃u ¬P (u, y) ∨ ∀v ¬ Q(x, v, z)
≡ ∃u ∀v ¬ Q(x, v, z) ∨ ¬P (u, y)
55 German: bereinigt
56 German: Pränexform
6.6. Predicate Logic (First-order Logic) 162
(8)
≡ ∃u ∀v ¬Q(x, v, z) ∨ ¬P (u, y)
≡ ∃u ∀v ¬Q(x, v, z) ∨ ¬P (u, y)
≡ ∃u ∀v ¬P (u, y) ∨ ¬ Q(x, v, z) .
In the first step we have renamed the bound variables, in the second step we
made use of the equivalence ¬(F ∧ G) ≡ ¬F ∨ ¬G (Lemma 6.1 8)), and then we
have applied the rules of Lemma 6.7, as indicated. We have also made explicit
the use of the commutative law for ∨ (Lemma 6.1 2)). In the second last step,
the removal of parentheses is made explicit. The last step, again making use
of Lemma 6.1 2), is included (only) to arrive at a form with the same order of
occurrence of P and Q.
One can also transform every formula F into a formula G in prenex form that
only contains universal quantifiers (∀). However, such a formula is in general
not equivalent to F , but only equivalent with respect to satisfiability. In other
words, F is satisfiable if and only if G is satisfiable. Such a normal form is called
Skolem normal form. This topic is beyond the scope of this course.
∀xF ⊢ F [x/t]
∀xF |= F [x/t].
Theorem 6.12. ¬∃x∀y P (y, x) ↔ ¬P (y, y) .
where we have made use of ¬(F ↔ ¬G) ≡ (F ↔ G), which is easily checked
to hold by comparing the truth tables of ¬(A ↔ ¬B) and (A ↔ B)
To see that the latter formula (i.e., ∀x ∃y P (y, x) ↔ P (y, y) ) is a tautology,
let A be an arbitrary suitable interpretation, which defines the universe U A and
the predicate P A . Below we omit the superscripts A and write simply U and P .
Since A is arbitrary, it suffices to show that
A(∀x ∃y P (y, x) ↔ P (y, y) ) = 1.
as was to be shown.
Let us now interpret Theorem 6.12. We can instantiate it for different uni-
verses and predicates. The first interpretation is Russel’s paradox:
Corollary 6.13. There exists no set that contains all sets S that do not contain them-
selves, i.e., {S| S 6∈ S} is not a set.
6.6. Predicate Logic (First-order Logic) 164
Proof. We consider the universe of all sets58 and, to be consistent with the chap-
ter on set theory, use the variable names R instead of x and S instead of y.59
Moreover, we consider the specific predicate P defined as P (S, R) = 1 if and
only if S ∈ R. Then Theorem 6.12 specializes to
¬∃R ∀S S ∈ R ↔ S 6∈ S .
This formula states that there is no set R such that for a set (say S) to be in R is
equivalent to not being contained in itself (S 6∈ S).
Example 6.24. The reader can investigate as an exercise that Theorem 6.12 also
explains the so-called barber paradox (e.g. see Wikipedia) which considers a
town with a single barber as well as the set of men that do not shave themselves.
Note that the proof of this corollary contains Cantor’s diagonalization argu-
ment, which is hence implicite in Theorem 6.12.
We discuss a further use of the theorem. If we understand a program as de-
scribable by a finite bit-string, or, equivalently, a natural number (since there is
a bijection between finite bit-strings and natural numbers), and if we consider
programs that take a natural number as input and output 0 or 1, then we ob-
tain the following theorem. (Here we ignore programs that do not halt (i.e.,
58 The universe of all sets is not a set itself. Formally, the universe in predicate logic need not be a
with the chapter on set theory where sets were denoted by capital letters and Russel’s proposed set
was called R. Here we have deviated from the convention to use only small letters for variables.
165 Chapter 6. Logic
loop forever), or, equivalently, we interpret looping as output 0.) The following
corollary was already stated as Corollary 3.24.60
Corollary 6.15. There are uncomputable functions N → {0, 1}.
We point out that the corollary does not exclude the existence of a program
that computes the function for an overwhelming fraction of the y, it excludes
only the existence of a program that computes the function for all but finitely
many arguments.
a given input, would require a more general theorem than Theorem 6.12, but it could be explained
in the same spirit.
61 This function of course depends on the concrete programming language which determines the
In this formula, y and z can depend on both w and x. It is not possible to express, as a
formula in predicate logic, that in the above formula, y must only depend on w and z
must only depend on x. This appears to be an artificial restriction that is not desirable.