A computably stable structure with no Scott family of finitary formulas (Q2501165)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A computably stable structure with no Scott family of finitary formulas |
scientific article |
Statements
A computably stable structure with no Scott family of finitary formulas (English)
0 references
4 September 2006
0 references
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.
0 references
computably stable structure
0 references
Scott family
0 references
0 references