FANDOM


  • Kyodaisuu

    順序数講座の12回目です。前回は、ブーフホルツのΨ関数を解説しました。フェファーマンのθやブーフホルツのψではTFBが限界となっていますが、その先にはどのような順序数表記があるでしょうか。今回の講座では、Googology Wiki で議論されている TFB を超える構成的順序数の表記についてざっと見ていきます。今回は、私自身も十分に理解できていないということもあり、いつもの「気持ちの講座」をさらにざっくりとさせた「気持ちの気持ちの講座」となります。この講座をきっかけとして興味を持った人が自習できるように、なるべく参考サイトを示しながら進めていきます。

    Googology Wiki で順序数崩壊関数についての理解が深まったのは、2013年の Deedlit11 さんの Ordinal Notations と題する一連のブログ記事です。まずは、そのブログ記事をざっと眺めてみます。

    Ordinal Notations I: Up to the Schutte Klammersymbolen

    この回では、カントールの標準形とヴェブレン関数について解説されています。ヴェブレン関数については、多変数および超限変数のバージョンも紹介されています。

    Ordinal notations II: Up to the Bachmann-Howard ordinal

    バッハマン・ハワード順序数 BHO までの順序数崩壊関数について、3種類が紹介されています。

    1. Wolfram Pohlers のψ関数
    2. フェファーマンのθ関数
    3. θ関数を1変数にしたϑ関数

    そして、ψ関数について標準形と基本列を定義しています。

    Ordinal Notations III: Collapsing Higher Cardinaliti ……
    全文を読む >
  • Merliborn

    FGH revisited (2)

    2018年6月20日 by Merliborn

    ←前回:ユーザーブログ:Merliborn/Fast-growing hierarchy rivisited

    LöbとWainerによるオリジナルの急増加関数の定義には、現在我々がよく知る定義には存在しない関数ρα(n)が介在していました。これは極限順序数σに対して基本列の取り方が一意ではないために、Fσの単調増加性が自明とはならないために起こった現象でした。

    1970年の論文ではε₀まで、のちの研究ではさらに大きい領域までの順序数について、特定の基本列を取ることでρα(n)=nとしてよいことが分かっています。
    この記事ではε₀までの順序数について、Wainerの定義による急増加関数が全て単調増加であることを示します。
    基本的には順序数αについての超限帰納法によって証明されるのですが、各場合における証明のメカニズムを明示するために数段階に分割して記載しています。

    -- --

    全文を読む >
  • AAAgoogology

    Dmytro Taranovsky氏のC表記の解析結果をまとめたページ(ユーザー:AAAgoogology/TaranovskyのC表記の解析)を作成しました。 解析結果は十分な検証がされていないため、私のユーザーページの下に用意したページで公開しますが、 内容は他のページに転載していただいて構いません。 更新情報についてはユーザーブログの方に記載します。 解析結果のページのまえがきとほぼ同じ文章をこの記事に載せますが、詳細は解析結果のページを参照してください。

    Dmytro Taranovsky氏のC表記についての私の解析結果がすべて正しいとは限りません。 また、記述が不十分なところも多いので、理解できないところがあればコメントをお願いします。

    基本列の規則については推測するのが困難であるため、 プログラムで自動チェックした正しい基本列と比較して何度も修正しています。 現在の基本列の規則は\(\Omega_2\)を含む\(C\)が9個以下の順序数、\(\Omega_3\)を含む\(C\)が8個以下の順序数、 \(\Omega_4\)を含む\(C\)が8個以下の順序数、\(\Omega_5\)を含む\(C\)が7個以下の順序数に対して プログラムでチェックを行い、正しいことを確認していますが、 プログラムにバグがある可能性や、チェックしたよりも複雑な順序数に対しては基本列の規則に誤りがあるかもしれません。 誤りの実例を見つけた場合はその順序数をコメントで教えていただけるとありがたいです。

    私の解析結果で特に意義があると思われるのは次の3点です。

    1. 括弧が入れ子になって読みづらくなるのを、木構造で見やすく表記したこと。
    2. \(n\)-built from belowに相当する定義をす ……
    全文を読む >
  • Kyodaisuu

    順序数講座の11回目です。前回は、フェファーマンのθ関数を紹介しました。

    今回の講座では、ブーフホルツがフェファーマンのθ関数を改良して1986年に次の論文で発表したψ関数を紹介します。

    Buchholz, W. (1986) "A New System of Proof-Theoretic Ordinal Functions". Annals of Pure and Applied Logic, 32; 195-207.

    論文の最初のところだけ読んでみます。

    この論文では ψν (ν ≤ ω) という順序数の関数族を発表する。これは大きな構成的順序数を表記するこれまでの中で最も簡単な方法のようである。これらの関数はθ関数の簡略化バージョンであるが、同じ強さを持つ。(原文: In this paper we present a family of ordinal functions ψν (ν ≤ ω), which seems to provide the so far simplest method for denoting large constructive ordinals. These functions are a simplified version of the θ-functions, but nevertheless have the same strength as those.)

    つまり、θ関数よりも「簡単なのに同じ強さ」というセールスポイントで発表された関数です。これがその定義です。


    定義(ブーフホルツのψ関数)
    ブーフホルツのψ関数 ψν(α) = ψνα を次のように定義する。
    1. 順序数 ν, α に対して、集合 Cν(α) を次のように定める。
    2. Ων よりも小 ……


    全文を読む >
  • P進大好きbot

    サラダ注意。

    当初は\(\Omega\)収束点を崩壊させるつもりが崩壊させずにそのまま使ってしまったため、FGHで\(\omega\)になるという不具合がありました。今度こそちゃんと崩壊させたので\(\psi_0(\psi_I(0))\)に到達してくれたと思います。




    何の工夫もなく翻訳したので、ものすごく長ったらしくてすみません。ちなみに使ったのはBuchholzのオリジナルのψ関数ではなく英語版にある拡張の方です。\(\Omega\)収束点を崩壊させています。

    ただしそのまま翻訳したとは言っても、

    • 順序数側の加法を降順に直すステップの順序数表記における記述方法が思い付かなかったため、降順でない加法も許している。
    • 原論文にある\(G\)に関する制約を一切課していないため、\(G\)に関して下降するような\(\psi\)の適用を許している。

    という事情で重複のある表記となっています。それに起因してどれくらい弱くなるのかは分かりません。

    そして順序数崩壊関数から順序数表記を構成する方法はBuchholzのオリジナルの構成\(\psi \mapsto OT\)を使っています。これが拡張の方でも機能しているのかはよく分かりません。





    \(5\)種類の記号\((\)と\()\)と\(\langle\)と\(\rangle\)と\(,\)のみからなる文字列が「配列」であるという概念と「組」であるという概念を、以下のように帰納的に定める。

    (1) \(()\)は配列である。

    (2) 配列\(X_1,X_2\)に対し、\(\langle X_1, X_2 \rangle\)は配列であり組である。

    (3) 組\(X_1, \ldots, X_m\)(\(1 \leq m < \infty\))に対し、\((X_ ……






    全文を読む >
  • Kyodaisuu

    順序数講座の10回目です。前回は、ヴェブレン関数の定義をしました。

    1. φαβ は 0 と + とφγ
    全文を読む >
  • Koteitan

    バシク行列システムから派生した亜種ルールを分類したものです。目的は、各ルールの違いを比べることです。


    ルールセット名
    作者
    初出 定義 bad root
    探索 bad part
    コピー 議論 順序数解析


    BM1
    バシク
    2015.8.21

    • 定義(BASIC言語)
    • 数式による説明

    左隣法 BM1方式

    • 停止しない例(hyp/^,cos)
    • 停止しない例(Bubby3)
    • 対策(bashicu)



    rTSS
    rpakr
    2018.5.25

    • 定義

    左隣法 BM1方式 BM1のトリオ数列システムと同じ



    [http://ja.googology.wikia.com/wiki/ユーザーブログ:BashicuHyudora/BASIC言語による巨大数のまとめ?useskin=oasis#.E3.83.90.E3.82.B7.E3.82.AF.E8.A1.8C.E5.88.97.E6.95.B0.28Bashicu_matrix_number.29 BM1.1 の左の列。

    cf. rpakrさんの解説


    全文を読む >
  • P進大好きbot

    巨大数コンテストでありえそうなレギュレーションの例を考えて一覧化してみました。

    ここでのレギュレーションとは、巨大数コンテストにおける以下の情報のことです:

    • 略式のルール説明
    • 主催者側が提示する設定
    • 自然数とは何か
    • どのような手法で巨大数を定義してよいか

    例えば何のレギュレーションも指定しないコンテストだと、ZFCの証明論的順序数でFGHするレベルの素晴らしい計算可能巨大数がエントリーしたとしても、ビジービーバー関数みたいな小さい計算不可能巨大数がエントリーするだけで負けてしまいます。しかし計算可能なもののみ許容、というレギュレーションをつければそういう自体は回避できるわけですね。今回はそれをもうちょっと細かく分けてみるとどうなるか、的な雑記です。

    ちなみに「主催者側が提示する設定」は公理等のことです。主催者側が提示した設定は変えることが出来ず、かつ主催者側が提示していない設定は使うことが出来ません。例えば公理\(T\)が提示されていてもメタ理論が提示されていない場合、「\(T\)における計算可能関数の定義文となる論理式全体の集合を\(\Sigma\)とする」のようなメタ理論内の操作は禁止されますし、「このコンテストで\(2\)位を取る巨大数エントリーに\(1\)を足した巨大数をエントリーする」のような原始意味論的語彙の使用も禁止されます。

    以下はざっと思い付いた例ですので、何かこういうのもあるとかあったら教えて下さい。



    平たく言うと、

    • 計算可能巨大数をエントリーする。

    というルールです。定義可能性や計算可能性を厳密に書いたら割と面倒なことになりますが、書いてみました。計算可能巨大数というのが自然数の性質ではなく自然数の定義文の性質である点が厄介ですね。

    • 主催者側が提示する設定
      • 形式言語\(L ……


    全文を読む >
  • Kyodaisuu

    順序数講座の9回目です。前回は、エプシロン数つまりφ1の定義をしてから、ゼータ数つまりφ2を定義しました。

    1. φ0(α) は 0 と + で閉じているα番目の順序数
    2. φ1(α) は 0 と + とφ0 で閉じているα番目の順序数
    3. φ2(α) は 0 と + とφ0 と φ1で閉じているα番目の順序数

    のように定義されました。そして、一般にφαの定義は

    φα(β) は 0 と + とφγ
    全文を読む >
  • P進大好きbot

    前回はモデルに依存した巨大数について書きました。モデルに依存する巨大数はその定義に、「証明可能性」を用いる定義文だけでなく「モデルにおける真理値」を用いる命名文を用いているため、非常に沢山の論理式を材料として用いていることになります。

    しかしモデルを用いる手法は万能ではありません。まず前回の復習として、モデルを用いた巨大数には「メタ自然数の形式化をモデル内に相対化させた自然数」と「メタ自然数」の2種類がある、という話を念頭に置いて下さい。そこを混同すると、以下は本当に意味不明な内容となります。前者は形式体系内のモデルの元なのでメタ理論の項でもありますが、それはメタ自然数そのものとは限らないのです。例えばラヨ数などでやろうとしているのは後者の構成です。


    「メタ自然数の形式化をモデル内に相対化された自然数」として巨大数を定義する上では論理式のモデルでの真理値が使えますが、「メタ自然数そのもの」として巨大数を定義するために論理式全体を動かした時の真理値を参照するには使用するモデルそのものの具体的な指定が必要であるため、多くの場合はそれが不可能となります。

    どうして不可能なのか、は説明が難しいですが、例えばメタ論理がZFC集合論で、その中で展開する形式体系もZFC集合論であるとして、その形式体系のモデルがメタ理論の中で具体的に構成出来てしまったら、それはZFC公理系が自己の無矛盾性を示してしまうことになります。するとメタ理論のメタ理論であるメタメタ理論においてZFC公理系の矛盾が証明可能になってしまいます。ZFC公理系の矛盾は誰も見つけていないため、そのようなことは出来ません。

    ただし、メタ理論がZFC公理系に(コード化された)ZFC公理系の無矛盾性を加えたものを公理とする場合は、メタ ……


    全文を読む >
  • Kyodaisuu

    順序数講座の8回目です。前回は、ε0 を何通りかの方法で定義しました。

    1. ε0は 0 と + とφ0 で閉じている最小の順序数
    2. ε0は 0 と + とφ0 で有限の文字で書けるすべての順序数の集合
    3. ε0は φ0(α) = α を満たす最小の順序数
    4. ε0は基本列がε0[n] = φ0n(0) の順序数
    5. ε0 = φ0ω(0)

    ε0 は、φ1(0) とも書きます。そして、実は

    φ1(α) = εα

    と書いて、これを「α番目のε数(エプシロン数)」のように言います。つまり、最小のε数がε0です。このφ1という関数は、どのような関数でしょうか。ということで、次は φ1 という関数について考えます。

    ε0は 0 と + とφ0 で閉じている最小の順序数

    という定義をφ1を使って書くと

    φ1(0) は 0 と + とφ0 で閉じている最小の順序数

    となります。そして、

    φ1(α) は 0 と + とφ0 で閉じているα番目の順序数

    がφ1 の定義となります。φ0の定義と並べてみましょう。

    1. φ0(α) は 0 と + で閉じているα番目の順序数
    2. φ1(α) は 0 と + とφ0 で閉じているα番目の順序数

    定義の規則性が見えてきますね。この定義を基本として、φ1 の同等の定義をいくつか示します。

    まずは、このφ1の定義は

    φ1(α) は 0 と + とφ0 とφ1(β) (α>β) で有限の文字で書けるすべての順序数の集合

    と同じです。これはどういうことでしょうか。

    たとえば φ1(1) について考えてみましょう。これはつまり ε1です。すでに φ1(0) = ε0 が定義されたので、このε0という順序数と + とφ0 を使って作れるすべての順序数が、次の0 と + とφ0で閉じている順序数ということになります。同様に、φ1(α) を定義するときには、す ……

    全文を読む >
  • P進大好きbot

    前回は関数型論理式を用いた関数の再帰の定義可能性について説明しました。ペアノ算術では項の定義文を用いるだけだと関数が定義できないのですが、ペアの表現可能性により関数型論理式を直接再帰する方法がある、というのが著しく非自明なところです。

    今回はモデルに依存した巨大数について書いていこうと思います。一般に集合論のモデルが絡む話は非常に難しく、そして自分ではまず思いつかないだろうエレガントな技術が次々と現れます。形式論理を勉強して解説を書く、というのがこのブログの趣旨ですが、今回は特に色々な発見がありました。しかしながらそれらが関わるのはまだ先の話なので、とりあえず普通にモデルの話をしていきます。




    \(L\)を形式言語とし、\(A\)をその公理とします。\(L\)における\(A\)のモデルとは、集合\(M\)とその上の付加構造の組であって、それらが\(A\)に属する任意の論理式\(\Phi\)の相対化\(\Phi^M\)と呼ばれる条件を満たすもののことでした。

    定義だけ見てもイメージがつかないと思うので、例を書きます。

    • 自然数全体の集合\(\omega\)や、超フィルター\(F\)を用いてその5で構成した集合\(\omega_F^*\)はその自然な構造に関してペアノ算術のモデルをなす。
    • 群論のモデルとは、群のことに他ならない。
    • 環論のモデルとは、環のことに他ならない。
    • 体論のモデルとは、体のことに他ならない。
    • 実数全体の集合\(\mathbb{R}\)はその自然な構造について実閉体論や順序体論のモデルをなすが、付値体論や代数閉体論のモデルをなさない。

    要するに、公理を付加構造の条件のようなものに翻訳して、それが成り立てばモデル、成り立たなければモデルでない、ということです。集合論のモデルもこれ ……



    全文を読む >
  • P進大好きbot

    前回は証明可能性という概念を導入しました。予告では「モデルに依存した巨大数」について説明するつもりでしたが、最近また話題の不完全性定理について復習したのでそれに絡んで関数の再帰について書こうと思います。

    まず1階述語論理には変数が項であるという制約があり、関数や関係を動く変数を使うことが出来ません。そのため「定義文による拡大」を行う際、項と全く同じ方法では定義文を考えることは出来ません。

    しかしながら、既に説明してあるように項と同様の方法で定義文を考えることが出来ます。そのためには、項の定義文のように変数を一意存在量化することでその変数として何かを定義しようとするのではなく、関数を関数型論理式というものに翻訳して定義することになります。要するに関数\( x \mapsto f(x) \)を直接定義する方法はないので、代わりに変数\( x \)と変数\( y \)の間の関係を表す論理式\( y = f(x) \)を定義するということです。




    まずは関数型論理式という概念を導入します。


    定義(関数型論理式)
    \( L \)を形式言語とし、\( A \)をその公理とし、\( x_1, \ldots, x_n, y \)を\( L \)の相異なる変数の記号とする。\( L \)の論理式\( F \)が\( L \)の\( A \)における変数\( x_1, \ldots, x_n, y \)に関する関数型論理式であるとは、\( L \)の論理式\( \forall x_1( \cdots \forall x_n( \exists! y(F) ) \cdots ) \)が\( A \)において証明可能であるということである。

    特に、\( L \)の任意の項\( t_1, \ldots, t_n ……





    全文を読む >
  • Kyodaisuu

    順序数講座の7回目です。前回は、

    1. ω0 = 1
    2. 加算で閉じているωnの次の順序数、すなわち ωn以下の加算で閉じている順序数の有限個の降順の和で書けるすべての順序数をωn+1とする

    という定義で ωn (n

    全文を読む >
  • Merliborn

    二重再帰 (2)

    2018年5月17日 by Merliborn

    ←前回:ユーザーブログ:Merliborn/二重再帰の増加速度

    前回、(2変数)アッカーマン関数を定義することで、私たちは二重再帰関数の入り口に到達しました。
    ここで、原始再帰関数の集合と同様に「二重再帰関数」の集合を取り扱いたいのですが、筆者が調べる限り形式的定義が見当たりませんでした。
    (「巨大数論」では二重再帰について非形式的に、“合成作用素を数え上げるような原始再帰操作を数え上げる操作を2重再帰作用素(操作)とする。(後略)”と表記されています。)

    ということでフィッシュの二重再帰の定義とRobinsonのDouble Recursionの定義を基に、二重再帰および二重再帰関数をなるべく形式的に定義したいと思います。
    細かい事言い出すとどんどん見づらくなるので、適度に省略している要素が存在することをご了承ください。

    全文を読む >
  • Merliborn

    アッカーマン関数に代表される二重再帰関数は原始再帰的でない全域的再帰関数の例として有名ですが、その証明においては「任意の原始再帰関数よりアッカーマン関数の方が速く増加する」ということを証明することで、アッカーマン関数が原始再帰関数で表現できないことを示します。

    ここから、二重再帰および多重再帰の考え方が生まれ、巨大数論の中でも一つのステップを形成するほど大きなトピックを構成するわけですが、実際二重再帰の繰り返しはどの程度の増加を示すのでしょうか?

    さしあたり、二重再帰関数をn重に数え上げる関数の大きさはÂ(n,m)=A(A(..A(A(m,1),1)...,1),1)と同程度でしかないことをざっくりと示します。
    厳密な定式化はしてないので細かいところで訂正が必要かもしれませんが、少なくともこれに関して直接的な対角化は関数の増加にあまり寄与しないことを示します。

    全文を読む >
  • P進大好きbot

    前回はメタ自然数の形式化という概念を導入し、異なる体系で定義された巨大数同士を比較する方法を紹介しました。

    今回は「モデルに依存する巨大数」の説明の準備として証明可能性について説明します。まずは証明という概念を導入するために、公理と似た概念である論理公理および推論規則という概念を導入します。


    定義(論理公理)
    \(L\)を形式言語とする。\(L\)における論理公理とは、\(L\)の論理式であって、以下の7条件のいずれかが成り立つことである:
    (1) \(L\)の論理式\(\Phi,\Psi\)を用いて\(\Phi \to (\Psi \to \Phi)\)と表せる。
    (2) \(L\)の論理式\(\Phi,\Psi,\Psi'\)を用いて\((\Phi \to (\Psi \to \Psi')) \to ((\Phi \to \Psi) \to (\Phi \to \Psi'))\)と表せる。
    (3) \(L\)の論理式\(\Phi,\Psi\)を用いて\((\neg(\Psi)) \to (\neg(\Phi))) \to (\Phi \to \Psi)\)と表せる。
    (4) \(L\)の論理式\(\Phi\)と\(L\)の変数の記号\(x\)と\(L\)の項\(t\)を用いて\((\forall x(\Phi)) \to ((\Phi)[t/x])\)と表せる。
    (5) \(L\)の論理式\(\Phi,\Psi\)と\(\Phi\)に出現しない\(L\)の変数の記号\(x\)を用いて\((\forall x(\Phi \to \Psi)) \to (\Phi \to (\forall x(\Psi)))\)と表せる。
    (6) \(L\)の変数の記号\(x\)を用いて\(\forall ……







    全文を読む >
  • P進大好きbot

    前回は「定義による拡大」という概念を導入しました。予告では今回「証明可能性」を紹介するつもりでしたが、気が変わったので「異なる体系間の自然数の比較方法」について紹介します。




    形式言語\( L \)とその公理\( A \)が与えられていて、「何らかの方法」でその体系内の自然数概念が定義されているとしましょう。その自然数は他の体系内の自然数と比較出来るでしょうか? 出来るとしたら、その大小関係は何の体系の論理式となるのでしょうか?

    そもそも、算術とも集合論とも限らない体系内の概念を何を以て自然数と呼ぶのでしょうか? もちろん\( L \)と\( A \)だけでは自然数概念の決め方は一意でないでしょうし、何かしらのメタ論理式を条件として要請せずに好き勝手定義してしまうと\( 0 = 1 \)が証明可能になってしまうこともありえます。

    最初から一般の状況で考えてもイメージしにくいと思いますので、ひとまずペアノ算術やZFC集合論を思い浮かべましょう。ペアノ算術の項を全て「ペアノ算術の自然数」と呼ぶことにしてあげれば、ペアノ算術において与えられた項が自然数であるか否かを判定する論理式は恒真式なら何でも良くなりますので、例えば\( n = n \)を用いることが出来ます。

    しかし自然数概念にメタ論理式を条件として課そうが課さまいがペアノ算術の項全てを自然数と呼ぶことに必然性があるわけではなく、例えばペアノ算術の項であって関数記号\( S \)と項\( n \)を用いて\( Sn \)と表せる項(ここでは後続項と呼びましょう)のみを「ペアノ算術の自然数」と呼んでも問題ありません。何故なら、そのように制限された項のみを集めて部分体系を考えても、ペアノ算術の公理を再び満たすからです。「ペアノ算術の ……



    全文を読む >
  • P進大好きbot

    前回は公理という概念を導入し、論理式が公理の上で恒真であるという概念を紹介しました。公理というと1つの論理式を指して、その意味で複数の公理を指す時は公理系と呼ぶ方が一般的ですが、その場合に「公理」という言葉が論理式以上の意味を持たず分かりにくいと思ったので、ここでは公理系という言葉を用いずに公理と呼んでいます。

    恒真性は証明可能性と同値な概念ですが、証明可能性より定義が比較的簡単だと思うので、そういう理由で(面倒な証明可能性の代わりを意図して)恒真性を導入しました。というわけで、今回の記事で何かしらの論理式に対して「証明可能である」という言及があった場合、それを「恒真である」と各自読み替えて下さい。こうすることで、証明可能性という難しい概念を導入することを後回しにしようという魂胆です。皆さんがコンパイラだったら証明可能性の方がすんなり理解できると思いますが、そうでない場合、厳密に証明を文字列の統語を用いて定義して演繹定理という複数種類の公理での証明可能性の比較に関するメタ定理を文字列の長さに関するメタ帰納法で証明してそれを用いて証明の定義を拡張して、というのをやっていくのを読むのは結構しんどいと思います。




    さて、現代の数学では、主観を交えた議論や曖昧な定義に基づく誤りを避けるために、形式論理で定式化可能な理論だけを考えます。形式論理では形式言語という言語を固定して理論を展開するため、形式言語を固定した時点で、形式言語に属していなかったような単語を自分で定義して使うことが出来ないという問題があります。

    それを回避するのが「定義による拡大」という概念で、それは通常の数学で暗黙に行われており、何ら問題なく新たな単語を定義していくことが出来るようになっています。定義による拡大を説明す ……



    全文を読む >
  • Kyodaisuu

    順序数講座の6回目です。前回は、順序数の足し算について話をしました。最後にいくつかの練習問題を出しましたので、まずはその解答を書きます。

    問1. ω+2 の後続順序数が ω+3 となることを、後続順序数の定義から確認してください。

    ω+3 = ω+2 ∪ {ω+2} = {0,1,2,3,...,ω,ω+1} ∪ {ω+2} = {0,1,2,3,...,ω,ω+1,ω+2}

    これはたしかにω+3よりも小さいすべての順序数となる。

    問2. 2+4 = 6 となることを、「集合の要素を順番に数える」方法で確認してください。

    {0,1} と {0,1,2,3} を順番に数えると、{0,1,2,3} は {2,3,4,5} を数えることになって

    {0,1} ∪ {2,3,4,5} = {0,1,2,3,4,5}

    問3. (ω+2) + (ω+1) = ω2 + 1 を「集合の要素を順番に数える」方法で確認してください。

    {0,1,2,...,ω,ω+1} と {0,1,2,...,ω} を順番に数えると、


    α0 α1 α2 ... αω αω+1 β0 β1 β2 ... βω
    0 1 2 ... ω ω+1 ω+2 ω+3 ω+4 ... ω2

    つまり、ω+1 = {0,1,2,...,ω} を {ω+2,,ω+3,ω+4,...,ω2} として

    {0,1,2,...,ω,ω+1} ∪ {ω+2,,ω+3,ω+4,...,ω2} = {0,1,2,...,ω,ω+1,ω+2,...,ω2}

    となる。

    問4. ω3 の濃度がωとなるのはなぜか説明してください。

    ω3 = {0,1,2,...,ω,ω+1,ω+2,...ω2,ω2+1,ω2+2,...) と ω = {0,1,2,...} を一対一で対応づければ ……



    全文を読む >
  • P進大好きbot

    前回は\( \omega_1^{\textrm{FSS}} \)上にFGHを拡張しました。拡張と言うからには普通のFGHと何らかの関係があるべきですが、実際「\( \omega_1 \)未満の極限順序数全てに基本列を定義した時に得られるFGH」の拡張になっています。そのことを確かめるために、まずは\( \omega_1^{\textrm{FSS}} \)と\( \omega_1 \)の関係を調べましょう。


    命題(順序数との関係)
    写像\( \textrm{ord} \colon \omega_1^{\textrm{FSS}} \to \omega_1 \)であって以下を満たすものがただ1つ存在する:
    (1) \( \textrm{ord}(\emptyset) = \emptyset \)である。
    (2) 任意の\( \alpha \in \omega_1^{\textrm{FSS}} \)に対し、\( \textrm{ord}(\{\alpha\}) = \textrm{ord}(\alpha) + 1 \)である。
    (3) 任意の\( (\alpha_n)_{n \in \omega} \in (\omega_1^{\textrm{FSS}})^{\omega} \)に対し、「任意の\( n \in \omega \)に対し\( \alpha_n \in \alpha_{n+1} \)」を満たすならば\( \textrm{ord}(\{ \alpha_n \mid n \in \omega \}) = \bigcup_{n \in \omega} \textrm{ord}(\alpha_n) \)である。
    証明:
    補題(\( \omega_1^{\textrm{FSS}} \) ……





    全文を読む >
  • P進大好きbot

    前回は性質\( \textrm{FSS} \)というものを満たす最小の集合として\( \omega_1^{\textrm{FSS}} \)というものを定義しました。\( \omega_1^{\textrm{FSS}} \)は\( \omega_1 \)の類似物であり実際「可算順序数+基本列」のデータの集合とみなせるのですが、その話をする前に一応の実用性を説明すべく、今回はFGHが\( \omega_1^{\textrm{FSS}} \)上に拡張されることを示します。


    命題(FGHの拡張性)
    写像\( f_{\bullet} \colon \omega_1^{\textrm{FSS}} \to \mathbb{N}^{\mathbb{N}}, \ \alpha \mapsto f_{\alpha} \)であって以下を満たすものがただ1つ存在する:
    (1) \( f_{\emptyset}(n) = n \)である。
    (2) 任意の\( \alpha' \in \omega_1^{\textrm{FSS}} \)に対し、\( \alpha := \{ \alpha' \} \in \omega_1^{\textrm{FSS}} \)と置くと\( f_{\alpha}(n) = f_{\alpha'}^n(n) \)である。
    (3) 任意の\( (\alpha_n)_{n \in \omega} \in (\omega_1^{\textrm{FSS}})^{\omega} \)に対し、「任意の\( n \in \omega \)に対し\( \alpha_n \in \alpha_{n+1} \)」を満たすならば、\( \alpha := \{ \alpha_n \mid n ……




    全文を読む >
  • P進大好きbot

    巨大数を定義する上で順序数より使い勝手の良いものを模索する記事です。空気のようにZFC公理系を課します。

    やりたいことは、基本列をわざわざ取らなくてもFGHを考えられるような可算順序数もどきを定義し、それに合わせて非可算順序数もどきや基数もどきを構成していこうと思います。

    最初から抽象的な定義に入っても意図が伝わりにくいと思うので、まずは\( \omega_1 \)の類似物を具体的に構成します。そのために、以下のような性質を考えます。


    定義(性質\( \textrm{FSS} \))
    集合\( X \)が性質\( \textrm{FSS} \)を満たすとは、以下の3条件を満たすということである:
    (1) \( \emptyset \in X \)である。
    (2) 任意の\( \alpha \in X \)に対し、\( \{\alpha\} \in X \)である。
    (3) 任意の\( (\alpha_n)_{n \in \omega} \in X^{\omega} \)に対し、「任意の\( n \in \omega \)に対し\( \alpha_n \in \alpha_{n+1} \)」を満たすならば\( \{ \alpha_n \mid n \in \omega \} \in X \)である。

    \( \textrm{FSS} \)を満たす最小の集合を使いたいので、最小が存在することを示します。


    命題(性質\( \textrm{FSS} \)を満たす最小の集合の存在)
    集合\( X \)であって以下を満たすものがただ1つ存在する:
    (1) \( X \)は\( \textrm{FSS} \)を満たす。
    (2) 集合\( Y \)が\( \textrm{FSS} \)を満たすならば\( X ……








    全文を読む >
  • P進大好きbot

    前回は(1階述語論理の)形式言語の定義を雑に説明しました。形式言語は文字の集合\(\Sigma\)と文字列の集合\(L\)などの色々なデータから構成されていましたが、その辺を全部書くのは面倒なので、ここからは単に形式言語\(L\)と表現します。本来は集合と演算の組\((G,\times)\)である群のことを単に群\(G\)と呼ぶのと同じです。

    形式言語は(弱いまたは強い)集合論の項をなしますが、形式言語で記述される理論は外側の集合論を参照することが出来ません。なので外側の集合論のことを、形式言語で記述される理論と区別してメタ理論と呼ぶことにします。同様に外側の集合論を記述する形式言語のことをメタ言語と呼ぶなど、注目している形式言語やその理論の外側にある集合論に関係する概念に「メタ」という接頭辞を付けて区別します。


    外側の集合論で扱われるメタ対象と形式言語で記述される内側の理論で扱う対象はそのままでは混同することが出来ないため、それらは明確に区別する必要があります。ただし、内側の理論が集合論や算術である場合、部分的に外側の理論のメタ対象を自然に内側の理論の対象に対応させる方法が存在するため、この行き来を通じて「強い集合論の中の巨大数を、内側の形式言語の理論を用いて定義する」という手法が得られます。

    ただ、この辺りを明示的に述べている文献が少ないからなのか、メタ対象と対象の無自覚な(場合によっては一意でないどころか存在もしない)同一視が行われやすい、というのも形式言語を扱う上で注意が必要なところです。




    さて、形式言語を用いて理論を展開する場合、理論で言及される対象は項に限られます。項というものは定数の記号と変数の記号と関数の記号を組み合わせて統語上適正に構成できる文字列なのですが ……



    全文を読む >
  • Merliborn

    2018/05/07 - コメントを受けて語彙の変更を行いました


    急成長階層(fast-growing hierarchy)は元々、自然数上の関数を分類するためにLöbとWeinerが考案した、(最大でℵ1層からなる)関数の階層です。

    階層を定義するために順序数を添え字とした関数の一群が定義され、これは急増加関数と呼ばれます。

    急成長階層はGrzegorczyk階層の拡張として提案された階層の一つですが、添え字として可算順序数すべてをカバーし得るような設計になっています(設計されているだけ)。

    -- --

    全文を読む >
  • Kyodaisuu

    順序数講座の5回目です。前回は、ωについて話しました。この講座ではωよりも大きな順序数について考えます。まずは、ωの次の順序数を考えてみます。

    すでに第3回の講座で、後続順序数の定義について

    順序数αの後続順序数である α+1 は、αと {α} の和集合で定義される

    という話をしました。このαに、ωを入れてみましょう。

    順序数ωの後続順序数である ω+1 は、ωと {ω} の和集合で定義される

    ということになります。これで、ω+1を定義できます。要素を並べる方法では、ω = {0,1,2,3,...} と {ω} の和集合なので

    ω+1 = {0,1,2,3,...,ω}

    と書くことができます。ただし、... には「すべての自然数」が入っているものとします。ここで「+」という記号を使っていますが、まだこの講座では「順序数の足し算」の定義をしていませんでした。そこで、この講座ではその定義をします。自然数の足し算についてはよく知っているのでそのままで解釈できますが、このような超限順序数の足し算については、自然数の足し算とは違う性質があるので、足し算の定義を理解しておく必要があります。

    さて、ωはすべての自然数 {0,1,2,3,...} です。そして 1 は {0} です。このωと1を足す「ω+1」とはどういうことなのか。それは「ωを数えた後に1を数える」ということです。つまり、

    順序数の足し算は、順序数を足し算の順番に数える

    ということです。これまでの講座で、何度も順序数とは「順番に数える」という話をしました。順序数の足し算は、それと同じ感じで「順番に数えて」いくことで定義されます。

    それでは、どうやって数えるのでしょうか。「順番に数える」ということなので、ωと1を順番に並べてみましょう。

    { …… 全文を読む >
  • P進大好きbot

    前回は、形式論理を導入しないと「どのような文章が自然数の定義文となるか」や「どのような条件に対してそれを満たす最大の自然数が定義できるか」という基本的なことさえ不明確になる、というお話でした。ネタバレをすると、これはベリーのパラドックスという、基礎論の有名な話題です。




    ベリーのパラドックスの背景には、自然言語に厳密性がないという事情があります。より正確に言うと、自然言語には固定された統語や公理がないという2点が問題になります。

    統語とは、項(言語で言及する名詞のようなもの)や論理式(項に関する文章のようなもの)として、どのような文字列(文字の並び)を許容するかのルールです。

    公理とは、統語によって論理式として許容される文字列であって、「証明可能性」や「恒真性」を定義するために使うものです。この恒真性を用いることで、新たな概念を定義することが出来ます。従って、何かを証明したいわけでなくても、概念を定義するためには公理が非常に重要な役割を持つのです。



    自然言語の具体例としては日本語がありますが、日本語にはどのような文字の並びが名詞を指し、どのような文字の並びが文章の体裁を持つか、は固定された定義がありません。例えば「はるさめ」は「春雨」と「貼る鮫」の2通りの構文を持ちうるため、特にこの「はる」の部分が名詞なのか動詞なのかが言語のみでは決まらない(文脈に依存する)ものとなり、固定された統語を持たないことが分かります。

    そこで自然言語の代わりに、固定された統語と公理を持った言語として通常の数学で導入される人工言語が、いわゆる形式言語です。ここでは形式言語のうち、1階述語論理の形式言語と呼ばれる特別なものしか扱わないため、それを形式言語と呼びましょう。



    形式言語を定義するには、適当に弱い集合 ……






    全文を読む >
  • P進大好きbot

    形式論理について、何度か同じことを書いてるので、自分で引用しやすいように記事にしておきます。



    まず次の巨大数を考えましょう。

     Berry := \(10^{100}\)文字以下の定義文を持つ最大の自然数

    この巨大数wikiに書かれている文字数はどうせ\(10^{100}\)文字以下でしょうから、Berryは巨大数wiki内の全巨大数より大きい、と言えるでしょうか?

    言えませんね。実際、Berry+1は

     \(10^{100}\)文字以下の定義文を持つ最大の自然数 + 1

    という24文字の定義文を持つ自然数ですので、

     Berry+1 \( \leq \) Berry

    となり矛盾します。つまり、Berryという巨大数はそもそも定義されていないわけですね。



    じゃあ定義を完全にするために、少し修正してみましょう。

     Berry := 平仮名と0と1と2と3と4と5と6と7と8と9のみを100文字以下まで並べた文で定義できる最大の自然数

    さて、平仮名と0~9までの数字という文字は有限種類しかありません。数えるのは面倒ですが、せいぜい100種類以下でしょう。そして、100種類以下の文字を100文字以下まで並べて得られる文字列は、\(100^{100}\)種類以下しかありません。なので、この中で自然数の定義文であるものもまた、\(100^{100}\)種類以下しかありません。

    例えば10という自然数は、「9たす1」という4文字の定義文を持ちますね。なので、平仮名と0と1と2と3と4と5と6と7と8と9のみを100文字以下まで並べた文で定義できる自然数全体の集合は、空でなく、かつ有限集合です。自然数のみからなる空でない有限集合は数学的帰納法により最大値を持ちますので、Berryの存在が証明されました。



    と ……






    全文を読む >
  • Koteitan

    ラヨ数を理解するために、集合の世界を有向グラフで表した説明を書きました。 間違っていたらコメントで指摘下さい。

    • 追記 Koteitan(トーク) 2018年5月6日 (日) 06:29 (UTC)
      • ラヨ数にはZFCが公理として適用されるという見方、ZFCではないが自然数が定義できる程度のなんらかの定理は適用されているという見方、公理が存在しないという見方のいずれの解釈の人もいるので、このページの説明している解釈は一般的ではないことが分かりました。
      • ラヨ数に公理がないと、ラヨ命名される数が一意に定まらないことがあり得るようです。その場合は無効にする、という対策をすれば良さそうですが、もとのラヨ数の定義にはそのような仕組みはありません。
      • ZFCには置換公理図式があり、これは有限の論理式では表せないという意見がありました。確認中です。


    全文を読む >
  • KurohaKafka

    これが自然数だ、という直観的イメージをできるだけ公平に共有できるようにしたい。

    たとえば日常的に「3」という数字で表される数は、どういう特徴をもっているか?

    • 1より大きい
    • 2より大きい
    • 4より小さい
    • 素数
    • 三国志
    • フェルマーの最終定理

    etc…

    これらの中から数学的特徴を必要最低限取り出し、紙に書くなりネットに投稿するなりしてどこの誰とでも議論できるようにしたい。そのために共通の言語が必要となる。形式言語を使う。

    大前提として、直観的イメージはそのすべてを形式的表現に置き換えられるものではないとする。(というのは数学的には関係ないだろうな)

    手順

    直観的な自然数のイメージ

    形式言語にある程度翻訳された自然数

    マイクロ言語への翻訳

    モデル

    個々の自然数は1階述語論理で健全かつ完全に定義可能、すなわち、たとえばある項が2となるのであれば2であることを必ず証明することが可能であり、かつ証明可能であれば必ず2である。しかし自然数の2階部分についてはこの限りではない。超準モデルが絡んでくるのが問題であり1階述語論理が完全でないとかいうのではない。ラヨ関数は証明可能性で定義するとビジービーバー関数相当にしかならない? 超準モデルを避けるためにあらかじめ標準モデルでラヨ命名されることを断っておかなければならず、これは1階述語論理による公理では解決できない。超準的な関数でよければ超準モデルを許容してもいいが、そういうのは望まれてないだろう。

    全文を読む >
  • Kyodaisuu

    順序数講座

    2018年5月2日 by Kyodaisuu

    巨大数論で重要な役割を果たす順序数の講座です。順序数の基本からはじめて、大きな可算順序数を作る方法について解説します。巨大数に関心がある方にも順序数に関心がある方にも読んでいただける内容です。


    • (1) はじめに
    • (2) 自然数で順番に数える
    • (3) 次の数を定義する
    • (4) ωは自然数の集合
    • (5) 順序数の足し算
    • (6) 加算で閉じている順序数
    • (7) ε0の色々な定義
    • (8) エプシロン数からゼータ数へ
    • (9) ヴェブレン関数
    • (10) フェファーマンのθ関数
    • (11) ブーフホルツのΨ関数
    • (12) 巨大基数の崩壊

    この講座の著者は巨大数論著者のフィッシュあるいはふぃっしゅっしゅです。

    皆様の率直な感想を、このツイートへの返信あるいは匿名で投稿できる質問箱でお寄せください。 もし、誤字や内容の不備等を見つけられた場合にも、お知らせいただけるとありがたいです。

    全文を読む >
  • Kyodaisuu

    順序数講座の4回目です。前回は、自然数の定義について「次の数」を定義する方法について話しました。「空集合」つまり「0」の定義と、「次の数」つまり「後続順序数」の定義から、自然数が定義されるということが、前回までのまとめとなります。

    これでだいぶ順序数の用語にも慣れてきたので、巨大数論の120ページ「5.1.2 超限順序数とフォン・ノイマンの順序数表記」の最初に書かれている、この段落を読んでみます。

    順序数の定義ができたので、まずは有限な全順序集合の順序数、すなわち有限順序数 (finite ordinal) を考えます。有限な全順序集合は、要素の無限降下列を作ることができないので整礎です。全順序集合 A と B がそれぞれ k 個の要素を持つとき(k は非負整数)、順序同型なので同じ順序型を持ちます。その順序型が順序数で、0, 1, 2, 3, ... のように要素の個数 k と等しい自然数(非負整数)で表記します。このように有限順序数が自然数で表記されるため、順序数は自然数を拡張した概念であるとされます。

    ここに書かれていることをまとめると

    有限な全順序集合の順序型(有限順序数)はその集合の要素の個数と等しい自然数だよ

    ということになります。これは、これまでの講座で説明してきた通りですね。ここで「有限順序数」という言葉が出ました。これまでの講座では「自然数」について考えていたということは「有限順序数」について考えていた、ということになります。ここで「有限」という言葉が使われていますが、そもそも「有限」とか「無限」ってなんでしょうか。

    日常的には「有限」とか「無限」という言葉はかなり曖昧に使われていますが、無限は「きりがないもの」「限りがないもの」というような意味で使われます。数学 ……

    全文を読む >
  • Kyodaisuu

    順序数講座の3回目です。前回は、巨大数論の115ページからはじまって、121ページの

    順序数を自分自身よりも小さいすべての順序数の集合であると定義できます。

    という定義から、自然数とは

    3つのリンゴがあったときに、それを0,1,2と順番に番号を振ると3になる

    ということだよ、という話をしました。そのときには、たとえば自然数の部分集合である {5,7,8,9} という整列集合を、「4よりも小さい自然数の集合」である {0,1,2,3} と「順番を変えずに」対応づけることが、ちょうど「順番に番号を振る」ということだよ、という話をしました。

    ここで、自然数を「自分自身よりも小さいすべての自然数の集合」である、つまり

    0 = {} 1 = {0} 2 = {0,1} 3 = {0,1,2} 4 = {0,1,2,3}

    のように定義するとはどういうことか、ということについてもう少し考えてみます。この定義を見ると、すべての自然数が定義できている「構造」を見ることができます。たとえば、ここには 5 の定義が書かれていませんが、

    5 = {0,1,2,3,4}

    であることはわかります。それはなぜでしょうか。それは、5は「5よりも小さいすべての自然数の集合」なので、これまでに定義したすべての自然数を要素とした集合を書けばいいのです。それでは「5よりも小さいすべての自然数の集合」が {0,1,2,3,4} であることはなぜわかるのでしょうか。それは、これまでに 0,1,2,3,4 を定義して、その次の数が5だからです。このように、「5よりも小さいすべての自然数」が定義されてはじめて、5という数が定義できます。こういう定義の構造を「帰納法」と言います。4という数が定義できれば、4の次の数である5を定義できる、 ……

    全文を読む >
  • Kyodaisuu

    順序数講座の2回目です。前回は、講座の進め方について話しました。巨大数論をテキストとして、順序数についてなるべく平易に解説をするという趣旨でした。それでは早速「第5章 順序数」から読み始めます。

    115ページは前書きで、何のために順序数を導入するのかということが書かれています。FGHのような順序数階層とかで使われるよ、ということですね。そして「5.1 順序数」で、順序数を定義します。その最初にこんなことが書いてあります(p.116)。

    集合論の創始者であるドイツの数学者、 (Georg Cantor, 1845-1918) は、自然数を拡張した順序数 (ordinal number) という概念を考えました。順番に並べられたものに対して、順序数で「番号」を振ることができます。ここで、その「順番に並べられたもの」が有限であれば「番号」は自然数で足りますが、無限にあるときにも番号を振ることができるようにしたものが順序数です。

    ここには何が書かれているかというと、順序数とは

    1. 自然数を拡張した概念だよ
    2. 順番に並べたものに番号を振るよ
    3. 無限にあってもかまわず番号を振るよ

    ということです。そこでまずは「自然数」「順番に並べたものに番号を振る」ということについて考えてみます。

    自然数という言葉は学校で習うと思いますが、自然数ってなんでしょうか?「1,2,3,...といった数」ですね。そして、自然数に「0」と「マイナスの数(-1,-2,-3,...)」を加えたものが「整数」である、といった感じで、自然数から先については詳しい説明がありますが、そもそも「1,2,3,...といった数がなんであるか」と聞かれると、あまりうまく説明できないのではないでしょうか。さて、まず小学校で最初に「数」を習うときに、どの ……

    全文を読む >
  • Hassium108

    S+C+U+N+fLで表されるシステムのバリエーション


    • 項は列でもある
    • 非負整数は列である
    • 列\(S\)と非負整数\(a\)に対し\([S]_a\)は項である
    • 項\(X\)と列\(S\)に対し\(XS\)は列である

    関数記号\(H_k\)、自然数\(n\)、列\(S\)に対し\(nH_kS\)を第\(k\)準ヒドラの正規形とする。


    \(T_k(n)=nH_k[[...[0]_n...]_1]_0\)

    第\(k\)準ヒドラ数\(=T_k^{10}(10)\)


    • \(a,b:\)非負整数
    • \(■:\)1個以上の項
    • \(□:\)0個以上の項

    rule1: \(nH_1a=n+a\)

    rule2: \(nH_1■a=(n+a)H_1■\)

    rule3: \(■0=■\)

    rule4: \([0]_0=n\)

    rule5: \([□a+1]_b=\underbrace{[□a]_b[□a]_b...[□a]_b}_n\)

    rule6: \([0]_{a+1}=f^n(0):f(x)=[x]_a\)


    \([[0]_1]_0={\varepsilon_0}\)
    \([[0]_11]_0={\varepsilon_0×{\omega}}\)
    \([[0]_1[0]_1]_0={\varepsilon_0^2}\)
    \([[1]_1]_0={\varepsilon_0^{\omega}}\)
    \([[[0]_1]_1]_0={\varepsilon_0^{\varepsilon_0}}\)
    \([[[0]_2]_1]_0={\varepsilon_1}\)
    \(T_1(n)\approx f_{\varepsilon_{\omega}}(n)\)

    小拡張第3配列システム


    • \(a,b:\)非負整数
    • \(m,a_1,a_2,...a_m:\)自 ……






    全文を読む >
  • Kyodaisuu

    この講座は巨大数論の著者であるフィッシュことふぃっしゅっしゅが、巨大数論で重要な役割を果たす「順序数」についてなるべく丁寧に解説しようと試みた講座です。

    巨大数論をやっていくと、順序数が一つの関門となります。それで「巨大数論」では、まずは第4章までは順序数を使わずに説明して、5章からおもむろに順序数を導入しています。これは、最初は「順序数という概念を理解しないでも読めるように」という配慮でした。そして順序数を使って急増加関数 (FGH) による関数の評価ができるようになり、巨大数の理解が進みます。ところが「巨大数論」を読む上で「順序数」に入ってからよくわからなくなる、という人も多くなってきていました。

    とりあえず「順序数なんてわからなくたって、ωを記号だと思えばFGHは理解できるし、なんとかなる」と進めていくのも一つの方法ですが、やはり順序数とはなにかがわかると、FGHについても理解が進みます。とはいえ、順序数を理解するためには、いわゆる数学基礎論の難しい話を理解しないと「きちんと」理解することができないので、どうしても敬遠しがちです。「巨大数論」では、第5章と7章に順序数を理解するために必要なことを書いたつもりですが、集合論の記号が出て来てしまうと、なかなか読み進めにくいという面もあるようです。

    私自身が数学の専門家ではないので、あまり数学的に厳密な書き方には慣れていないのですが、「巨大数論」では私なりに数学的に正確な記述を目指して書きました。一方で、数学的に正確な記述がわかりやすいかというと、どうもそれだけではわかりにくい、という面もあるようです。つまり、ある式の定義がわかったとしても、その式に込められている「気持ち」のようなものがわからないと、理解できた気持ちにはならな ……

    全文を読む >
  • Kyodaisuu

    3変数アッカーマン関数とチェーン表記の間には、次のような関係がある。

    x=1, y>1 または x>1, y+z>0 のとき

    \[A(x,y,z) < \underbrace{3 \rightarrow3 \rightarrow \cdots \rightarrow 3}_{x+1個の3} \rightarrow z+2 \rightarrow y+1 < A(x,y,z+1)\]

    証明はアッカーマンチェーン定理を参照。

    したがって、たとえば

    • A(1,2,1) < 3→3→3→3 < A(1,2,2)
    • A(2,2,1) < 3→3→3→3→3 < A(2,2,2)
    • A(3,2,1) < 3→3→3→3→3→3 < A(3,2,2)

    となる。

    全文を読む >
  • Koteitan

    Tranovsky's C Notation のツリー表示による図解です。

    • Edwin Shade, "A Complete Analysis of_Taranovsky's Notation" (Googology Wiki)
    • Boboris, 'Analysis of Taranovsky's Ordinal Notation with "standard OCFs."' (Googology Wiki)

    を参考にしました。

    全文を読む >
  • Koteitan

    書いては見ましたが

    今考えると、停止性の証明可能性の観点では一番下の定義は蛇足で、上2つあたりがいいです。数の増加を考えるとどれが良いのかはわかりません。

    全文を読む >
  • Nayuta Ito

    test

    2018年3月29日 by Nayuta Ito

    これはサンドボックスです。

    日本語の文字を含むTeXを出力できる環境がここしかない(英語版でもできない)のでこちらにも日本語検証用のサンドボックスを作りました。

    \( \text{123}^\text{あいう} \)

    全文を読む >
  • Koteitan

    ペア数列のヒドラ表記は ユーザーブログ:Koteitan/バシク行列のヒドラ表記 で解説しましたが、このポストではトリオ数列以上のバシク行列はどう表現されるか、展開はどう表現されるかを解説します。


    このポストで説明している表記法は、ユーザーブログ:KurohaKafka/バシク行列のブーフホルツのヒドラを応用した表現 (KurohaKafka, 2017.5.24) の「多次元空間上のツリー」をビジュアライズしたものです。

    このポストで説明している展開方法は、バシク行列システムの解説 2版 (Bashicu, 2017.6.25--2017.7.17, SlideShare) にある説明、つまり、BM2 をビジュアライズしようとしたものだったのですが、実際には SlideShare のものとは少し異なる展開方法になってしまいました。この新しい展開方法をもつシステムはBM2.1としてこちらに掲載しました。BM2は、BM1 が (0,0)(1,1)(2,1)(3,1)(2,0)(1,1)(2,1)(3,1) で停止しなくなる問題を修正されたものですが、こちらのBM2.1でも同様の展開ができ、かつこちらの方がBM1に近く、ヒドラの動きから見ても本質的な修正になるのではないかと考えています。


    (注意)[2]の怒る親の選定方法がバシクさんのSlideShareと少し異なります。また、図8のΔの足し方も少し異なります。


    全文を読む >
  • Koteitan

    ペア数列までのバシク行列のヒドラ表記の仕方の解説です。 一次資料は下記。

    • ユーザーブログ:KurohaKafka/バシク行列のブーフホルツのヒドラを応用した表現 (KurohaKafka, 2017.5.24)
    • バシク行列システムの解説(第2版)(Bashicu, 2017.6.25--2017.7.17, SlideShare)
    • W. Buchholz, "An independence result for "

    下記はε0~ζ0のペア数列のヒドラ表記の例です。



    次にバシク行列のヒドラの書き方を説明します。

    ペア数列をヒドラ表記に変換する方法を一気に説明するとこれになります。 実際は以下の手順で書いていくと書きやすいです。まずは1行目の数字を高さにして空の丸を書いていきます。 次に2行目を見て丸の中にラベルを書いていきます。 次に枝を付けます。注目する子ノードに対して、「1階層低くかつ一番右にあるノード」を親ノードとして、子ノードと親ノードを枝でつなぎます。これを全部のノードに対して行うと完成です。


    ここからはペア数列の展開の方法を説明します。ラベル0の子が刈られると親は怒ってn倍に分裂します。 1以上ののラベルの子が刈られるときは、刈られた子から親へ親へと辿りながら、刈られた子よりも小さなラベルを持つノードを探します。見つかったら、それがコピーされる親(bad root)になります。親が子の場所に遺族ごと階層方向にn+1倍にコピーされます。遺族というのは親より右にあるすべてのノードです。(点線で囲った部分)


    ペア数列とブーフホルツのヒドラの展開の違いです。

    伸び量
    ペア数列はn+1倍に伸びますが、ブーフホルツのヒドラは毎回2倍になり、nに依存しません。
    親のコピー先のラベル
    ブーフホルツの ……





    全文を読む >
  • Kyodaisuu

    ペア数列解析の訳

    2018年2月25日 by Kyodaisuu

    ペア数列数のトークページに書かれていることを、ざっくりと訳しました。


    このシステムをかなり時間をかけて解析したところ、ここまでは記事と同様の結果を得た。

    私が得た基本的な結果:

    |A| を数列 A の順序数とする。

    定理1. (0,0) は数列を加法(連結)に分解する。たとえば
    |(0,0) A (0,0) B (0,0) C| = |(0,0) A| + |(0,0) B| + |(0,0) C|

    証明:

    (0,0) は計算ルールをストップさせて数列を分割させる働きを持っている。すなわち「悪い列」を探す規則は、(0,0)を飛び越えることはない。したがって、(0,0) によって分離された部分数列は、順番に評価され、最終的な順序数は分離された数列ごとに評価された順序数の和となる。


    数列 A のそれぞれの項について、1つ目の数を b 減らして2つ目の数を c 減らすことを [A - (b,c)] と書く。たとえば [(1,1)(2,1)(3,1) - (1,1)] = (0,0)(1,0)(2,0) である。

    定理 2. (0,0) が含まれない数列の部分では、(1,0) は以下を満たす。
    |(0,0) A (1,0) B| = |(0,0)A| * ω^|[(1,0) B - (1,0)]|

    証明:

    指数 |[(1,0)B - (1,0)]| についての帰納法による。

    後続順序数のとき:定理1により |(0,0) B| + 1 = |(0,0) B (0,0)| である。よって

    |(0,0) A| * ω^|(0,0) B (0,0)| = |(0,0) A| * ω^(|(0,0) B| + 1)

    = |(0,0) A| * ω^|(0,0) B| * ω

    = |(0,0) A (1,0) [B + ……





    全文を読む >
  • Koteitan

    原始数列数から対応する順序数を簡単に求める方法の図解です。

    原始数列数

    Primitive sequence analyzer (by Kyodaisuu )

    全文を読む >
  • Hassium108

    順序数表記

    2018年2月20日 by Hassium108

    自作の順序数表記の構想メモ。定義は多分一生完成しない。

    ※関数記号に特に意味はありません。使われていないものを適当に選んでいます。


    ψ関数を拡張した順序数崩壊関数。

    \({\rho^{\omega}_n}(0)={\rho^{n+1}_n}({\Omega_{n+1}})\)

    \({\rho_1}({\Omega_2×{\alpha}})→{\Omega_{1+\alpha}}\)

    \({\rho}_0(0)={\psi}_0(0)\)
    \({\rho}_0({\Omega})={\psi}_0({\Omega})\)
    \({\rho}_0({\rho}_1(0))={\psi}_0({\psi}_1(0))\)
    \({\rho}_0({\rho}_1({\rho}_1({\Omega}_2)))={\psi}_0({\psi}_1({\Omega}_2))\)
    \({\rho}_0({\rho}_1({\rho}_1({\Omega}_2)+1))={\psi}_0({\psi}_1({\Omega}_2+1))\)
    \({\rho}_0({\rho}_1({\rho}_1({\Omega}_2)^}})))={\rho_0({\rho}_1({\rho}_1({\rho}_2(0))))}\)

    数列を利用した順序数崩壊関数。\({\rho}\)関数の旧バージョンの簡略化。

    \({\tau_0}()=0\)

    \({\tau_0}(\#,0)={\tau_0}(\#)+1\)

    \({\tau_0}(\#,{\alpha+1})={\tau_0}(\#,{\alpha},{\alpha},{\alpha},...)\)

    \({\tau_0}(\#,{\alpha})[n]={\tau_0}(\#,{\ ……



    全文を読む >
  • Kyodaisuu

    原始数列の順序数を表示するプログラムを作成した。

    • Primitive sequence analyzer 原始数列解析

    ボックスに原始数列を入れて送信ボタンを押すと、対応する順序数が表示される。

    原始数列の入力方法は、たとえば (0,1,2,3) を入れるためには、

    0123

    と、数字をそのまま並べれば良い。

    2桁以上の数を入れるためには、セパレーターとしてスペースまたはカンマを使う。セパレーターを使うと、数字の並びはすべて1つの数として認識される。

    たとえば、

    0123412333

    と入力すると、(0, 1, 2, 3, 4, 1, 2, 3, 3, 3) の順序数が

    \[\omega^{\omega^{\omega^\omega}+\omega^{\omega^3}}\]

    のように表示される。

    なお、原始数列について詳しくは『巨大数論 第2版』の160〜167ページを参照。


    数列は次のように標準化される。

    • 0で始める
    • 1つずつ数が増える
    • 順序数の足し算で、\(\alpha < \beta\) のときに \(\alpha + \beta\) の形のときに \(\alpha\) を取る

    たとえば、(1,3,5,7) は (0,1,2,3) として、(0,1,0,1,2) は (0,1,2) とする。


    ソースコードはMITライセンスで公開されている。

    Python 2 のプログラムであり、通常モードではコマンドラインプログラムとしてターミナルで動かすことができる。環境変数 SCRIPT_NAME が設定されているときには、CGI プログラムとして動作する。

    全文を読む >
  • じぇいそん

    拡張矢印表記

    2018年2月8日 by じぇいそん
    全文を読む >
  • Kyodaisuu

    Hassiumさんの巨大数問題10

    大グラハム数を11で割った余りを求めよ。

    を考えるついでに、グラハム数を自然数Nで割った余りを計算するプログラムを作りました。

    - グラハム数 mod N の計算

    オンライン版はサーバーに負荷をかけたくないので N = 10^5 までにしています。

    TokusiN さんによるグラハム数1,000,000桁表〈最終巻〉では N=10^10^6 が計算されています。そのように大きな N の値を計算するためには、もっと効率的なアルゴリズムを使う必要があると思います。

    N = 11 として計算すると

    3^n mod 11 = [1, 3, 9, 5, 4] (cycle length = 5) 3^3^n mod 11 = [3, 5, 4, 9] (cycle length = 4) 3^3^3^n mod 11 = [5, 9] (cycle length = 2) 3^3^3^3^n mod 11 = [9] (cycle length = 1)
    G mod 11 = 9

    のように表示されます。Hassiumさんの解答と比べると、同じ結果となっています。

    3^n mod 11 = [1, 3, 9, 5, 4] (cycle length = 5)

    というのは、3^n mod 11 を n=0 から計算すると、このような長さ5のループとなることを示しています。

    N = 109 を計算すると

    3^n mod 109 = [1, 3, 9, 27, 81, 25, 75, 7,..., 105, 97, 73] (cycle length = 27) 3^3^n mod 109 = [3, 27, 63, 1] => 1 Rotation is 3^3 ……
    全文を読む >
  • 海老天

    メモ

    2017年11月8日 by 海老天

    \(B(m,n) = A(\underbrace{m,m,\dots,m}_{n個})\)


    \(A(a_1,a_2,\dots,a_k) = A(\underbrace{A(a_1,a_2,\dots,a_k-1),\dots,A(a_1,a_2,\dots,a_k-1)}_{(k-1)個},a_k-1)\)

    \(A(a_1,a_2,\dots,a_k,0) = A(a_1,a_2,\dots,a_k)\)

    \(A(x) = x^{x}\)

    全文を読む >
  • Hassium108

    fghの剰余

    2017年10月26日 by Hassium108

    twitterで出した問題[1]について調べてみると結構面白かったので、計算結果を残す。

    ※\(n\)が小さいとき例外的に成り立たないことがあるかもしれないが、とりあえず無視する。

    \(f_{\omega}(20n+)≡ (mod 10)\)





    \(f_{\omega}(6n+3)≡0 (mod 3)\)
    \(f_{\omega}(6n+4)≡1 (mod 3)\)
    \(f_{\omega}(6n+5)≡1 (mod 3)\)




    \(f_{\omega}(20n+10)≡0 (mod 5)\)
    \(f_{\omega}(20n+11)≡3 (mod 5)\)
    \(f_{\omega}(20n+12)≡2 (mod 5)\)
    \(f_{\omega}(20n+13)≡1 (mod 5)\)
    \(f_{\omega}(20n+14)≡1 (mod 5)\)
    \(f_{\omega}(20n+15)≡0 (mod 5)\)
    \(f_{\omega}(20n+16)≡1 (mod 5)\)
    \(f_{\omega}(20n+17)≡4 (mod 5)\)
    \(f_{\omega}(20n+18)≡2 (mod 5)\)
    \(f_{\omega}(20n+19)≡2 (mod 5)\)




    \(f_{\omega}(6n+3)≡0 (mod 6)\)
    \(f_{\omega}(6n+4)≡4 (mod 6)\)
    \(f_{\omega}(6n+5)≡4 (mod 6)\)




    \(f_{\omega}(20n+10)≡0 (mod 10)\)
    \(f_{\omega}(20n+11)≡8 (mod 10)\)
    \(f_{\omega}(20n+12)≡2 (mod 10)\)
    \(f_{\omega}(20n+13)≡6 (mod 1 ……































    全文を読む >