• 締切済み

再帰的定義と体系の強さ

再質問になります、ご容赦ください。 ［ゲーデルに挑む 田中一之］のp152の記述に、形式的な定義は略記に限るものとし x^0=1 x^(y+1)=x^y・x のような再帰的な(略記でない)定義で論理式を形式体系に付け加えることは公理を増やすことに他ならず体系の強さが変わってしまう可能性がある とあるのですが、これはどういうことでしょうか。 つまり、再帰的定義は記号の使い方を定めているだけであり(上の例であれば、関数記号^の記号としての使い方)、この定義によって初めてその記号が登場してくるならば、それによって体系内で何か新しいことができるようになったりはしないと思うですが...。すなわち定義を追加するだけでは、公理を増やすことにはならず体系の強さも変わらないと思うのです(もちろん、定義するだけでなく、定義した記号に関する公理を追加すれば話は別ですが)。 この方面に詳しい方いらっしゃいましたらお助け下さい、よろしくお願いします。

みんなの回答

  • jcpmutura
  • ベストアンサー率84% (311/366)
回答No.1

x^0=1 は xと0の演算^の結果x^0を1と定義するのだけれども それ以前にxが定義されていないので xをある数とします x^(y+1)=x^y・x は xとyの演算^の結果x^yが定義されているとき に限り xとy+1の演算^の結果x^(y+1)をx^yとxの積x^y・xと定義する のだから それ以前にx,y,x^yの3つがともに定義されていなければなりません それ以前に定義されているのは xはある数 x^0=1 なので y=0 となるので x^(y+1)=x^y・x は x^1=x^0・x=1・x=x となりますが 形式上再度 x^(y+1)=x^y・x を繰り返す指定が省略されているとはいえないので x^0=1 x^1=x の2つを定義しただけで定義終了となって 再帰的定義とならないと思います。 x^0=1 for(k=0～y-1)x^(k+1)=x^k・x のように 繰り返し指定記号for()とその意味を 追加すれば xとyの演算^の結果x^yの 再帰的定義となると思います。

student0201
質問者

お礼

ありがとうございます、本当に遅くなってしまい申し訳ありません。 x^(y+1)をX^y+xに書き換えてよいということなら新しい公理をいれていることになるのですね。

  1. カテゴリ
  2. 学問・教育
  3. 数学・算数

関連するQ&A

  • ゲーデルの不完全性定理

    ゲーデルの不完全性定理の証明のアイデアが知りたいと思い、適当な入門書(基礎論の教科書ではないです。)を読んでいるのですが、 まず、定理の主張が「形式的体系Tで通常の自然数を含み、強い意味で無矛盾であり、そこにおける公理や推論規則は帰納的に定義されているかまたはその数が有限であるようなもの、においては文GでGも￢Gも証明できないものが存在する。」 とあるのですが、形式的体系Tがなにを意味しているのかがよくわかりません。これは、形式的と書いてあるのだから文字通り「意味を考えない記号の世界(記号の集まりと、記号を並べて得られる列を変形するいくつかの規則)」と考えればよいのでしょうか？ それで、もう一つ質問があるのですが、 まず、準備として記号 ￢,∧,∨,→,∃,∀,(,),0,',+,×,=,x,y,zを用意して、 x,y,zを変数記号と呼びます。 それで、項を次のように定義します。 (i) 0,x,y,zは項。 (ii) t,sが項であるとき、'(t),+(t,s),×(t,s)は項。 (iii)このようにして得られるものだけが項。 (iV)'(t),+(t,s),×(t,s)を簡単にそれぞれt',t+s,t×sと記したりする。また、0',0'',0''',…をそれぞれ1,2,3,…と記す。 また、項tを上の記号の括弧としてではなく、見易さのための補助記号としての(,)を用いることにより、しばしばt(x,y,z)と記したりする。 次に論理式を次のように定義します。 (i)t,sが項のとき、t=sは論理式。 (ii)φとψが論理式でxが変数記号のとき、(￢φ),(φ∧ψ),(φ∨ψ),(φ→ψ),(∀xφ),(∃xφ)は論理式。 (iii)このようにして得られるもののみが論理式 (iV)見易さのために括弧を適当に省略して論理式を記すこともある。 以上により、与えられた記号列が項か論理式かそれ以外のものか判定できるようになります。 準備した記号￢,∧,∨,→,∃,∀,(,),0,',+,×,=,x,y,zを普通に解釈することで、論理式の意味を考えることができるようになります。 ただし、'は後者関数と解釈します。 次に、￢,∧,∨,→,∃,∀,(,),0,',+,×,=,x,y,zに 素数2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53を割り当てます。 記号列が与えられたとき、各記号を上記の対応に従い素数n_1,n_2,n_3,…に置き換え、2^(n_1)*3^(n_2)*5^(n_3)*…を対応させます。対応する数をゲーデル数と呼びます。 以上で準備は終わりで、 質問ができるのですが、 「mがTのある論理式のゲーデル数である」という非形式的な主張は mを素因数分解して各素数の指数を調べることである論理式のゲーデル数であるかどうかがチェックできるので、解釈すると「mがTのある論理式のゲーデル数である」という意味になる論理式が作れる、とあるのですが"具体的"にはどのようにして作るのでしょうか？ 私は、論理式の定義が再起的であるから、「mがTのある論理式のゲーデル数であるかどうか」をコンピュータに判定させること(とてつもなく時間がかかりそうですが)可能だと思うので上のような論理式は作れると思うのですが、実際に作るとどんな論理式になるのか興味があります。

  • 私がよく分らないのは　ゲーデルの第１不完全性定理です。『形式的体系Ｓに

    私がよく分らないのは　ゲーデルの第１不完全性定理です。『形式的体系Ｓにおいて、形式的体系Ｓが無矛盾である限り、「形式的体系Ｓにおいて命題は証明可能である。」という命題も「形式的体系Ｓにおいて命題は証明不可能である。」という命題も証明不可能である。』　と表される（別表現もありますが）とあります。 ここで現れる命題は抽象的言語であってよく分らないのです。例えばユークリッド幾何学においてはこの具体例は何でしょうか。私の理解は　『例えば無限遠点において平行線は交わるは証明可能である』はその例のように思うのですが　間違っているでしょうか。 問題は　無限遠点が公理を用いて表されるか　どうか　という先輩のご指摘があり公理をあらためてみてみますと　公理２に線分を限りなく伸ばすことができる　とあります。つまり無限遠点は「公理２の限りなく線分を伸ばした点」と理解され　公理の定義を用いることで表されるとおもうのです。間違っているでしょうか。参考までに公理を挙げておきます。 ＜ユークリッド 幾何学の公理＞ （公理１）与えられた２点に対して、それらを結ぶ線分をちょうど１つ引くことができる。 （公理２）与えられた線分は、どちらの側にも限りなく伸ばすことができる。 （公理３）平面上に２点が与えられたとき、一方を中心とし、他方を通る円をちょうど１つ書くことができる。 （公理４）直角はすべて相等しい。 （公理５（平行線公理））直線外の１点を通り、その直線に平行な直線は１本に限る

  • 私が知りたいのは　ゲーデルの不完全性定理の幾何学での理解です。

    私が知りたいのは　ゲーデルの不完全性定理の幾何学での理解です。 (1)第２不完全性定理では　次の表現があり『公理系Ｎにおいて、その無矛盾性を証明することは不可能である』、そのなかで問題として『　真であるが証明不可能な主張とは何か。』に対して　答え『公理』とあり　自己言及を表現していることは　理解し易いのです。幾何学では５公理です。この理解はたぶん正しいと思います。 ところが (2)私がよく分らないのは　第１不完全性定理です。『形式的体系Ｓにおいて、形式的体系Ｓが無矛盾である限り、「形式的体系Ｓにおいて命題は証明可能である。」という命題も「形式的体系Ｓにおいて命題は証明不可能である。」という命題も証明不可能である。』　と表される（別表現もありますが）とあります。 ここで現れる命題は抽象的言語であってよく分らないのです。例えばユークリッド幾何学においてはこの具体例は何でしょうか。私の理解は　「例えば無限遠点において平行線は交わるは証明可能である」はその例のようにおむのですが。つまり　例題には　ユークリッド幾何学では未定義の無限遠点が現れており　証明はできない　のです。いくら公理を増やして定義を明白にしても　未定義の領域はある　ということです。 もう一つの例ですが　無限遠点は扱わないという６番目の公理を追加したとしても　例えば　「X・X＝－１　は根がない　は証明可能である」も証明できない　と思うのです。なぜなら複素数は未定義だからです。つまり　『公理で定義されても未定義域は必ずある』が第一不完全性定理の一つの別表現ではないか と思うのです。この理解が間違っているのかどうか　どなたかにお教えて頂きたかったのですが　

  • ゲーデル数と自然数の有限列について

    　ピンポイントな質問で申し訳ないのですが、もし答えられる方がいらっしゃればお願いします。 　田中一之著「ゲーデルに挑む」の原論文第一節　p29に論理式は自然数の有限列で表されるとあって、その下の脚注8に「この有限列というは自然数の始切片で定義される数論的関数であって数が隙間を空けて並んでいるのではない」とありますが、ただ数が隙間を空けているものとすると、どのようにまずいのでしょうか（扱いにくくなってとても不便ことはわかりますが）。 　このあとにゲーデル数を実際導入する際は素数を使って定義していますが、これは「自然数の始切片で定義される数論的関数」となっているのでしょうか（数論的関数なるものがどういうものなのかがよくわかっていないのです）。 　またゲーデルが行ったのは、ある種の自然数がある性質をもつかどうか調べることが、体系内である論理式が証明できるかどうかを調べることになるということを、正確に定式化することだと考えているのですが、 前者の自然数の性質がどういった内容をあらわすか、つまりある自然数がどの論理式の証明可能性をあらわしているかは、数学は教えてくれず（解釈自体は体系内で行われることでなく）、人間が解釈を行う必要があるということでしょうか（もちろんゲーデル数の性質と記号変形としての証明の手順の間には対応があるので恣意的に解釈することは全く不可能ですが）。 変な質問になってしまって、恐縮ですが、お詳しい方お時間あればよろしくお願いします。

  • ユークリッド幾何学にまつわる不完全性定理的理解について

    ユークリッド幾何学にまつわる不完全性定理的理解について ゲーデルの不完全性定理の対象となる数学は『公理系Ｎが無矛盾である』が前提です。ユークリッド幾何学は　一階述語論理で表されることが出来る自然数の部分集合であって、ゲーデルの不完全性定理の対象である　公理Ｎの無矛盾である　論理の対象になってないとなり　それ以上のユークリッド幾何学の論理的理解が進みません。そこでゲーデル理解を拡張して『公理系Ｎが無矛盾ではない』として不完全性定理を理解すると（須田隆良氏、中西章氏など） (1)ゲーデルの第一不完全性定理の解釈＝＝＞公理系Ｎが無矛盾であろうがなかろうが　公理系Ｎにおいて、「公理系Ｎにおいて命題は証明可能である。」という命題も、「公理系Ｎにおいて命題は証明不可能である。」という命題も証明不可能である (2)第２不完全性定理の解釈＝＝＞公理系Ｎが無矛盾であろうがなかろうが　その無矛盾性を証明できない となります。これらはゲーデル不完全性対象から外れておりますが、対象外のユークリッド幾何学を理解するには都合がよい　と思うのです。 (2)によりユークリッド幾何学の公理の無矛盾性は証明できない。 (1)によりユークリッド幾何学の未定義領域（非ユークリッド幾何学、虚数、無限遠点とか）は　公理系Ｎにふくまれ　多くの証明できない命題があることになります。もちろん　公理定義内では完全性理論は保証されています。 なぜ　このようなユークリッド幾何学に　こだわる　かと申しますと　世の中の　論理（数学、哲学、論理を用いた論文　など）は　ユークリッド幾何学的なものが　圧倒的に多いと思うのです。これら論文は　ほとんどは一階述語理論で表され　かつ　ゲーデル不完全性定理　対象論理ではないのです。それら論文の特に(2)に関わる自己証明は出来ない　ということは重要であると思うのです。もちろん　自己証明が出来ないと言って間違いとはなりません　が　常に　冷静に謙虚に　主張理論の原点を見直すことに　繋がっていると思うのです。勿論、論理構成が出来ていないシロモノは　論外であります。 　　 以上のように理解しているのですが、ユークリッド幾何学にまつわるゲーデル不完全性定理の場外理解は問題ないでしょうか。諸先生のコメント頂けましたら幸甚です。

  • 命題「存在は定義できない」について。

    「存在は定義できない」という命題が真か偽か、意見が分かれると思います。 ハイデガーなどはこの命題が真であるとの立場をとり、西洋哲学（＝哲学史）を勉強した人などもこの主張を支持する人が多いようです。 私はこの命題が偽であるとの立場で論理的な説明を試みたのですが、途中で疲れてしまいました。 疲れてしまう理由は、「どこの誰かが何か言った」などという論理的ではないリファレンスが登場して、これを逐一否定しようとすると枝葉末節に入り込んでしまうからなのです。 そこで、「どこぞの某がこう言った、ああ言った」というリファレンスを無しに、命題が偽であることを説明できないかと考えています。 方法論は、公理的集合論（axiomatic set theory）を用いるのが良いと思っています。 あくまで「存在は定義できない」というのは公理ではないとし、他に、一般に合意可能な内容をいくつか公理として選択し、最終的に「存在は定義できない」という命題が偽であると立証したいのです。 数学や論理学など得意な方、どなたか、手伝っていただけないでしょうか？ 質問：命題「存在は定義できない」が偽であることを立証できますか？ （なお、これが命題である以上、これを公理には選択できません。）

  • 本物の要素関係∈と言語としてのεの関係

    再質問になります、御容赦ください。 「数とは何かそして何であるべきか」や「ゲーデルと２０世紀の論理学　４」などにおいて 集合論の言語として｛ε｝を用いる、ただしεは２変数関係記号である。体系の外で考えているとき、あるいは集合論のモデルで考えているときの、「本当の」要素関係∈と区別するためこの記号を使用する とあり、言語記号としてのεと実際の要素関係を表す∈を区別しています、しかしこの区別はどういう意味があるのでしょうか。 記号そのものと、それが表現するものの違いだ、と一旦は分かった気になるのですが、さらに考えてみると本物の要素関係∈なるものも何らかの公理と推論規則、つまり形式体系で書かれるしかないのではないか？ならばそれも言語記号と違わないのでは？と堂々巡りになっていますのです。（この二つの記号はいつも同じ内容を表すとは限らないために区別しているのだ、と考えても両者とも結局包含関係を表す訳で・・・、二者の間に意味の違いがあるという状況を想像出来ないのです。） また、 「体系の言語で記述される（内的な）無限降下列 とモデルでの無限降下列の区別」と http://kurt.scitec.kobe-u.ac.jp/~fuchino/foundation.html　（渕野 昌先生） にある文章においても（同じことだと思うのですが、）悩んでおり、その区別がいかなるものか分かっていません。 「本物の」要素関係なるものが記述はされないが存在する　などと言うことではないと感じるのですが・・・。 おそらくはじめの部分で勘違いをしていると思います、しかし、それがどういうものなのかはっきりしておらず苦しんでおります、この方面に明るい方助けていただければ幸いです。

  • スコーレムの定理の意味　論理式の表現の可能性

    　以前、言葉尻の異なる同じような内容の質問をしております。ご容赦ください。 　 　スコーレムの定理によりべき集合公理をもつ公理系にも可算モデルが存在する 　無限体k上のベクトル空間の次元という概念は論理式では表現できない 　ペアノ算術において自然数の非標準モデルが存在する 　といったものから 　モデル側の性質をすべて形式体系で書くことはできないということが結論されているのを見るのですが、自分としてはそのような形式体系で書くことができない性質があるということ、その性質について考えるとことが、なぜ記号を対象とした数学という分野でできるのかということが不思議なのです。 　つまり（あくまで建前上ではですが）、イメージや心象を閉め出して形式的な文字列の変形、生成で議論できるはずの数学においては形式体系、公理系のモデルも結局何らかの形式的な文字列の変形、生成で定義される以外無いはずであって（モデルを決めるというのは形式体系側の記号や述語に、新しい記号や述語を対応させた新しい形式体系を実装として定めるということだと考えています） 例えば 実数の公理系の非可算のモデルの更なる可算モデルを考えると、そもそも非可算モデルとはなんだったのだろうか（何をもって非可算といっていたのだろうか　もちろん元の体系内で、ある集合が可算無限の集合と１：１対応のつけられないということが証明できるということをもってなのでしょうが、しかしそれも体系の外に出てみると可算モデルになっていることがあるということならどこまで行っても本当に非可算かどうかを確かめることはできないのではないだろうか　つまり何をもって非可算となすという基準が作れないように見え、それならば非可算というもの自体がどういうものかわからないのではないか　なら最初の非可算モデルとはいったい何だったんだろうといったように） ベクトルの次元という概念も表現できる視点があって初めて、ある論理上では表現できないということが分かるのであってその表現できる視点というのも論理式の集合で書かれるしかないのではないか　ならば次元という概念も論理式の集合で表現できることになるのでは 標準的な(N,0,1,＋,・,＜)のＮも数学で考えるために論理式で定義されるものなら標準モデルだけを表す公理系があるのではないだろうか　もしないならどうやって数学の議論の台に乗せるのだろうか などといった、おそらく擬似問題に悩んでしまうのです。 　認識といってしまうといきなり怪しい話になってしまい恐縮ですが、「モデル側の性質をすべて形式体系で書くことはできない」ということは一見して数学の論理は、人間の心象、意味内容を全て認識することができないと受け取ってしまいそうになりますが、形式とモデルの関係はそのようなことをいっているのではなく、数学上の話である以上、体系間の関係のことをいっていると思うのですが正確にはどういうことを表しているのかわからないのです。 おおざっぱにいうと論理式で表せない性質があるということをいうためにはその性質を表すことが必要であり、数学においてはそれも論理式で書くことになると思うので、結局どういうことをしているのか混乱しているのです。 　それとも最初に書いたようなことは人間側の推論と論理式での推論の関係（これは本当にイメージ心象と論理式の関係であって、想像上の集合、モデルと形式体系は１：１には対応しない）を、体系同士の関係で表した、まねさせたことから出てきた成果なので たとえば非可算かどうかを確認する絶対的基準なものがどこにあるかなどと言うことは意味をなさないのでしょうか。つまり実装（モデル）側で、ある論理式（可算性、非可算性に相当する）を証明できるものを可算モデル、非可算モデルという名前を付けているだけであって人間の使う非可算という意味とは（建前上は）関係がないということでしょうか。 　もちろん例えば、自然数といわれればその意味するところはわかりますし、その自然数と同型でないモデルというのも色々なところで図などをつかって解説されている限り同型でないということや、どういうものかということは分かります、ただそれは明らかにイメージに頼ったものであって、厳密な意味での数学ではどうするのだろう（というか論旨式で表せないものを表すとは何だろう）と考え質問いたしました。 メタレベルと対象レベルを区別できてないが故の疑問だと感じているのですが、モデル（実装）にたいしても、その実装は？さらにその実装は？といっていくと結局非可算かどうかを区別できる視点などないのではないかということにならないのでしょうか？ かなり初歩的な勘違いをしていると思いますが、この方面に明るい方、過去このような疑問を持たれた方、お時間ありましたら解答、解説お願いします

  • 関数（定義域・値域）の質問

    中二の息子が期末テスト勉強をしていますが、学校で配られたプリントの問題を解けません。ぜひ解法と答えを教えていただけませんでしょうか？ 次の関数について,それぞれその定義域と値域を言え。(答えのみでよい) ただし、関数の定義域が略されている場合や略記されている場合には、妥当と思われる解釈をして定義域となる集合を記せ （１） ｈ（ｘ）＝１／ｘ （２） ｙ＝１／ｘ－２ （３）ｙ＝３ｘ＋２（－２＜ｘ≦２） （４）ｇ：Ｒ→Ｒ、ｇ：ｘ→ｘ＋５　

  • 形式化の表す内容について

    　再質問になります。 　以前、言葉尻の異なる同じような内容の質問をしております。ご容赦ください。 　 　スコーレムの定理によりべき集合公理をもつ公理系にも可算モデルが存在する 　無限体k上のベクトル空間の次元という概念は論理式では表現できない 　ペアノ算術において自然数の非標準モデルが存在する 　といったものから 　モデル側の性質をすべて形式体系で書くことはできないということが結論されているのを見るのですが、自分としてはそのような形式体系で書くことができない性質があるということ、その性質について考えるとことが、なぜ記号を対象とした数学という分野でできるのかということが不思議なのです。 　つまり（あくまで建前上ではですが）、イメージや心象を閉め出して形式的な文字列の変形、生成で議論できるはずの数学においては形式体系、公理系のモデルも結局何らかの形式的な文字列の変形、生成で定義される以外無いはずであって（モデルを決めるというのは形式体系側の記号や述語に、新しい記号や述語を対応させた新しい形式体系を実装として定めるということだと考えています） 例えば 実数の公理系の非可算のモデルの更なる可算モデルを考えると、そもそも非可算モデルとはなんだったのだろうか（何をもって非可算といっていたのだろうか　もちろん元の体系内で、ある集合が可算無限の集合と１：１対応のつけられないということが証明できるということをもってなのでしょうが、しかしそれも体系の外に出てみると可算モデルになっていることがあるということならどこまで行っても本当に非可算かどうかを確かめることはできないのではないだろうか　つまり何をもって非可算となすという基準が作れないように見え、それならば非可算というもの自体がどういうものかわからないのではないか　なら最初の非可算モデルとはいったい何だったんだろうといったように） ベクトルの次元という概念も表現できる視点があって初めて、ある論理上では表現できないということが分かるのであってその表現できる視点というのも論理式の集合で書かれるしかないのではないか　ならば次元という概念も論理式の集合で表現できることになるのでは 標準的な(N,0,1,＋,・,＜)のＮも数学で考えるために論理式で定義されるものなら標準モデルだけを表す公理系があるのではないだろうか　もしないならどうやって数学の議論の台に乗せるのだろうか などといった、おそらく擬似問題に悩んでしまうのです。 　認識といってしまうといきなり怪しい話になってしまい恐縮ですが、「モデル側の性質をすべて形式体系で書くことはできない」ということは一見して数学の論理は、人間の心象、意味内容を全て認識することができないと受け取ってしまいそうになりますが、形式とモデルの関係はそのようなことをいっているのではなく、数学上の話である以上、体系間の関係のことをいっていると思うのですが正確にはどういうことを表しているのかわからないのです。 おおざっぱにいうと論理式で表せない性質があるということをいうためにはその性質を表すことが必要であり、数学においてはそれも論理式で書くことになると思うので、結局どういうことをしているのか混乱しているのです。 　それとも最初に書いたようなことは人間側の推論と論理式での推論の関係（これは本当にイメージ心象と論理式の関係であって、想像上の集合、モデルと形式体系は１：１には対応しない）を、体系同士の関係で表した、まねさせたことから出てきた成果なので たとえば非可算かどうかを確認する絶対的基準なものがどこにあるかなどと言うことは意味をなさないのでしょうか。つまり実装（モデル）側で、ある論理式（可算性、非可算性に相当する）を証明できるものを可算モデル、非可算モデルという名前を付けているだけであって人間の使う非可算という意味とは（建前上は）関係がないということでしょうか。 　もちろん例えば、自然数といわれればその意味するところはわかりますし、その自然数と同型でないモデルというのも色々なところで図などをつかって解説されている限り同型でないということや、どういうものかということは分かります、ただそれは明らかにイメージに頼ったものであって、厳密な意味での数学ではどうするのだろう（というか論旨式で表せないものを表すとは何だろう）と考え質問いたしました。 メタレベルと対象レベルを区別できてないが故の疑問だと感じているのですが、モデル（実装）にたいしても、その実装は？さらにその実装は？といっていくと結局非可算かどうかを区別できる視点などないのではないかということにならないのでしょうか？ かなり初歩的な勘違いをしていると思いますが、この方面に明るい方、過去このような疑問を持たれた方、お時間ありましたら解答、解説お願いします

注目のQ&A

カテゴリ

専門家に質問してみよう

職業から探して質問する

あなたにピッタリな商品が見つかる！ OKWAVEセレクト

質問する