Computable structure theory : within the arithmetic / Antonio Montalbán.

Format:

Book

Author/Creator:

Montalbán, Antonio, author.

Series:

Perspectives in logic

Language:

English

Subjects (All):

Computable functions.

Physical Description:

1 online resource (xxii, 190 pages) : digital, PDF file(s).

Place of Publication:

Cambridge : Cambridge University Press, 2021.

Summary:

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.

Contents:

Cover

Half-title

Series information

Title page

Copyright information

Dedication

CONTENTS

PREFACE

NOTATION AND CONVENTIONS

Chapter 1 STRUCTURES

1.1. Presentations

1.2. Presentations that code sets

Chapter 2 RELATIONS

2.1. Relatively intrinsic notions

2.2. Complete relations

2.3. Examples of r.i.c.e. complete relations

2.4. Superstructures

Chapter 3 EXISTENTIALLY-ATOMIC MODELS

3.1. Definition

3.2. Existentially algebraic structures

3.3. Cantor's back-and-forth argument

3.4. Uniform computable categoricity

3.5. Existential atomicity in terms of types

3.6. Building structures and omitting types

3.7. Scott sentences of existentially atomic structures

3.8. Turing degree and enumeration degree

Chapter 4 GENERIC PRESENTATIONS

4.1. Cohen generic reals

4.2. Generic enumerations of sets

4.3. Generic enumerations of structures

4.4. Relations on generic presentations

Chapter 5 DEGREE SPECTRA

5.1. The c.e. embeddability condition

5.2. Co-spectra

5.3. Degree spectra that are not possible

5.4. Some particular degree spectra

Chapter 6 COMPARING STRUCTURES AND CLASSES OF STRUCTURES

6.1. Muchnik and Medvedev reducibilities

6.2. Turing-computable embeddings

6.3. Computable functors and effective interpretability

6.4. Reducible via effective bi-interpretability

Chapter 7 FINITE-INJURY CONSTRUCTIONS

7.1. Priority constructions

7.2. The method of true stages

7.3. Approximating the settling-time function

7.4. A construction of linear orderings

Chapter 8 COMPUTABLE CATEGORICITY

8.1. The basics

8.2. Relative computable categoricity

8.3. Categoricity on a cone

8.4. When relative and plain computable categoricity coincide

8.5. When relative and plain computable categoricity diverge

Chapter 9 THE JUMP OF A STRUCTURE.

9.1. The jump-inversion theorems

9.2. The jump jumps-or does it?

Chapter 10 Σ-SMALL CLASSES

10.1. Infinitary Π[sub(1)] complete relations

10.2. A sufficient condition

10.3. The canonical structural jump

10.4. The low property

10.5. Listable classes

10.6. The copy-vs-diagonalize game

BIBLIOGRAPHY

INDEX.

Notes:

Title from publisher's bibliographic system (viewed on 11 Jun 2021).

ISBN:

1-108-53442-2

1-108-52574-1

OCLC:

1257800778