r.e.チューリング次数の構造
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/06/24 05:45 UTC 版)
「チューリング次数」の記事における「r.e.チューリング次数の構造」の解説
帰納的可算集合を持つ次数は r.e.（recursively enumerable 帰納的可算）または c.e.（computably enumerable 計算可枚挙） と呼ばれる。全ての r.e.次数は 0′よりも小さいか等しい。しかしながら 0′よりも小さい全ての次数が r.e.次数という訳ではない。 (G. E. Sacks, 1964) r.e.次数は稠密。任意の二つのr.e.次数の間には、必ず別のr.e.次数がある。 (A. H. Lachlan, 1966a and C. E. M. Yates, 1966) r.e.次数の中には下限を持たないような、r.e.次数の対が存在する。 (A. H. Lachlan, 1966a and C. E. M. Yates, 1966) 下限が 0 であるような 0 でないr.e.次数の対が一つ存在する。 (S. K. Thomason, 1971) 全ての有限な分配束はr.e.次数に埋め込める。実際に、可算で atomless なブール束を上限と下限を保つように埋め込むことが出来る。 (A. H. Lachlan and R. I. Soare, 1980) （上限と下限を保つように）r.e.次数に埋め込めないような、有限な束が存在する。特に次の束は r.e.次数に埋め込めない。 (A. H. Lachlan, 1966b) r.e.次数の対で、下限が0かつ上限が 0′であるものは存在しない。この結果は非公式に「ノンダイアモンド定理」と呼ばれている。 (L. A. Harrington and T. A. Slaman, see Nies, Shore, and Slaman (1998))言語 ⟨ 0 , ≤ , = ⟩ {\displaystyle \left\langle 0,\leq ,=\right\rangle } を用いて書かれたr.e.次数の一階理論は真である一階算術と多対一同値。
※この「r.e.チューリング次数の構造」の解説は、「チューリング次数」の解説の一部です。
「r.e.チューリング次数の構造」を含む「チューリング次数」の記事については、「チューリング次数」の概要を参照ください。
- r.e.チューリング次数の構造のページへのリンク
