FANDOM


  • P進大好きbot

    反例アドベントカレンダー9日目のエントリーです。

    \(\textrm{Lim}\)で\(0\)でない極限順序数全体のクラスを表します。

    この記事では関数と言ったら写像\(\mathbb{N} \to \mathbb{N}\)を指し、関数全体の集合を\(\textrm{Func}\)と置きます。2つの関数\((g,h) \in \textrm{Func}^2\)に対し、その大小関係\(g < h\)を増大度の大小で定義します。すなわち、\(g < h\)であるとは、ある\(N \in \mathbb{N}\)が存在して任意の\(n \in \mathbb{N}\)に対し\(n > N\)ならば\(g(n) < h(n)\)となるということです。

    順序数\(\alpha\)で添字付けられた関数の族\((g_{\beta})_{\beta \in \alpha} \in \textrm{Func}^{\alpha}\)が線形階層であるとは、任意の\((\beta,\gamma) \in \alpha^2\)に対し\(\beta < \gamma\)ならば\(g_{\beta} < g_{\gamma}\)が成り立つということとして定義します。

    可算順序数\(\alpha\)とその基本列系 \begin{eqnarray*} \textrm{Lim} \cap \alpha & \to & \alpha^{\mathbb{N}} \\ \beta & \mapsto & (\beta[n])_{n \in \mathbb{N}} \end{eqnarray*} に付随するFGH。

      1. \(\beta[n] = \gamma_0 + \cdots + \gamma_{m-1} + \gamm ……
    全文を読む >
  • P進大好きbot

    5周年

    2018年12月5日 by P進大好きbot

    今日は英語版の創立10周年記念日だそうです。


    そこで、日本語版の創立はいつなのか気になってみて調べてみました。


    皆さんは、ご存知でしょうか?


    少し考えてみて下さい。


    答えは↓に書いてあります。






















    分かりましたか?


    そう、日本語版の方は、英語版の創立5周年記念日に創立されたようですね。


    ということは、ある1つの重要な事柄にお気付きではないでしょうか?


    簡単な演繹ですので、もう一度じっくり考えてみて下さい。


    答えは↓にあります。
























    もうお分かりでしょうか?


    まだの方は、もう少しお考え下さい。



























    もうお分かりですね?


    そう、その通りです。


    なんと今日は!


    日本語版の創立5周年記念日でもあるというわけですね!


    証明


    我々は巨大数を扱っているので、このような計算もお手の物です。


    おめでとうございます。

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

    Math Advent Calender 2日目の記事です。

    \(\textrm{ZFC}\)公理系の下で、\(\textrm{ZFC}\)公理系の無矛盾性を仮定して矛盾を導きます。(※よくあるネタです)

    \(L\)を\(\textrm{ZFC}\)集合論の言語とします。つまり可算無限個の変数記号\(x_0, x_1, x_2, \ldots\)と2つの二項関係記号\(=, \in\)を持つ、\(1\)階述語論理の形式言語です。\(L\)論理式の集合である\(\textrm{ZFC}\)公理系を\(A\)と置きます。仮定より\(A\)は無矛盾となります。

    \(A\)の下で\(\emptyset\)や\(\cup\)や\(\mathbb{N}\)における大小関係\( 0\)ならば、\(P_n\)は\(L\)論理式\(\forall x_{n-1}(P_{n-1} \to (x_n = x_{n-1} \cup \{x_{n-1}\}))\)である。 これは自然数のvon Neumann構成そのものですので、\(\exists x_n(P_n)\)は\(A\)の下で証明可能です。

    \(L\)に定数記号\(c\)を添加した形式言語を\(\hat{L}\)と置きます。

    \(\hat{L}\)論理式\(c \in \mathbb{N}\)を\(Q\)と置きます。

    各自然数\(n\)に対し、\(\hat{L}\)論理式\(\forall x_n(P_n \to (n < c))\)を\(R_n\)と置きます。

    \(\hat{L}\)論理式の集合である公理系\(A \cup \{\Psi\} \cup \{R_n \mid n \in \mathbb{N}\}\)を\(\hat{A}\)と置きます ……

    全文を読む >
  • Koteitan

    6月くらいに考えた Upper-Branch-Ignoring モデル (上枝無視モデル) というバシク行列(BM4)のヒドラ表現を紹介します。(バシク行列の展開ルールと、この記事内の数式については、バシク行列の数式的定義 を見てください。バシクさんのオリジナルの定義はこちらにあります。)


    BM4 の bad root 探索の方法については、Bubby3 さん、Ecl1psed276 さん、Alemagno12 さんが下記の記事で分かりやすく説明してくれています。

    • Bubby3, BM1 は期待より弱い -その修正方法
    • Ecl1psed276 and Alemagno12, BM2 のプログラムフリーな定義?

    これらの方法は内容は同じで、Ecl1psed276 さん、Alemagno12 さんはこの方法を sequence reduction method (数列削除法) と呼び、Bubby3 さんは upper-branch removing method (上枝削除法)と呼んでいます。

    Bubby3 さんは下記のように (0,0)(1,1)(2,2)(3,0)(2,1)(3,1)(4,1) という行列を例に upper-branch removing method を使った bad root の見つけ方を説明してくれています。

    1. (0,0)(1,1)(2,2)(3,0)(2,1)(3,1)(4,1)
    2. (0,0)(1,1)(2,2)(3,0)(2,1)(3,1)(4,1)
    3. (0,0)(1,1)(2,2)(3,0)(2,1)(3,1)(4,1)
    4. (0,0)(1,1)(2,2)(3,0)(2,1)(3,1)(4,1)
    5. (0,0)(1,1)(2,2)(3,0)(2,1)(3,1)(4,1)
    6. (0,0)(1, ……

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

    解析の練習です。浮笠さんのキマイラ数2号 Ver. 4を解析します。

    左辺の変数の最大値を\(M\)と置き、\(M \geq 3\)とする。\(X\)の長さを\(L\)と置き、\(L \geq 3\)とする。\(n \geq 3\)とする。左辺の変数末尾が\(a+1,b+1\)の式は数学的帰納法で導出している。左辺に\(n\)が現れる式は数学的帰納法で導出している。 \begin{eqnarray*} \textrm{Ch}[1](a,b) & \leq & \max \{a^b,a^a\} \leq M^M < f_3(M) \\ \textrm{Ch}[1](x_1,a,1) & = & \textrm{Ch}[1](x_1,a) < f_3(M) \\ \textrm{Ch}[1](x_1,1,b+1) & = & x_1^{x_1} \leq M^M < f_3(M) \\ \textrm{Ch}[1](x_1,1,2) & < & f_3(M) = f_3^1(M) \\ \textrm{Ch}[1](x_1,a+1,2) & = & \textrm{Ch}[1](x_1,\textrm{Ch}[1](x_1,a,2),1) < f_3(f_3^a(M)) = f_3^{a+1}(M) < f_4(M)\\ \textrm{Ch}[1](x_1,1,3) & < & f_3(M) < f_4^1(M) \\ \textrm{Ch}[1](x_1,a+1,3) & = & \textrm{Ch}[1](x_1,\textrm{Ch}[1](x_1,a,3),2) < f_4(f_4^a(M)) < f_4^{ ……

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

    巨大数たんアドベントカレンダー初日エントリー用の記事です。どうやら僕以外に誰も投稿しなさそうなので、遠慮なくこっそり事前公開してしまいます。

    全域計算可能関数\(\textrm{AC}_1(x)\)を定義します。誰か解析して下さい。

    ちなみに使って良い関数等は四則演算と自身が定義するものとカレンダー内で定義されたもののみというルールですので、冪乗や合成等も定義していきます。



    \(\mathbb{N}_{+}\)で正整数全体の集合を表す。


    正整数\(x\)と整数\(n\)に対し、正有理数\(x^n\)を以下のように再帰的に定める:

    1. \(n = 0\)ならば、\(x^n = 1\)である。
    2. \(n > 0\)ならば、\(x^n = x^{n-1} \times x\)である。
    3. \(n < 0\)ならば、\(x^n = \frac{1}{x^{-n}}\)である。


    正整数\(x\)と\(n\)に対し、正整数\({}^n x\)を以下のように再帰的に定める:

    1. \(n = 0\)ならば、\({}^n x = 1\)である。
    2. \(n > 0\)ならば、\({}^n x = x^{({}^{n-1} x)}\)である。


    写像\(f \colon \mathbb{N}_{+} \to \mathbb{N}_{+}\)と自然数\(n\)に対し、写像 \begin{eqnarray*} f^n \colon \mathbb{N}_{+} & \to & \mathbb{N}_{+} \\ x & \mapsto & f^n(x) \end{eqnarray*} を以下のように再帰的に定める:

    1. \(n = 0\)ならば、\(f^n(x) = x\)である。
    2. \(n > 0\)ならば、\(f^n(x) = f(f^{ ……





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

    全文を読む >
  • Kyodaisuu

    指摘された箇所と、どのような修正が必要になるのかをメモ。

    • 巨大数とビジービーバー
    • ビジービーバーQ&A: 計算不可能の鳥瞰図
    • 「いかなる再帰的理論でもビジービーバー関数の全域性を証明することができません」(p.241)は誤り。その前後の説明も見直しが必要。
    • 計算不可能関数のFGHによる近似はなくする。そのかわりに、ふぃっしゅ数バージョン4は「ふぃっしゅ関数バージョン4はω^(ω+1)*63次ビジービーバー関数程度の増加速度である」といったような表現を使う。
    • 無限時間チューリングマシンについては、とりマセブログを引用すれば紹介できる。
    • ACA_0がペアノ算術と同じ強さ、Z_2+PDとZFCとn-Woodin基数の証明力が同じ、など不正確な記述(proof-theoretic strengthという用語の勘違い?)
    全文を読む >
  • P進大好きbot

    巨大数たんシステムによる1ルール関数模索記事です。



    1ルールとは何かについては人それぞれの定義があると思うので、ここでは1つ定義を固定します。


    1. \(T\)を算術を含む理論とする。自然数なり実数なり数とみなしたい対象のクラスを\(T\)の中で固定し、それに値を持つ関数のみをここでは単に関数と呼ぶ。
    2. \(T\)における1ルール関数の定義文とは、関係記号(\(=,\neq,,\leq,\geq,\ldots\))がちょうど1つ出現する。



    \(=,\neq,,\leq,\geq\)は\(\leq\)のみで定義可能なので\(\leq\)の判定式さえあれば十分ですが、論理式の短縮および辞書作成を目的にそれらの判定式も与えておきます。

    また実数に対し適用可能な判定式を与えれば自然数に対しても適用可能なので十分ですが、代入する数によってたまたま他の判定式より短くなったりすることもあるので、適用範囲を狭めた場合特有の判定式も与えておきます。(いくつか判定式が重複しますが、各適用範囲ごとにまとめた方が見やすいので重複した判定式も略さず書きます)



    \(x \in \mathbb{R}\)とします。

    \begin{eqnarray*} \lim_{n \to \infty} \frac{1}{2^{x^2 n}} & = & \left\{ \begin{array}{ll} 1 & (x = 0) \\ 0 & (x \neq 0) \end{array} \right. \\ \lim_{n \to \infty} \frac{1}{2^{2^{x^2 n}}} & = & \left\{ \begin{array}{ll} 1 & (x \neq 0)\\ 0 & (x = 0) \end{array ……








    全文を読む >
  • GEBach

    \(\psi(0) = \psi_0(0) = 1\)

    \(\psi_{\beta}(0) = \Omega_\beta (\beta \ge 1)\)

    \(\psi_{\beta}(\Omega_{\beta+1}) = \epsilon_{\Omega_\beta+1}\)

    \(\psi(A+\Omega_{\beta+1})\)なら、\(\alpha\mapsto A+\psi_\beta(\alpha)\)の不動点をとり、一番外側に\(\psi\)をかぶせる。

    \(\psi(B + A\times\Omega_{\beta+1})\)なら、\(\alpha\mapsto B + A\times\psi_\beta(\alpha)\)の不動点をとり、一番外側に\(\psi\)をかぶせる。

    \(\psi(B + A^{\Omega_{\beta+1}})\)なら、\(\alpha\mapsto B + A^{\psi_\beta(\alpha)}\)の不動点をとり、一番外側に\(\psi\)をかぶせる。


    \(\psi(0) = 1\)

    \(\psi(1) = \lim[\psi(0), \psi(0) + \psi(0), \cdots] = \omega\)

    \(\psi(2) = \lim[\psi(1), \psi(1) + \psi(1), \cdots] = \omega^2\)

    \(\psi(\omega) = \psi(\psi(\psi(0))) = \lim[\psi(0), \psi(1), \psi(2), \cdots] = \omega^\omega\)

    \(\psi(\Omega) = \lim[\psi(0), \psi(\psi(0)), \psi(\p ……

    全文を読む >
  • GEBach

    練習

    2018年10月2日 by GEBach

    八卦数の中括弧配列表記の対応する順序数

    全文を読む >
  • Koteitan

    バシク行列システムの展開ルール BM4 の定義を数式だけで書いてみました。


    \begin{eqnarray*} \mathrm{巨大数:}~K&=&\mathrm{Bm}^{10}(9)\\ \mathrm{巨大関数:}~\mathrm{Bm}(n)&=&\mathrm{expand}((\underbrace{0,0,\cdots,0}_{n+1})(\underbrace{1,1,\cdots,1}_{n+1})[n])\\ \mathrm{発展ルール:}~\mathrm{expand}([n])&=&n\\ \mathrm{expand}({\boldsymbol S}[n])&=&\left\{\begin{array}{ll} \mathrm{expand}({\boldsymbol S}_0\cdots{\boldsymbol S}_{X-2}[f(n)])&(\mathrm{if}~\forall y~S_{(X-1)y}=0)\\ \mathrm{expand}({\boldsymbol G}{\boldsymbol B}^{(0)}{\boldsymbol B}^{(1)}{\boldsymbol B}^{(2)} \cdots {\boldsymbol B}^{(f(n))}[f(n)])&(\mathrm{otherwise})\\ \end{array}\right.\\ \mathrm{活性化関数:}~f(n)&=&n^2\\ \mathrm{行列:}~{\boldsymbol S}&=&{\boldsymbol S}_0{\boldsymbol S}_1\cdots{\boldsymbol S}_{X-1}\\ \mathrm{列:}~{\bo ……


    全文を読む >
  • 400011westo

    多層タワー関数

    2018年9月9日 by 400011westo
    全文を読む >
  • Kyodaisuu

    巨大数論のp.250-251で、ラヨ数の定義とZFC公理系の証明可能性について書いていますが、この記述は不正確のようなので、p進さんのブログを参照する形で書き直そうかと考えています。まずは、こんな感じで書いてみました。添削をお願いします。PDFも更新しています。


    ラヨ数は哲学の教授が考案したものであることから定義には問題がないものと多くの人が考えて、Wikipedia には英語版、日本語版だけでなく8ヶ国語版のページができています。榎宮祐「ノーゲーム・ノーライフ」9巻ではラヨ関数が使われています。しかし、数学者の間では、ラヨ数の定義は不十分なのではないかという意見があります。たとえばp進大好きbotは以下のような問題点を指摘しています。

    1. ラヨ数の定義には「二階述語論理に使われる公理系」と、ラヨ数の定義において式\(\phi(x_1)\)がある性質を「満たすような」自然数の集合を定義するために必要な「一階集合論の公理系」が指定されていない。
    2. 1については、いずれも一階述語論理のZFCであると解釈可能かもしれない。しかし、一階述語論理のZFCを使って再定式化したとしても、なお以下の点から定義が不十分である。
    3. ラヨ数の定義では、式\(\phi(x_1)\)がある性質を「満たすような」自然数の集合を定めている。ところがこれがどのような「モデル」で満たすという意味なのかが定められていないので、定義文になっていない。
    4. 3のモデルがなんらかの集合論のモデルであるとすると、「自然数を構成するための理論の公理系」と「モデルに課される公理系」がいずれもZFCであるとすれば、不完全性定理からモデルを明示する方法がなくなってしまう。
    5. 3のモデルが定義可能クラスであれば定義可能であるが、その場合は証明可能 ……

    全文を読む >
  • Kyodaisuu

    BM4

    2018年8月31日 by Kyodaisuu

    BM4の候補について、19:01, August 31, 2018版がうまく動かなかったのですが、このブログのコメント欄でバシクさんからの修正があり、19:07, September 1, 2018版でとりあえず動きました。

    • BASIC 版
    • Yabasic 直訳
    • Yabasic計算機

    テスト行列をBM2との比較スクリプトで比較したところ、テストした行列の中では3行まではBM2と完全に一致し、以下の2つのみが異なりました。

    (0,0,0,0)(1,1,1,1)(2,2,0,0)(3,1,1,0)(1,1,1,1)[2]


    計算機への移植は、これからします。

    (追記1)

    BM2.3 と BM4 の比較をしたところ、テスト行列では完全に一致しました。他の行列でも必ず一致するのかどうかはわかりません。

    (追記2)

    • basmatに入れました。テスト行列でBASIC版と完全に一致しました。
    • 計算機に入れました。

    (追記3)

    • koteitan によるとBM2.3とアルゴリズムは同じです。
    • 4行6列までのすべての標準BM4行列について、BM4=BM2.3を確認しました。
    • 同様の比較でBM2 と BM4 の展開が異なるパターンを抽出しました。
    全文を読む >
  • Kyodaisuu

    Akihiko Koga さんから、巨大数論の内容について以下の指摘を受けました。

    「巨大数論」の p118 の枠内の「整礎」の定義が間違っているように思います.枠内に書かれているのは整列集合の定義じゃないでしょうか? 「最小元」でなく「極小元」と思います.Wikipedia 等で「整礎」の定義を確認してみてください.

    「最小元」を「極小元」に修正する旨を返信したところ、さらに以下のように教えていただきました。

    修正案ですが,「最小元」から「極小元」に変えるのは良いのですが, その後の括弧の中も「極小元」に合わせた表現にする必要があります. 今は「最小元」の説明になっていますから.「極小元」の定義は https://ja.wikipedia.org/wiki/%E9%A0%86%E5%BA%8F%E9%9B%86%E5%90%88#%E6%A5%B5%E5%B0%8F にありますが,簡易な表現としては,
    二項関係 ≤ が整礎であるとは、集合 X の任意の空でない部分集合 A が極小元を持つことをいう(a0∈A が A の極小元であるとは、自分自身より真に小さい元が A に存在しないこと, つまり,a < a0 となる a∈A が存在しないことをいう)。

    くらいでしょうか.極小元の場合,最小元と違って複数あり得ますから, 「A の極小元 a0」と一意に決る表現は定義の部分では避けたいと思います.

    こうすると,あまり数学の熟練度のない読者には,整列集合の 「最小元」と整礎集合の「極小元」が結びつかなくなってしまう 可能性があるので,囲み記事の直後に

    全順序集合では極小元と最小元(その部分集合で一番小さい元)の概念は一致しますから、要するに、整列集合とはその任意の空でない部分集合に最小元 ……
    全文を読む >
  • Nayuta Ito

    非公開ページからの和訳・転載です。


    ここでは[-o-o…-o] nが


    となるので、元の式が証明された。

    全文を読む >
  • Kyodaisuu

    巨大数論2版2刷

    2018年8月8日 by Kyodaisuu

    巨大数論はインプレスの著者向けPOD出版サービスで出版していますが、当初は出版したものは修正不可能となっていましたが、あらためて調べてみると改修申請というのができるようになっていました。正誤表の項目も増えてきて、せっかくならば修正したものを購入したいという意見も出ているので、改修して2版2刷を発行することを検討します。改修の条件としては

    • 本文PDF(ページ数の増減は不可)
    • 表紙PDF
    • 裁ち落としの有無
    • 内容紹介
    • 検索キーワード
    • モノクロ書籍をカラーに変更したり、判型を変更したりは不可
    • 費用:5400円

    となっています。有料でもあり、今回の改修が最後の改修になるかもしれないので、改修の項目を検討します。

    なるべく、同じ版の同じページには同じ内容が書かれているようにしたいと思います。

    PDF版に、修正したものを随時アップしながらこのブログのコメントで確認していきます。

    なお、改修前のPDFファイルについては過去の版アーカイブ (ユーザー名 large パスワード number) あるいはGitHub レポジトリからアクセスできます。


    修正一覧

    • 正誤表と注釈の修正。p.202の追加はけっこう分量が多いので脚注にして、そのあとの式を少し削った。
    • p.44 Googology Wiki の言語が増えた。
    • p.118 ユーザーブログ:Kyodaisuu/極小元と最小元の違い
    • p.184-186 ユーザーブログ:Kyodaisuu/順序数講座 (10) フェファーマンのθ関数で検証したの記述の誤りを訂正
    • p.206〜 ペア数列プログラムの新しいバージョンで書き直した
    • p.226 強配列表記のNDAN以降が停止しないことの記述
    • p.223 BM4までの経緯をざっくりとまとめた
    • p.250-251 ユーザーブログ:Kyoda ……

    全文を読む >
  • Kyodaisuu

    バシク行列計算機に実装されているBM2は、バシクさんのBM2のBASICコードを私が読んでCに翻訳したものです。当時のブログの記事が2017年4月11日付となっていることから、その前日のバージョンを読んで作ったものだと推定したものです。

    今までこのバシクさんの元BASICプログラムを動かしたことがなかったので、BM3でやったのと同じようにして、バシクさんのプログラムを動かしてみて翻訳がきちんとできていたのかどうかを検証しておく必要があるかと思い、今さらながらやってみました。やり方の流れはユーザーブログ:Kyodaisuu/バシク行列バージョン3と同じです。

    まずはYabasic への直訳プログラムを作りました。これは、文法エラーをなくしただけのものです。

    次に計算過程を出力するプログラムを作りました。

    そしてテストスクリプトによって、この数列の全てを一括で計算結果の比較をしたところ、すべて一致しました。よって、翻訳が正確であることが示されました。もっとも、有限の数列を検証しただけなので数学的に証明されたわけではありません。

    実は、最初はまったく一致しなかったのでなんでだろうと思ったのですが、BM2sim.yab の78行目が

    for Q=1 to F D(Q)=0 next

    となっているところの、最初の Q=1 を Q=0 として

    for Q=0 to F D(Q)=0 next

    と直す必要がありました。BM2sim.yab の中には、コメントで修正を記入しました。検証はすぐに終わると思っていたのですが、このバグの発見に手間取ってしまいました。

    これは単純なバグ修正ということで、本質的にはバシクさんの意図したプログラムを改変していなかったということで許してください。

    …… 全文を読む >
  • Nayuta Ito
    1. により定義される整列集合への、単射であって全射でない写像が存在する、ということの形式的証明であって、複雑性≦dであるものが存在する
    2. そうでないとき、RWO(n,d)=0とする
    全文を読む >
  • P進大好きbot

    以前の記事では\(\textrm{ZFC}\)のPTOの証明論的類似を構成しました。同様の手法を用いることで、\(\textrm{ZFC}\)のPTOに対応する順序数表記を定義します。

    この順序数表記は標準的に強半順序の制限が再帰的強整列順序となるような標準形からなる再帰的部分集合を持ちませんが、\(\textrm{ZFC}\)の下で計算可能巨大関数を与えます。

    \(\textrm{ZFC}\)のPTOの証明論的類似に関する以前の記事と同様、形式言語\(L^{\textrm{M}}\)と\(\textrm{ZFC}\)公理系\(A^{\textrm{M}}\)で形式化された\(\textrm{ZFC}\)集合論\(T\)で考え、メタ理論の\(MT\)には\(\textrm{Con}(T)\)を課すことにします。

    元の記事は英文ですので少しずつ翻訳していこうと思います。誰か解析して下さい。



    I will define a map \(\textrm{RWO}\) sending an \(n \in \mathbb{N}\) to (the Goedel number of) a formula \(\textrm{RWO}(n)\) in an internal set theory such that the statement that \(\textrm{RWO}(n)\) is a definition of a recursive well-order on a recursive subset of \(\mathbb{N}\) admits a formal proof. Then \(\textrm{RWO}\) yields a non-recursive " ……



    全文を読む >
  • AAAgoogology

    巨大数関係でのTaranovskyのC表記の情報を探していましたが、巨大数関係では今のところHyp cos氏が最もTaranovskyのC表記に詳しいようです。Hyp cos氏は自身の作成した強配列表記の強さを評価するためにTaranovskyのC表記を用いています。また、強配列表記と他の順序数崩壊関数との比較も行っているので、強配列表記を介して間接的にTaranovskyのC表記と他の順序数崩壊関数との比較もある程度知ることができます。(私の予想でこの比較と合わない部分は撤回しました)

    Hyp cos氏による強配列表記とTaranovskyのC表記との比較のページ[1]ではTaranovskyのC表記よりもっと標準的な表記と比較してほしいというコメントもありましたが、Hyp cos氏によれば標準的な表記ではprimary dropping array notation (pDAN)の限界に届かないのでTaranovskyのC表記を用いているとのことでした。

    Hyp cos氏によるpDANの限界に対応する順序数のTaranovskyのC表記は、 \[ C(C(\Omega_22+C(\Omega_2+\epsilon_{C(\Omega_2,C(\Omega_22,0))+1},0),0),0)= \] \[ C(C(\Omega_22+C(\Omega_2+C(C(\Omega_2,C(\Omega_2,C(\Omega_22,0))),C(\Omega_2,C(\Omega_22,0))),0),0),0)= \] \[ \begin{array}{ccccccccccccc} & & & &\Omega_2& & & & ……

    全文を読む >
  • Hassium108

    数列・行列関連

    2018年7月8日 by Hassium108

    物置が広くなってきたので移しました。



    完成
    ×
    ×
    ×
    ×

    ×


    ◯?
    ×

    ×
    ×




     項を0の列に、セパレータを1に変換。


    \((3,3,0,2,1)→(0,0,0,0,1,0,0,0,0,1,0,1,0,0,0,1,0,0)\)


    • 巨大数探索スレッド10の>>638
    • 巨大数探索スレッド11.75の>>1

    \(L_1+NZ\)

    \((1)=[1,0]={\omega}\)
    \((1,0)=[1,1]={\omega+1}\)
    \((1,0,0)=[1,2]={\omega+2}\)
    \((0,1)=[2,0]={\omega×2}\)
    \((0,1,0)=[2,1]={\omega×2+1}\)
    \((0,0,1)=[3,0]={\omega×3}\)
    \((1,0,1)=[1,0,0]={\omega^2}\)
    \((1,0,0,1)=[1,1,0]={\omega^2+{\omega}}\)
    \((0,1,0,1)=[2,0,0]={\omega^2×2}\)
    \((1,0,1,0,1)=[1,0,0,0]={\omega^3}\)
    \((1,1)=[1[0]0]={\omega^{\omega}}\)
    \((1,1,0)=[1[0]1]={\omega^{\omega}+1}\)
    \((1,1,0,1)=[1[0],1,0]={\omega^{\omega}+{\omega}}\)
    \((1,1,0,1,0,1)=[1[0]1,0,0]={\omega^{\omega}+{\omega^2}}\)
    \((0,1,1)=[2[0]0]={\omega^{\omega}×2}\)
    \((1,0,1,1)=[1,0[0]0]={\omega^{\omega+1}}\)
    \((1,1,0,1,1)=[1[0]0[0]0]={ ……






















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

    この記事では\(\textrm{ZFC}\)集合論を用います。算術を含む帰納的公理系でも同様の議論が可能であることを注意しておきます。

    それでは\(\textrm{ZFC}\)のPTOの「証明論的類似」を表す再帰的順序数表記を定義し、それに標準的な基本列を1つ定めます。

    これでも大きい順序数を表現できていると思いますが、まだ満足していないです。今後も更新して、強めつつもサラダビリティを減らしていきます。

    原文は英語の記事なため、少しずつ日本語に翻訳していきます。誰か解析して下さい。



    I will define a map \(\textrm{RWO}\) sending an \((n,d) \in \mathbb{N} \times \mathbb{N}\) to (the Goedel number of) a formula \(\textrm{RWO}(n,d)\) in an internal set theory such that if there is a formula \(F\) satisfying the following two conditions with respect to the notion of the complexity of a formal proof defined later, then \(\textrm{RWO}(n,d)\) also satisfies them:

    1. The statement that \(F\) is a definition of a recursive well-order on a recursive subset of \(\mathbb{N} \times \mathbb{N}\) adm ……


    全文を読む >
  • Kyodaisuu

    BM2.2のバグ修正

    2018年7月1日 by Kyodaisuu

    BM2.2 の計算にバグがありました。バグの修正ができました。

    バグの修正

    バシク行列計算機では、この修正をしました。この修正により、BM2.2の計算結果が変わる可能性があります。 オフライン版は、次回のリリースでこのバグが修正されます。


    BM2.2 で (0,0,0)(1,1,1)(2,2,2)(2,1,1)(3,2,2)[2] を計算しようとすると、Web版では問題なく動くのだけど、オフライン版で実行すると

    basmat -v 2.2 -o 1 -s 50 -t 3 "(0,0,0)(1,1,1)(2,2,2)(2,1,1)(3,2,2)[2]"

    のように実行したときに、うまくいくときは


    つまり、

    frame #0: 0x00000001000009a4 basmat`getParent(S=0x00000001001020e0, r=3, c=1073741824, nr=3) at basmat.c:55

    のところで c=1073741824 というのがなにかありそうです。

    その後はコメント欄にて。lldb の使い方を覚えたのが収穫。

    全文を読む >
  • Kyodaisuu

    BM2の復活

    2018年6月30日 by Kyodaisuu

    BM3をバシク行列計算機に実装したところ、早速Nishさんが無限ループを指摘、そしてそれを見たバシクさんがBM2の停止しないパターンを見つけるということになり、残っている(停止しないパターンが見つかっていない)のはBM2.2と未実装のBM2.3だけになりました。

    • 追記1:バシクさんによると、停止するというのは誤解でした。
    • 追記2:さらにその後、Bubby3さんが4行行列の停止しないパターンを見つけました。

    そして、早速バシクさんが新しいバージョンを作りました。

    バシク行列数 16:19, June 30, 2018‎ バージョン

    A=9:dim B[∞,∞],C[∞] for D=0 to 9  for E=0 to A   B[1,E]=1  next  for F=1 to 0 step -1   A=A*A   for G=0 to F    for H=0 to E     if B[F-G,H] 全文を読む >
  • AAAgoogology

    TaranovskyのC表記と他の順序数崩壊関数との比較を途中まで行いました。

    ユーザー:AAAgoogology/TaranovskyのC表記と他の順序数崩壊関数との比較

    英語版wikiのBoboris02氏のユーザーブログの比較と途中から一致しないので、どちらかに間違いがあるはずです。 私の比較に誤りがありました。現時点では\(\psi_{\Omega_1}(I_1)=\psi(\psi_I(I))\)は一致していますが、途中に一致しないところがあります。\(\psi\)関数の定義の違いによるものかもしれません。

    また、TaranovskyのC表記を木構造で表すとき、LaTeX表記を書くのは複雑な順序数になると大変なので、LaTeX表記を出力するpythonスクリプトを以下のページで公開しました。

    ユーザー:AAAgoogology/C表記の木構造のLaTeX表記のスクリプト

    全文を読む >
  • Kyodaisuu

    バシク行列計算機に実装されているバシク行列の最新バージョンは、バシクさんのオリジナル定義ではバージョン2です。それぞれの定義はユーザー:Kyodaisuu/バシク行列のバージョンにまとめました。バージョン2の後もユーザーブログ:BashicuHyudora/BASIC言語による巨大数のまとめでは定義が更新されているようなので、そろそろ計算機に入れようかと考えています。


    ユーザーブログ:BashicuHyudora/BASIC言語による巨大数のまとめの 21:32, June 12, 2018 に更新されたバージョンが、このブログ執筆時点での最新バージョンです。これを以下にコピーしました。

    • バシク行列最新バージョン:バシクさんの定義

    まずは BASIC の文法チェックをするために、Yabasic に翻訳しました。いくつかの文法エラーを直しました。それが以下のプログラムです。

    • バシク行列最新バージョン:yabasicへの翻訳

    変更した箇所は、

    1. Dim の中の∞を有限の値にしました。とりあえず文法チェックを通すための暫定です。
    2. 配列の [] を () にしました。例:B[1,E] → B(1,E)
    3. & を and にしました。
    4. | を or にしました。
    5. L.39: 計算順序を確定するために () を加えました。
    6. L.26, 39: endif を加えました。

    これで文法エラーはなくなりました。配列を有限にしているので配列が足りないというエラーになります(Redim で定義し直すこともできますが、結局メモリが足りなくなるだけなのでこのままでは計算は終了しません)。


    上の直訳プログラムでは計算の様子が見えないので、計算過程表示プログラムにしました。

    • バシク行列最新バージョン:計算過程表示

    このプログラムでは ……




    全文を読む >
  • AAAgoogology

    巨大な(再帰的)順序数の大きさを測るための「ものさし」としてTaranovskyのC表記がもっと使われてもよいと個人的には思うのですが、今のところ普遍的な「ものさし」としてはほとんど使われていません。 「ものさし」となる表記法には何が必要なのか、TaranovskyのC表記には何が足りていないのか、ということについて個人的な考えを述べます。

    まず、「ものさし」となる表記法には以下のような性質が必要であると思います。

    • 巨大な順序数を表記できる強力さ
    • 基本列や順序関係等の性質の分かりやすさ
    • 表記法の単純さ
    • 人間にとっての表記の見やすさ
    • 証明に裏付けされた厳密さ

    これらをヴェブレン関数やψ関数(の拡張)のような「ものさし」として使われている表記法と比較していきます。

    まず、強力さについてはTaranovskyのC表記が圧勝しています。ヴェブレン関数は2変数であればフェファーマン・シュッテの順序数\(\Gamma_0=\varphi(1,0,0)=\psi_0(\Omega^\Omega)=C(C(C(\Omega_1,\Omega_1),\Omega_1),0)\)未満の順序数を表すことができ、多変数であれば小ヴェブレン順序数\(\psi_0(\Omega^{\Omega^\omega})=C(C(C(C(0,\Omega_1),\Omega_1),\Omega_1),0)\)未満の順序数を表すことができます。ψ関数はブーフホルツのψ関数であれば竹内・フェファーマン・ブーフホルツ順序数\(\psi_0(\epsilon_{\Omega_\omega+1})=C(C(\Omega_2,C(C(0,\Omega_2),0)),0)\)未満の数を表すことができ、拡張されたψ関数であっても\(C(C ……

    全文を読む >
  • 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

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

    The English version is Here.


    ルールセット名
    作者
    初出 定義 bad root
    探索 bad part上昇 bad part上昇改変 議論


    BM1
    バシク
    2015.8.21

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

    左隣法 全枝有効方式 改変なし

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



    rTSS
    rpakr
    2018.5.25

    • 定義

    左隣法 全枝有効方式 改変なし

    • 停止しない
    • 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

    bad root
    bad part(悪い部分)の最左列のことです。

    • バシク行列は要素が自然数である行列と、ブラケットと呼ばれる一つの自然数から成る。
    • バシク行列では\(\begin{pmatrix}c_{11}&c_{12}\\c_{21}&c_{22}\end{pmatrix}\)を\((c_{11},c_{21})(c_{12},c_{22})\)のように列の要素を横に並べて書くことが多いのでこの資料でもそのように表記することにする。
    • \(f(n)\)は自然数から自然数への関数で、BM1, rTSS, BM1.1, Bubby3's fix, BM2, BM4 では\(f(n)=n^ ……













    全文を読む >
  • 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}} \) ……





    全文を読む >