計算論と集合論における関数について

質問

再質問になっています、ご容赦ください

　いわゆる計算論において、関数は有限回の帰納的な操作によって記号を別の記号に書き換えること（「ｎ」に「‘」を書き足し「ｎ’」にするなどして）を記号間の関係として定義したモノだと考えています。

　そして、集合においても順序対として関数は導入されると思うのですが、
集合論の言葉では関数というのはある性質を持った、対応付けが存在するという風に書かれていると感じます。
　この「存在する」という書き方の関数の定義で、上の定義と同様に有限回の操作で、ある対象に対応づけられた対象を特定できるのでしょうか、つまり実際に対応物をどうやって見つけてくるのかを教えてくれないのではないかといったことは問題として発生しないのでしょうか。
　もちろん、論理的に問題なければ（人間の意味のレベルで）実際特定可能かどうかは本質的な問題ではないと思うのですが（非可述的定義も許されているわけですし）。

　ただ、計算論ではそのような関数は出てこない、帰納的関数を主として扱うようなので、集合論における関数と何か相違点（そういった関数を扱わない理由）があるのだろうかと感じていまして、また逆に集合論では計算論で扱えないような関数も扱っているのだろうかとも思うのです・・・。
そしてもし本当に集合論で扱っている関数がもっと広いものであるならそれはどういうように扱われるのでしょうか（どのようにって集合論側の構文規則に則って扱われるのでしょうが、それで問題などは発生してこないのでしょうか）。

　以上の質問で、かなり勘違い、無理解の類が混じっていると思い不安なのですが、もしお時間に余裕ありましたらよろしくお願いします。

回答No.3

itshowsun

こんばんは、
質問を読んで思ったのは、考え方が逆ではないかということです。
ある関数または論理式が決定可能であるのは、
その変数たちと関数値がどの集合に属するのか決定可能である時です。
または集合によってその関数が構成できる時です。
例えば、f(x) = 2x + 1 なる関数を考えると、
整数（という集合）1 を x に代入すると、整数 3 を得る。
整数 2 を x に代入すると、整数 5 を得る。
・・・・・
このような処理というのは、定義域と値域を整数という集合としたとき、
上の関数に対応する具体的な集合の要素たちの対応を列挙しているに他ならない：
1→3
2→5
・・・・・
これに問題がないとき、私たちは f(x) が決定可能であると言えるのでは？

集合の1つの要素をどうやって見つけるのか？
もしそのような疑問を持っているならば、
少なくともZFC集合論を勉強すべきでは？
特にZFCのCは選択の公理を意味し、
集合から任意の要素を選択する方法（選択関数）が存在することを保証している。
この辺のところはキチンと集合論をやらないと理解できない。
（私なんかはやっても、まだ理解できていない。）

お礼

ありがとうございます。遅れてしまい申し訳ありません。

たしかに集合論を勉強せねばとは考えているのですが、私の疑問はその前のところにあるように思うのです。
回答のように集合を下地に関数を考えるというのは確かに筋の通った思考だと思うのですが、では集合とはどのような身分であって（どのように記述され）、どのようにしてその性質を決定されるのかということが同様の問題になると感じます。つまり集合はＺＦＣの公理を含んだ一階論理で書かれる文字列間の関係の中にその性質を表す何かであるはずなのですが、ならばその文字列操作の中に存在するもの（集合）によって計算論では扱えない関数を存在させそれ扱うということがなぜ可能なんだろうかという疑問が出てくるのです（計算論では記号変形によって扱うことができるのものは対象になるはずなので）。
回答ありがとうございました。もっと勉強していきたいと思います。