Mathematical Logic A First Course

Suitable for advanced undergraduates and graduate students, this self-contained text will appeal to readers from diverse fields and varying backgrounds including mathematics, philosophy, linguistics, computer science, and engineering. Topics include 1st-order recursive arithmetic, 1st- and 2nd-order logic, and the arithmetization of syntax. Numerous exercises; some solutions. 1969 edition.

PREFACE

v

NOTE TO THE STUDENT

xi

Chapter 1 The Propositional Calculus

1

(31)

§1 Formation Rules for P

4

(4)

§2 Formal Semantics of P

8

(6)

§3 Axiomatization of P

14

(2)

§4 The Deduction Theorem

16

(4)

§5 Some Theorem Schemas of P

20

(2)

§6 Completeness

22

(10)

Chapter 2 First-Order Logic

32

(34)

§7 Formation Rules for L( , X)

34

(3)

§8 Free and Bound Variables

37

(1)

§9 Models

38

(3)

§10 Validity

41

(2)

§11 Axiomatization of L( , X)

43

(1)

§12 Propositional Calculus

44

(1)

§13 The Deduction Theorem

45

(3)

§14 Some Theorems of First-Order Logic

48

(2)

§15 The Soundness Theorem

50

(2)

§16 The Extension Lemma

52

(2)

§17 The Completeness Theorem

54

(2)

§18 First-Order Logic with Equality

56

(10)

Chapter 3 First-Order Recursive Arithmetic

66

(24)

§19 Primitive Recursive Functions

66

(3)

§20 Some Primitive Recursive Functions

69

(3)

§21 Formation Rules for RA

72

(4)

§22 Semantics

76

(2)

§23 Axiomatics

78

(2)

§24 Soundness

80

(1)

§25 Sentences without Variables

81

(9)

Chapter 4 Arithmetization of Syntax

90

(21)

§26 Finite Sums and Products

90

(1)

§27 Primitive Recursive Relations

91

(3)

§28 Definition by Cases and the Least Number Operator

94

(2)

§29 Prime Numbers

96

(3)

§30 Primitive Recursiveness of the Prime Decomposition

99

(1)

§31 Gödel Numbers

100

(3)

§32 Primitive Recursiveness of the Notion of Function Constant

103

(2)

§33 Primitive Recursiveness of the Notion of Term

105

(1)

§34 Primitive Recursiveness of the Notion of Wff

106

(1)

§35 Substitution

107

(2)

§36 Deductions

109

(2)

Chapter 5 The Incompleteness Theorems and Other Applications of the Liar Paradox

111

(21)

§37 The First Gödel Incompleteness Theorem

112

(4)

§38 Proof of the First Gödel Theorem in RA

116

(1)

§39 The Second Gödel Incompleteness Theorem

117

(2)

§40 Tarski's Theorem

119

(2)

§41 Arithmetical Sets

121

(1)

§42 Recursive Sets and Decision Procedures

122

(4)

§43 Church's Theorem for RA

126

(6)

Chapter 6 Second-Order Logic

132

(39)

§44 Formation Rules for L( , X)

133

(1)

§45 Axiomatics for L2( , X)

134

(3)

§46 Semantics of Second-Order Logic

137

(3)

§47 The Completeness Theorem for Second-Order Logic

140

(2)

§48 Equality

142

(3)

§49 Second-Order Peano Arithmetic

145

(3)

§50 Primitive Recursive Functions

148

(5)

§51 Numeralwise Representability

153

(3)

§52 Gödel's Theorem for PA2

156

(2)

§53 Church's Theorem for Second-Order Logic

158

(3)

§54 Categoricity of PA2

161

(3)

§55 Skolem's Paradox

164

(2)

§56 Formal Set Theory

166

(5)

Appendix

171

(12)

§A1 Sets and Functions

171

(4)

§A2 Induction

175

(3)

§A3 Primitive Recursion

178

(2)

§A4 Countable Sets

180

(3)

ANSWERS TO SELECTED EXERCISES

183

(16)

FREE SHIPPING

Amazon no longer offers textbook rentals. We do!

Mathematical Logic A First Course

Summary

Table of Contents

Supplemental Materials