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

質問

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

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

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

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

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

回答No.3

itshowsun

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

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

お礼

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

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

回答No.2

stomachman

> 実際に対応物をどうやって見つけてくるのかを教えてくれないのではないか

　その通りです。

> 集合論における関数と何か相違点（そういった関数を扱わない理由）があるのだろうかと感じていまして

　計算論で扱う関数は、要するにプログラムが書ける関数です。そのプログラムの文字列を「ゲーデル数」の仕掛けを使って自然数に対応付けることを考えればわかるように、そのような関数は高々可算無限個しかありません。だから、計算論で扱えない関数がいくらでもあることは最初から明らか。

> 集合論で扱っている関数がもっと広いものであるならそれはどういうように扱われるのでしょうか

　ご質問で「順序対」と仰っている通り、「f(x)とは、<x,y>∈fである唯一のyのこと」という風にです。

> それで問題などは発生してこないのでしょうか

　何を以て「問題」と言うかです。たとえば、計算できないことを指して「問題」と言うのなら、問題のある関数だらけです。

> 実際特定可能かどうかは本質的な問題ではない

　本質的な問題にする場合もある。計算論はその一例ですね。

お礼

回答ありがとうございます。ずっと返すことができず申し訳ありませんでした。

確かにプログラムがかける関数は高々可算無限個しかないということはわかるのですが、非可算無限個の関数があってそれが集合論の中に存在し集合論の中でかけるというのはどこからの視点なのでしょうか。
（関数を数えて高々可算無限個しかないということを言う視点がもうすでにメタ的な訳ですが・・・）
集合論も可算個の記号で書かれたものであるはずなのにその中である無限集合間に全単射の対応が存在しないということがいえるということが腑に落ちないのです。形式体系の中で１：１の対応が存在しないを意味するであろう文字列を生成できるということなら記号は可算個でも問題はないと感じるのですが、スコーレムの定理を考えると非可算無限個であるということを保証するのはどの体系からみてのことなのかということが依然モヤモヤとしたままなのです・・・。つまりある体系内で１：１の対応を付けられないものが存在すると言えても、その外に出た視点からすると外の体系では依然１：１対応は付けられると言えるなら、そのことが繰り返されて結局真の（とでもいいましょうか）非可算無限などというものはどこにあるといえるのか、とはならないのでしょうか。おそらくメタレベルと対象レベルを混同しているせいだとは思うのですが・・・。

この度は本当にありがとうございました。参考にして参りたいと思います。

回答No.1

Tacosan

ふつうに「ある性質を持った対応付け」とするだけで「計算できない関数」もそのまま扱えます. 少なくとも「集合」の意味では全く問題ありません.

例えば, ポストの対応問題は簡単に書けるよね.

お礼

ありがとうございます。
問題はないのですね、ただ計算できない関数も集合としては記述できるという風になぜ二つの間に段差ができてしまうのか、などとやはり内容と形式について自分にはわからないことが沢山あるようで、もっと勉強していきたいと思います。

回答助かりました、参考にさせていただきます。