Back to Search Start Over

Measuring complexities of classes of structures

Authors :
Barbara F. Csima
Carolyn Knoll
Source :
Annals of Pure and Applied Logic. 166:1365-1381
Publication Year :
2015
Publisher :
Elsevier BV, 2015.

Abstract

How do we compare the complexities of various classes of structures? The Turing ordinal of a class of structures, introduced by Jockusch and Soare, is defined in terms of the number of jumps required for coding to be possible. The back-and-forth ordinal, introduced by Montalban, is defined in terms of Σ α -types. The back-and-forth ordinal is (roughly) bounded by the Turing ordinal. In this paper, we show that, if we do not restrict the allowable classes, the reverse inequality need not hold. Indeed, for any computable ordinals α ≤ β we present a class of structures with back-and-forth ordinal α and Turing ordinal β . We also present an example of a class of structures with back-and-forth ordinal 1 but no Turing ordinal.

Details

ISSN :
01680072
Volume :
166
Database :
OpenAIRE
Journal :
Annals of Pure and Applied Logic
Accession number :
edsair.doi...........419ef3941ee34303021b1ec97443b74b
Full Text :
https://doi.org/10.1016/j.apal.2015.08.001