Scholarlink

<p>We investigate degree structures induced by computable reducibility ≤<sub>c</sub> on binary relations having domain ω. We prove that for each of the following structures induced by ≤<sub>c</sub>, its first-order theory is recursively isomorphic to the second-order arithmetic: the structure <b>Pr</b> of all preorders, and the structure <b>LP</b> of all linear preorders.</p>

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

The Structure of Computable Reducibility on Preorders

  • 期刊论文

  • 发表日期：

    2026年7月9日

查看全文
  • D. B. Alish,
  • N. A. Bazhenov

摘要

We investigate degree structures induced by computable reducibility ≤c on binary relations having domain ω. We prove that for each of the following structures induced by ≤c, its first-order theory is recursively isomorphic to the second-order arithmetic: the structure Pr of all preorders, and the structure LP of all linear preorders.