A computably stable structure with no Scott family of finitary formulas

DOI10.1007/S00153-005-0326-7MaRDI QIDQ2501165zbMATH OpenOpenAlexFDO

Authors Richard A. Shore, Peter A. Cholak, Reed Solomon

Publication date 4 September 2006

Published in Archive for Mathematical Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00153-005-0326-7

zbMATH Keywords

computably stable structureScott family

Mathematics Subject Classification ID

Computable structure theory, computable model theory (03C57) Theory of numerations, effectively presented structures (03D45)

Review text

A computable structure is one with universe coded by \(\omega\) and whose open diagram is computable. Such a structure, like a computable linear ordering of order type \(\omega\) with computable successor relation, is called computably stable iff every isomorphism from it to a computable copy of itself is computable. This is related to being computably categorical where now we ask that every computable structure isomorphic to the given one is computably isomorphic to it. It is known that these concepts are related to Scott families, which are families of formulae ``naming the model. In the relativized world it is known that the syntactic condition of having a computable Scott family captures the notion of computable categoricity, but it is known that certain examples going back to Goncharov demonstrate that this is not necessary. The paper at hand uses similar methods to construct a rigid computably stable graph with no Scott family of finitary formulae.

Recommendations

• scientific article; zbMATH DE number 1222106
• Intrinsic bounds on complexity and definability at limit levels
• Computability-theoretic categoricity and Scott families
• An autostable 1-decidable model without a computable Scott family of -formulas
• Computable isomorphisms, degree spectra of relations, and Scott families

Cites work

• A computably categorical structure whose expansion by a constant has infinite computable dimension
• An autostable 1-decidable model without a computable Scott family of -formulas
• Autostability and computable families of constructivizations
• Computably categorical structures and expansions by constants
• Degree spectra of intrinsically c. e. relations
• Effective model theory vs. recursive model theory
• Enumerations of families of general recursive functions
• Generic copies of countable structures
• scientific article; zbMATH DE number 4091484 (Why is no real title available?)
• scientific article; zbMATH DE number 53151 (Why is no real title available?)
• Model Theory
• The quantity of nonautoequivalent constructivizations

Cited in

(4)

• Computable Scott sentences for quasi-Hopfian finitely presented structures
• An autostable 1-decidable model without a computable Scott family of -formulas
• scientific article; zbMATH DE number 1222106 (Why is no real title available?)
• Applications of Kolmogorov complexity to computable model theory

This page was built for publication: A computably stable structure with no Scott family of finitary formulas

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2501165)