A First Course in Logic An Introduction to Model Theory, Proof Theory, Computability, and Complexity

by Hedman, Shawn

• ISBN13: 9780198529804
• ISBN10: 0198529805
• Format: Hardcover
• Copyright: 2004-09-16
• Publisher: Oxford University Press

Summary

This title includes the following features: Extensive coverage of thebasics of classical logic; Extremely clear, thorough and accurate; Idealtextbook for a first or refresher course; Contains numerous exercises; Aimed ata broad audience from students of computer science through mathematics, logicand philosophy

Table of Contents

1 Propositional logic	1	(52)
1.1 What is propositional logic?	1	(6)
1.2 Validity, satisfiability, and contradiction	7	(2)
1.3 Consequence and equivalence	9	(3)
1.4 Formal proofs	12	(10)
1.5 Proof by induction	22	(5)
1.5.1 Mathematical induction	23	(2)
1.5.2 Induction on the complexity of formulas	25	(2)
1.6 Normal forms	27	(5)
1.7 Horn formulas	32	(5)
1.8 Resolution	37	(7)
1.8.1 Clauses	37	(1)
1.8.2 Resolvents	38	(2)
1.8.3 Completeness of resolution	40	(4)
1.9 Completeness and compactness	44	(9)
2 Structures and first-order logic	53	(46)
2.1 The language of first-order logic	53	(1)
2.2 The syntax of first-order logic	54	(3)
2.3 Semantics and structures	57	(9)
2.4 Examples of structures	66	(7)
2.4.1 Graphs	66	(3)
2.4.2 Relational databases	69	(1)
2.4.3 Linear orders	70	(2)
2.4.4 Number systems	72	(1)
2.5 The size of a structure	73	(6)
2.6 Relations between structures	79	(10)
2.6.1 Embeddings	80	(3)
2.6.2 Substructures	83	(3)
2.6.3 Diagrams	86	(3)
2.7 Theories and models	89	(10)
3 Proof theory	99	(48)
3.1 Formal proofs	100	(9)
3.2 Normal forms	109	(4)
3.2.1 Conjunctive prenex normal form	109	(2)
3.2.2 Skolem normal form	111	(2)
3.3 Herbrand theory	113	(7)
3.3.1 Herbrand structures	113	(3)
3.3.2 Dealing with equality	116	(2)
3.3.3 The Herbrand method	118	(2)
3.4 Resolution for first-order logic	120	(8)
3.4.1 Unification	121	(3)
3.4.2 Resolution	124	(4)
3.5 SLD-resolution	128	(9)
3.6 Prolog	137	(10)
4 Properties of first-order logic	147	(51)
4.1 The countable case	147	(5)
4.2 Cardinal knowledge	152	(11)
4.2.1 Ordinal numbers	153	(3)
4.2.2 Cardinal arithmetic	156	(5)
4.2.3 Continuum hypotheses	161	(2)
4.3 Four theorems of first-order logic	163	(7)
4.4 Amalgamation of structures	170	(4)
4.5 Preservation of formulas	174	(9)
4.5.1 Supermodels and submodels	175	(4)
4.5.2 Unions of chains	179	(4)
4.6 Amalgamation of vocabularies	183	(6)
4.7 The expressive power of first-order logic	189	(9)
5 First-order theories	198	(69)
5.1 Completeness and decidability	199	(6)
5.2 Categoricity	205	(6)
5.3 Countably categorical theories	211	(5)
5.3.1 Dense linear orders	211	(3)
5.3.2 Ryll-Nardzewski et al.	214	(2)
5.4 The Random graph and 0-1 laws	216	(5)
5.5 Quantifier elimination	221	(12)
5.5.1 Finite relational vocabularies	222	(6)
5.5.2 The general case	228	(5)
5.6 Model-completeness	233	(6)
5.7 Minimal theories	239	(8)
5.8 Fields and vector spaces	247	(10)
5.9 Some algebraic geometry	257	(10)
6 Models of countable theories	267	(32)
6.1 Types	267	(4)
6.2 Isolated types	271	(4)
6.3 Small models of small theories	275	(5)
6.3.1 Atomic models	276	(1)
6.3.2 Homogeneity	277	(2)
6.3.3 Prime models	279	(1)
6.4 Big models of small theories	280	(6)
6.4.1 Countable saturated models	281	(4)
6.4.2 Monster models	285	(1)
6.5 Theories with many types	286	(3)
6.6 The number of nonisomorphic models	289	(1)
6.7 A touch of stability	290	(9)
7 Computability and complexity	299	(58)
7.1 Computable functions and Church's thesis	301	(11)
7.1.1 Primitive recursive functions	302	(5)
7.1.2 The Ackermann function	307	(2)
7.1.3 Recursive functions	309	(3)
7.2 Computable sets and relations	312	(4)
7.3 Computing machines	316	(4)
7.4 Codes	320	(7)
7.5 Semi-decidable decision problems	327	(5)
7.6 Undecidable decision problems	332	(5)
7.6.1 Nonrecursive sets	332	(3)
7.6.2 The arithmetic hierarchy	335	(2)
7.7 Decidable decision problems	337	(11)
7.7.1 Examples	338	(6)
7.7.2 Time and space	344	(3)
7.7.3 Nondeterministic polynomial-time	347	(1)
7.8 NP-completeness	348	(9)
8 The incompleteness theorems	357	(31)
8.1 Axioms for first-order number theory	358	(4)
8.2 The expressive power of first-order number theory	362	(8)
8.3 Gödel's First Incompleteness theorem	370	(4)
8.4 Gödel codes	374	(6)
8.5 Gödel's Second Incompleteness theorem	380	(3)
8.6 Goodstein sequences	383	(5)
9 Beyond first-order logic	388	(20)
9.1 Second-order logic	388	(4)
9.2 Infinitary logics	392	(3)
9.3 Fixed-point logics	395	(5)
9.4 Lindström's theorem	400	(8)
10 Finite model theory	408	(18)
10.1 Finite-variable logics	408	(4)
10.2 Classical failures	412	(5)
10.3 Descriptive complexity	417	(6)
10.4 Logic and the P = NP problem	423	(3)
Bibliography	426	(2)
Index	428