• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Journal of logic and computation >Counting the back-and-forth types
【24h】

Counting the back-and-forth types

机译：计算来回类型

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

摘要

Given a class of structures K and n∈ω, we study the dichotomy between there being countably many n-back-and-forth equivalence classes and there being continuum many. In the latter case, we show that, relative to some oracle, every set can be weakly coded in the (n - 1 )st jump of some structure in K. In the former case, we show that there is a countable set of infinitary ∏_n relations that captures all of the ∏_n information about the structures in K. In most cases, where there are countably many n-back-and-forth equivalence classes, there is a computable description of them. We will show how to use this computable description to get a complete set of computably infinitary ∏_n formulas. This will allow us to completely characterize the relatively intrinsically ∑_(n+1)~0 relations in the computable structures of K, and to prove that no Turing degree can be coded by the(n- 1)st jump of any structure in K unless that degree is already below 0~(n-1).
机译：给定一类结构K和n∈ω，我们研究了存在大量n个前后等效类与存在多个连续统之间的二分法。在后一种情况下，我们表明，相对于某些oracle，每个集合都可以在K中某个结构的第（n-1）个跳转中进行弱编码。在前一种情况下，我们表明存在一个可数的无穷集合。 ∏_n关系捕获关于K中结构的所有∏_n信息。在大多数情况下，当n个来回等效类很多时，有一个可计算的描述。我们将展示如何使用此可计算的描述来获得可计算的无限式∏_n公式的完整集合。这将使我们能够完全刻画K的可计算结构中相对固有的∑_（n + 1）〜0关系，并证明在任何结构的第（n-1）次跳跃中都无法编码​​图灵度。除非该度已经低于0〜（n-1），否则K。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号