Abstract <p>In this paper, we study the joint degree spectrum of the successor and the block relations on computable linear orders. The joint degree spectrum of relations <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(R_{1},R_{2},\dots,R_{n}\)</EquationSource> <!--LobJMat2561063Frolov-m1--> </InlineEquation> on a computable structure <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(\mathcal{A}\)</EquationSource> <!--LobJMat2561063Frolov-m2--> </InlineEquation> is the set of all Turing degrees <InlineEquation ID="IEq3"> <EquationSource Format="TEX">\(\mathbf{x}\)</EquationSource> <!--LobJMat2561063Frolov-m3--> </InlineEquation> such that there is a computable <InlineEquation ID="IEq4"> <EquationSource Format="TEX">\(\mathcal{B}\cong\mathcal{A}\)</EquationSource> <!--LobJMat2561063Frolov-m4--> </InlineEquation> and the degrees of all <InlineEquation ID="IEq5"> <EquationSource Format="TEX">\(R_{i}(\mathcal{B})\)</EquationSource> <!--LobJMat2561063Frolov-m5--> </InlineEquation> are the same and coincide with <InlineEquation ID="IEq6"> <EquationSource Format="TEX">\(\mathbf{x}\)</EquationSource> <!--LobJMat2561063Frolov-m6--> </InlineEquation>. We prove that the joint degree spectrum of the successor and the block relations on a computable non-trivial <InlineEquation ID="IEq7"> <EquationSource Format="TEX">\(\eta\)</EquationSource> <!--LobJMat2561063Frolov-m7--> </InlineEquation>-like linear order is closed upwards in c.e. degrees. Also we obtain some effective properties of the successor relation on computable linear orders.</p>

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

The Complexity of the Successor and the Block Relations on Computable Linear Orders

  • A. N. Frolov,
  • M. V. Zubkov

摘要

Abstract

In this paper, we study the joint degree spectrum of the successor and the block relations on computable linear orders. The joint degree spectrum of relations \(R_{1},R_{2},\dots,R_{n}\) on a computable structure \(\mathcal{A}\) is the set of all Turing degrees \(\mathbf{x}\) such that there is a computable \(\mathcal{B}\cong\mathcal{A}\) and the degrees of all \(R_{i}(\mathcal{B})\) are the same and coincide with \(\mathbf{x}\) . We prove that the joint degree spectrum of the successor and the block relations on a computable non-trivial \(\eta\) -like linear order is closed upwards in c.e. degrees. Also we obtain some effective properties of the successor relation on computable linear orders.