Measuring complexities of classes of structures

详细信息    查看全文

• 作者：Barbara F. Csima ; ¹ ; ^{csima@uwaterloo.ca" class="auth_mail" title="E-mail the corresponding author} ; ; Carolyn Knoll² ; ^{caknoll@uwaterloo.ca" class="auth_mail" title="E-mail the corresponding author}
• 关键词：03D28 ; 03D30 ; 03D45 ; O3C57
• 刊名：Annals of Pure and Applied Logic
• 出版年：2015
• 出版时间：December 2015
• 年：2015
• 卷：166
• 期：12
• 页码：1365-1381
• 全文大小：444 K

文摘

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 Montalbán, is defined in terms of 危_伪${\mathrm{危}}_{伪}$-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 cd4a687c2b" title="Click to view the MathML source">伪≤尾$伪\le 尾$ 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.