最大セット

再帰理論、つまり計算可能性の数学的理論では、極大集合とは、自然数の共有限な再帰的可算部分集合Aであり、自然数のさらに任意の再帰的可算部分集合Bに対して、 Bが共有限であるか、BがAの有限変形であるか、B がAのスーパーセットではないかのいずれかである。これにより、再帰的可算集合の 束内で簡単に定義できる。

極大集合には、多くの興味深い性質がある。極大集合は、単純、超単純、超超単純、r-最大である。r-最大の性質は、すべての再帰集合Rには、 Aの補集合の有限個の要素のみが含まれるか、 Aの補集合のほぼすべての要素が含まれるというものである。極大でない r-最大集合も存在する。極大集合の中には、極大スーパーセットを持たないものもある。Myhill (1956) は極大集合が存在するかどうかを問い、Friedberg (1958) はそれを構築した。Soare (1974) は、極大集合が、包含の下で (有限集合を法として)再帰的に可算な集合の自己同型に関して軌道を形成することを示した。一方では、すべての自己同型は、極大集合Aを別の極大集合Bに写像する。他方では、すべての 2 つの極大集合A、Bに対して、 AがBに写像されるような再帰的に可算な集合の自己同型が存在する。

• フリードバーグ、リチャード M. (1958)、「再帰列挙に関する 3 つの定理。I. 分解。II. 最大集合。III. 重複のない列挙」、The Journal of Symbolic Logic、23 (3)、Association for Symbolic Logic: 309–316、doi :10.2307/2964290、JSTOR  2964290、MR  0109125、S2CID  25834814
• マイヒル、ジョン (1956)、「タルスキの問題の解決」、記号論理学ジャーナル、21 (1)、記号論理学協会: 49–51、doi :10.2307/2268485、JSTOR  2268485、MR  0075894、S2CID  19695459
• H. Rogers, Jr., 1967. 「再帰関数と効果的な計算可能性の理論」、第2版1987年、MIT Press。ISBN 0-262-68052-1 (ペーパーバック)、ISBN 0-07-053522-1。  
• Soare, Robert I. (1974)、「再帰的に可算な集合の束の自己同型。I. 極大集合」、Annals of Mathematics、第 2 シリーズ、100 (1)、Annals of Mathematics: 80–120、doi :10.2307/1970842、JSTOR  1970842、MR  0360235