数学基礎論の質問スレッド

1 名前：1 [04/10/13 18:26:50] 数学基礎論の質問スレッドが、今、無いようなので、新しくたてました。 ほかに質問のある方、どしどしと、質問してみてください。誰かが、教えてくれることもあるでしょう。 さて、私の質問ですが、 『論理学をつくる』という本の、一階述語論理の公理系の例のところに、 公理として、　∀ξ（ξ=ζ）　　　ξ、ζは個体変項をあらわす図式文字 というものがあがっていました。 公理ということは、恒真式なはずなんだけど、それが、なぜ、恒真式なのかが、わからなくて、疑問におもっています。 どなたか、わかる方、お教えください。 75 名前：１３２人目の素数さん mailto:sage [04/12/12 00:22:34] >>71 > 集合論をどう仮定するんでしょうか。無矛盾性を仮定するんですか？ >> 一階の理論はモデルをもてば無矛盾。 >> 一階の自然数論はモデルをもつ。 >> 一階の自然数論は無矛盾。 これらを、集合論の命題として表現し、集合論の公理の下で証明する。 > 集合論を仮定すれば、どうしてモデルをもつことの証明ができるんですか？ 無限公理があるので楽勝。 >>72 検索した文書の素性を確かめることができない人は、検索をしても時間の無駄だと思う。 76 名前：１３２人目の素数さん mailto:sage [04/12/12 02:16:13] >>75 ありがとうございます。 モデルをもつことの証明には無限集合の存在が重要ということですか。 その理由もどうやって集合論の言葉で書くのかも良く分かりませんね。 たぶんここで説明していただくには膨大すぎるでしょうから、 そういう話が載っている本などをご紹介していただければ嬉しいのですが。 （なるたけ易しく書かれたものなら、なおありがたいです） 77 名前：１３２人目の素数さん mailto:sage [04/12/12 13:35:00] >そういえば、明らかに真になりそうだと思って、実際にそうなるかは確かめたことがありません。 >本にも当然のように、次がモデルとなる、とか書かれていたし・・・。 ぶっちゃけ、反証待ち、それまでは、公然と材料として用いる、ということでよくね？ 78 名前：１３２人目の素数さん mailto:age [04/12/12 23:45:47] >>67 そういうのってどうやって調べたら良いんだろう？ やっぱ原論文の著者名を確認したりしないと駄目？ >>71 集合論が意味を持った理論なら、集合論の言葉を用いて、 「理論Tのモデル」とかの術語が定義できて、 「ある構造（というか集合）がある理論のモデルになっていること」が 定義でき、証明できる、という事です。 究極的には記号の羅列と見做せるような形式的な理論が意味を持つのはなぜだろう？ そもそも本当にそのような理論が意味を持つのだろうか？とかいった疑問は、 分析哲学とかを勉強してくださいです。その種の問題意識は数学の範疇ではありません。 >>72 書いてる人が全然分かってないだけです。不完全性定理とかも多分巷間の トンデモ本程度の理解しかないんでしょう。 ってか誰かこの金沢大学の教員も大変だな。。。 こんなDQNも教えないといけないなんて 79 名前：１３２人目の素数さん mailto:sage [04/12/13 23:41:19] 数学基礎論というのはドイツ語 (それもテクニカルターム) からの翻訳でしょ。 80 名前：１３２人目の素数さん [04/12/14 21:00:57] 数学を発展させたのはデカルト、ライプニッツ、フレーゲ、ラッセル、 ウィトゲンシュタイン、ポパー等の哲学者です 81 名前：１３２人目の素数さん [04/12/15 19:43:30] 嘘コケ馬鹿 82 名前：１３２人目の素数さん [04/12/15 20:55:15] >>72 > 一方、ＡＣと¬ＡＣのうちどちらかは偽の命題です。 > このとき、２つの数学理論ＺＦ＋ＡＣとＺＦ＋¬ＡＣのうちどちらかは、 > 偽の命題を仮定として有する矛盾した数学理論です。 > したがって、ＺＦ＋ＡＣとＺＦ＋¬ＡＣがともに無矛盾ということはあり得ず 83 名前：１３２人目の素数さん [04/12/16 08:08:27] >>78 ん？ページを辿るとこんな文章があるが･･･ wwwhep.s.kanazawa-u.ac.jp/users/tomoya/sikatan/occult/daigo/daigo.htm >これは、数年前にうちの研究室に 匿名で 郵送されてきた文書です。 84 名前：78 mailto:sage [04/12/16 09:37:22] まあじゃあ匿名で郵送した人 （か元の文章を書いた人）が分かってないんでしょう 72の書き方はミスリーディングだと思う 85 名前：１３２人目の素数さん mailto:sage [04/12/16 10:11:45] >>79 つか数学基礎論は日本でも死語 数学者以外の時代遅れの素人が用いてるだけ 86 名前：１３２人目の素数さん mailto:sage [04/12/16 10:24:40] うそつけ 87 名前：１３２人目の素数さん mailto:sage [04/12/16 11:17:03] ってか基礎論自体が時代錯（りゃ 88 名前：１３２人目の素数さん mailto:sage [04/12/16 21:57:23] >>85はさすがに大嘘だな 89 名前：１３２人目の素数さん mailto:sage [04/12/16 23:13:37] 岩波数学辞典の数学基礎論の項目の記述がなかなか面白い。 この意味で使っている人はどれくらいいるのか。 90 名前：１３２人目の素数さん mailto:sage [04/12/17 03:26:27] 自分の専門分野に「数学基礎論 foundations of mathematics」を挙げている数学者。 Harvey Friedman www.math.ohio-state.edu/people/display/display.php?ID=104 Stephen Simpson www.math.psu.edu/simpson/foundations/ Edward Nelson www.math.princeton.edu/~nelson/ 田中一之 www.math.tohoku.ac.jp/~tanaka/myself.html 91 名前：１３２人目の素数さん mailto:sage [04/12/17 03:30:30] Simpson の主張する「数理論理学」と「数学基礎論」との区別 www.cs.nyu.edu/pipermail/fom/2001-January/004712.html 92 名前：１３２人目の素数さん [04/12/21 21:23:14] 質問させてください。 某板棒スレで意見が分かれています。 >ふと思ったがL9999999999999^99999999999999って実際どのくらいの値になるの？  >10の14乗に15掛けたくらいかな。まちがてるとおもうけどそんなもん。  >10の14乗を15乗したくらいだろ  >(10^13-1)^(10^14-1)と考えて二項展開どうかなって思ったけど  >対数をとれば桁数はでるんじゃない？  >それでやったんだけど間違ってるかな、9の数かぞえまちがえたかな。 >普通に10^{13*(10^14-1)}=10^1299999999999987くらいになる希ガス  数学板的な正解はどうなんでしょう？ 93 名前：１３２人目の素数さん [04/12/21 22:00:57] >>78 ７１とかです。遅レスですが、ありがとうございます。 集合論のなかでモデル理論を展開できるということだったんですね。 そういうことの具体的な話は細かく言うとどういう分野に該当するんでしょうか。 少し見た限りでは普通の集合論の本にもモデル理論の本にも載っていないようでした。 （といっても、まだ集合論とかほとんど分からないので、実際に学べるのはもう少し先になりそうですが・・） 何か哲学では、公理の無矛盾性を保証するためには構造が存在しなければならないが、 現実世界に無限的構造の存在を立証することは難しい、といわれたりするそうですが、 なんで現実世界に構造（モデルのことですよね？）が存在すればよいのか、 現実世界にモデルのような抽象概念が存在するとはどういったことなのか、よくわかりませんでした。 基礎論で業績のあるひとでも、こういう哲学の話に興味を持つということからすると、 何かのもっともな根拠があるのに、ぼくが気づいていないだけでしょうか。 94 名前：１３２人目の素数さん mailto:sage [04/12/21 22:07:38] あと、自然数が存在するとか、そうではなくてオメガ列という構造が存在するんだとか、 哲学では言われるようですが、なんで存在を現実世界の意味で捉えるのか良く分かりませんでした。 想定できる、と言っても同じことだと思うんですが。 ペガサスを想像（想定）できますが、べつに現実に存在する必要はないですよね・・。 スレ違いだったらごめんなさい。 ここの見識のある皆さんならどう思われるのか興味があるので・・。 95 名前：１３２人目の素数さん mailto:sage [04/12/21 22:10:42] >>93 根拠というのは問題意識の源泉というような意味合いで用いました。 どういう発想なのだろう、ということです。 96 名前：１３２人目の素数さん [04/12/21 22:31:15] 体 　From：はな(大学3) 04/12/21(Tue) 21:53:12 No. 16081 / 34 [RES] からだの理論を1階の理論として表しなさい 97 名前：１３２人目の素数さん mailto:sage [04/12/22 00:39:27] 　そういうことの具体的な話 おまいさんが先ずもっと具体的に分かるように書いてくれ 意味が分からん あと哲学は、漏れも知らんので哲学板の分析哲学スレにいけ ∀∃　分析哲学総合III　∃∀ academy3.2ch.net/test/read.cgi/philo/1087594214/l50 98 名前：１３２人目の素数さん [04/12/22 22:26:39] >>97 すんません。 集合論を仮定すればモデルの存在が証明できるという話についての具体的な議論を知りたいんです。 レスをお借りすれば、↓のような事柄です。よろしくお願いします。 集合論の言葉を用いて、 「理論Tのモデル」とかの術語が定義できて、 「ある構造（というか集合）がある理論のモデルになっていること」が 定義でき、証明できる、という事です。 99 名前：１３２人目の素数さん mailto:sage [04/12/22 22:27:42] （たぶん今のぼくにはこれ以上具体的に書くことはできないと思います。何とか意を汲み取ってやって下さい・・） 100 名前：１３２人目の素数さん mailto:sage [04/12/22 22:28:00] >>99 101 名前：１３２人目の素数さん mailto: [04/12/23 19:37:29] どなたか、わかる方、お教えください。 102 名前：９８とか [04/12/24 15:53:38] （紛らわしいひとですね・・。９２の中の人ですか・・。） 前原さんの本のクライゼルの注意の箇所をつまみ読みしたんですが、 ロッサーの論理式？を用いて1=0が証明できないことを表した論理式 が証明可能になるのは、無矛盾性の仮定の下でですよね？ 実際、その証明に使われている定理のなかに無矛盾性を仮定して導かれている定理があるので、 無矛盾性を仮定しているように思われるんですが、前原さんは言及していないことが気になります。 他の定理では、いちいち無矛盾性の仮定に言及してあるんで、余計に気がかりです。 しかも、別の部分では、無矛盾性を表すロッサー型の論理式は「つねに証明できる」と書かれています。 ここには、どういった意図があるんですか？ぼくは何か愚かな勘違いを犯してるんですか？ 助言お願いしたいです。 103 名前：１３２人目の素数さん mailto:sage [04/12/24 16:00:57] あと、他の本でクライゼルの注意への言及があるものは見たことがないんですが、 たいして重要なことではないと考えるひとが多いのですか？ 素人目にはびっくり仰天の話だと思うんですが・・・。 それにこの注意を考慮すると、「無矛盾性は体系内で証明できない」 と無制限に主張することはできないと思うのですが、 実際には「」のような書き方がなされていることが多いですよね？ これはどういう観点からなんですか？ いろいろと質問しましたが、部分的にでも答えてもらえれば、ありがたいです。 104 名前：１３２人目の素数さん mailto:sage [04/12/24 16:43:22] >>102 ＞前原さんの本のクライゼルの注意の箇所をつまみ読みしたんですが、 残念ですがそれでは理解できないでしょう。 ＞ロッサーの論理式？を用いて1=0が証明できないことを表した ＞論理式が証明可能になるのは、無矛盾性の仮定の下でですよね？ 私の懸念は的中しました。上の質問の答えは「いいえ」です。 そもそも無矛盾でないなら何でも証明できますから。 ＞無矛盾性を表すロッサー型の論理式は ＞「つねに証明できる」と書かれています。 ええ、その通りです。 ＞ここには、どういった意図があるんですか？ なんの意図もありません。正しいから書いたのでしょう。 ＞ぼくは何か愚かな勘違いを犯してるんですか？ 愚かかどうかはともかくとして勘違いをしています。 断言します。 105 名前：１３２人目の素数さん mailto:sage [04/12/24 16:51:23] ＞あと、他の本でクライゼルの注意への言及があるものは ＞見たことがないんですが、 林晋氏の「パラドックス」には書いてあります。 ただしクライゼルの名前は出していませんが。 ＞たいして重要なことではないと考えるひとが多いのですか？ 重要です。ただし”数学”としてではなく。 ＞素人目にはびっくり仰天の話だと思うんですが・・・。 本当に理解すればあなたの心臓が止まるかもしれません。 ＞それにこの注意を考慮すると、 ＞「無矛盾性は体系内で証明できない」 ＞と無制限に主張することはできないと思うのですが、 そもそも、無矛盾性を体系内で表現できると単純素朴に 考えることができません。林晋氏が「パラドックス」で いいたかったのはそういうことです。 106 名前：１３２人目の素数さん mailto:sage [04/12/24 16:59:36] >>104-105 早速のレスありがとうございます。 レスを手がかりに考え直してみます。 107 名前：１３２人目の素数さん mailto:sage [04/12/24 16:59:45] >>104 でも勘違いなのでしょうか？ 「無矛盾性は体系内で証明できない」というとき、どう書くか? を問題としなければ、矛盾していることがでてきても勘違いじゃ ないんじゃないでしょうか? 108 名前：１３２人目の素数さん mailto:sage [04/12/24 17:01:41] 確かに無矛盾性の過程は要りませんでした。阿呆でした。逝ってきます。 109 名前：１３２人目の素数さん mailto:sage [04/12/24 17:03:36] ＞実際には「無矛盾性は体系内で証明できない」 ＞のような書き方がなされていることが多いですよね？ まあ、そうですね。 ＞これはどういう観点からなんですか？ 例えばゲーデルの定義したBewとロッサー型のBewは 体系が無矛盾であるなら同じ意味ですが、両者の 同値性は、体系内では証明できません。 これがクライゼルの指摘からみちびかれる結論の 真に驚愕すべき点です。 110 名前：１３２人目の素数さん mailto:sage [04/12/24 17:10:46] >>109 林晋は証明論による無矛盾性証明が、クライゼルが指摘するような 別のBew（カットのない証明）を利用している点を問題だと指摘している。 ただし、この場合にはカットのある証明から、それ抜きの証明への 変換を用いており、その手順の停止性の証明は体系内ではできない ので、ゲーデルの第二不完全性定理に抵触するわけではない。 111 名前：１０２とか mailto:sage [04/12/24 17:14:23] 帰ってきました。ちなみに１０７はぼくじゃないです。 ＞そもそも、無矛盾性を体系内で表現できると単純素朴に ＞考えることができません。 そういえば、前原さんも「数値別に正確に表現しているわけではない」と書いておられました。 林さんの本も読んでみます。いろいろとありがとうございました。 どなたとどなたが同一なのか分かりませんが、レスをくれた方にはすべて感謝したいです。 （なんかもう110さんみたいな賢者がでてくるなんて、2chはすごすぎる・・・） 112 名前：１３２人目の素数さん mailto:sage [04/12/24 17:25:27] >>107 ＞どう書くか? を問題としなければ、 そう。まさにそこが問題であると林晋は言っている。 しかし、それはもはや”数学”の問題ではない。 はっきりいえば、数学よりももっと根本的な 言語とそれを用いる自分にかかわる”哲学” の問題である。 113 名前：１３２人目の素数さん mailto: [04/12/29 05:50:41] どなたか、わかる方、お教えください。 114 名前：１３２人目の素数さん [05/01/02 23:36:49] 651 115 名前：１３２人目の素数さん [05/01/05 13:15:52] 自然数の和と積に関する理論（いわゆる、ロビンソン算術）を作りたい、と考えて、 まず、語彙、項、論理式の定義を設定する、と、 これで、論理式はつくることができる、と、 で、その論理式が、自然数の和と積に関する一連の内容を表現できるように、と、モデルを設定する、と、 これで、十分なんじゃないか、と、 なんで、公理系をつくるんだろう？、と、 具体的に、論理式の集まりを把握したい、という目的とか、 その理論の意味論的完全性を示せば、その理論の公理系で証明できることを示すことによって、 すなわち、（意味論的に）真である、が言える（別にいらんなぁ）、とか、 そこらへんの目的からっすかね？ 誰か詳しい人、教えてください 116 名前：１３２人目の素数さん mailto:sage [05/01/05 13:25:25] >>115 意味不明。公理系も無いのに、モデルが作られるか。 117 名前：１３２人目の素数さん mailto:sage [05/01/05 15:15:51] >>116 確かに、115のいうモデルは、数理論理学でいう それとは異なるようだね。 115は漫然とモデルという言葉を使わずに 全く別の言葉で説明するように。 118 名前：１３２人目の素数さん mailto:sage [05/01/05 15:20:25] ところで115は、ロビンソン算術の命題が どんなものか知っているのかな？ 119 名前：１３２人目の素数さん mailto:sage [05/01/05 15:29:38] １１５はのいうモデルはモーデルのことだな。 120 名前：１３２人目の素数さん [05/01/05 16:08:38] >>116 なんといったらいいのか、意味論的な諸設定とでも、いいましょうか、 115で言いたかった内容を、もう一度繰り返すと、 まず、語彙、項、論理式の定義を設定する、と、 これで、 #a＋##a＝###a #　後続者関数、 項、論理式の定義は、ロビンソン算術とよばれているもののそれと同じいうことで という論理式がつくれる、と、 で、 これに 一足す二は三 という内容をもたせるべくして、意味論的な諸設定（論議領域に自然数を設定したり、個体定項aに自然数0割り当てたり、関数に付値したり、・・　ここんところを、115では、モデルという語を用いてあらわしました）、を設定する、と、 これで、いいじゃん、と、（他の命題の表現についても、同様。で、これをもって、自然数の和と積に関する理論、ということでいいじゃん、と） 以下、115の内容へと続く 121 名前：１３２人目の素数さん mailto:sage [05/01/05 17:10:36] ＞論議領域に自然数を設定したり 簡単にいうけど、そもそも自然数全体が 無限個あるってことが問題なわけなんだけど。 単純に列挙なんかできないよ。どうするの？ 122 名前：１３２人目の素数さん mailto:sage [05/01/05 20:51:33] つーか、だって、それが、一階の理論の意味論なんやねんもん、 そんなところ批判されたって、言葉につまるというか、 最初に言い出した奴に言ってくれというか、 違うねん、そういうところにひっかかると、話が遠ざかってしまう。 そうじゃなくて、 ロビンソン算術の意味論は、上でも言ってるように、論理式に、意味みたいなもん、与えてくれてる。 これは、この理論が、自然数の和と積というものを表現しようとしているかぎり必要、ということはわかる。 俺が聞いてるのは、じゃあ、構文論とか、形式的体系（公理系）は、自然数の和と積を表現しようとしたやつに、 いったい、何を与えてくれてんねん、ということ、 123 名前：115とか mailto:sage [05/01/05 21:15:36] ごめんごめんごめんごめん 自爆、 よくよく考えてみると、いるな、公理系、 上での書き方もまずかった、 なんか、標準モデルひとつおいて、意味論、みたいな書き方してる あほや、俺 ごめん、質問、なかったことにしてください・・逝ってくる・・ 124 名前：１３２人目の素数さん [05/01/07 17:01:17] 自然数の公理系Nが無矛盾であるなら、その肯定形も否定形もNで証明できないようなNの閉じた式が存在する ということらしいですが、 その肯定形も否定形もNで証明できないようなNの閉じた式を仮定された論理式としてその形式的体系に設定した場合、 形式的体系の無矛盾性は崩れて、Nの任意の論理式を演繹することができる、ということであってますか？ 125 名前：１３２人目の素数さん [05/01/07 17:28:26] >>124 矛盾することはない。 ふたたび別の論理式が決定不能になる。（証明を学べば簡単に分かる） 126 名前：１３２人目の素数さん mailto:sage [05/01/07 18:24:07] >>125さんの言うとおりです Nは公理を勝手に増やしたり増やしたりしたらN'≠Nになってしまいます。 つまり、証明能力が変わってしまうと言うことです。当たり前ですね。 でもN'にも（一気に無限種類の公理を考えたりする荒業をしなければ） 閉論理式でN'から独立なものは存在します。（NにN'を代入するだけ） 127 名前：１３２人目の素数さん mailto:sage [05/01/07 19:08:16] >>125 >>126 ある「その肯定形も否定形もNで証明できないようなNの閉じた式」を、形式的体系に加えようとも、 まだ、他に、その形式的体系にとって、「その肯定形も否定形もNで証明できないようなNの閉じた式」はある、ということでしょうか？ 128 名前：１３２人目の素数さん mailto:sage [05/01/07 19:51:01] うん。 N'で証明できない式はNでも証明できないからね。 ちなみに、 公理の集合Σからφが証明できない ⇔Σ∪{¬φ}は無矛盾な公理系 だけどこういうことはご存知ですよね？ 129 名前：１３２人目の素数さん mailto:sage [05/01/07 20:09:15] Σの無矛盾性を仮定するのを忘れておったわ ハァッハッハハハ 130 名前：１３２人目の素数さん mailto:sage [05/01/08 00:30:53] はい。 ところで、 ＞（一気に無限種類の公理を考えたりする荒業をしなければ） 一気に、すべての「その肯定形も否定形もNで証明できないようなNの閉じた式」を考える、ということですか？ 131 名前：１３２人目の素数さん [05/01/08 00:39:51] まあ大体そういうことですー より正確に知りたい場合はrecursively enumerableとか そういう言葉をキーワードに件の定理を勉強してくださいですー 132 名前：１３２人目の素数さん mailto:sage [05/01/08 02:29:38] もうちょっと、集合論とか証明論とか、勉強してみます。 ありがとうございました。 133 名前：１３２人目の素数さん [05/01/10 20:11:30] ググった、先のサイトで、こんなのを見つけました。 ＞ある数学的構造に対して完全な公理系が見つかれば，その構造における命題の真偽は決定可能である． ＞ゲーデルが１９３０年に発見した第一不完全定理は，自然数論を含むどんな公理系も完全でなく，また決定可能でないというものである． ＞命題の真偽は決定可能である． というのは、、命題の、真である・真でない（意味論的な真理値）を決定できる、ということですか？ 134 名前：１３２人目の素数さん mailto:sage [05/01/10 20:20:34] >>133 決定可能というのはあるアルゴリズムによって有限回の計算で求められるということ。 135 名前：伊丹公理 ◆EniJeTU7ko [05/01/10 23:36:57] >>133 ＞ある数学的構造に対して完全な公理系が見つかれば，その構造における命題の真偽は決定可能である． 完全な公理系では、公理が有限個なら、全ての論証を列挙する事によって、 真理値が有限回の計算で求められるが無限個なら一般には分からない。 しかし多くの場合帰納的可算であるから、決定可能。 136 名前：１３２人目の素数さん [05/01/11 00:25:36] だから一言で言えばYesだね。 もちろん誰も貴方の家のPCとか東大工学部にあるスパコンとかで 1000万年内に求まる、とかそういう保証はしてないですからね。 137 名前：１３２人目の素数さん [05/01/11 00:36:36] >>135 本物？だとしたら勇み足だよー 第一不完全性定理はチョー厳密に言えば、 r.e.（c.f. >>131 再帰的枚挙可能とか帰納的可算と訳す） 公理化可能な無矛盾な公理系でPeano算術（本当はそれより弱いRobinson算術QでOK） を含むものは（「含む」の意味もきちんと定義できます。）不完全、とか言う定理 です。で、普通数学の理論は自然数論を含みますしr.e.axiomatizableですから、 不完全、かつ決定不可能です。 というわけで、参考文献二つだけ。 　Computability and Unsolvability (Mcgraw-Hill Series in Information Processing and Computers.) Martin Davis (著) ペーパーバック (1982/11/01) Dover Pubns Aspects of Incompleteness (Lecture Notes in Logic, 10) Per Lindstrom (著) ペーパーバック (2003/11) A K Peters Ltd 　Godel's Incompleteness Theorems (Oxford Logic Guides, No 19) by Raymond M. Smullyan 一番上のほうの本は和訳もあります。計算可能性理論の古典。 一番下は和訳は訳語が酷いので、英語でベンキョーした方がむしろわかりやすいでしょう。 138 名前：１３２人目の素数さん [05/01/11 00:40:10] と思ったが、「完全な公理系」は多くの場合、r.e.だといってるのかな？ それなら正しいですね。 実際に人間が扱う理論（代数トポロジーとか無限次元Hilbert空間論とか 概均質ベクトル空間論とか、まあ何でも）は全てr.e.ですよ。 r.e.じゃない理論なんて、集合論を使って無限個の公理を一気に付け加えて、 とかそうやって作ったよう分からん理論です。 139 名前：１３２人目の素数さん mailto:sage [05/01/11 09:16:41] >>138 ところで 人間が扱い得る＝r.e.(recursively enumerable) かどうかは、未だ解決されていない。 140 名前：１３２人目の素数さん mailto:sage [05/01/11 13:48:54] ところで、 Robinson算術Q（構文論的不完全な公理系の例として）は、 再帰的枚挙可能.（recursively enumerable）だが、再帰的 (recursive)ではない、ということであってますか？ 141 名前：１３２人目の素数さん [05/01/11 21:10:26] >>140 そんな質問をするのは再帰的を理解していない証拠。よぉくかんがえてみろ、自明だぞ。 142 名前：１３２人目の素数さん [05/01/12 00:00:08] 学んでる途中の者が、質問というよりは、確認の目的で書き込んだことなので、 あんまり気にせずに、 さくっと、もしくは、さらっと、流してください ＞自然数もしく有限の記号列の集合が r.e.（recursively enumerable, 再帰的に枚挙可能）であるというのは，その要素をすべて並べあげる機械的な手続きがあることをいう． ＞r.e.集合で，その補集合もr.e.になるものを，再帰的 (recursive)という． というのを、上のググッた先で見ました。 例えば、構文論的完全な公理系の要素の集合、その補集合（全体集合は任意の論理式の集合）もr.e.になるので，再帰的 (recursive)、 ということか？という感じで読んでいましたが、 いまひとつ、確証が持てなかったので、上のように、書き込んでみました。 143 名前：１３２人目の素数さん mailto:sage [05/01/12 00:12:25] >>141 Q の「公理」全体の集合は有限集合なので、もちろん再帰的だけれど、 Q の「定理」全体の集合が再帰的かどうかも自明？ 144 名前：伊丹公理 ◆EniJeTU7ko [05/01/12 00:13:50] >>137 公理系が完全と言う前提での話し。 145 名前：１３２人目の素数さん mailto:sage [05/01/12 00:46:41] >>142 ちゃんと本読んで勉強したほうが速いよ >>143 定理の集合をTh_Qとでも置けば、φ∈Th_{Q}かどうかは、 計算機を使って証明をゲーデル数の少ない順に虱潰しに調べていって 証明B_g（gはゲーデル数）がφの証明になっているかどうか確かめればよいから 明らかに再帰的でしょ >>144 そうなのか、ｽﾏｿ。 モデル理論にあまり詳しくないが、実体の理論とかのことでしょうね。 146 名前：143 mailto:sage [05/01/12 00:57:00] >>145 それは、再帰的に枚挙可能なことの証明。 147 名前：１３２人目の素数さん [05/01/12 01:00:34] だったっけ…… ホントだ、recursiveな函数の定義域ですからね。 いや、『数学基礎論講義』で勉強したことはあるんですが、 どうもよく一章のその部分は分からなかったんですよ。 『帰納的関数と述語』も去年の春休み頃だいぶ読んだんですが、 もう忘れてしまっていて…… 欝出し脳orz 148 名前：１３２人目の素数さん [05/01/12 01:15:48] 公理が「有限個」と言うときは、公理シェーマは一つとして数えるのが普通ですか？ 149 名前：１３２人目の素数さん mailto:sage [05/01/12 01:19:17] 知らんがなｗｗｗ ただ、実質的に公理図式と言うのは、無限個の公理と言っても 一つの規則で、普通人間は、無限個の公理がある、という意識はあまり持たないですよね。 そういったことにきちんと数学的な説明を与えるために axiom schemeとかrecursiveとか、そういう用語があるわけです。 150 名前：１３２人目の素数さん mailto:sage [05/01/12 01:26:57] すんません 誰か ＞自然数もしく有限の記号列の集合が r.e.（recursively enumerable, 再帰的に枚挙可能）であるというのは，その要素をすべて並べあげる機械的な手続きがあることをいう． ＞r.e.集合で，その補集合もr.e.になるものを，再帰的 (recursive)という． について、コメントお願いします。 レスの流れを、見ていましたが、いっそう、 再帰的(recursive)というものが、どういうものか、わからなくなってきました。 Qは再帰的なんですか？ ちなみに、おおもとはここからです。 ttp://members.at.infoseek.co.jp/nbz/ref/hprogram.html 151 名前：１３２人目の素数さん [05/01/12 01:27:12] ありがとうｗｗｗ 152 名前：１３２人目の素数さん [05/01/12 01:28:35] >>150 再帰的は決定可能と同じだよ。 153 名前：１３２人目の素数さん mailto:sage [05/01/12 01:32:16] Qは決定不可能ですよね、 じゃあ、Qは再帰的ではない、ということですか？ 154 名前：１３２人目の素数さん [05/01/12 01:35:59] 女の子はうんこをしないように　Ｑは再帰的ではない 155 名前：143 mailto:sage [05/01/12 01:39:07] >>153 不完全性定理の文脈での決定不能命題の定義と、 公理系 T が決定可能であることの定義を復習しましょう。 これらは全く別の概念です。 156 名前：１３２人目の素数さん [05/01/12 01:40:45] 学んでいないものを復習することはできない。 157 名前：１３２人目の素数さん mailto:sage [05/01/12 01:51:46] >>143で言ってる再帰的と >>150で言ってる再帰的とは、別の内容ですかね？ 158 名前：１３２人目の素数さん [05/01/12 01:54:06] >>157 １４３は帰納的の意味ですね。 159 名前：１３２人目の素数さん mailto:sage [05/01/12 01:58:04] 帰納的の意味というのは、 再帰的に枚挙可能というやつですか？ 160 名前：１３２人目の素数さん mailto:sage [05/01/12 02:05:34] recursive＝帰納的＝再帰的 ただ、最初（一般帰納関数の概念が出てくる前）は primitive recursiveのことを単にrecursiveといっていたので注意。 161 名前：１３２人目の素数さん mailto:sage [05/01/12 02:09:19] 公理から、ある命題もその否定も導かれないならば どっちが正しいか決めることは出来ませんね。 たとえば連続体仮説のように。 というか、マジで自分で勉強しろって。 河合文化教育研究所の数学基礎論シリーズの 0巻か1巻が、丁寧に書いてあってお勧め。 （もちろん0巻は1,2巻の内容の概説なので 途中の議論は一部飛ばされています。） 162 名前：１３２人目の素数さん [05/01/12 02:15:12] >>161 そんな誤植だらけの絶版本を薦めるなよ。 163 名前：１３２人目の素数さん [05/01/12 06:17:50] いや、良く読んでないから誤植と言われても良く分からんのだが、 （0巻は集合論以外は読んだ。1巻は読んでない。持ってるだけ） 0巻『数学基礎論へのいざない』は寝転んで読む分には 最適だと思うのだがどうよ？内容は古いけどさ。 ってか絶版になってたっけ？ >>162さんは代わりとしては何を薦めるんですか？ 164 名前：１３２人目の素数さん [05/01/12 11:57:08] >>155 ズバリ言ったら？ 定理の全体がr.e.というのと、 公理の全体がr.e.というのとは違う、ってさ。 r.e.公理化可能って後者のことでしょ？ 165 名前：１３２人目の素数さん mailto:sage [05/01/12 17:13:13] チョー要約すると 公理かどうかはごく簡単に判定できるし、定理は公理から 帰納的に（段階的に）定義されるものだけど、定理かどうかの 判定は非常に難しい、ということね。 166 名前：１３２人目の素数さん mailto:sage [05/01/12 17:31:22] >>165 ＞公理かどうかはごく簡単に判定できる r.e.公理化可能といっても、 一般に公理かどうかの判定は 不可能だと思うぞ。 recursiveじゃないからな。 167 名前：１３２人目の素数さん [05/01/12 21:44:31] >>166 そういう体系（公理がreでnon-recursive）の例はどんなものがあるんですか？ 168 名前：１３２人目の素数さん mailto:sage [05/01/13 02:39:24] >>167 多くの体系では、定理全体が r.e. で recursive でないのだから、 いくらでも作ることができる。 こういう話での基本的なトリックに、r.e. な公理系を持つ体系は、 recursive な公理系が存在するという結果がある。 169 名前：１３２人目の素数さん [05/01/13 18:17:04] >>168 ありがとうございます。定理全体を公理にすればよいんですね。 170 名前：１３２人目の素数さん mailto:sage [05/01/14 02:14:04] もっとくだらない例。 トートロジー A をひとつ固定し、An = A∧A∧...∧A (n個) と定める。 r.e. だが recursive でない自然数の集合 S に対し、 { An | n∈S } は r.e. だが recursive でない公理系。 171 名前：１３２人目の素数さん mailto:sage [05/01/14 19:20:56] >>170 は、明らかに recursive 172 名前：１３２人目の素数さん [05/01/17 03:32:37 ] なぁなぁみんな cot(x) ってなんだ？ 173 名前：１３２人目の素数さん [05/01/17 03:44:59 ] >>172 市ね 174 名前：１３２人目の素数さん [05/01/17 03:45:29 ] >>172 いやマジで聞いてるんだが 175 名前：１３２人目の素数さん mailto:sage [05/01/17 23:55:52 ] 高校生スレにGO！

---

---

[ 続きを読む ] / [ 携帯版 ]

read.cgi ver5.27 [feat.BBS2 +1.6] / e.0.2 (02/09/03) / eucaly.net products.
担当:undef