帰納的分離不能対とは? わかりやすく解説

Weblio 辞書 > 辞書・百科事典 > 百科事典 > 帰納的分離不能対の意味・解説 

帰納的分離不能対

(recursively inseparable pair から転送)

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2015/02/22 17:06 UTC 版)

計算可能性理論において帰納的分離不能対(きのうてきぶんりふのうつい、: recursively inseparable pair)とは自然数の集合の対で帰納的集合によって分離できないものをいう(Monk 1976, p. 100)。この概念は計算理論におけるΠ1集合と関係が深い。帰納的分離不能対はゲーデルの不完全性定理とも関係する。

定義

自然数の集合を とおく。互いに素 の部分集合 が与えられたとき、分離集合 とは の部分集合であって かつ (あるいは同じことだが かつ )を満たすものをいう。例えば はそれ自身と との対の分離集合である。

互いに素な集合の対 が帰納的分離集合を持たないとき帰納的分離不能であるという。

もし集合 が帰納的でないならば、 とその補集合は帰納的分離不能である。しかしながら が互いに素であり、互いに補集合でなく、帰納的分離不能であるような様々な の例がある。さらには 帰納的可算であるような例が存在する。

  • を部分計算可能関数の標準的なナンバリングとする。このとき とは帰納的分離不能である(Gasarch 1998, p. 1047)。
  • ロビンソン算術の論理式の標準的なゲーデルナンバリングとする。このとき定理の集合 と反定理の集合 は帰納的分離不能である。この事実はロビンソン算術の本質的決定不可能性を導く。他の多くの算術の形式的体系においても同様にして帰納的分離不能対が得られる(Smullyan 1958)。

他方で任意の互いに素な補帰納的可算(Π1)集合の対は帰納的分離可能である。

参考文献

  • Cenzer, Douglas (1999), “Π0
    1
    classes in computability theory”, Handbook of computability theory, Stud. Logic Found. Math., 140, Amsterdam: North-Holland, pp. 37–85, MR1720779
     
  • Gasarch, William (1998), “A survey of recursive combinatorics”, Handbook of recursive mathematics, Vol. 2, Stud. Logic Found. Math., 139, Amsterdam: North-Holland, pp. 1041–1176, MR1673598 
  • Monk, J. Donald (1976), Mathematical Logic, Graduate Texts in Mathematics, Berlin, New York: Springer-Verlag, ISBN 978-0-387-90170-1 
  • Smullyan, Raymond M. (1958), “Undecidability and recursive inseparability”, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik 4: 143–147, doi:10.1002/malq.19580040705, ISSN 0044-3050, MR0099293 

関連項目




英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

帰納的分離不能対のお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



帰納的分離不能対のページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアの帰納的分離不能対 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。

©2025 GRAS Group, Inc.RSS