[過去ﾛｸﾞ]
巨大数探索スレッド12 [無断転載禁止]©2ch.net (1002ﾚｽ)
巨大数探索スレッド12 [無断転載禁止]©2ch.net http://rio2016.5ch.net/test/read.cgi/math/1484923121/
上
下
前次
1-
新
通常表示
512ﾊﾞｲﾄ分割
ﾚｽ栞
抽出解除
ﾚｽ栞
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索
歴削→次ｽﾚ
栞削→次ｽﾚ
過去ﾛｸﾞﾒﾆｭｰ
462: １３２人目の素数さん [sage] 2017/07/06(木) 00:21:19.45 ID:VqI6Xr1R “加算無限濃度より大きく連続体濃度より小さい濃度の個数”というだけでは 答えが自明にならないため、自明になるまでいろいろ理論を付け加えなければ ある数を命名したことにはならない、というのがラヨ関数のルールのひとつ http://rio2016.5ch.net/test/read.cgi/math/1484923121/462
470: １３２人目の素数さん [sage] 2017/07/08(土) 20:52:06.98 ID:fLvsPSGe >>461で言うところの、超準的自然数を出力するプログラムは停止しないものと見なす、というのは、 それこそまさしく>>457で言った補足入りBB(n)の定義と同じではないか。 いかなる自然数のモデルでも停止する機械、と言っているのだから、停止するまでにかかるステップ数を表す自然数が、 モデルによってあったりなかったりする可能性は無くなる。 >>462については後にしよう。 >>457で後日にすると約束した、補足入りBB(n)の定義においてさえも(普通の自然数に対して)超準的自然数を返すという話が そっくりラヨ関数にも適用できるため、その話をしてからのほうが良さそうだ。 あと、こちらはBB(n)の値の一意性を問題にしてるわけではない。問題にしてるのは、ある程度大きな数nについてのBB(n)、 例えばBB(100)とかBB(10000)とかBB(10^20)とかについて、その返り値がPAのモデルのとりかたによらず存在してるのか、 言い換えると普通の自然数でありえるのか、という存在性についてである。 http://rio2016.5ch.net/test/read.cgi/math/1484923121/470
477: １３２人目の素数さん [sage] 2017/07/08(土) 21:44:23.58 ID:fLvsPSGe 前述の証明によって、PAがω無矛盾ならBB(n)はある程度大きな(それが10000なのか10^10なのかは分からないが) nについて普通の自然数の値をとることができない、と分かった。 もしPAがω矛盾であるとするなら、BB(n)がPAだけから存在を保障できる自然数になっていても おかしくないが、その場合はPAのモデルがすべて奇妙な性質の自然数を含んでいるということになる。 さて、>>462についてだが、前述の論法を応用すればラヨ関数についても同様のことが言える。 ラヨ関数において、論理式によって命名されたと言えるためには、その論理式をみたす自然数が 集合論のモデルのとり方によらず存在していなければならない。 一階述語論理の完全性から、モデルのとり方によらず存在しているなら、そのことを集合論から 証明可能である。 記号数n以下の論理式を枚挙して前述のチューリング機械Mと似たようなことをする機械を構成すれば、 もし集合論がω無矛盾なら前述のものと同様にラヨ関数Rayo(n)を計算する計算機になる。 しかし、このようなチューリング機械も、一階述語論理の論理式に変換できるから、 そこからラヨ関数の定義との矛盾を導ける。 二階述語論理以降なら完全性が成り立たないからこの論法が使えないのは確かだが、 二階述語論理以降は一階述語論理を包含していて、ラヨ関数より増加が速いはずだから 結局二階以上バージョンのラヨ関数を作っても普通の自然数を返すようにはならない、と言える。 http://rio2016.5ch.net/test/read.cgi/math/1484923121/477
上
下
前次
1-
新
書
関
写
板
覧
索
設
栞
歴
ｽﾚ情報
赤ﾚｽ抽出
画像ﾚｽ抽出
歴の未読ｽﾚ
AAｻﾑﾈｲﾙ
Google検索
Wikipedia
ぬこの手
ぬこTOP
1.461s*