A first course in logic : an introduction in model theory, proof theory, computability, and complexity / Shawn Hedman.

Format:

Book

Author/Creator:

Hedman, Shawn, author.

Series:

Oxford texts in logic ; 1.

Oxford scholarship online.

Oxford texts in logic ; 1

Oxford scholarship online

Language:

English

Subjects (All):

Logic.

Physical Description:

1 online resource (xx, 431 pages) : illustrations

Edition:

1st ed.

Place of Publication:

Oxford : Oxford University Press, 2020.

Language Note:

English

Summary:

The ability to reason and think in a logical manner forms the basis of learning for most mathematics, computer science, philosophy and logic students. Based on the author's teaching notes at the University of Maryland and aimed at a broad audience, this text covers the fundamental topics in classical logic in an extremely clear, thorough and accurate style that is accessible to all the above. Covering propositional logic, first-order logic, and second-order logic, as well as proof theory, computability theory, and model theory, the text also contains numerous carefully graded exercises and is ideal for a first or refresher course.

Contents:

Intro

Contents

1 Propositional logic

1.1 What is propositional logic?

1.2 Validity, satisfiability, and contradiction

1.3 Consequence and equivalence

1.4 Formal proofs

1.5 Proof by induction

1.5.1 Mathematical induction

1.5.2 Induction on the complexity of formulas

1.6 Normal forms

1.7 Horn formulas

1.8 Resolution

1.8.1 Clauses

1.8.2 Resolvents

1.8.3 Completeness of resolution

1.9 Completeness and compactness

2 Structures and first-order logic

2.1 The language of first-order logic

2.2 The syntax of first-order logic

2.3 Semantics and structures

2.4 Examples of structures

2.4.1 Graphs

2.4.2 Relational databases

2.4.3 Linear orders

2.4.4 Number systems

2.5 The size of a structure

2.6 Relations between structures

2.6.1 Embeddings

2.6.2 Substructures

2.6.3 Diagrams

2.7 Theories and models

3 Proof theory

3.1 Formal proofs

3.2 Normal forms

3.2.1 Conjunctive prenex normal form

3.2.2 Skolem normal form

3.3 Herbrand theory

3.3.1 Herbrand structures

3.3.2 Dealing with equality

3.3.3 The Herbrand method

3.4 Resolution for first-order logic

3.4.1 Unification

3.4.2 Resolution

3.5 SLD-resolution

3.6 Prolog

4 Properties of first-order logic

4.1 The countable case

4.2 Cardinal knowledge

4.2.1 Ordinal numbers

4.2.2 Cardinal arithmetic

4.2.3 Continuum hypotheses

4.3 Four theorems of first-order logic

4.4 Amalgamation of structures

4.5 Preservation of formulas

4.5.1 Supermodels and submodels

4.5.2 Unions of chains

4.6 Amalgamation of vocabularies

4.7 The expressive power of first-order logic

5 First-order theories

5.1 Completeness and decidability

5.2 Categoricity

5.3 Countably categorical theories

5.3.1 Dense linear orders

5.3.2 Ryll-Nardzewski et al.

5.4 The Random graph and 0-1 laws

5.5 Quantifier elimination

5.5.1 Finite relational vocabularies

5.5.2 The general case

5.6 Model-completeness

5.7 Minimal theories

5.8 Fields and vector spaces

5.9 Some algebraic geometry

6 Models of countable theories

6.1 Types

6.2 Isolated types

6.3 Small models of small theories

6.3.1 Atomic models

6.3.2 Homogeneity

6.3.3 Prime models

6.4 Big models of small theories

6.4.1 Countable saturated models

6.4.2 Monster models

6.5 Theories with many types

6.6 The number of nonisomorphic models

6.7 A touch of stability

7 Computability and complexity

7.1 Computable functions and Church's thesis

7.1.1 Primitive recursive functions

7.1.2 The Ackermann function

7.1.3 Recursive functions

7.2 Computable sets and relations

7.3 Computing machines

7.4 Codes

7.5 Semi-decidable decision problems

7.6 Undecidable decision problems

7.6.1 Nonrecursive sets

7.6.2 The arithmetic hierarchy

7.7 Decidable decision problems

7.7.1 Examples

7.7.2 Time and space

7.7.3 Nondeterministic polynomial-time

7.8 NP-completeness

8 The incompleteness theorems

8.1 Axioms for first-order number theory

8.2 The expressive power of first-order number theory

8.3 Gödel's First Incompleteness theorem

8.4 Gödel codes

8.5 Gödel's Second Incompleteness theorem

8.6 Goodstein sequences

9 Beyond first-order logic

9.1 Second-order logic

9.2 Infinitary logics

9.3 Fixed-point logics

9.4 Lindström's theorem

10 Finite model theory

10.1 Finite-variable logics

10.2 Classical failures

10.3 Descriptive complexity

10.4 Logic and the P = NP problem

Bibliography

Index.

Notes:

Previously issued in print: 2004.

Includes bibliographical references and index.

Description based on print version record.

Description based on publisher supplied metadata and other sources.

ISBN:

0-19-191665-X

0-19-158677-3

1-280-75897-X

9786610758975

1-4237-7079-X

OCLC:

1027137349