Computable categoricity and the Ershov hierarchy (Q958489): Difference between revisions

From MaRDI portal
Import240304020342 (talk | contribs)
Set profile property.
ReferenceBot (talk | contribs)
Changed an Item
 
(One intermediate revision by one other user not shown)
Property / full work available at URL
 
Property / full work available at URL: https://doi.org/10.1016/j.apal.2008.06.010 / rank
 
Normal rank
Property / OpenAlex ID
 
Property / OpenAlex ID: W1976898576 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4943318 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Equivalence structures and isomorphisms in the difference hierarchy / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q5619076 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q5619077 / rank
 
Normal rank
Property / cites work
 
Property / cites work: On the role of procrastination in machine learning / rank
 
Normal rank
Property / cites work
 
Property / cites work: Limiting recursion / rank
 
Normal rank
Property / cites work
 
Property / cites work: Autostability of models / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4513969 / rank
 
Normal rank
Property / cites work
 
Property / cites work: A proof of Beigel's cardinality conjecture / rank
 
Normal rank
Property / cites work
 
Property / cites work: \(\Delta_{2}^{0}\)-categoricity in Boolean algebras and linear orderings / rank
 
Normal rank
Property / cites work
 
Property / cites work: Supersimple sets and the problem of extending a retracing function / rank
 
Normal rank
Property / cites work
 
Property / cites work: Trial and error predicates and the solution to a problem of Mostowski / rank
 
Normal rank
Property / cites work
 
Property / cites work: Recursively Categorical Linear Orderings / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q5573961 / rank
 
Normal rank

Latest revision as of 22:04, 28 June 2024

scientific article
Language Label Description Also known as
English
Computable categoricity and the Ershov hierarchy
scientific article

    Statements

    Computable categoricity and the Ershov hierarchy (English)
    0 references
    0 references
    0 references
    0 references
    5 December 2008
    0 references
    A structure is \(F_{\alpha}\)- (accordingly \(G_{\alpha}\)-) categorical, if it has computable presentations and any two computable presentations are isomorphic via a function which belongs (accordingly, its graph belongs) to the \(\alpha\)-th level of the Ershov hierarchy. It is proved that for every ordinal notation \(\alpha\) there is a graph which is \(F_{\alpha}\)-categorical but not \(G_{\alpha}\)-categorical. A graph \(G\) is constructed which is not \(G_{\alpha}\)-categorical for any ordinal notation \(\alpha\). It is also proved that there is a graph which is \(G_2\)-categorical but not \(F_{\alpha}\)-categorical for any notation \(\alpha\). Examples of \(D_3\)-categorical but not \(G_2\)-categorical graphs are given. Considering linear orderings, the authors prove that a linear order \((L,<)\) is \(F_{\alpha}\)-categorical for some \(\alpha\) if and only if it is countable and has only finitely many successive pairs. (By definition, for \(x,y\in L\), \(\langle x,y\rangle\) is a successive pair if \(x<y\) and there are no elements in \(L\) between \(x\) and \(y\).) It follows from this result and some other known facts that every \(F_{\alpha}\)-categorical linear order is also computable-categorical. At last, an example of a linear order which is \(\Delta^0_2\)-categorical but not \(G_{\alpha}\)-categorical for any \(\alpha\), is given.
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    Ershov hierarchy
    0 references
    categoricity
    0 references
    graphs
    0 references
    linear orders
    0 references
    recursive ordinal
    0 references
    0 references