Positive undecidable numberings in the Ershov hierarchy (Q695803): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Removed claims |
||
Property / author | |||
Property / author: Q695801 / rank | |||
Property / author | |||
Property / author: Andrea Sorbi / rank | |||
Revision as of 22:49, 11 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Positive undecidable numberings in the Ershov hierarchy |
scientific article |
Statements
Positive undecidable numberings in the Ershov hierarchy (English)
0 references
17 December 2012
0 references
In the paper under review the authors give a sufficient condition under which an infinite computable family of \(\Sigma^{-1}_a\) sets has computable positive but undecidable numberings. Here \(a\) is a notation for a computable ordinal \(>0\). In particular, it is shown that if \(a\) is a notation for an infinite computable ordinal and \({\mathcal A}\) is an infinite family of \(\Sigma^{-1}_a\) sets containing an \(n\)-c.e. set, then \({\mathcal A}\) has infinitely many computable positive undecidable numberings, which are pairwise incomparable with respect to Rogers reducibility.
0 references
Ershov hierarchy
0 references
families of \(\Sigma^{-1}_a\) sets
0 references
computable ordinals
0 references
positive numberings
0 references
Rogers reducibility
0 references