Computable Structure Theory
Within the Arithmetic

Presents main results and techniques in computable structure theory together in a coherent framework for the first time in 20 years.

Antonio Montalbán (Author)

9781108423298, Cambridge University Press

Hardback, published 24 June 2021

250 pages
24 x 16.2 x 1.8 cm, 0.49 kg

'This exceptionally well-written book is the first modern monograph on computable structure theory in 20 years … The author succeeds in bringing together new and old results and presenting them in a coherent framework, making it easy for the reader to learn the main results and techniques in the area for application in their own research.' Alexandra Andreeva Soskova, MathSciNet

In mathematics, we know there are some concepts - objects, constructions, structures, proofs - that are more complex and difficult to describe than others. Computable structure theory quantifies and studies the complexity of mathematical structures, structures such as graphs, groups, and orderings. Written by a contemporary expert in the subject, this is the first full monograph on computable structure theory in 20 years. Aimed at graduate students and researchers in mathematical logic, it brings new results of the author together with many older results that were previously scattered across the literature and presents them all in a coherent framework, making it easier for the reader to learn the main results and techniques in the area for application in their own research. This volume focuses on countable structures whose complexity can be measured within arithmetic; a forthcoming second volume will study structures beyond arithmetic.

1. Structures
2. Relations
3. Existentially-Atomic Models
4. Generic Presentations
5. Degree Spectra
6. Comparing Structures and Classes of Structures
7. Finite-Injury Constructions
8. Computable Categoricity
9. The Jump of a Structure
10. ?-Small Classes
Bibliography
Index.

Subject Areas: Mathematical modelling [PBWH], Set theory [PBCH], Mathematical logic [PBCD]