巨大数探索スレッド7
■ このスレッドは過去ログ倉庫に格納されています
0001１３２人目の素数さん
2006/11/19(日) 23:44:01http://www.geocities.co.jp/Technopolis/9946/
前スレ、過去スレ、避難所はこのページからどうぞ。
「前の数＋1」
「1/x x→0」
「∞」
「９を延々と書き続けるプログラム」
「本日からこのスレでは、いっさいの数学的ではない話を禁止する。
私以外で検証する能力を持っている人間はいないようなので、
数学的に明確に証明できた場合以外は反論しないように。
特に今日のような低俗な煽りには徹底して放置で対応すること。」
という類の投稿は放置推奨。
0051１３２人目の素数さん
2006/12/19(火) 22:30:37俺はBB(G+1)の方が大きいんじゃないかと思ってるんだが。
もちろんこんなもん比べようも無いがみんなの意見聞かせて。
0052１３２人目の素数さん
2006/12/20(水) 15:20:24漏れもBB(G)↑↑BB(G)＜BB(G+1)説に同意
そのレベルになるともう1増えるだけで全然違うだろうからな
0053１３２人目の素数さん
2006/12/21(木) 22:44:310054KingOfUniverse ◆667la1PjK2
2006/12/21(木) 23:32:390055KingOfUniverse ◆667la1PjK2
2006/12/21(木) 23:33:280056１３２人目の素数さん
2006/12/22(金) 00:18:13階乗なんかは滑らかな関数に延長できるんだっけ？
0057１３２人目の素数さん
2006/12/22(金) 00:55:38まぁBBに関しては無理だろう。
BB(X)とBB(X+1)に計算可能な関係が存在しないんだから。
0058１３２人目の素数さん
2006/12/22(金) 01:02:490059１３２人目の素数さん
2006/12/23(土) 08:18:44BB(x+1)<BB(y+1)-BB(y)+BB(x)
ということなので
まあ成り立つ
0060１３２人目の素数さん
2006/12/23(土) 14:09:53BB(3)-BB(2) = 2
(･д･)
0061１３２人目の素数さん
2006/12/23(土) 18:26:410062１３２人目の素数さん
2006/12/23(土) 18:42:28引数が小さなときだけの特殊な場合なのか、
もっと大きいときでも逆転が起こるのか興味あるな。
逆転が起こるとしたらどんな理由だろ？
0063１３２人目の素数さん
2006/12/23(土) 20:24:240064１３２人目の素数さん
2006/12/24(日) 08:33:550065１３２人目の素数さん
2006/12/24(日) 19:37:08=BB(x+1)<BB(x+2)-BB(x+1)+BB(x)
=2BB(x+1)<BB(x+2)+BB(x)
xが充分に大きければBB(x+1)<<<<<<<<<<<<<<<<<<<<<<<<<BB(x+2)
みたいになるからほぼ成り立つだろう
0066１３２人目の素数さん
2006/12/25(月) 21:39:06いや、58はそもそもBB(x+1)<<<<<<<<<<<<<<<<<<<<<<<<<BB(x+2)
を疑っているのだろう。
BB(x+1)-BB(x)>BB(y+1)-BB(y)
は無理かもしれないが、
BB(x+1)/BB(x)>BB(y+1)/BB(y)
くらいなら案外ありうるかも。
0067１３２人目の素数さん
2006/12/25(月) 22:53:30( ﾟдﾟ )
0068１３２人目の素数さん
2006/12/25(月) 23:09:570069１３２人目の素数さん
2006/12/25(月) 23:36:02俺定義。
0070もやしっ子
2006/12/31(日) 04:36:27前スレからHardy functionのもう少し堅いやつを拾ってきたので
性懲りもなくまた貼ります。言いだしっぺはあの人でした。懐かしい…
****
60 名前：有流才蔵 ：03/04/06 11:13
Hardy Function のHierarchyというのが面白そう。
以下、[]の0,a,λは順序数(ordinal)
H[0](x)=x+1
H[a+1](x)=H[a](x+1)
H[λ](x)=H[Λ(x)](x)
λは極限順序数、
Λ(x)はλに収束する基本列
(canonical fundamental sequence)
三行目はふぃっしゅ氏の"対角化"に似ているけれども
違うのは"Λ(x)"ってところ。
61 名前：有流才蔵 ：03/04/06 11:25
Hardy FunctionのHierarchyでいうと、
primitive recursive functionはH[ω＾ω]より小さく
multiply recursive functionはH[ω＾ω＾ω]より小さく
general recursive functionはH[ε0]より小さいそうだ。
（ε0とはω＾ω＾･･･なる順序数）
***
勝てない相手より、こっちの観戦がしたいです(他力本願)
対角化っていまだに何だか理解してないですから。ええ。
0071もやしっ子
2006/12/31(日) 04:56:34アルゴリズムや定義論みたいなのに行ってしまいましたが。まあいいか。
巨大数スレ6のDATを募集中です。
0072もやしっ子
2006/12/31(日) 05:47:37チェーンの簡易表記の解説でもしようかな。
a→b→c→dをf(a,b,c,d)と表記されたのは画期的でした。
同じことな訳ですが、初見で面食らう方もいると思うので
定義の同じところだけ噛み砕こうと思います。
f(a)=a
これはチェーンでいえば何もない状態なので、a＝aってことです。
f(a,b)=a^b
これはa→bのことですね。つまりa→b＝a^bです。
f(a,…,x,y,1)=f(a,…,x,y)
これは、a→…→x→y→1と同じです。
チェーンの最後の数が1のときはこれを落とすことができるので、
a→…→x→y→1＝a→…→x→y ということです。
f(a,…,x,1,z)=f(a,…,x)
同様に、a→…→x→1→zのことです。1より後ろは落とせるので
a→…→x→1→z＝a→…→x となります。
f(a,…,x,y,z)=f(a,…,x,f(a,…,x,y-1,z),z-1)
a→…→x→y→zのことです。チェーンの定義より、
a→…→x→y→z
＝a→…→x→(a→…→x→(y-1)→z)→(z-1) となります。
0073もやしっ子
2006/12/31(日) 05:49:09第一歩、こんな定義をしてる模様。
f((a,…,z),(1))=f(a,…,z)
ほら、なんとなく分かるかも？
続きは来年…
00745-682
2006/12/31(日) 19:24:25今Veblen関数とリスト構造を組み合わせた
巨大増加関数の案がまとまりつつあります。
（Veblen関数の変数中をリスト構造で表したものです。）
さらに一言付け加えるとすれば
リスト構造を順序数ωのように表すことができるようです。
これで順序数を大幅に拡張できます。
これを使ってナゴヤ関数をもっと詳しく
説明できるかもしれませんね。
さらにナゴヤ関数Ver２まで発展していきたいところです。
0075１３２人目の素数さん
2006/12/31(日) 19:47:16どうしても(＾ω＾)が見えてきてしまうのは俺だけか
0076１３２人目の素数さん
2007/01/01(月) 00:19:49↓このスレを見ている人はこんなスレも見ています。(ver 0.20)
0077１３２人目の素数さん
2007/01/03(水) 07:49:220078もやしっ子
2007/01/04(木) 15:43:34時に激しく。
で、73の続きですが、途中で分からない箇所があったので
(前スレで解決があったのかもしれませんが見てないです)、
わかるとこまで書きます。
>>77
ナゴヤ関数というのは現時点でも超強い関数、のはずです。
BBはすべての計算可能関数より強いので比較するまでもなく鬼強い、はずです。
(適当)
0079もやしっ子
2007/01/04(木) 15:54:36レス順ずれちゃいました。どもども。
現在前スレを読めないので、どの関数がどんなんだったか
サイトに記載した以外のものはド忘れしております。申し訳ない。
僕としては強いのが産まれれば何でもいいというか(BBは仕方ないもんなぁ)、
うまくまとまることを願ってやみません。またそれをイノセントな方々に
語り部として咀嚼するのが自分のささやかな使命、ってことでひとつ。
以前ロジシャンやプログラマの面々まで首を突っ込んで頂いた
well-defined がそもそも何だったのか、と(ヘボ)。
well-definedな関数でないと、何が起こってしまうのでしょうか。
なぜあの議論になったのかであるとか、結論などを記載していかないと
埋もれてしまうかな、と思ったり…
0080もやしっ子
2007/01/04(木) 20:16:51f((a),(n))＝a なぜ個々に括弧？ つまり、 f(a,n)とすると
a→nという式と同じになってしまうので区別してる訳です。
f((a,b),(n))＝f((a,…,(b個),…,a),(n-1))
もうチェーンでは表現できないかな。でも怖くないですよ。たぶん…
f((a,…,x,y,1),(n))＝f((a,…,x,y),(n)) 最後の1が落ちただけです。
f((a,…,x,1,z),(n))＝f((a,…,x),(n)) これも1以下が落ちただけ。
f((a,…,x,y,z),(n))＝f((a,…,x,f((a,…,x,y-1,z),(n)),z-1),(n))
ここがミソです。
手前の(a,…,x,y,z)が化ける訳です。後ろ2つのy,zが。
zは(z-1)になるだけなので怖くないです。むしろyですよ。
yは、f((a,…,x,(y-1),z),(n))といった具合に肥大化します。
0081もやしっ子
2007/01/04(木) 20:35:41さっき入れた(n)、これが(*,…,*)という「リスト」に拡張されるという。
と、進む前に一応。nも他のaやzのように、こちらが数を決めて
ぶっこんでもよい、みたいです。つまり例えば、
f((4,6,2,3,5),(10))と書いても平気で、これは一意の巨大数として決まると。
で、(*,…,*)ですが、これがどういうニュアンスなのかちとわからんです。
(n)は1次で、2次以上だと(*,…,*)と書いて、リストと呼ぶってことなのかなぁ。
この次数がどう決まるのか、とかわからんです。
ひょっとしてf_nの定義から逆読みしていけばちゃんと決まるのかなぁ。
あと、m重リストってのは、
m＝1で(*,…,*)
m＝2で((*,…,*),(*,…,*)) みたいに続くのかな。
これらリストの次数は互いに異なってもいいのかな。あはん
0082１３２人目の素数さん
2007/01/04(木) 22:10:28(*,…,*)というのは、その前に(a,…,z)とか書いていたのと同じ意味です。
つまり、(*,…,*)は具体的には(31,41,5,9,2)とか(2,71,8)とか(6)のようなものです。
(1重)リストの定義はきちんと書けば下の通りです。
{(a_1,a_2,…,a_n)|ｎは自然数; ∀i=1,…,n , a_iは自然数}
nを要素の個数、a_iを(i番目の)要素と呼ぶ。
任意のリストを表す記号として(*,…,*)を使っています。(n)は要素が1個のリストです。
同様に、m重リストは下のように再帰的に定義します。
{(L_1,L_2,…,L_n)|ｎは自然数; ∀i=1,…,n , L_iは(m-1)重リスト}
注：L_iの要素の個数は互いに異なっていても構わない
2重リストなら((*,…,*),…,(*,…,*))となります。
f((a),(n))＝aというのは、((a),(n))という2重リストにfが作用していると見ることができます。
個々に括弧がついているのは、(a)と(n)が1重リストであることを示すためです。
0083もやしっ子
2007/01/05(金) 00:50:221重リストは多分わかりました。(*,…,*)をきちんと書くとそうなるという
理解でいいのかしら。
2重リストはそうすると、定義が
{(L_1,L_2,…,L_n)|ｎは自然数; ∀i=1,…,n , L_iは1重リスト}
ですよね。
例えばn＝4なら
(L_1,L_2,L_3,L_4) となって、L_1番目からL_4番目までリストが入ってると。
でもって、この4つのリストの要素の個数は互いに異なってもよいのですね。
つまり((4),(3,8,5,7),(2,9,3),(6,5))とかやっても大丈夫。
順番にやらないと分からん脳みそなので、次は3重リストの例も書きます。
0084もやしっ子
2007/01/05(金) 01:14:11{(L_1,L_2,…,L_n)|ｎは自然数; ∀i=1,…,n , L_iは2重リスト} ということで、
例えばn＝5で書きましょう。5にしている意味は別にないです。
やはり見た目は(L_1,L_2,L_3,L_4,L_5) となる訳ですが、今度は
L_1〜L_5が、それぞれ2重リストでなければならないみたいです。
ちょっと戻っていいですか。
1重リストにおいてn＝1のとき、
(L_1) ただし L_1は自然数
2重リストにおいてn＝1のとき、
(L_1) ただし L_1は1重リスト 1重リストは(*,…,*)の形態をとる訳ですが、
この場合、1重リストの要素の個数にもn＝1を適用するかというと、そうではないと。
なぜなら、定義よりL_1の要素の個数が互いに異なってもよいから。
さて戻ります。さっき作った3重リスト
(L_1,L_2,L_3,L_4,L_5) L_1〜L_5はそれぞれ2重リスト ですが、
L_1〜L_5の要素(内包する1重リストの個数)も互いに異なってよい訳です。
ということは、
(((2,3,4),(5,6)),((7,8,9,8)),((7,6),(5),(4,3,2,3)),((4,5,6,7,8),(9,8)),((7),(6,5),(4),(3,2,3)))
とかどうでしょうか。大丈夫でしょうか。
(((7)))なんかも3重リストですか。
0085もやしっ子
2007/01/05(金) 01:41:45リストがなんなのかを踏まえたということで、f関数のルールいきましょう。
原文で「リストの列」と呼ばれる(*,…,*),…,(*,…,*)を短縮して[L]と表記してみます。
ちなみにこいつは1重リストですね。(n)も同じく1重リストですが、ちょいと区別しときます。
では2重リストのf関数のルールを。
f([L],(1))＝f([L])
f([L],(1,b))＝f([L])
f([L],(a,b))＝f([L],(f([L],(a-1,b)),b-1))
f([L],(a,…,x,y,1))＝f([L],(a,…,x,y))
f([L],(a,…,x,1,z))＝f([L],(a,…,x))
f([L],(a,…,x,y,z))＝f([L],(a,…,x,f([L],(a,…,x,y-1,z)),z-1))
f([L],(1),(n))＝f([L])
f([L],(a),(n))＝f([L],(a))
f([L],(1,b),(n))＝f([L])
f([L],(a,b),(n))＝f([L],(a,…,a),(n-1)) ただしaはb個
f([L],(a,…,x,y,1),(n))＝f([L],(a,…,x,y),(n))
f([L],(a,…,x,1,z),(n))＝f([L],(a,…,x),(n))
f([L],(a,…,x,y,z),(n))＝f([L],(a,…,x,f([L],(a,…,x,y-1,z),(n)),z-1),(n))
最後の行、原文はf([L],(a,…,x,f([L],(a,…,x,y-1,z),n),z-1)とありましたが、
nに括弧がないのは誤植でしょうか。
括弧の展開は、例によって一番ケツから定義に従って開いていけばよいです。
こうしてみると、チェーンのお約束にリストがぶりぶりくっついた物体のように
見えないこともないかな、と。
0086もやしっ子
2007/01/05(金) 02:03:48f(m重リストの列,(a,b),(n))=f(m重リストの列,((a,…,a),…,(a,…,a)),(n-1))
ただし((a,…,a),…,(a,…,a))はm重リストで、各リストの要素はb個。
[L]がm重になって、後のルールは概ね同様ってことでいいでしょうか。
そんな気がする年頃。
じゃあf_2関数いきましょう。
関数のルールが変わるだけです。びびらずに…
f_2の計算法はfとほとんど同じだが、下の式が違う。
f_2(a,b)=f((a,…,a),…,(a,…,a))
ただし((a,…,a),…,(a,…,a))はb重リストで、各リストの要素はb個。
f関数は、f(a,b)=a^bとなっていました。ここんとこを強化してる訳です。
この強化方式を悶々と拡張していった結果、こんな関数ができます。
f_n(a,b)=f_(n-1)((a,…,a),…,(a,…,a))
リストが何なのか分かれば、関数の構造自体は割とシンプルなようです。
しかしそれでいて、バード数がf_63(3,3)に到底及ばないという強力さ。
そんで思ったのは、関数がシンプルでこれだけ強いんだから、強化方式に
ふぃっしゅ系のなんかよくわからんアレをうまいこと組み込んだら
どんな感じでしょうか。有意でしょうか。
とりあえずこんな感じで…
0087１３２人目の素数さん
2007/01/05(金) 07:15:30最後の例はちゃんと3重リストになってます。
>>85
nには括弧が必要ですね。
>>86
これを書いたときは「三重以降も同様」で済むかと思ってましたが、
三重のときはもう少しきちんと書くべきだと思ったので次のレスで書いておきます。
バード数より大きくするには、実はf_2どころか3重リストを持ち出すまでもなく、
要素がたった3個の2重リストでも十分です。バード数＜f((3,3),(3,3),(3,3,2))
0088１３２人目の素数さん
2007/01/05(金) 07:17:03f(((a,…,z)),((1)))=f(a,…,z)
f(((a)),((n)))=a
f(((a,b)),((n)))=f(((a,…,a),…,(a,…,a)),((n-1))) ただしaはb個,(a,…,a)もb個
f(二重リスト,((n)))で上記に当てはまらないときは、二重リスト部分を二重リストのみの時と同様に計算。
二重リストの列を[L2]と書くと、
f([L2],((1)))=f([L2])
f([L2],((1,b)))=f([L2])
f([L2],((a,b)))=f([L2],((f([L2],((a-1,b))),b-1)))
f([L2],二重リスト)で上記に当てはまらないときは、二重リスト部分を二重リストのみの時と同様に計算。
f([L2],((1)),((n)))=f([L2])
f([L2],((a)),((n)))=f([L2],((a)))
f([L2],((1,b)),((n)))=f([L2])
f([L2],((a,b)),((n)))=f([L2],((a,…,a),…,(a,…,a)),((n-1))) ただしaはb個,(a,…,a)もb個
f([L2],二重リスト,((n)))で上記に当てはまらないときは、二重リスト部分を二重リストのみの時と同様に計算。
特に分かりにくいのは、f(((*,…,*),(m)),((n)))のようになっているときに
(m)も((n))もそのままにして(*,…,*)の部分を計算することだと思います。
例えばf(((a,…,y,z),(m)),((n)))=f(((a,…, f(((a,…,y-1,z),(m)),((n))) ,z-1),(m)),((n)))
0089もやしっ子
2007/01/05(金) 07:51:14リストを使ったふぃっしゅ系関数との比較とかやれるもんなんでしょうか。
眠れないので過去ログを読んでいました。
僕が読み飛ばしてただけで、結構皆さんチェーン拡張の可能性を
探ってたんですね。当時は喧嘩ログばかり読んでたもんで…
懲りずにVeblen関数の定義を見ましたが、やはり模様にしか見えませんでした。
0090１３２人目の素数さん
2007/01/05(金) 08:29:15ということは
f_2(a,b)には(a,…,a)（aがb個の一重リスト）がb^b-1個あるということ？
気が遠くなる........
f_n(a,b)なんて化け物ですはい、僕にはf_n(a,b)=g(n,a,b)ぐらいしか次が思い浮かびません
0091１３２人目の素数さん
2007/01/05(金) 15:44:45初代スレから今までのスレで登場した色んな巨大数の大きさを
わかりやすくランキング形式でまとめてもらえまへんか？
とリクエスト
0092もやしっ子
2007/01/05(金) 16:07:26それはなかなか難儀なことなのです。総て挙げればかなりの量です。
各々の比較はいまだ途上ですし、好みや難易度などの問題もあります。
基本的にはスレが進むにつれ強力な関数が出てくるので、研究室のログを
全部読むと把握しやすいと思います。不明な点は聞けば誰かしら答えるかと。
産まれた経緯なんかも含めて面白いんです。
とりあえず、いま上に書いてある関数は相当強いですよ。
0093１３２人目の素数さん
2007/01/05(金) 19:07:55さらにg(n,a,b)もg((a)(b)(c)(d)(e))みたいに多重リスト化していって
それを繰り返してf1_2(a,b)=f_2(a,b) f2_2(a,b)=g_2(a,b)
みたいに定義できたら.........う〜ん
0094１３２人目の素数さん
2007/01/05(金) 19:08:39まあBBには勝てないと思うけどね
0095１３２人目の素数さん
2007/01/05(金) 19:50:29f_2(a,b)=f(((…(((a,…,a),…,(a,…,a)),…,((a,…,a),…,(a,…,a)))…)))とか書いた方が良かったかも。
>>90
一重リストの個数よりは、m重リストのmが大きいことの方がずっと重要です。
後で気付いたことですが、下のような式が成り立ちますし。
f_2(a,b)=f(((…((a,b))…)),((…((2))…))) (b+1)重リスト
この式には一重リストは2つしかありません。
こういう風に、無駄なところで頑張らずに単純かつ効果的な拡張を行うことが
巨大数作りには重要だと思います。
>>94
BB(n)は「ｎ文字のプログラムで計算できる最大の数」というのと似たような意味なので、
プログラムを書けるような関数を考えている時点でBBには勝てないはず。
0096もやしっ子
2007/01/05(金) 21:13:06増やしても大差ない列というのはありましたね。初期のふぃっしゅ関数の
改良の中でも。最小限で最高の効率を得るにはどうチョイスするかですが、
こういうのはやはり再帰的帰納なんとかを知らないといかんのでしょうか。
そういえばn重帰納云々の議論は埋もれましたね。結局は絶対安心な定義が
無かったんでしょうかあれは。
あと、ログ漁ってたら
＞無限順序数は有限の数ではないが、関数を定義すれば
＞有限の数はすぐに得られる
という発言がありました。そうなのですか。
長いこと揉めてますが、とりあえずのシンプルな
「ωを導入した、有限数を得る関数」を見たいです。
どういう仕組みで動くのか興味があります。
0097１３２人目の素数さん
2007/01/05(金) 22:02:14A(x+1,y+1) = A(x,A(x+1,y))
a→...→x→y→z＝a→...→x→(a→...→x→y-1→z)→z-1
という定義だと思います。
ここには何重にも入れ子にする強さが隠れているわけで、リスト関数の定義でもこうした定義を使っています。
あとは、↑表記の持つ、並べることの強みを使っています。
そして、f_nの定義では、ふぃっしゅ数の持つ特徴のうちの一つである、
大元の関数をどんどん強くするという強みを使っています。
そう考えると、リスト関数は色々なものの長所を併せ持っていると言えるかもしれません。
>>93
リスト関数の拡張としては、f_nのnの部分を多重リストにするというのが考えられます。
たとえばf_(y,z)(多重リスト)=f_( f_(y-1,z)(多重リスト) ,z-1)(多重リスト)のようにして、
f_(多重リスト)という関数を定義するとか。
ただ、初めてリスト関数を書き込んだときにはあまり反響がなかったので、
それ以上先を考えることはしなかったけど。
0098１３２人目の素数さん
2007/01/06(土) 04:11:21ただ、ω^ω^nよりも先には進めませんでした。
(n)=(n,1)＜(1,2)=ω
右側に1を付け足しても同じものとします。
ただし、fの計算と違って(a,1,b)≠(a)です。途中に1があっても消せません。
また、右側の数字が大きいリストの方が大きいとします。
すると、(1,2)はどんな自然数nよりも大きいのでωと同一視できます。
(n+1,2)=ω+n
一番左の数字にnを足すのは、順序数にnを足すのと同じとみなせます。
すると、以下のような式が成り立ちます。
(1,3)=ω+ω=ω*2 (1,n+1)=ω*n (1,1,2)=ω*ω=ω^2 (1,1,3)=ω^2+ω^2=ω^2*2
(1,1,1,2)=ω^2*ω=ω^3 (1,1,1,1,2)=ω^4
多重リストの大小関係としては、右側のリストが大きい多重リストの方が大きいとします。
(1,1,1,1,2)=((1,1,1,1,2),(1))＜((1),(2))=ω^ω ((1),(3))=ω^ω+ω^ω=ω^ω*2
((1),(1,2))=ω^ω*ω=ω^(ω+1) ((1),(1,1,2))=ω^(ω+1)*ω=ω^(ω+2)
((1),(1),(2))=ω^(ω+ω)=ω^(ω*2) ((1),(1),(1),(2))=ω^(ω+ω)=ω^(ω*3)
(((1)),((2)))=ω^(ω*ω)=ω^ω^2 (((1)),((1),(2)))=ω^ω^2*ω^ω=ω^(ω^2+ω)
(((1)),((1),(1),(2)))=ω^(ω^2+ω*2) (((1)),((1)),((2)))=ω^(ω^2+ω*ω)=ω^(ω^2*2)
((((1))),(((2))))=ω^(ω^2*ω)=ω^ω^3 (((((1)))),((((2)))))=ω^ω^4
((…(1)…),(…(2)…))=ω^ω^n ただし(n+1)重リスト
0099１３２人目の素数さん
2007/01/06(土) 04:25:45最終的にどんなリストよりも「小さい」自然数に変換していると考えられます。
fは順序数(の一部)から自然数への関数ともみなせます。
もしもε_0やη_0を表すことができるリスト構造を作ることができたなら、
リスト関数をもっと強力なものに拡張できるのではないかと思います。
順序数の話はよく分からなくて読み飛ばしていたので、似たような構想は既にあるのかもしれませんが。
0100１３２人目の素数さん
2007/01/06(土) 05:35:39＞順序数を使う代わりに2変数にしたりするのが通常のやり方といえます。
＞（結果n変数になったりリストが入れ子になったりして行き詰まる）
という書き込みが見つかった。これって私が今陥っている状況そのものだろうか。
ちなみに、多重リストのm重リストを(m,2)重リストと表し、
多重リストの多重リストのm重リストを(m,3)重リストと表し、
…として（多重リスト）重リストなるものを定義したら、
ω＾ω＾…＾ω＾ωはリストとして表せました。でも、ε_0には到達できませんでした。
（どうしても（（…（（多重リスト）重リスト）…重リスト）重リスト）重リストから先に進めない）
0101もやしっ子
2007/01/06(土) 05:49:20僕はこれだけで十分満足です。
試しに咀嚼してもいいですか。
まず、ここでの1重リスト(n)は、どう頑張ろうが有限の自然数です。
(最終的に ある関数f(n)がこの形から有限数を出力する必要があるため？
出口が無限では意味がなかろう、と勝手に理解。)
定義よりイコールなので(n,1)も有限の自然数です。
関数とリストがごっちゃになりそうですが、よーするにリストとは
記法の問題で、ルールに沿って展開していけばいつかは一意に定まった
数になりますから、つまりは数なんです。そうしましょう。
さて、前とは展開のルールが若干異なるようなので気を付けつつ…
新ルールは、右端の数(またはリスト)の大小を優先的に評価するからなのか、
途中の1は飛ばせない仕様になっているようです。
「右端の数(リスト)が大きいものが、大小関係で上に立つ」ルールにより、
(n,1)＜(1,2) という不等式が書けます。
これはつまり、
[任意の大きさの自然数]＜(1,2) ということです。
ここで(1,2)の1は飛ばせません。最もコンパクトな形になってます。
そして、(1,2)とは(n,1)より大きいリストのうち最小のものです。
繰り返しますが、リストとは1つの数です。すると…
(1,2)とは「任意の有限の数よりも大きい最初の数」ということになります。
そして「任意の有限の数よりも大きい最初の数」とは、ズバリωのことです。
だから(1,2)=ω なんでございます。いかがでしょうか。
0102もやしっ子
2007/01/06(土) 06:19:27f{4}(1,2)というものを考えてみました。
この関数f{m}(*)は、(*)がωを用いた式で表せる超限順序数だったとして、
ωをnに置き換えた式に自然数mを代入した値を出力するというものです。
(ヘボは承知なので、あまり突っ込まないように…)
したらばf{4}(1,2)は、(1,2)=ωなのでこれをnに引きずり落として、
nに4を代入して、そのまんまですが4が出力されます。
例2。
f{10}((1),(1,2))
((1),(1,2))=ω^(ω+1)なのでn^(n+1)に引き下げてnに10を代入。
よって出力は10^11=100000000000 みたいな。
定義がやばい上に弱いですが、個人的に無限を組み込んだ関数から
有限の出力を得たので勝手に納得。
あまりにクルクルパーであればご指導ください。
0103１３２人目の素数さん
2007/01/06(土) 08:04:38途中の1を飛ばすと、多重リスト自体は「小さく」なります。
リスト関数では、多重リストをどんどん小さくしていく必要があるので、
途中の1を飛ばすことが許されるわけです。
一方、多重リストを順序数と対応させるときは、リストの「大きさ」が変わるような変化は許されません。
末尾の1が自由に付け外しできるのは、有限小数の末尾に無限個の0が省略されているのと同様に、
「多重リストの末尾には無限に1が並んでいるが、省略されている」と考えているからです。
再帰的に関数を定義するときは、ある引数がどんどん小さくならないときちんと定義されません。
リスト関数の場合は、リストそのものが小さくなっていく「引数」と考えられます。
「小さくなる」という考え方ができるということは「順序関係を持っている」ということであり、
順序数と対応付けられるのは自然なことなのかもしれません。
0104１３２人目の素数さん
2007/01/06(土) 08:10:01m重リストを表す括弧には_mをつけて表記する。（ただし_1は省略）
また、あるリストの唯一の要素となっている多重リストの括弧は省略する。
（例えば、((a,b))は(a,b)_2、((a),(b))は((a),(b))_2、(((n)))は(n)_3のように表記）
f(a)_m=a
f(a,b)_m=a^b
多重リストの要素に自然数の1または1のみを要素とする多重リストがあるとき、そこから右側の要素をすべて取り去る。
リストの右側のカンマから順番に見ていき、以下の表記に当てはまる最初のカンマに対し変換を適用する。
f(…y,z…)_m=f(… f(…y-1,z…)_m ,z-1…)_m
f(…(y),(z)…)_m=f(…(y,…,y),(z-1)…)_m ただしyはy個
f(…(y)_n,(z)_n…)_m=f(…((y)_(n-1),…,(y)_(n-1))_n,(z-1)_n…)_m ただし(y)_(n-1)はy個
f_n(a)_m=f_(n-1)((a)_(a-1),…,(a)_(a-1))_a ただし(a)_(a-1)はa個
定義は以上です。以前のリスト関数と定義が一部変わっているので
二重リスト以上に対しては異なる値となりますが、
f(a,b,…,y,z)=a→b→…→y→zなことには変わりはありません。
これだと、>>100で述べた（多重リスト）重リストにも拡張しやすいと思います。
0105もやしっ子
2007/01/06(土) 09:06:39なるほど、1を飛ばす根拠はその辺りにあったのですね。ははあ。
しかし順序数をガチで学ぼうとするとZFCの公理系とかで即コケます。
全順序とか半順序とか、関係についてすら定義ありますもんね。うう…
>>104ではかなりスマートになりましたね。かつ明解。
軽く咀嚼を混ぜて改訂版を研究室に載せたいですね。
0106１３２人目の素数さん
2007/01/06(土) 20:57:43それはともかく、リストに対する別の見方について。
一重リストは、自然数から自然数への関数と対応付けることができます。
つまり、(a_1,a_2,…,a_n)というリストは、1→a_1, 2→a_2, …, ｎ→a_ｎ, ｎ+1→1, … という関数に対応付けられます。
もしも多重リストの(a_1,a_2,…,a_n)要素というのを、
n重リストのa_n番目の要素である、(n-1)重リストのa_(n-1)番目の要素である、…、
2重リストのa_2番目の要素である、1重リストのa_1番目の要素と定義すれば、
多重リストは一重リストから自然数への関数と対応付けられます。
同様に考えれば、多重リストから自然数への関数と対応付けられるリスト構造を考えることができます。
それは、>>100で少しだけ書いた(一重リスト)重リストと同じものです。
同様にして(多重リスト)重リスト、((一重リスト)重リスト)重リスト、…というリスト構造が作れます。
そして、リストと順序数の対応を考えて見ます。
ωより小さい任意の順序数は、自然数と対応付けできます。
ω^ωより小さい任意の順序数は、一重リストと対応付けできます。
ω^ω^ωより小さい任意の順序数は、多重リストと対応付けできます。
そして、ω^ω^ω^ωより小さい任意の順序数は、(一重リスト)重リストと対応付けできます。
すると、上で考えたリスト構造は、ε_0より小さい任意の順序数と対応付けできます。
ε_0から先を表すには、また別の工夫が必要でしょう。
0107１３２人目の素数さん
2007/01/07(日) 01:18:33ttp://up.spawn.jp/file/up63970.lzh.html
かちゅの.datを圧縮しただけ あとはまかせる
0108１３２人目の素数さん
2007/01/07(日) 04:41:05順序数表記をリスト構造の表記法とみなす方がいいように思えてきた。
ε_0より小さい順序数はω＾α*aの形の項の和として表されます。
>>106で多重リストの(*,…,*)要素という言い方を考えたのですが、
(*,…,*)の部分は指数αであり、要素の値は係数a+1となっています。
例えば、((1),(1,2))=ω^(ω+1)を考えると、指数はω+1=(2,2)、係数は1です。
リストを見ると、(2,2)要素が係数+1の2となっています。
このような見方をすれば、リスト関数は順序数の係数を変化させていく関数と言えます。
注：(a)というリストにはa-1という順序数を対応させないと自然な関係になりません。
つまり、(1)=0, (2)=1, (3)=2, …
0109１３２人目の素数さん
2007/01/07(日) 18:06:00f((3,3),(2))_2=f((f((f((1,3),(2))_2,2),(2))_2,2),(2))_2
=f((f((1,2),(2))_2,2),(2))_2=f((1,2),(2))_2=1
となってしまい、二重リスト以上で常に1になってしまいます。
0110１３２人目の素数さん
2007/01/07(日) 21:29:28Hardy functionの定義は、大きく分けると下の二種類があるようです。
F[0](x)=x+1
F[α+1](x)=F[α]^x(x) （αは順序数）
F[λ](x)=F[Λ(x)](x) （λは極限順序数、Λ(x)はλに収束する基本列）
H[0](x)=x
H[α+1](x)=H[α](x+1)
H[λ](x)=H[Λ(x)](x)
FとHの間には、F[α](x)=H[ω^α](x)という関係が成り立つそうなので、以下ではFを使います。
順序数についての説明。
自然数を小さい順に並べると、0,1,2,3,…となります。
そして、あらゆる自然数よりも大きい「数」の中で最小のものをωと表します。
ωのような「数」を導入しても順序関係は保たれるので、このような「数」を順序数と呼びます。
ωよりも大きい順序数を順番に考えると、ω,ω+1,ω+2,ω+3,…のようになります。
ω,ω+1,ω+2,ω+3,…のうちのどの順序数よりも大きい最小の順序数は、ω*2=ω+ωと書けます。
このとき、ω,ω+1,ω+2,ω+3,…をω*2に収束する基本列と呼びます。
この基本列をΛ(x)としたときには、Λ(x)=ω+xです。
また、基本列を用いて定義した順序数を極限順序数と呼びます。
同様に、ω*3=ω*2+ω, ω*4=ω*3+ω, …という順序数を考えることができます。
そして、Λ(x)=ω*ｘという基本列を考えます。
この基本列のどの数よりも大きい最小の順序数をω^2=ω*ωと書きます。
ω*a+b(a,bは自然数)に対し、ω*a+b<ω*a+ω=ω*(a+1)<ω*ω=ω^2ですから、ω*a+b<ω^2です。
そして、ω^2+1,ω^2+2,…と順に考えれば、ω^2+ω, ω^2+ω*ｎ, ω^2*2=ω^2+ω^2, ω^2*ｎが表せます。
Λ(x)=ω^2*ｘを考えると、ω^3=ω^2*ωが表せます。
同様にω^nを表し、Λ(x)=ω^xを考えればω^ωが定義できます。
0111１３２人目の素数さん
2007/01/07(日) 21:58:15ω^ω^ω, ω^ω^ω^ω, ω^ω^ω^ω^ωなどが表せます。
Λ(x)=ω^ω^…^ω^ω(ωはx個) としたときの収束先がε_0です。
ω^ε_0という数を考えると、ω^Λ(x)=ω^ω^…^ω^ω(ωはx+1個)よりも大きい最小の順序数となりますが、
これはε_0です。よってω^ε_0=ε_0という関係が成り立ちます。
細かい計算を書くと長くなるので省略しますが、
Hardy functionのF[α]でαに1を足すことは、リスト関数でxの右の数に1を足すことに相当します。
また、αにωを足すことは、リスト関数でxを一つ右に移動させることに相当します。
αにω＾2を足すことは、リスト関数でxの一つ右の一重リストの数に1を足すことに相当し、
αにω＾3を足すことは、リスト関数でxを一つ右の一重リストに移動させることに相当します。
一般に、αにω＾(2n)を足すことは、xの一つ右のn重リストの数に1を足すことに相当し、
αにω＾(2n+1)を足すことは、xを一つ右のn重リストに移動させることに相当します。
f_2を使うとn重リストのnをいくらでも大きくできるので、f_2はF[ω＾ω]に相当します。
結論として、f_(n+1)はF[ω^ω*n]に相当します。
過去ログによれば、ふぃっしゅ関数ver.1<F[ω^2]、ふぃっしゅ関数ver.2<F[ω^3]、
ふぃっしゅ関数ver.3はF[ω^ω*63]程度だそうなので、
f_64(3,3)はふぃっしゅ数ver.3程度の大きさということになります。
多重リストはω^ω^ωより小さい順序数に対応しますが、f_2≒F[ω^ω]=H[ω^ω^ω]なので、
リスト構造を拡張してε_0未満まで表せるようにしてもせいぜいH[ε_0]程度でしょう。
それならばリスト関数を使わずともHardy functionを使えばいいわけで、
リスト関数を拡張する意味はもはやないと思います。
それはともかく、このスレから読み始めた人向けの順序数やHardy functionの説明も必要でしょうね。
前スレでの順序数やHardy functionの説明はまとまってないので。
0112もやしっ子
2007/01/07(日) 23:50:03それにしても、えらいことになってきましたな…
0113１３２人目の素数さん
2007/01/08(月) 20:47:46今までは、
急激に増加する関数を作る→関数を利用して巨大数を作る
という考えだったわけです。
ところが、多変数関数やリスト構造などを利用した大抵の関数よりもH[ε_0]の方が大きい。
それならば、巨大な順序数を作ってHardy functionを利用する方が簡単に大きな関数が作れます。
では、巨大な順序数を作るにはどうすればいいか。
それには、順序数から順序数への大きな関数を作ればいいわけです。つまり、
急激に増加する順序数の関数を作る→関数を利用して巨大な順序数を作る
→Hardy functionを利用して巨大数を作る
ということです。順序数の関数を作るには、Veblen関数を拡張するのがいいでしょう。
結局、これはナゴヤ関数と同じ考えです。
これから先、効率よく巨大数を作っていくためには、
順序数、Veblen関数、Hardy functionの理解が欠かせないと思います。
>>105
ZFCの公理系とか、全順序･半順序とかはひとまず無視しても支障はないかと思います。
ε-δ論法を知らなくても極限や微積分についてある程度理解はできるように、
そういうことを知らなくても順序数やVeblen関数、Hardy functionは理解できると思います。
ただ、Veblen関数やHardy functionについてのまとまった説明がないのが難しいところですが。
0114１３２人目の素数さん
2007/01/08(月) 21:44:46Veblen関数については、6-292の定義だけを見ても全く分からないと思います。
Veblen関数で定義される順序数への収束列というのを考えると理解しやすいでしょう。
以下の説明では具体例を書くと長くなるので、具体例は自分で考えてみてください。
α(n) (ただしnは自然数)という順序数の数列を考えたとき、
α(n)のどの項よりも大きい順序数の中で最小のものをαとすれば、
α(n)はαへの収束列です。ωへの収束列はω(n)=nとして考えます。
Veblen関数に入る前に、和や積に関する収束列を考えます。
以下では、βとγはそれぞれβ(n)とγ(n)の収束先になっているとします。
α=β+γのとき、α(n)=β+γ(n)とします。
α=β*(m+1) (mは自然数)のとき、α(n)=β*m+β(n)とします。
α=φ_0(γ)=ω^γとします。
γ=0のとき、α=ω^0=1なので収束列は考えません。
γ=γ'+1と表されるとき、α(n)=φ_0(γ')*n=ω^γ'*nとします。
α(n)の収束先は、ω^γ'*ω=ω^(γ'+1)=ω^γとなり、αに一致します。
γへの収束列がγ(n)のとき、α(n)=φ_0(γ(n))=ω^(γ(n))とします。
α=φ_(β'+1)(γ)とします。
γ=0のとき、α(0)=φ_β'(0)、α(ｎ+1)=φ_β'(α(n))という漸化式で定義します。
γ=γ'+1のとき、α(0)=φ_(β'+1)(γ')+1、α(ｎ+1)=φ_β'(α(n))とします。
γへの収束列がγ(n)のとき、α(n)=φ_(β'+1)(γ(n))とします。
βへの収束列がβ(n)のとき、α=φ_β(γ)とします。
γ=0のとき、α(ｎ)=φ_(β(n))(0)とします。
γ=γ'+1のとき、α(n)=φ_(β(n))(φ_(β)(γ')+1)とします。
γへの収束列がγ(n)のとき、α(n)=φ_(β)(γ(n))とします。
01155-682
2007/01/08(月) 23:13:01最初の案のナゴヤ関数はF[＊](x)の＊の部分が
2変数以上のリストのとき、HardyFunctionを利用して
順序数から巨大な順序数を作ることになるということです。
例えばF[1, 1](x) = F^x[ω](x) = F[F[ ... F[ω](ω) ... ](ω)](x)
となり、[ ]のネストで順序数ωから巨大順序数が作られます。
つまり、順序数→順序数変換の段階からHardyFunctionを
使っていることになります。
01165-682
2007/01/08(月) 23:24:06ところでHardyFunctionでは
F[ε0](x) >=(( ... m(x) ...)m(2)f)(x) となることがわかっているので
F[ε0](ω)はふぃっしゅ関数Ver5相当の巨大な順序数になります。
ということはVeblen関数を多変数に拡張してもF[ε0](ω)には
足元にも及ばないと思われます。
（それどころか(多重リスト)リストに拡張しても追いつかないと考えられる）
したがって、ナゴヤ関数はF[2, n](x)の段階で
多重リスト関数に拡張したVeblen関数を使ったHardyFunctionを
はるかに越える巨大増加関数になってしまいます。
01175-682
2007/01/08(月) 23:51:12どの形の順序数で表されるかが問題になっています。
例えばF[1](x) = x + 1として、
F[ω](x) = x*2
F[ω*2](x) = x*2^x
F[ω*3](x) = ( ... (x*2^x)* ... )*2^(x*2^( ... (x*2^x) ...)) > x*2^^x
F[ω*2^ω](x) >= F[ω*ω](x) >= 2^^ ... ^^x = ak(2, x, x)
となり、途中で2^xとか2^2^ ... 2^xが出てくるところが曲者です。
今はF[λ(2^ω)](x) = F[λ(2^x)](x)としているところです。
0118１３２人目の素数さん
2007/01/09(火) 04:42:57順序数に対する演算は自然数に対する演算と性質が違うので、
単純にxとωを置き換えても、一意に定まる保障がありません。
例えば、1+x=x+1ですが、1+ω=ω≠ω+1です。
そして、2^ω=ωとなってしまいます。
2^ω=ωなのに2^xとxという違うものに置き換えてしまうと、一意的に定義されるのかが不安です。
もし、順序数に対するHardy functionの定義を最初に戻って考えるとすれば、
H[0](x)=x H[α+1](x)=H[α](x+1)
に対しては
H[0](β)=β H[α+1](β)=H[α](β+1)
とすればいいですが、
H[α](x)=H[α_x](x)
に対しては、α_βが定義できなければ単純な置き換えはできません。
もしも、α_βはβが極限順序数のときにα_β_nの極限だとしてしまうと、α_ωはαそのものになります。
すると、H[α](ω)=H[α_ω](ω)=H[α](ω)となって定義されません。
なので、α_nのnを順序数に拡張することはできません。
かといって、H[α](β)をH[α_n](β_n)の極限としてもおかしくなります。
というのも、H[α](ω)はH[α_n](n)の極限ですが、
H[α_n](n)は自然数なのでその極限はωであり、H[α_n](ω)=ωとなってしまいます。
そして、H[α](β)をH[α_n](β)の極限としたときには、H[ω](β)=β+ωまではうまく定まるのですが、
H[ω+1](β)=β+1+ω=β+ωとなってしまい、これ以上大きくなりません。
こういった変なことを起こさずに、うまく順序数に対するHardy functionを定義できるのでしょうか。
0119１３２人目の素数さん
2007/01/09(火) 04:45:38順序数に対する演算は自然数に対する演算と性質が違うので、
単純にxとωを置き換えても、一意に定まる保障がありません。
例えば、1+x=x+1ですが、1+ω=ω≠ω+1です。
そして、2^ω=ωとなってしまいます。
2^ω=ωなのに2^xとxという違うものに置き換えてしまうと、一意的に定義されるのかが不安です。
もし、順序数に対するHardy functionの定義を最初に戻って考えるとすれば、
H[0](x)=x H[α+1](x)=H[α](x+1)
に対しては
H[0](β)=β H[α+1](β)=H[α](β+1)
とすればいいですが、
H[α](x)=H[α_x](x)
に対しては、α_βが定義できなければ単純な置き換えはできません。
もしも、α_βはβが極限順序数のときにα_β_nの極限だとしてしまうと、α_ωはαそのものになります。
すると、H[α](ω)=H[α_ω](ω)=H[α](ω)となって定義されません。
なので、α_nのnを順序数に拡張することはできません。
かといって、H[α](β)をH[α_n](β_n)の極限としてもおかしくなります。
というのも、H[α](ω)はH[α_n](n)の極限ですが、
H[α_n](n)は自然数なのでその極限はωであり、H[α_n](ω)=ωとなってしまいます。
そして、H[α](β)をH[α_n](β)の極限としたときには、H[ω](β)=β+ωまではうまく定まるのですが、
H[ω+1](β)=β+1+ω=β+ωとなってしまい、これ以上大きくなりません。
こういった変なことを起こさずに、うまく順序数に対するHardy functionを定義できるのでしょうか。
0120１３２人目の素数さん
2007/01/09(火) 06:22:16Hardy functionのもう一つの定義である、
F[0](x)=x+1 F[α+1](x)=F[α]^x(x) F[α](x)=F[α_x](x)
を使えばうまく定義できそうです。
F[0](β)=β+1
F[α+1](β)=F[α]^β(β)
F[α](β)はF[α_n](β)の極限(ただしβ<ωのときn=β)
ただし、F[α]^β(γ)は以下のように定義します。
F[α]^0(γ)=γ
F[α]^(β+1)(γ)=F[α](F[α]^β(γ))
F[α]^β(γ)はF[α]^(β_n)(γ)の極限
こうすると、F[1](β)=β*2、F[2](β)=β*2＾β、F[3](ω)=ε_0となります。
ただ、F[3](ω)への収束列はω, ω^2, ω^ω, ω^ω^ω, …となり、
ε_0への普通の収束列とは少し異なります。
0121１３２人目の素数さん
2007/01/09(火) 07:37:32F[3](ω)への収束列はω, ω^2, ω^ω^2, ω^ω^ω^2, …です。
おそらく、β≧ω＾2ならば2＾β=ω^βだと思います。
0122１３２人目の素数さん
2007/01/09(火) 12:32:09自分は全くの門外漢なので応援しつつ
スレの成り行きを見守らせてもらいます
0123１３２人目の素数さん
2007/01/09(火) 19:46:58再度訂正。
F[3](ω)への収束列はω, ω^2, ω^ω, ω^ω^ω, …で、
β≧ω＾ωならばたぶん2＾β=ω^βです。
とりあえず、6-510の書き込みを元に、勝手にナゴヤ関数の2変数リスト以下の場合を再定義してみます。
L[1](x) = f(x)
L[n+1](x) = f(L[n](x))
L[ω](x) = L[x](x)
はそのまま使いますが、f(x)に対しては「順序数に対してもきちんと定義されているもの」という条件をつけます。
（例えばf(x)=x+1とか）
そして、収束列α_nの定められた極限順序数αに対して、
L[α](x) = L[α_x](x)
L[α+n+1](x) = L[α](L[α+n](x))
とします。リストが2項のときは
L[2 , 1](x) = L[ω](x)
L[2 , n+1](x) = L[L[2 , n](ω)](x)
L[m+1 , 1](x) = L[m , ω](x)
L[m+1 , n+1](x) = L[m ,L[m+1 , n](ω)](x)
とします。ここまでは、元の定義とほぼ同じです。
リストの右の数が順序数のときの定義は見当たらないようなので、
L[2 , α](x) = L[α_x](x)
L[2 , α+n+1](x) = L[L[2 , α+n](ω)](x)
L[m+1 , α](x) = L[m , α_x](x)
L[m+1 , α+n+1](x) = L[m ,L[m+1 , α+n](ω)](x)
としておきます。
0124１３２人目の素数さん
2007/01/09(火) 19:48:12まず、ωの収束列はω_n=nとします。そして、xがωのときは以下のように定義します。
L[1](ω) = f(ω)
L[n+1](ω) = f(L[n](ω))
L[ω](ω) は収束列が L[n](ω) の極限順序数
L[α](ω) は収束列が L[α_n](ω) の極限順序数
L[α+n+1](ω) = L[α](L[α+n](ω))
L[2 , 1](ω) = L[ω](ω)
L[2 , n+1](ω) = L[L[2 , n](ω)](ω)
L[m+1 , 1](ω) = L[m , ω](ω)
L[m+1 , n+1](ω) = L[m ,L[m+1 , n](ω)](ω)
L[2 , α](ω) は収束列が L[α_n](ω) の極限順序数
L[2 , α+n+1](ω) = L[L[2 , α+n](ω)](ω)
L[m+1 , α](ω) は収束列が L[m , α_n](ω) の極限順序数
L[m+1 , α+n+1](ω) = L[m ,L[m+1 , α+n](ω)](ω)
こうすれば、関数がきちんと定義されないということは避けられるはずです。
0125１３２人目の素数さん
2007/01/10(水) 07:48:27定義が長いので、とりあえず定義だけを書いておきます。
φ([α,β],[γ,δ],…,[ε,ζ])という形で表記する。
ただしα＞γ＞…＞εであり、φ(…,[α,0],…)=φ(…,…)とする。
φ([1,α],[0,β])=φ_α(β)、φ([2,1])=Γ_0である。
α=lim α_nと書いたとき、αはα_nを収束列とする極限順序数とする。
元のVeblen関数とΓ_0の定義。
φ([0,0])=φ()=1
φ([0,α+1])=lim φ([0,α])*n
φ([0,α])=lim φ([0,α_n]) (φ([0,α])≠αのとき)
φ([1,α+1],[0,0])=φ([1,α+1])=lim φ_n
ただしφ_0=φ([1,α]),φ_(n+1)=φ([1,α],[0,φ_n])
φ([1,α+1],[0,β+1])=lim φ_n
ただしφ_0=φ([1,α+1],[0,β])+1,φ_(n+1)=φ([1,α],[0,φ_n])
φ([1,α+1],[0,β])=lim φ([1,α+1],[0,β_n]) (φ([1,α+1],[0,β])≠βのとき)
φ([1,α],[0,0])=φ([1,α])=lim φ([1,α_n]) (φ([1,α])≠αのとき)
φ([1,α],[0,β+1])=lim φ([1,α_n],[0,φ([1,α],[0,β])+1])
φ([1,α],[0,β])=lim φ([1,α],[0,β_n]) (φ([1,α],[0,β])≠βのとき)
φ([2,1])=lim φ_n
ただしφ_0=φ(),φ_(n+1)=φ([1,φ_n])
0126１３２人目の素数さん
2007/01/10(水) 07:49:20φ(…,[α+1,1])=lim φ_n
ただしφ_0=φ(),φ_(n+1)=φ([α,φ_n])
φ(…,[α+1,1],[0,β+1])=lim φ_n
ただしφ_0=φ(…,[α+1,1],[0,β])+1,φ_(n+1)=φ([α,φ_n])
φ(…,[α+1,1],[0,β])=lim φ(…,[α+1,1],[0,β_n]) (φ(…,[α+1,1],[0,β])≠βのとき)
φ(…,[α+1,β+1])=lim φ_n
ただしφ_0=φ(…,[α+1,β])+1,φ_(n+1)=φ(…,[α+1,β],[α,φ_n])
φ(…,[α+1,β+1],[0,γ+1])=lim φ_n
ただしφ_0=φ(…,[α+1,β+1],[0,γ])+1,φ_(n+1)=φ(…,[α+1,β],[0,φ_n])
φ(…,[α+1,β+1],[0,γ])=lim φ(…,[α+1,β+1],[0,γ_n]) (φ(…,[α+1,β+1],[0,γ])≠γのとき)
φ(…,[α+1,β])=lim φ(…,[α+1,β_n]) (φ(…,[α+1,β])≠βのとき)
φ(…,[α+1,β],[0,γ+1])=lim φ(…,[α+1,β_n],[0,φ(…,[α+1,β],[0,γ])+1])
φ(…,[α+1,β],[0,γ])=lim φ(…,[α+1,β],[0,γ_n]) (φ(…,[α+1,β],[0,γ])≠γのとき)
αが極限順序数のとき。
φ(…,[α,1])=lim φ(…,[α_n,1])
φ(…,[α,1],[0,β+1])=lim φ(…,[α_n,1],[0,φ(…,[α,1],[0,β])+1])
φ(…,[α,1],[0,β])=lim φ(…,[α,1],[0,β_n]) (φ(…,[α,1],[0,β])≠βのとき)
φ(…,[α,β+1])=lim φ(…,[α_n,φ(…,[α,β])+1])
φ(…,[α,β+1],[0,γ+1])=lim φ_n
ただしφ_0=φ(…,[α,β+1],[0,γ])+1,φ_(n+1)=φ(…,[α,β],[0,φ_n])
φ(…,[α,β+1],[0,γ])=lim φ(…,[α,β+1],[0,γ_n]) (φ(…,[α,β+1],[0,γ])≠γのとき)
φ(…,[α,β])=lim φ(…,[α,β_n]) (φ(…,[α,β])≠βのとき)
φ(…,[α,β],[0,γ+1])=lim φ(…,[α,β_n],[0,φ(…,[α,β],[0,γ])+1])
φ(…,[α,β],[0,γ])=lim φ(…,[α,β],[0,γ_n]) (φ(…,[α,β],[0,γ])≠γのとき)
これで、lim φ_n (φ_0=φ(),φ_(n+1)=φ([φ_n,1]))を考えると非常に大きい順序数ができます。
0127１３２人目の素数さん
2007/01/10(水) 20:07:020128菅_理人@kmath1107BBS ◆.ffFfff1uU
2007/01/10(水) 20:13:12マスマティカ
0129１３２人目の素数さん
2007/01/10(水) 22:16:40>>126の式なんかもOKなの？
あとフリーなのが良い…
0130１３２人目の素数さん
2007/01/11(木) 06:33:04どの定義式もφ(…,[α,β],[0,γ])=という形をしていますが、
α,β,γに対して0 or 1,後続,極限の3通りを考えなければならないので式が27種類もできてしまいます。
(Γ_0=φ([2,1])の定義式は数えない)
うまくまとめれば式を12種類にまで減らせますが、それだとどの式を適用するか多少分かりづらくなります。
「φ(…,[α,β])≠βのとき」とかいうのは、例えばω^ε_0=ε_0で
左辺と右辺に別々の収束列を定義してしまうのを避けるためです。
右辺では1, ω, ω^ω, ω^ω^ω, …となりますが、
左辺ではω, ω^ω, ω^ω^ω, ω^ω^ω^ω, …と一つずれてしまいます。
もっとも、順序数は巨大数の計算のための道具に過ぎないと考えて
ω^ε_0≠ε_0としてしまっても、巨大数の計算をすることは可能です。
つまり、ω^ε_0やε_0は単なる収束列を表す記号に過ぎないという考えをとるわけです。
すると、収束列の異なる順序数は「別のもの」であるとみなせるわけです。
ω^ε_0=ε_0という性質は、関数の増加度を見積もるときに使えば十分なわけです。
>>126の最後の順序数でH[α](2)の計算をしたとすると、順序数の減り方は
φ([φ([1,1]),1])=φ([ε_0,1])→φ([ω^ω,1])→φ([ω^2,1])→φ([ω*2,1])→φ([ω+2,1])→
φ([ω+1,φ([ω+1,1])])→φ([ω+1,φ([ω,φ([ω,1])])])→φ([ω+1,φ([ω,φ([2,1])])])→
φ([ω+1,φ([ω,φ([1,φ([1,1])])])])=φ([ω+1,φ([ω,φ([1,ε_0])])])→
φ([ω+1,φ([ω,φ([1,ω^ω])])])→φ([ω+1,φ([ω,φ([1,ω^2])])])→
φ([ω+1,φ([ω,φ([1,ω*2])])])→φ([ω+1,φ([ω,φ([1,ω+2])])])→
φ([ω+1,φ([ω,φ([1,ω+1],[0,φ([1,ω+1],[0,φ([1,ω+1])])])])])→
φ([ω+1,φ([ω,φ([1,ω+1],[0,φ([1,ω+1],[0,φ([1,ω],[0,φ([1,ω],[0,φ([1,ω])])])])])])])→
φ([ω+1,φ([ω,φ([1,ω+1],[0,φ([1,ω+1],[0,φ([1,ω],[0,φ([1,ω],[0,φ([1,2])])])])])])])
=φ([ω+1,φ([ω,φ([1,ω+1],[0,φ([1,ω+1],[0,φ([1,ω],[0,φ([1,ω],[0,η_0])])])])])])→
…となり、入れ子構造がすごいことになるのが分かります。
0131１３２人目の素数さん
2007/01/11(木) 08:10:44Hardy Functionに順序数を入れるときは、極限順序数は収束列のx番目の項に置き換えるわけです。
ならば、Hardy Functionを使う分には極限順序数と収束列は一対一に対応するものとみなせます。
では、1+ω=ω≠ω+1のような、順序数に対する等式は何を意味するのでしょうか。
これは、Hardy Functionに入れたときの関数の増加度を表しています。
F[1+ω](x)=F[1+x](x), F[ω](x)=F[x](x), F[ω+1](x)=F[ω]^x(x)という三つの関数を考えたとき、
F[ω](x)＜F[1+ω](x)＜F[ω](x+1)となるので、この二つの関数の増加度はほぼ同じです。
一方、F[ω](x)とF[ω+1](x)では明らかに増加度が違います。
なので、急激に増加する関数を作りたいときは、順序数の大きさをちゃんと考えなければいけません。
でも、順序数の大きさが分からなくても計算することだけならできます。
順序数を使った関数の計算法を理解したいだけなら、
「極限順序数と収束列が一対一に対応する」という不正確な理解でも十分です。
0132１３２人目の素数さん
2007/01/12(金) 00:31:42順序数を知らない人は「極限順序数」を「数列」と読み替え、
limは無視して「左辺の記号＝右辺の数列」だと思えば理解できると思います。
α=lim φ_nと書いたとき、αは極限順序数、α_n=φ_n
βが極限順序数のとき
α+β=lim α+β_n
φの定義(Veblen関数の拡張)
φ(…,[α,0],…)=φ(…,…)
φ()=1
φ([0,α+1])=lim φ_n
ただしφ_0=0,φ_(n+1)=φ_n+φ([0,α])
φ(…,[α+1,1],[0,β+1])=lim φ_n
ただしφ_0=φ(…,[α+1,1],[0,β])+1,φ_(n+1)=φ(…,[α,φ_n])
φ(…,[α+1,β+1])=lim φ_n
ただしφ_0=0,φ_(n+1)=φ(…,[α+1,β],[α,φ_n])
β≠0のとき
φ(…,[α,β+1],[0,γ+1])=lim φ_n
ただしφ_0=φ(…,[α,β+1],[0,γ])+1,φ_(n+1)=φ(…,[α,β],[0,φ_n])
αが極限順序数のとき
φ(…,[α,1],[0,β+1])=lim φ(…,[α_n,1],[0,φ(…,[α,1],[0,β])+1])
φ(…,[α,β+1])=lim φ(…,[α,β],[α_n,1])
βが極限順序数のとき
φ(…,[α,β])=lim φ(…,[α,β_n])
φ(…,[α,β],[0,γ+1])=lim φ(…,[α,β_n],[0,φ(…,[α,β],[0,γ])+1])
Fの定義(Hardy function)
F[0](x)=x+1
F[α+1](x)=F[α]^x(x)
αが極限順序数のとき
F[α](x)=F[α_x](x)
巨大関数の定義
f(x)=F[φ_x](x) ただしφ_0=0,φ_(n+1)=φ([φ_n,1]))
0133１３２人目の素数さん
2007/01/12(金) 09:17:41小さい値について計算してみると、こうなります。
f(0)=F[0](0)=1
f(1)=F[φ([0,1])](1)=F[1](1)=F[0](1)=2
f(2)=F[φ([φ([0,1]),1])](2)=F[φ([φ([0,1]),0],[2,1])](2)=F[φ([2,1])](2)=F[φ([2,0],[1,φ([2,0],[1,0])])](2)
=F[φ([1,φ()])](2)=F[φ([1,1])](2)=F[φ([1,0],[0,φ([1,0],[0,0])])](2)=F[φ([0,φ()])](2)=F[φ([0,1])](2)
=F[2](2)=F[1]F[1](2)=F[1]F[0]F[0](2)=F[1](4)=F[0]F[0]F[0]F[0](4)=8
この関数はH[Γ_0]よりもずっと大きい関数なので、このスレで今まで出てきた関数の中では
ナゴヤ関数とBBを除くどの関数よりも急激に増加するはずです。
BBは計算可能などの関数よりも大きいので、当然この関数よりも大きいです。
ナゴヤ関数は、順序数にHardy functionを適用するとどの位大きくなるか見積もらないと比較できません。
リスト構造で比較してみると、ナゴヤ関数Ver.1は”自然数”個の変数を使っているのに対し、
この関数では[α,β]を「α番目の要素がβ」という意味で解釈しているので、
ある意味では”順序数”個の変数を使っていることになります。
見た目はただの2重リストですが、要素が順序数なので自然数を要素とする2重リストよりは
はるかに複雑な構造となります。
>>116では"Veblen関数を多変数に拡張してもF[ε0](ω)には足元にも及ばない"と書いてありますが、
F[ε0]はあくまでも「自然数のリスト構造」を変数とする関数より大きいだけで、
「順序数のリスト構造」となるとそうは言い切れないと思います。
0134１３２人目の素数さん
2007/01/12(金) 09:56:15考察乙です
0135１３２人目の素数さん
2007/01/12(金) 23:28:37どうやらF[α](β)≒φ_α(β)となりそうです。α＜ω*2の場合しか確かめてませんが。
少なくとも、F[ω+n](φ_[ω+n](α))=φ_[ω+n-1](φ_[ω+n](α)*2)という式が成り立ちます。
Veblen関数は、実はかなり巨大な順序数を作り出せる関数のようです。
この推測に基づいてナゴヤ関数と>>132の関数を比較すると、
L[α,β](ω)≒φ([2,1],[1,α],[0,β])ということになるようです。
(左辺はナゴヤ関数、右辺は>>132の拡張Veblen関数)
もし、L[a_n, …, a_0](ω)≒φ([n,a_n],…,[0,a_0])という関係が成り立つのなら、
ナゴヤ関数Ver.1より>>132の関数の方が大きいということになります。
でも、ナゴヤ関数Ver.2はずっと巨大なものになるそうなので、
>>132を上回るような関数になることを期待しています。
それと、上の記述はかなり推測が入っているので、間違いがあるかもしれません。
0136１３２人目の素数さん
2007/01/13(土) 13:20:48β≠0のとき
φ(…,[α,β+1],[0,γ+1])=lim φ_n
ただしφ_0=φ(…,[α,β+1],[0,γ])+1,φ_(n+1)=φ(…,[α,β],[0,φ_n])
αが極限順序数のとき
φ(…,[α,1],[0,β+1])=lim φ(…,[α_n,1],[0,φ(…,[α,1],[0,β])+1])
の式を、
φ(…,[α+1,β+1],[0,γ+1])=lim φ_n
ただしφ_0=φ(…,[α+1,β+1],[0,γ])+1,φ_(n+1)=φ(…,[α+1,β],[α,φ_n])
αが極限順序数のとき
φ(…,[α,β+1],[0,γ+1])=lim φ(…,[α,β],[α_n,φ(…,[α,β+1],[0,γ])+1])
に訂正します。
0137１３２人目の素数さん
2007/01/15(月) 19:28:51ナゴヤ関数なるものが最強候補なわけですな
0138１３２人目の素数さん
2007/01/16(火) 09:38:57そういうことですね。ただ、ナゴヤ関数は>>117のように定義が怪しいところもあるようです。
その点では、>>132、>>136の関数はちゃんと定義できていてナゴヤ関数Ver.1より大きいようなので
現時点では最強なのかもしれません。自分で言っても説得力はありませんが。
>>132、>>136の関数の定義がよく分からない人がいたら聞いてください。
0139１３２人目の素数さん
2007/01/17(水) 11:11:45α=φ(…,[β,γ],…)のとき、γをαのβ成分と呼ぶ。
γ=φ(…)のとき、α＜γ,β＜γならばα+β＜γ
β=φ(…)のとき、α＜βならばα+β=β、α≧βならばα+β＞α,β
α=φ(…),β=φ(…)のとき、αのγ成分＞βのγ成分 となるγが存在して、
δ＜γならばα＞βのδ成分 であり、ε＞γならば αのε成分=βのε成分 が成り立つとき、α＞β
α=φ(…,[β,γ]),γ=φ(…)のとき、δ＜βならば αのδ成分=0 であり、
ε＞βならば αのε成分≦γのε成分 であり、
ζ＞β、αのζ成分＜γのζ成分 となるζが存在するならばα=γ
上記のような大小関係が成り立つように、>>132、>>136で収束列を定めてあります。
ただし、上の式での=は順序数として等しいだけで、>>132、>>136で定義される収束列は異なるので、
>>132、>>136の関数の計算で=とすることはできません。
また、上の大小関係を見ると0以外の自然数が出てきていませんが、
0より大きくφ()よりも小さい数が存在しないとしても矛盾は生じないので
φ()を1とみなせることが分かります。
0140１３２人目の素数さん
2007/01/18(木) 04:54:260に+,φを次々に適用して得られる数の集合(仮にΦと呼ぶ)に対し順序関係がきちんと定まるはずです。
(α+β)+γ=α+(β+γ)
α+0=0+α=αをみたす元0が存在する
任意のα,βに対しα＞β,α=β,α＜βのうちいずれか一つのみが成り立つ
α＜β,β＜γならばα＜γ
また、厳密に+やφという演算を定義すれば、
+:Φ×Φ→Φ; (α,β)├→α+β
E={e:Φ→Φ; α├→e(α)|Ψ⊂Φ, α∈Ψでなければe(α)=0}として
φ:E→Φ; e├→φ(…,[α,e(α)],…,[β,e(β)],…) ただしα,β∈Ψ, α＞β
ただし、eはαに対しα成分を与える写像です。
こんな説明は理解しなくても>>132、>>136の関数は理解できるはずですが、
この関数について詳しく知りたい人がいたときのために書いておきます。
0141１３２人目の素数さん
2007/01/18(木) 09:40:19一つ抜けてました。Ψは要素が有限個の集合です。
0＜φ()というのは、以下のように導けます。
0≧φ()とすると>>139の4行目より0+φ()＞0
ところが0+φ()=φ()であるからφ()＞0となり矛盾する よって0＜φ()
0142もやしっ子
2007/01/19(金) 05:31:56F[λ](x)=F[Λ(x)](x) （λは極限順序数、Λ(x)はλに収束する基本列）
ここのくだりが長いことわからなかったのですが、要するに
例えばλ=ωの場合であれば Λ(x)=x なので
F[ω](x)=F[x](x) のようになるんでしょうか。
λ=ω*2の場合は Λ(x)=ω+x より
F[ω*2](x)=F[ω+x](x)
これはここからどう展開するのか分からんです。(そもそも合っているのか)
0143もやしっ子
2007/01/19(金) 20:20:30記述があったのでそういう理解をしております。荒っぽいでしょうか。
＞The first limit ordinal is ω.
0144１３２人目の素数さん
2007/01/19(金) 20:32:210145１３２人目の素数さん
2007/01/19(金) 20:39:19ただ、0を極限順序数とする人も多いよ
0146１３２人目の素数さん
2007/01/19(金) 20:40:05だとしたらそれで良いはずですけど。
別にどういう用語を使っても良いだろうけど「超限」ってのは
transfiniteの訳語として使うことが一般的じゃないのかな。
しかし超限ってどういう意味ですか、と聞かれるとちょっと困りますね
0147もやしっ子
2007/01/19(金) 20:44:51英語で検索したところ、
http://mathworld.wolfram.com/LimitOrdinal.html
ここにそういう記載がありました。
超限順序数を英語で何と呼ぶのかが見つかっておりません。
wikipediaではωは最小の超限順序数であるとも書いてありますね。
謎は置いておいて、目先の疑問に触れてみた、ということでひとつ。
0148もやしっ子
2007/01/19(金) 20:50:00との記述を発見。でも序数って「first」「second」みたいなもんですか？
むう…
0149もやしっ子
2007/01/19(金) 20:53:30正の整数の超限順序数はωによって指定されます。
0150もやしっ子
2007/01/19(金) 21:07:50＞超限数は，超限順序数と超限基数に分かれる
ここでの運用を勝手に推測すると、ωは極限順序数であるし、また
超限順序数でもあるから混乱を避けるため呼称を統一した、とか？
あるいは、極限順序数の定義でいかないと基本列のカラクリが使えないとか。
妄想です。
0151１３２人目の素数さん
2007/01/19(金) 21:27:10それは、「正の超限順序数をωと表すとする」って約すのが正解。
「傾きをvとおく」みたいなものだ。
■ このスレッドは過去ログ倉庫に格納されています