帰納的可算集合の束(lattice)
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/06/24 05:44 UTC 版)
「再帰理論」の記事における「帰納的可算集合の束(lattice)」の解説
ポストは単純集合（「無限帰納的可算集合を一つも含まないような無限補集合」を持つ帰納的可算集合）を定義し、そこから帰納的可算集合同士の包含関係を研究し始めた。この束 (lattice) は今日では詳細に研究された構造となっている。ある集合が帰納的である必要十分条件は、集合とその補集合が共に帰納的可算であることである。この基本的な結果を用いて、この構造内に帰納的集合を定義できる。無限帰納的可算集合は常に無限帰納的集合を部分集合として持つのに対し、単純集合は余無限 (coinfinite) な帰納的集合を上位集合として持たない。ポスト(1944)は既に超単純集合と超々単純集合を導入していた。後に極大集合 (maximal set) が構成されたが、これは帰納的可算である全ての上位集合が所与の極大集合の有限な変種かまたは余有限 (co-finite) であるような帰納的可算集合である。ポストがこの束を研究した元々の動機は、この性質を満たす全ての集合のチューリング次数が、帰納的集合と停止問題の何れのチューリング次数とも異なるということを構造的に示せないかという点にあった。ポストはそのような性質を見出すことはできず、彼の問題は代わりに優先度法を用いて解決されたが、Harrington と Soare (1991) はそのような性質をついに発見した。
※この「帰納的可算集合の束(lattice)」の解説は、「再帰理論」の解説の一部です。
「帰納的可算集合の束(lattice)」を含む「再帰理論」の記事については、「再帰理論」の概要を参照ください。
- 帰納的可算集合の束のページへのリンク
