Foundations of Mathematics - (Malestrom), engineering
[ Pobierz całość w formacie PDF ]
Copyright
c
1995–2007 by Stephen G. Simpson
Foundations of Mathematics
Stephen G. Simpson
October 16, 2008
Department of Mathematics
The Pennsylvania State University
University Park, State College PA 16802
simpson@math.psu.edu
This is a set of lecture notes for my course, Foundations of Mathematics I,
offered as Mathematics 558 at the Pennsylvania State University, most recently
in Spring 2007.
1
Contents
1 Computable Functions 6
1.1 Primitive Recursive Functions . . . . . . . . . . . . . . . . . . . . 6
1.2 The Ackermann Function . . . . . . . . . . . . . . . . . . . . . . 13
1.3 Computable Functions . . . . . . . . . . . . . . . . . . . . . . . . 17
1.4 Partial Recursive Functions . . . . . . . . . . . . . . . . . . . . . 23
1.5 The Enumeration Theorem . . . . . . . . . . . . . . . . . . . . . 25
1.6 Consequences of the Enumeration Theorem . . . . . . . . . . . . 30
1.7 Unsolvable Problems . . . . . . . . . . . . . . . . . . . . . . . . . 34
1.8 The Recursion Theorem . . . . . . . . . . . . . . . . . . . . . . . 39
1.9 The Arithmetical Hierarchy . . . . . . . . . . . . . . . . . . . . . 41
2 Undecidability of Arithmetic 48
2.1 Terms, Formulas, and Sentences . . . . . . . . . . . . . . . . . . . 48
2.2 Arithmetical Definability . . . . . . . . . . . . . . . . . . . . . . . 50
2.3 Godel Numbers of Formulas . . . . . . . . . . . . . . . . . . . . . 57
3 The Real Number System 60
3.1 Quantifier Elimination . . . . . . . . . . . . . . . . . . . . . . . . 60
3.2 Decidability of the Real Number System . . . . . . . . . . . . . . 66
4 Informal Set Theory 69
4.1 Operations on Sets . . . . . . . . . . . . . . . . . . . . . . . . . . 69
4.2 Cardinal Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . 71
4.3 WellOrderings and Ordinal Numbers . . . . . . . . . . . . . . . 74
4.4 Transfinite Recursion . . . . . . . . . . . . . . . . . . . . . . . . . 78
4.5 Cardinal Numbers, Continued . . . . . . . . . . . . . . . . . . . . 81
4.6 Cardinal Arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . 83
4.7 Some Classes of Cardinals . . . . . . . . . . . . . . . . . . . . . . 85
4.8 Pure WellFounded Sets . . . . . . . . . . . . . . . . . . . . . . . 87
4.9 SetTheoretic Foundations . . . . . . . . . . . . . . . . . . . . . . 88
5 Axiomatic Set Theory 92
5.1 The Axioms of Set Theory . . . . . . . . . . . . . . . . . . . . . . 92
5.2 Models of Set Theory . . . . . . . . . . . . . . . . . . . . . . . . 96
2
5.3 Transitive Models and Inaccessible Cardinals . . . . . . . . . . . 99
5.4 Constructible Sets . . . . . . . . . . . . . . . . . . . . . . . . . . 103
5.5 Forcing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
5.6 Independence of CH . . . . . . . . . . . . . . . . . . . . . . . . . 111
6 Topics in Set Theory 114
6.1 Stationary Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
6.2 Large Cardinals . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
6.3 Ultrafilters and Ultraproducts . . . . . . . . . . . . . . . . . . . . 116
6.4 Measurable Cardinals . . . . . . . . . . . . . . . . . . . . . . . . 119
6.5 Ramsey’s Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . 119
3
List of Figures
1.1 Register Machine Instructions . . . . . . . . . . . . . . . . . . . . 18
1.2 An Addition Program . . . . . . . . . . . . . . . . . . . . . . . . 18
1.3 The Initial Functions . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.4 Generalized Composition . . . . . . . . . . . . . . . . . . . . . . 20
1.5 A Multiplication Program . . . . . . . . . . . . . . . . . . . . . . 21
1.6 Primitive Recursion . . . . . . . . . . . . . . . . . . . . . . . . . 22
1.7 Minimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
1.8 A Program with Labeled Instructions . . . . . . . . . . . . . . . 27
1.9 Incrementing P
i
. . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
1.10 Decrementing P
i
. . . . . . . . . . . . . . . . . . . . . . . . . . . 31
1.11 Stopping . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
1.12 Parametrization . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
4
List of Tables
1.1 The Ackermann branches. . . . . . . . . . . . . . . . . . . . . . . 14
5
[ Pobierz całość w formacie PDF ]