まず p.77 定理5.6（および定理5.8）に関してです。『定理5.6 １）において表現可能な全域関数や関係は、すべて再帰的である。 ２）任意の再帰的全域関数、任意の再帰的関係は、上の適当な論理式、ならびに適当な論理式でにおいて表現される。』 おおっとい…

Part Bに入りました。いよいよ算術です。なぜか新井敏康著『数学基礎論』ではPAオンリーでロビンソンの算術Qは出てきません。 算術Qで不思議なのはやはり、p.69の でしょうか。公理A4でがあるので、これは加法の交換法則の特殊なもの すら成立していないこと…

またもや重箱の隅をつついて遊ぶ探究ではありますが、p.54 補題4.15で『 AがREならば [tex:\forall y が再帰的でないことの証明(ほとんどRiceの定理の証明)： 再帰的であると仮定して、その特性関数をとする。 また と定義すると は(定理4.19)をREとして特徴…

PART A 第４講に入りました。テキストのこの講はかなり駆け足というか猛ダッシュで、クリーネの標準型定理が説明だけなのは肩すかしをくらったような感がありますが、計算論のどの教科書にも載っている内容だからということなのかもしれません。私もちょこち…

今回は結構悩みました。p.38 辺りです。まずは系3.11のメモから。 『次の系は上の定理からただちに導かれる』とあるのですが、そこが第一の悩みポイントでした。分かってしまうとなーんだということになるのですが、系3.11の条件の下で、(は複数のxの略記と…

ちょこっと計算にもっともふさわしい問題である。ただし、=100,000,000＝一億以下の素数を求めておく必要がある。いままで使っていた既知の素数で割ってみるテストを繰り返すという schemeプログラムだと時間がかかりすぎてどうにもならなかったので、エラト…

引き続きこっそり読んでいます。この本の冒頭に挙げられた問いの一つは 問1 ある形式体系Tにおいて、が証明できても、が証明できるような、あるが存在するとは限らない。その例を挙げよ。 で、直観には真っ向反していますが、こういうことが起こりうるのが形…

引き続きこっそり読んでいます。もうちょっとでPartA 第三講が終わります。 いくつか、コメントというかメモっぽいものを。p.31 定理3.2（演繹定理）の証明は読者に任されていますが、その証明中で唯一問題になりそうなのは の導出だと思います。ちょこちょ…

こっそり読んでいます。まだまだ最初の方の命題論理のコンパクト性のところなのですが、いきなり悩んでました... こちらのテキストでは、前提のある場合の命題論理の一般化された完全性定理『 』を先に証明して、そこからコンパクト性定理『 が充足可能 ⇔ 任…

先日たまたま大阪に出張する機会があり、帰りに梅田の旭屋を覗いてみると、な、なんと日本評論社の『数学基礎論講義』が復刊されて置いてあるではありませんか！ 数学基礎論講義―不完全性定理とその発展作者: 田中 一之,角田 法也,鹿島 亮,菊池 誠出版社/メ…

有名な Cauchyの素数生成多項式の問題である。まずはちょこっと計算により、の値(-40≦x≦39)を出してみた。ただし、負の整数部分については単に折り返しているだけなので実質は0≦x≦39である。 41, 43, 47, 53, 61, 71, 83, 97, 113, 131, 151, 173, 197, 223,…

１章のハイライトのひとつ、定理1.4.14(コンパクト性定理）の証明についてコメントする。まず、P.30の初めにある『1階論理のトートロジー』の定義であるが、よく理解できなかったので、ちょっと調べてみるとその採用した体系によって若干異なる定義があり、…

まず、(ここに)の収束性について。帰納法により n≧2ならば が示せるので、となり、上に有界であるので収束する。□ さて、d(n)の母関数を考える。 前問1.14から、十分大きなkに対しては [tex:d(k)n]の場合がある。2)と3)の場合の数は同じなので、2)の場合を二…

正整数nの因子の数をd(n)とするとき、任意のについて、を証明せよ、という問題であるがなかなか不思議な結果である。ヒントに沿って考えてみる。 pを素数として、とする。このときである。を満たすpとkを考えると、kを動かすと右辺が指数関数であるのでpを固…

Legendreによる素数定理π(x)=o(x)の証明を再現する問題らしい。まず、 であるが、の定義から、『1≦n≦x で nの素因子がすべてより大きいような n』の個数である。ところが、nがより大きな素数のどれかに一致しない場合、nのその他の素因子はより小さくなるた…

厳密に定式化せよ(cast in rigorous language)ということであるが、ある整数xが与えられた時点でそれが素数かどうかは決まっているので、『xが素数である確率』といったもような表現はそもそも変である。 そこで、xが素数かどうかということを知るための情報…

まず、N以下の正整数で、有限素数列のいずれかで割り切れるものの数が-\sum_{i0.22857\cdots]である。 さて、後半。の逆数の和が発散するとして、の任意の有限部分列を作ると先の議論と同様にして、の漸近密度がで抑えられることがわかる。にできるのでの漸…

まず、前半。 は明らかなので、aの位数dはnの約数である。もし、d＜n だとすると [tex:1\le a^d-1

問題1.7によく似ているが、与えられた数の素因子のどれか一つはmod 4で1になるという部分がうまくいかないため、全く違う解法となった。 qをの素因子の一つとすると、 一方、フェルマーの小定理よりであるが、もし (q-1)/2 が奇数であるととなり、矛盾してし…

はその形から、n≡3(mod 4)である。しかも、p以下の素数では割り切れないため、その素因子はpより大きな素数である。そのどれか一つは少なくとも mod 4で3になる。なぜなら、そうでないと 素因子は全て mod4 で1になるが、それらを掛け合わせた nは mod 4で3…

Euclidの証明を少し変えて としてを考える。（の条件をつけるのはとしたいため。）これはのどれでも割り切れないため、より大きな素数を素因子として含む。 よって 。 ∴ [tex:p_n\frac{1}{ln2}ln ln x] □ しかしながら実際にこの不等式を計算してみるとπ(10)…

こっちのネタ本の方もすこし読み進めてみた。気になったところをコメントする。 P.13の命題1.2.1の下のあたりに、『どんな閉論理式の有限集合をとっても、それが任意の可除アーベル群で正しければ、可除でないアーベル群でも正しくなってしまう』というステ…

n番目の素数を与える Gandhi formula を証明せよという問題。（GahndiとprimeでWeb検索するとどうしてもprime minister Gahndiが出てくるというオチが...）ヒントを参考に、から、d桁毎に1が立っている二進小数展開ができ、それが合成数のところでうまく打ち…

π(x)を与える一見すごそうな公式に見えるのだが、実は前問と同じく計算としては実用性のないものである。nをkで割って n=k･m+r , 0≦r＜k と表しておく。であるから、 よって ⇔ r≠0 ⇔ kはnを割り切らない ⇔ r=0 ⇔ kはnを割り切るが成立する。よって = nの2以…

和の中でm=nの時とm=1の時はどちらもとなるので、それ以外の項の和が 0 かどうかで素数判定できるという等式である。n:素数でない⇒ ∃p,q＞1 (n=p・q) ⇒ であるから素数でないなら和は2でない。つまり 問題の和=2 ⇒ n:素数 逆に 1＜m＜n かつ なる m が存在し…

ユークリッド整域 ⇒ 単項イデアル域 ⇒ 素元分解整域というような一般論もあるが、ここではユークリッド互除法を使って直接証明してみる。素数pとpで割り切れない整数xに対して、ユークリッド互除法を繰り返し使うとkp+lx=1 なるような整数k,lが存在する。同…

さっそく練習問題を解いてみる。私は練習問題をちまちまと解くのが好きである。練習問題愛好家と言ってもいいであろう。暇人の一種である。 さて、問題は２つ出されていて、問、次のそれぞれの条件を満たす最大のNを求めよ。 1) {2,3,..,N-1} の中の数でNと…

とまあ、最初は有限群の勉強と思ってブログを始めたのだが、それからコロコロと興味が変わってしまい、更新もごぶさたであった。しかし…最近、私の趣味の数学魂を刺激する次の2つの書物がでてしまったのだ。数学基礎論作者: 新井敏康出版社/メーカー: 岩波書…