Metalogic: An Introduction to the Metatheory of Standard First Order Logic

Title ......Page 1
Copyright ......Page 2
Dedication ......Page 3
Contents ......Page 5
Preface ......Page 9
Part One: Introduction: General Notions ......Page 13
1 Formal languages ......Page 16
2 Interpretations of formal languages. Model theory ......Page 18
3 Deductive apparatuses. Formal systems. Proof theory ......Page 19
4 \'Syntactic\', \'Semantic\' ......Page 21
6 Using and mentioning. Object language and metalanguage. Proofs in a formal system and proofs about a formal  system. Theorem and metatheorem ......Page 22
7 The notion of effective method in logic and mathematics ......Page 25
9 1-1 correspondence. Having the same cardinal number as. Having a greater (or smaller) cardinal number than ......Page 28
10 Finite sets. Denumerable sets. Countable sets. Uncountable sets ......Page 29
11 Proof of the uncountability of the set of all subsets of the set of natural numbers ......Page 33
12 Sequences. Enumerations. Effective enumerations ......Page 37
13 Some theorems about infinite sets ......Page 38
14 Informal proof of the incompleteness of any finitary formal system of the full theory of the natural numbers ......Page 40
Appendix 1: Intuitive theory of infinite sets and transfinite cardinal numbers ......Page 42
Part Two: Truth-functional Propositional Logic ......Page 55
15 Functions ......Page 58
16 Truth functions ......Page 60
17 A formal language for truth-functional propositional logic: the formal language P ......Page 66
18 Conventions: 1. About quotation marks 2. About dropping brackets ......Page 68
19 Semantics for P. Definitions of interpretation of P, true/false for an interpretation of P, model of a  formula/set of formulas of P, logically valid formula of P, model-theoretically consistent formula/set of  formulas of P, semantic consequence (for formulas of P), tautology of P ......Page 69
20 Some truths about |-P. The Interpolation Theorem for P ......Page 73
21 P\'s powers of expression. Adequate sets of connectives ......Page 74
22 A deductive apparatus for P: the formal system PS. Definitions of proof in PS, theorem of PS, derivation in  PS, syntactic consequence in PS, proof theoretically consistent set of PS ......Page 83
23 Some truths about |-PS ......Page 89
24 Concepts of consistency ......Page 90
25 Proof of the consistency of PS ......Page 91
26 The Deduction Theorem for PS ......Page 96
27 Note on proofs by mathematical induction ......Page 100
28 Some model-theoretic metatheorems about PS ......Page 103
29 Concepts of semantic completeness. Importance for logic of a proof of the adequacy and semantic completeness  of a formal system of truth-functional propositional logic ......Page 104
30 Outline of Post\'s proof of the semantic completeness of a formal system of truth-functional propositional  logic ......Page 107
31 Proof of the semantic completeness of PS by Kalmar\'s method ......Page 108
32 Proof of the semantic completeness of PS by Henkin\'s method ......Page 117
33 Concepts of syntactic completeness. Proof of the syntactic completeness (in one sense) of PS ......Page 128
34 Proof of the decidability of PS. Decidable system and decidable formula. Definition of effective proof  procedure ......Page 130
35 Extended sense of \'interpretation of P\'. Finite weak models and finite strong models ......Page 132
36 Proof of the independence of the three axiom-schemata of PS ......Page 134
37 Anderson and Belnap\'s formalisation of truth-functional propositional logic: the system AB ......Page 137
Part Three: First Order Predicate Logic: Consistency and Completeness ......Page 147
38 A formal language for first order predicate logic: the language Q. The languages Q+ ......Page 149
39 Semantics for Q (and Q+). Definitions of interpretation of Q (Q+), satisfaction of a formula by a  denumerable sequence of objects, satisfiable, simultaneously satisfiable, true for an interpretation of Q (Q-),  model of a formula/set of formulas of Q (Q+), logically valid formula of Q (Q+), semantic consequence (for  formulas of Q (Q+)), k-validity ......Page 153
40 Some model-theoretic metatheorems for Q (and Q+) ......Page 164
41 A deductive apparatus for Q: the formal system QS. Definitions of proof in QS, theorem of QS, derivation in  QS, syntactic consequence in QS, [proof theoretically] consistent set of QS ......Page 178
42 Proof of the consistency of QS ......Page 180
43 Some metatheorems about QS ......Page 182
44 First order theories ......Page 185
45 Some metatheorems about arbitrary first order theories. Negation-completeness. Closed first order theories.  The Lowenheim-Skolem Theorem. The Compactness Theorem ......Page 186
46 Proof of the semantic completeness of QS ......Page 207
47 A formal system of first order predicate logic with identity: the system QS-. Proof of the consistency of  QS=. Normal models. Proof of the adequacy of QS- ......Page 208
48 Isomorphismof models. Categoricity. Non-standard models ......Page 213
49 Philosophical implications of some of these results ......Page 217
50 A formal system of first order monadic predicate logic: the system QSM. Proofs of its consistency, semantic  completeness and decidability ......Page 220
Part Four: First Order Predicate Logic: Undecidability ......Page 229
51 Some results about undecidability ......Page 231
52 Church\'s Thesis (1935). Church\'s Theorem (1936) ......Page 242
53 Recursive functions. Recursive sets ......Page 244
54 Representation, strong representation and definability of functions in a formal system ......Page 246
55 A formal system of arithmetic: the system H ......Page 248
56 Proof of the undecidability of H ......Page 251
57 Proof of the undecidability of QS=. The undecidability of QS ......Page 261
58 Decidable subclasses of logically valid formulas of Q. Prenex normal form. Skolem normal form. Two negative  results ......Page 263
59 Odds and ends: 1. Logical validity and the empty domain. 2. Omega-inconsistency and omega-incompleteness. 3.  Godel\'s theorems. 4. The Axiom of Choice. 5. Recursively enumerable sets ......Page 267
Appendix 2: Synopsis of basic metatheoretical results for first order theories ......Page 271
References ......Page 274
Index ......Page 287