文档介绍：G¨odel’sTheorems
and Theories of Arithmetic
Peter Smith
Faculty of Philosophy
University of Cambridge
Version date: August 21, 2004
Copyright:
c 2004 Peter Smith
Not to be cited or quoted without permission
The book’s website is at
Contents
Preface v
Part I Introducing pleteness 1
1 What G¨odel’sFirst Theorem Says 3
pleteness and basic arithmetic 3
Why it matters 5
What’s next? 7
2 The Idea of an Axiomatized Formal Theory 8
Formalization as an ideal 8
Formal axiomatized theories 10
Decidability 13
Enumerable sets 15
More definitions 17
Three simple results 19
plete theories are decidable 20
3 Capturing Numerical Properties 22
Remarks on notation 22
Standard arithmetical languages 23
Expressing numerical properties and relations 25
Case-by-case capturing 26
A note on our jargon 28
4 Sufficiently Strong Arithmetics 29
The idea of a ‘sufficiently strong’ theory 29
An undecidability theorem 30
An pleteness theorem 31
But what have we really shown? 33
Part II Arithmetics and Primitive Recursion 35
5 Four Formalized Arithmetics 37
BA – Baby Arithmetic 37
Q – Robinson Arithmetic 40
i
Contents
Capturing properties and relations in Q 43
An aside: introducing ‘<’ and ‘≤’ into Q 44
Induction and the Induction Schema 44
IO – Arithmetic with induction for quantifier-free formulae 46
PA – First-order Peano Arithmetic 47
Is PA Consistent? 49
More theories 51
6 Primitive Recursive Functions 52
Introducing . functions 52
Defining the . functions more carefully 53
The . functions putable 55
Not putable functions are . 56
The idea of . adequacy 58
7 More on Functions, Properties and Relations 60
Extensionality 60
Characteristic functions 61
Capturing functions 62
‘Capturing as a function’ 63
8 . Adequate Arithmetics 65
The