Classical mathematical logic : the semantic foundations of logic

Cover
Title Page
Copyright Page
Table of Contents
Preface
Acknowledgments
Introduction
I. Classical Propositional Logic
	A. Propositions
		Other views of propositions
	B. Types
		• Exercises for Sections A and B
	C. The Connectives of Propositional Logic
		• Exercises for Section C
	D. A Formal Language for Propositional Logic
		1. Defining the formal language
			A platonist definition of the formal language
		2. The unique readability of wffs
		3. Realizations
		• Exercises for Section D
	E. Classical Propositional Logic
		1. The classical abstraction and truth-functions
		2. Models
		• Exercises for Sections E.1 and E.2
		3. Validity and semantic consequence
		• Exercises for Section E.3
	F. Formalizing Reasoning
		• Exercises for Section F
	Proof by induction
II. Abstracting and Axiomatizing Classical Propositional Logic
	A. The Fully General Abstraction
		Platonists on the abstraction of models
	B. A Mathematical Presentation of PC
		1. Models and the semantic consequence relation
		• Exercises for Sections A and B.1
		2. The choice of language for PC
		Normal forms
		3. The decidability of tautologies
		• E Exercises for Sections B.2 and B.3
	C. Formalizing the Notion of Proof
		1. Reasons for formalizing
		2. Proof, syntactic consequence, and theories
		3. Soundness and completeness
		• E Exercises for Section C
	D. An Axiomatization of PC
		1. The axiom system
		• E Exercises for Section D.1
		2. A completeness proof
		• E Exercises for Section D.2
		3. Independent axiom systems
		4. Derived rules and substitution
		5. An axiomatization of PC in L(Ø, ®, Ù, Ú)
		• E Exercises for Sections D.3–D.5
		A constructive proof of completeness for PC
III. The Language of Predicate Logic
	A. Things, the World, and Propositions
	B. Names and Predicates
	C. Propositional Connectives
	D. Variables and Quantifiers
	E. Compound Predicates and Quantifiers
	F. The Grammar of Predicate Logic
		• Exercises for Sections A–F
	G. A Formal Language for Predicate Logic
	H. The Structure of the Formal Language
	I. Free and Bound Variables
	J. The Formal Language and Propositions
		• Exercises for Sections G–J
IV. The Semantics of Classical Predicate Logic
	A. Names
	B. Predicates
		1. A predicate applies to an object
		2. Predications involving relations
		The platonist conception of predicates and predications
		• Exercises for Sections A and B
	C. The Universe of a Realization
	D. The Self-Reference Exclusion Principle
		• Exercises for Sections C and D
	E. Models
		1. The assumptions of the realization
		2. Interpretations
		3. The Fregean assumption and the division of form and content
		4. The truth-value of a compound proposition: discussion
		5. Truth in a model
		6. The relation between \" and $
	F. Validity and Semantic Consequence
		• E Exercises for Sections E and F
	Summary: The definition of a model
V. Substitutions and Equivalences
	A. Evaluating Quantifications
		1. Superfluous quantifiers
		2. Substitution of terms
		3. The extensionality of predications
		• Exercises for Section A
	B. Propositional Logic within Predicate Logic
		• Exercises for Section B
	C. Distribution of Quantifiers
		• Exercises for Section C
		Prenex normal forms
	D. Names and Quantifiers
	E. The Partial Interpretation Theorem
		• Exercises for Sections D and E
VI. Equality
	A. The Equality Predicate
	B. The Interpretation of ‘=’ in a Model
	C. The Identity of Indiscernibles
	D. Equivalence Relations
	• Exercises for Chapter VI
VII. Examples of Formalization
	A. Relative Quantification
	B. Adverbs, Tenses, and Locations
	C. Qualities, Collections, and Mass Terms
	D. Finite Quantifiers
	E. Examples from Mathematics
	• Exercises for Chapter VII
VIII. Functions
	A. Functions and Things
	B. A Formal Language with Function Symbols and Equality
	C. Realizations and Truth in a Model
	D. Examples of Formalization
		• Exercises for Sections A–D
	E. Translating Functions into Predicates
		• Exercises for Section E
IX. The Abstraction of Models
	A. The Extension of a Predicate
		• Exercises for Section A
	B. Collections as Objects: Naive Set Theory
		• Exercises for Section B
	C. Classical Mathematical Models
		• Exercises for Section C
X. Axiomatizing Classical Predicate Logic
	A. An Axiomatization of Classical Predicate Logic
		1. The axiom system
		2. Some syntactic observations
		3. Completeness of the axiomatization
		4. Completeness for simpler languages
			a. Languages with name symbols
			b. Languages without name symbols
			c. Languages without aa
		5. Validity and mathematical validity
		• Exercises for Section A
	B. Axiomatizations for Richer Languages
		1. Adding ‘=’ to the language
		2. Adding function symbols to the language
		• Exercises for Section B
		Taking open wffs as true or false
XI. The Number of Objects in the Universe of a Model
	Characterizing the Size of the Universe
		• Exercises
	Submodels and Skolem Functions
XII. Formalizing Group Theory
	A. A Formal Theory of Groups
		• Exercises for Section A
	B. On Definitions
		1. Eliminating ‘e’
		2. Eliminating ‘–1’
		3. Extensions by definitions
		• Exercises for Section B
XIII. Linear Orderings
	A. Formal Theories of Orderings
		• Exercises for Section A
	B. Isomorphisms
		• Exercises for Section B
	C. Categoricity and Completeness
		• Exercises for Section C
	D. Set Theory as a Foundation of Mathematics?
	Decidability by Elimination of Quantifiers
XIV. Second-Order Classical Predicate Logic
	A. Quantifying over Predicates?
	B. Predicate Variables and Their Interpretation: Avoiding Self-Reference
		1. Predicate variables
		2. The interpretation of predicate variables
		Higher-order logics
	C. A Formal Language for Second-Order Logic, L2
		• Exercises for Sections A–C
	D. Realizations and Models
		• Exercises for Section D
	E. Examples of Formalization
		• Exercises for Section E
	F. Classical Mathematical Second-Order Predicate Logic
		1. The abstraction of models
		2. All things and all predicates
		3. Examples of formalization
		• Exercises for Sections F.1–F.3
		4. The comprehension axioms
		• Exercises for Section F.4
	G. Quantifying over Functions
		• Exercises for Section G
	H. Other Kinds of Variables and Second-Order Logic
		1. Many-sorted logic
		2. General models for second-order logic
		• Exercises for Section H
XV. The Natural Numbers
	A. The Theory of Successor
		• Exercises for Section A
	B. The Theory Q
		1. Axiomatizing addition and multiplication
		• Exercises for Section B.1
		2. Proving is a computable procedure
		3. The computable functions and Q
		4. The undecidability of Q
		• Exercises for Sections B.2–B.4
	C. Theories of Arithmetic
		1. Peano Arithmetic and Arithmetic
		• Exercises for Sections C.1
		2. The languages of arithmetic
		• Exercises for Sections C.2
	D. The Consistency of Theories of Arithmetic
		• Exercises for Section D
	E. Second-Order Arithmetic
		• Exercises for Section E
	F. Quantifying over Names
XVI. The Integers and Rationals
	A. The Rational Numbers
		1. A construction
		2. A translation
		• Exercises for Section A
	B. Translations via Equivalence Relations
	C. The Integers
		• Exercises for Sections B and C
	D. Relativizing Quantifiers and the Undecidability of Z-Arithmetic and Q-Arithmetic
		• Exercises for Section D
XVII. The Real Numbers
	A. What Are the Real Numbers?
		• Exercises for Section A
	B. Divisible Groups
		The decidability and completeness of the theory of divisible groups
		• Exercises for Section B
	C. Continuous Orderings
		• Exercises for Section C
	D. Ordered Divisible Groups
		• Exercises for Section D
	E. Real Closed Fields
		1. Fields
		• Exercises for Section E.1
		2. Ordered fields
		• Exercises for Section E.2
		3. Real closed fields
		• Exercises for Section E.3
		The theory of fields in the language of name quantification
	Appendix: Real Numbers as Dedekind Cuts
XVIII. One-Dimensional Geometry in collaboration with Leslaw Szczerba
	A. What Are We Formalizing?
	B. The One-Dimensional Theory of Betweenness
		1. An axiom system for betweenness, B1
		• Exercises for Sections A and B.1
		2. Some basic theorems of B1
		3. Vectors in the same direction
		4. An ordering of points and B101
		5. Translating between B1 and the theory of dense linear orderings
		6. The second-order theory of betweenness
		• Exercises for Section B
	C. The One-Dimensional Theory of Congruence
		1. An axiom system for congruence, C1
		2. Point symmetry
		3. Addition of points
		4. Congruence expressed in terms of addition
		5. Translating between C1 and the theory of 2-divisible groups
		6. Division axioms for C1 and the theory of divisible groups
		• Exercises for Section C
	D. One-Dimensional Geometry
		1. An axiom system for one-dimensional geometry, E1
		2. Monotonicity of addition
		3. Translating between E1 and the theory of ordered divisible groups
		4. Second-order one-dimensional geometry
		• Exercises for Section D
	E. Named Parameters
XIX. Two-Dimensional Euclidean Geometry in collaboration with Lesõaw Szczerba
	A. The Axiom System E2
		• Exercises for Section A
	B. Deriving Geometric Notions
		1. Basic properties of the primitive notions
		2. Lines
		3. One-dimensional geometry and point symmetry
		4. Line symmetry
		5. Perpendicular lines
		6. Parallel lines
		• Exercises for Sections B.1–B.6
		7. Parallel projection
		8. The Pappus-Pascal Theorem
		9. Multiplication of points
	C. Betweenness and Congruence Expressed Algebraically
	D. Ordered Fields and Cartesian Planes
	E. The Real Numbers
	• Exercises for Sections C–E
	Historical Remarks
XX. Translations within Classical Predicate Logic
	A. What Is a Translation?
		• Exercises for Section A
	B. Examples
		1. Translating between different languages of predicate logic
		2. Converting functions into predicates
		3. Translating predicates into formulas
		4. Relativizing quantifiers
		5. Establishing equivalence-relations
		6. Adding and eliminating parameters
		7. Composing translations
		8. The general form of translations?
XXI. Classical Predicate Logic with Non-Referring Names
	A. Logic for Nothing
	B. Non-Referring Names in Classical Predicate Logic?
	C. Semantics for Classical Predicate Logic with Non-Referring Names
		1. Assignments of references and atomic predications
		2. The quantifiers
		3. Summary of the semantics for languages without equality
		4. Equality
		• Exercises for Sections A–C
	D. An Axiomatization
		• Exercises for Section D
	E. Examples of Formalization
		• Exercises for Section E
	F. Classical Predicate Logic with Names for Partial Functions
		1. Partial functions in mathematics
		2. Semantics for partial functions
		3. Examples
		4. An axiomatization
		• Exercises for Section F
	G. A Mathematical Abstraction of the Semantics
XXII. The Liar Paradox
	A. The Self-Reference Exclusion Principle
	B. Buridan’s Resolution of the Liar Paradox
		• Exercises for Sections A and B
	C. A Formal Theory
		• Exercises for Section C
	D. Examples
		• Exercises for Section D
	E. One Language for Logic?
XXIII. On Mathematical Logic and Mathematics
	Concluding Remarks
Appendix: The Completeness of Classical Predicate Logic Proved by Gödel’s Method
	A. Description of the Method
	B. Syntactic Derivations
	C. The Completeness Theorem
Summary of Formal Systems
	Propositional Logic
	Classical Predicate Logic
	Arithmetic
	Linear Orderings
	Groups
	Fields
	One-dimensional geometry
	Two-dimensional Euclidean geometry
	Classical Predicate Logic with Non-referring Names
	Classical Predicate Logic with Name Quantification
Bibliography
Index of Notation
Index