...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Journal of mathematical logic >Direct and local definitions of the Turing jump
【24h】

Direct and local definitions of the Turing jump

机译：图灵跳的直接和本地定义

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

We show that there are Pi(5) formulas in the language of the Turing degrees, D, with <=, V and boolean AND, that define the relations x" <= y", x" = y" and so x epsilon L-2(y) = {x >= y vertical bar x" = y"} in any jump ideal containing 0((omega)). There are also Sigma(6)&&UPI;(6) and Pi(8) formulas that define the relations w = x" and w = x", respectively, in any such ideal I. In the language with just <= the quantifier complexity of each of these definitions increases by one. For a lower bound on definability, we show that no Pi(2) or Sigma(2) formula in the language with just <= defines L-2 or L-2( y). Our arguments and constructions are purely degree theoretic without any appeals to absoluteness considerations, set theoretic methods or coding of models of arithmetic. As a corollary, we see that every automorphism of I is fixed on every degree above 0" and every relation on I which is invariant under the double jump or under join with 0" is definable over I if and only if it is definable in second order arithmetic with set quantification ranging over sets whose degrees are in I.
机译：我们显示存在图灵度D语言的Pi（5）公式，其中<=，V和布尔AND，定义关系x“ <= y”，x“ = y”以及x epsilon L -2（y）= {x> = y竖线x“ = y”}在任何包含0（（ω））的跳跃理想值中。在任何这样的理想I中，还有Sigma（6）&& UPI;（6）和Pi（8）公式分别定义关系w = x“和w = x”。在仅<=量词复杂度的语言中这些定义中的每一个都增加一个。对于可定义性的下限，我们显示在仅<=的语言中，没有Pi（2）或Sigma（2）公式定义L-2或L-2（y）。我们的论点和结构纯属度理论，对绝对性，设置理论方法或算术模型编码没有任何吸引力。作为推论，我们看到I的每个自同构都固定在大于0“的每个度上，并且在且仅当在第二个条件下可定义的情况下，I上的每个关系都可以在I上定义，该关系在双跳下或与0”连接时不变集合量化的阶数算术，其范围为度为I的集合

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号