ZFCで集合を指定する

質問

申し訳ありません、再質問になります、ご容赦ください。
真の算術の任意の文のなす集合や、万能関数Φ(i,X)が停止する入力(i,X)のなす集合は帰納的でないと学んだのですが、これらはどういう意味で集合として存在しているのでしょう。

集合を形成するというのはZFCのような形式体系の言語で記述できるということだと思うのですが、一方で帰納的でないというのはその集合のメンバーであるかを計算する関数が計算可能なレベルにないということですよね。つまりプログラムが書けず要素を集める基準が書けないということではないでしょうか。

実際集めてくることができないものの性質をどうして形式言語で書けるのだろうか？(ほかの集合と区別できる仕方でしかも自然言語の意味に訴えずに書けるのだろうか)というのが質問なのですが、おそらく無理解による勘違いだと思われます。お時間に余裕のあるこの方面に明るい方助けてくだされば幸いです。

回答No.1

noname#221368 · ベストアンサー

非構成的証明（要素を1個1個を具体的に指定するようなプログラムは書けない）を普通は認めるからです。集合の定義条件を形式言語に直した時、それが矛盾しなければ何でもOKよ、という事になります。以下は自分の印象です(^^;)。

　非構成的で集合にできない有名な条件に、ラッセルのパラドックス（自己言及パラドックス）に現れる、

　　「自分自身をその要素として含まない集合の集合」

がありますが、次の例だって普通には、ちょっと躊躇すると思うんですよ。

　自然数と全単射対応にならない実数の集合は、非構成的（←たぶん正しいと思う）で非帰納的（←自信なし(^^;)）と思いますが、「自然数と全単射対応にならない実数の存在」は、対角線論法で証明されます。

　実際に対角線論法を個々の数値相手に実行するようなプログラムは絶対書けませんが、それでもそういう実数の存在を1個でも認めてしまうと（非構成的証明）、集合「x｜xは、自然数と全単射対応にならない実数」は存在する事になります。

　「万能関数Φ(i,X)が停止する入力(i,X)のなす集合は帰納的でない」証明は、「対角線論法だ！。自己言及パラドックスを逆手にとりやがったな」と思いませんでしたか？(^^;)。

　戸惑うのは帰納的集合だって、普通の感覚ではちょっと躊躇するところです。

　自然数全体の集合は帰納的集合の代表ですが（数学的帰納法の発生源）、ペアノ公理系だって、個々の数値相手に実行するようなプログラムとしては無理ですよね。無限回操作が含まれるからです。

　という事は、帰納的集合だって職業プログラマーの感覚としては、尋常なものじゃない事になります(^^;)。

お礼

回答ありがとうございます。
とても遅くなり申し訳ありません。
記述でき、矛盾しない限り存在を認めるということがよく理解できず、考えておりました。つまりただ書いただけでは、ある性質を持つことにならず、他のモノとの関係の中で性質というのは決まってくると感じるのです。
まだ、きちんとわかってはいないと思うのですが、帰納的集合の関連など大変参考になるました。
ありがとうございました。