Computable structures and the hyperarithmetical hierarchy
type: Item
instance of: scholarly article
title: Computable structures and the hyperarithmetical hierarchy
zbMATH Open document ID: 0960.03001
author: C. J. Ash
author: J. F. Knight
published in: Studies in Logic and the Foundations of Mathematics
publication date: 2000-07-20T00:00:00Z
review text: This exceptionally well-organized book explores an important part of computable model theory. The basic structures of concern are countable models coded in such a way that the open diagram, or perhaps the diagram, exhibits some level of effectiveness; typically, the open diagram will be computable. One asks questions about effectivity related to the isomorphism type of the given structure, perhaps with some distinguished relation. For an illustrative example, a computable presentation of a linear ordering would be \(\mathbb{N}\), the natural numbers equipped with an ordering \(\preceq\) such that the relation \(x\preceq y\) is computable. The actual classical order type could be any countable ordering that happens to have a computable presentation. The types of questions examined in this book are based upon observations like the following. Take two computable presentations of the rationals, considered as a countable dense linear ordering without endpoints. Then, after Cantor, these two orderings are not just isomorphic, but computably isomorphic, in the sense that there is a computable isomorphism taking one to the other. Clearly this argument extends to demonstrate that if the two orderings have only a finite number of adjacencies, then they are computably isomorphic. On the other hand, it is easy to construct a copy of \(\omega\), the order type of the positive integers, where the relation ``\(x\) is adjacent to \(x\)'' is not computable. Hence, there are two computable copies of \(\omega\) which are not computably isomorphic. We call a structure computably categorical iff any two computable copies of the structure are computably isomorphic. Remmel and Goncharov independently showed that a computable linear ordering is computably categorical iff it has a finite number of adjacencies. On the other hand, while \(\omega\) is not computably categorical, it does have the property that it is \(\Delta^0_2\) categorical, in the sense that between any two computable copies…
Mathematics Subject Classification ID: 03-02
Mathematics Subject Classification ID: 03D45
Mathematics Subject Classification ID: 03C57
Mathematics Subject Classification ID: 03D25
Mathematics Subject Classification ID: 03D30
zbMATH DE Number: 1479595
zbMATH Keywords: computable model theory
zbMATH Keywords: countable models
zbMATH Keywords: effectiveness
zbMATH Keywords: computable presentation
zbMATH Keywords: stability
zbMATH Keywords: adjacency
zbMATH Keywords: computable categoricity
zbMATH Keywords: computability
reviewed by: Rodney G. Downey
MaRDI profile type: Publication
Recommended article: Generalized hyperarithmetical computability over structures
Recommended article: Computable Structure Theory
Recommended article: Q4451633
Recommended article: Q4460832
Recommended article: Q4266205
Recommended article: Q4513965
Recommended article: Realizing levels of the hyperarithmetic hierarchy as degree spectra of relations on computable structures
Recommended article: Computability-Theoretic Complexity of Countable Structures
Recommended article: Q5371227
Recommended article: On computably enumerable structures
description: scientific article; zbMATH DE number 1479595