A computably stable structure with no Scott family of finitary formulas (Q2501165)

From MaRDI portal
Revision as of 18:50, 24 June 2024 by ReferenceBot (talk | contribs) (‎Changed an Item)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
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
    0 references
    0 references
    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

    Identifiers