- ベストアンサー
ZFCで集合を指定する
申し訳ありません、再質問になります、ご容赦ください。 真の算術の任意の文のなす集合や、万能関数Φ(i,X)が停止する入力(i,X)のなす集合は帰納的でないと学んだのですが、これらはどういう意味で集合として存在しているのでしょう。 集合を形成するというのはZFCのような形式体系の言語で記述できるということだと思うのですが、一方で帰納的でないというのはその集合のメンバーであるかを計算する関数が計算可能なレベルにないということですよね。つまりプログラムが書けず要素を集める基準が書けないということではないでしょうか。 実際集めてくることができないものの性質をどうして形式言語で書けるのだろうか？(ほかの集合と区別できる仕方でしかも自然言語の意味に訴えずに書けるのだろうか)というのが質問なのですが、おそらく無理解による勘違いだと思われます。お時間に余裕のあるこの方面に明るい方助けてくだされば幸いです。
- student0201
- お礼率64% (32/50)
- 数学・算数
- 回答数1
- ありがとう数1
- みんなの回答 （1）
- 専門家の回答
質問者が選んだベストアンサー
- ベストアンサー
非構成的証明（要素を1個1個を具体的に指定するようなプログラムは書けない）を普通は認めるからです。集合の定義条件を形式言語に直した時、それが矛盾しなければ何でもOKよ、という事になります。以下は自分の印象です(^^;)。 非構成的で集合にできない有名な条件に、ラッセルのパラドックス（自己言及パラドックス）に現れる、 「自分自身をその要素として含まない集合の集合」 がありますが、次の例だって普通には、ちょっと躊躇すると思うんですよ。 自然数と全単射対応にならない実数の集合は、非構成的（←たぶん正しいと思う）で非帰納的（←自信なし(^^;)）と思いますが、「自然数と全単射対応にならない実数の存在」は、対角線論法で証明されます。 実際に対角線論法を個々の数値相手に実行するようなプログラムは絶対書けませんが、それでもそういう実数の存在を1個でも認めてしまうと（非構成的証明）、集合「x｜xは、自然数と全単射対応にならない実数」は存在する事になります。 「万能関数Φ(i,X)が停止する入力(i,X)のなす集合は帰納的でない」証明は、「対角線論法だ！。自己言及パラドックスを逆手にとりやがったな」と思いませんでしたか？(^^;)。 戸惑うのは帰納的集合だって、普通の感覚ではちょっと躊躇するところです。 自然数全体の集合は帰納的集合の代表ですが（数学的帰納法の発生源）、ペアノ公理系だって、個々の数値相手に実行するようなプログラムとしては無理ですよね。無限回操作が含まれるからです。 という事は、帰納的集合だって職業プログラマーの感覚としては、尋常なものじゃない事になります(^^;)。
関連するQ&A
- ＺＦＣ集合論(公理的集合論)について．
ＺＦＣ集合論の問題をやっています。 集合論はこれまでにまったく習っておらず参考書などで調べながら自分なりに考えてみても混乱するばかりでわかりませんでした． 集合論て難しいですね(^^;) 問題なのですが， 「Ａ＝｛ｘ｜＃ｘ＝１｝はＺＦＣ集合論の意味での集合になるかどうか調べよ」です． 初心者の私でもわかるような解説がありましたら教えてください．
- ベストアンサー
- 数学・算数
- ZFCの論理式の表す内容について
集合論と形式的な論理式の関係についてです、よろしくお願いします。 ZFCで扱われるのは煎じ詰めれば、有限の文字列(∋などを含んだ論理式)だと思うのですが、そんなZFCにより再帰的でない関数や実数から実数への関数全体などのいろいろな無限構造を表現し議論することが多いと感じます。しかし再帰的ですらない関数全体などを有限にすぎない記号列で表現できるのでしょうか。 つまりZFCはどうして十分な高い表現能力を持っているといえるのだろう、ということなのですが。 もちろん、そのような複雑な無限構造も考えたり、思い描いたりすることはできると思いますし、可能ならば数学的に扱えるようにしておくべきだとも思います。 誤解されるかもしれませんが、哲学的な話をしたいわけではありません。そうではなく、フォーマルな意味で有限の形式的な文字列がきちんと意図した構造を表現している、ということは数学的にはどのようにして保証されているのか、ということを伺いたいのです。
- 締切済み
- 数学・算数
- 計算論と集合論における関数について
再質問になっています、ご容赦ください いわゆる計算論において、関数は有限回の帰納的な操作によって記号を別の記号に書き換えること（「ｎ」に「‘」を書き足し「ｎ’」にするなどして）を記号間の関係として定義したモノだと考えています。 そして、集合においても順序対として関数は導入されると思うのですが、 集合論の言葉では関数というのはある性質を持った、対応付けが存在するという風に書かれていると感じます。 この「存在する」という書き方の関数の定義で、上の定義と同様に有限回の操作で、ある対象に対応づけられた対象を特定できるのでしょうか、つまり実際に対応物をどうやって見つけてくるのかを教えてくれないのではないかといったことは問題として発生しないのでしょうか。 もちろん、論理的に問題なければ（人間の意味のレベルで）実際特定可能かどうかは本質的な問題ではないと思うのですが（非可述的定義も許されているわけですし）。 ただ、計算論ではそのような関数は出てこない、帰納的関数を主として扱うようなので、集合論における関数と何か相違点（そういった関数を扱わない理由）があるのだろうかと感じていまして、また逆に集合論では計算論で扱えないような関数も扱っているのだろうかとも思うのです・・・。 そしてもし本当に集合論で扱っている関数がもっと広いものであるならそれはどういうように扱われるのでしょうか（どのようにって集合論側の構文規則に則って扱われるのでしょうが、それで問題などは発生してこないのでしょうか）。 以上の質問で、かなり勘違い、無理解の類が混じっていると思い不安なのですが、もしお時間に余裕ありましたらよろしくお願いします。
- 締切済み
- 数学・算数
- PAの実装としてのZFC
以前類似した質問をしており、また再質問になります、ご容赦ください。 １．PAのモデルには標準的なものと非標準的なものがあり、PA上の論理式では区別できないとよく目にします（だからこそ両方ともモデルといえる訳ですが） しかし、これらのモデルもなんらかの実装で再帰的に定義して扱わないと形式の守備範囲でなくなってしまい、「PAでは」区別できないということが何を表しているか分からなくなってしまうと感じます。 そこでZFCを実装として使うものと理解していたのですがこれは正しい理解でしょうか。 つまり標準モデルNも非標準モデルも 実装としてZFCを使って、再帰的に別々のものとして個々に扱えると考えてよいのでしょうか（再帰的とは文字列間の関係として定義して、というような意味で使っています）。 また上の質問とは関係なくて申し訳ないのですが、もう一つ教えていただきたいことがあります。 ２．算術の言語における理論Kに対して新たに、個体定数cを加え、次の可算無限個の論理式を公理として加える（sは後者関数） c≠0、c≠s0、c≠ss0、c≠sss0、c≠ssss0・・・ そうして拡大した理論をK＋とする などというのを良くみるのですが、 無限個の閉論理式を公理として加えるとは具体的にはどういう意味なのかということです。 理論にいわゆるシェーマというもので実質的に無限個の公理が含まれていることは認められるように感じるのですが、上の書き方では「・・・」の中に何が来るかが記述されてないように見えます（もちろんそれでも何が来るかは分かるのですが、論理式において見る側の類推に任せるというのは問題ではないでしょうか、しかし同時にどのような記述を採ったとしても見る側の類推に一切頼らないなどということはあり得ないのでは？とも感じるのです）。 例えば c≠0、c≠φが公理であるとすればc≠sφも公理である や c≠0、 ∀n（c≠n→c≠s(n)） などとしては意味がかわってしまうのでしょうか。（後者は強すぎる要請になってしまうのでしょうか） 懐疑論のような何を疑問に思ってるのかわかりにくい、そもそも疑問として成り立つのか怪しい質問と思いますが、 この方面に明るい方お時間に余裕があればよろしくお願いします。
- ベストアンサー
- 数学・算数
- 集合に関する証明です。
集合の問題で証明の仕方が分からないので質問させてください。 X,Yは集合,fは関数で f:X→Y, I,Jは添字集合 Ai,i∈IはすべてXの部分集合 Bj,j∈JはすべてYの部分集合 (1)f[∪Ai]=∪f[Ai] (2)f^(-1)[∪Bj]=∪f^(-1)[Bj] (3)f[∩Ai]⊂∩f[Ai] (4)f^(-1)[∩Bj]=∩f^(-1)[Bj) この(1)～(4)の証明です。 宜しくお願いします。
- 締切済み
- 数学・算数
- 基礎論（集合論）の問題が解けません
基礎論の入門書にある問題が解けません。解答がついていないので、教えてもらえればありがたいです。 問題だけを挙げても意味不明になりそうなので、少し前のところから、なるべく丸写ししたいと思います。 以下、問題です。よろしくお願いします。 ＜に関する帰納法（正則性の公理と同等） （注！ 記号が自由にならないので、「ｙはｘの元（要素）である」をｙ＜ｘ、全称量化記号（Ａを逆さまにしたやつ）をＡと表記します） 数学において帰納法といえば、普通は自然数に関する帰納法をいう。 ＜に関する帰納法というのは、集合にも同じような性質があったほうがよいという要請を公理の形で書いたものである。 ＜に関する帰納法とは次のようなものである。 Ａｘ（Ａｙ＜ｘＡ（ｙ）→Ｐ（ｘ））→ＡｘＰ（ｘ） つまり自然数に関する帰納法はｎ－１について成り立つならばｎでも成り立つとき、すべての自然数でも成り立つということであるが、＜に関する帰納法はｙ＜ｘとなるすべてのｙで成り立つならばｘでも成り立つとき、すべての集合でも成り立つということを述べている。 問題 自然数に関する帰納法では０で成り立つことがはじめに必要であるが、＜に関する帰納法ではこのようなものがない。なぜか考えよ。 ヒント：命題論理でｐ→ｑのｐがＦ（＝偽）ならば、この式はいつでもＴ（＝真）であることを思い出せ（そして、ｘ＜φの真偽値がＦであることも）。
- 締切済み
- 数学・算数
- 全順序集合と半順序集合
x=(x1,…xn) , y=(y1,…,yn) ∈R^n に対して x≦yを Σ(i=1からkまで)x(i) ≦ Σ(i=1からkまで)y(i) (k=1,2,…,n) によってR^nに関係≦を導入する。 R^nはこの≦に関して半順序集合になっていることを示せ。 また、x≦(にならない)y , y≦(にならない)x となるx,yの例をあげよ。 という順序集合の問題です。 反射的・反対称的・推移的の3つを示せば良いのは分かるのですが、どのように書いて良のか分かりません。 例：推移的を示す 任意のx=(x1,…xn) , y=(y1,…,yn) , z=(z1,…,zn) ∈R^n に対して Σ(i=1からkまで)x(i) ≦ Σ(i=1からkまで)y(i) かつ Σ(i=1からkまで)y(i) ≦ Σ(i=1からkまで)z(i) ならば Σ(i=1からkまで)x(i) ≦ Σ(i=1からkまで)z(i) は成り立つ。 このように、そのまま書けば良いのでしょうか・・・？ それから、最後の例をあげよのところは、全順序集合にはならないための反例になっているのだと思いますが、どうしても思いつきません。 ∞を考えるのでしょうか・・・？ そもそも全順序集合は半順序集合が成り立つことが前提みたいに習いましたが、反対称的の 任意のa,b∈Xに対して aRb,bRa⇒a=b ここで、aRbとbRaが成り立つことを言ってしまっているので、必ずaRbかbRaになっているような半順序集合は全順序集合という定義も意味がないような気がしてしまいます。 よろしくお願いします。
- ベストアンサー
- 数学・算数
- 絶対値？集合？ どうやって解くのかさっぱりです・・
受験用に数学の問題をしているんですが、以下の問題にお手上げ状態です。 まず、私の疑問点を挙げます。 ？１：絶対値をはずす時、どう考えたら条件で ｘ≦-2 がでてくるんでしょうか？絶対値の中が+2だからですか？ ？２：（２）は文章の意味もよくわかってないのが原因ですが、、、aの値の9/2はどうやって導かれたのでしょうか？？ ぜひ解説をおねがいします！！ 問題： ａを実数とし （ｘ+2）｜ｘ-1｜＝｜ｘ+2｜（ｘ-1）+a を満たす実数ｘの集合をSであらわす。 集合Sの要素の個数を調べるために、関数 ｆ（ｘ）＝（ｘ+2）｜ｘ-1｜-｜ｘ+2｜（ｘ-1） を考える。 （１）この関数は ｘ≦-2 のとき ｆ（ｘ）＝０ -2＜ｘ≦1 のとき ｆ（ｘ）＝-2ｘ＾2-2ｘ+4 １＜ｘ のとき ｆ（ｘ）＝0 である。 （２）よって、Sがただ１個の要素からなるようなaの値は a＝9/2 で、Sがちょうど２個の要素からなるようなaの値の範囲は 0＜a＜9/2 である。また、 a＝0 のとき、Sの要素は無数にある。その他のaの値に対しては、Sは空集合となる。
- 締切済み
- 数学・算数
- 集合の問題！
集合の基礎的な問題です。 わからなくてかなり困っています！ 明日テストがあるので、これらの問題をどうしても理解したいです。 自分で解いてみたのですが、以下のことくらいしかわかりませんでした。 たぶん証明を見れば理解できると思うので、至急回答お願いしたいです。 よろしくお願いします！！>< ＜問題＞ 問１：FがΩの集合体であるとき、次を示せ。 (1)Ω∈F (2)A,B∈Fならが、A⊂B,A＼B,AΔB∈F (3)A1,A2,…,An∈Fならば、∪(i=1,n)Ai,∩(i=1,n)Ai∈F 問２：集合X,Yの濃度が同じである、すなわちX～Yは同値関係であることを示せ。 問３：ベルンシュタインの定理を用いて、次を示せ。 (1){x｜0＜x≦1}～{x｜0≦x≦1} (2){(x,y)｜0＜x≦1,0＜y≦1}～{x｜0≦x≦1,0≦y≦1} (3)a＜bであるとき、[a,b]～R^2 (4)a＜bであるとき、[a,b]～D 但し、D⊂R^2でDは少なくとも１つの内点をもつ。 問４：Fをσ集合体とするとき、以下を示せ。 A1,A2,…,An,…∈F ⇒ ∪(i=1,∞)Ai∈Fとするとき (i)∩(i=1,∞)Ai∈F (ii)lim(n→∞)supAn∈F ※問４は記述がわかりづらいですが、A1から始まる無限大の和集合がFに含まれる、(i)はA1から始まる無限大の積集合である、という意味です。(ii)はn→∞がlimの下にくれば正しい記述になります。問１の(３)の記述も同じくです。 ＜考えたもの＞ 問２：X～Yということから濃度の定義より、XとYの間には全単射がX→Yが存在する。その上で、反射律・対称律・推移率を示せばよい。 という考えまでは至ったんですが、やってみようとしてもここからの証明の仕方というか記述の仕方がわかりません… 問４：（ii)は、lim(n→∞)supAn∈F＝∩(i=1,∞)(∪(i=1,∞)Ai)：上極限集合 なので、これがFに含まれることを証明すればいいんだろうとは思うのですが記述の仕方がいまいちわかりません。(i)もどのように記述していけばよいのでしょうか？ 問１、問３は証明の見通しが立ちません…。 特にこの２つがわからないです。
- ベストアンサー
- 数学・算数
- 再帰的定義と体系の強さ
再質問になります、ご容赦ください。 ［ゲーデルに挑む 田中一之］のp152の記述に、形式的な定義は略記に限るものとし x^0=1 x^(y+1)=x^y・x のような再帰的な(略記でない)定義で論理式を形式体系に付け加えることは公理を増やすことに他ならず体系の強さが変わってしまう可能性がある とあるのですが、これはどういうことでしょうか。 つまり、再帰的定義は記号の使い方を定めているだけであり(上の例であれば、関数記号^の記号としての使い方)、この定義によって初めてその記号が登場してくるならば、それによって体系内で何か新しいことができるようになったりはしないと思うですが...。すなわち定義を追加するだけでは、公理を増やすことにはならず体系の強さも変わらないと思うのです(もちろん、定義するだけでなく、定義した記号に関する公理を追加すれば話は別ですが)。 この方面に詳しい方いらっしゃいましたらお助け下さい、よろしくお願いします。
- 締切済み
- 数学・算数
お礼
回答ありがとうございます。 とても遅くなり申し訳ありません。 記述でき、矛盾しない限り存在を認めるということがよく理解できず、考えておりました。つまりただ書いただけでは、ある性質を持つことにならず、他のモノとの関係の中で性質というのは決まってくると感じるのです。 まだ、きちんとわかってはいないと思うのですが、帰納的集合の関連など大変参考になるました。 ありがとうございました。