順序数を作る①
順序数のことを何も知らないやつが、順序数に対する学びを深めて、新しい順序数を作れるようになるまでの日記（多分無理）
順序数を作る① →学習する
順序数を作る② →作り方を実践する
順序数を作る③ →順序数の構想を考える
順序数を作る④ →その構想から定義を作る
不動点が存在しないφ関数
veblen関数は、正規関数の不動点を取ることで得られる関数の族である。veblen関数は順序数をそのまま扱う側の人からすると扱いやすい関数であるが、順序数表記としては扱いづらかったりする。というのも、正規関数なせいで不動点がいくらでも存在してしまい、例えば\(\varphi_1(0) = \varphi_0(\varphi_1(0))\)を満たすので、異なる記号列が同じ順序数に対応してしまうのである。
そこで、今回はあえて正規性を捨てることで、閉点と不動点を別物にし、閉点を数え上げるが不動点は持たないような順序数関数を構成する。また、別の記事にて必要となるので、最初から多変数化(から少し増やして\(\omega+1\)変数化)したものを定義する。
\(\alpha\)を順序数とする。可算順序数の\(\alpha\)個組のうち、\(0\)でない成分が有限個であるようなものを\(\Omega^\alpha\)と書くことにする。巨大数論の文脈では\(\Omega\)を最小の非可算基数とすることがあるが、今回は混同を避けるため、順序数冪は\(\omega_1^\alpha\)と書き、\(\Omega^\alpha\)は可算順序数の組の集合として区別する。
特に\(\Omega^\omega\)の元は\((\cdots,\alpha_n,\alpha_{n-1},\cdots,\alpha_1,\alpha_0)\)のように右から順に無限列として書き表し、任意の\(i \ge n\)について\(\alpha_n = 0\)ならば省略して\((\alpha_{n-1},\cdots,\alpha_1,\alpha_0)\)と書いてもよいこととする。任意の\(\Omega^\omega\)の…
拡張ブーフホルツのψ関数に伴う順序数表記の定義を現行の定義作法で書いてみた
- 1 概要
- 2 拡張ブーフホルツのψ関数に伴う順序数表記（非公式現代版）
- 2.1 表記
- 2.2 順序
- 2.3 共終数
- 2.4 基本列
- 2.5 急増加関数
- 2.6 限界関数
- 2.7 標準形
ユーザーブログ:P進大好きbot/拡張Buchholz_OCFに伴う順序数表記をもとに、現代風の定義を作成しました。
定義の書き方は三関数を参考にしました。
なお、本記事の作成にあたり、資料の利用および内容の整理についてご快諾いただいたP進大好きbot氏に、ここに深く感謝の意を表します。
\(0\)と\(+\)と\(\psi\)と\((\)と\(,\)と\()\)のみからなる文字列の集合\(T\)と\(PT\)を以下のように同時に再帰的に定める:
- \(0 \in T\)である。
- いかなる\((a,b) \in PT \times (T \setminus \set{0})\)に対しても、\(a+b \in T\)である。
- いかなる\((a,b) \in T^2\)に対しても、\(\psi(a,b) \in PT \cap T\)である。
各\((a,b) \in T^2\)に対し\(\psi(a,b)\)を\(\psi_a(b)\)と略記する。
計算可能性に意味を持たせるために\(\omega\)を単なる文字列として扱い、\(\mathbb{N}^+ := \mathbb{N} \cup \set{\omega}\)と定める。
計算可能全域写像 \begin{eqnarray*} $ \colon \mathbb{N}^+ & \to & T \\ n & \mapsto & $n \end{eqnarray*} を以下のように再帰的に定める:
- \(n = 0\)ならば、\($n := 0\)である。
- \(n = 1\)ならば、\($n …
2026-01-02 のメモ
メモです。
- 1 バシク行列システムの解析のシート
- 2 バシク行列システムの解析の始点
- 3 バシク行列システムの解析
- 4 構成主義数学における幾何学
- 5 git
- 6 プログラミング・パラダイムを網羅する
- 7 構成主義数学を行うことができる定理証明支援システム
- 8 不可能なプログラム
- 9 well-quasi-order
- 10 ラッセルのパラドックス
- 11 集合論よりも型理論が良い理由
- 12 灼熱のホモトピー型理論入門
- 13 引数は後ろになるほど長く
直後のリンクの先にあるシートで解析している。
https://docs.google.com/spreadsheets/d/1ElQ6Mcm5lFaLW466mOopcB1NvKpT40k10oaH6zHFt58/edit?usp=sharing
以下の行列を始点に選んでいる。
- ε
- 最小の順序数を観察するために。
- ()()()
- () を追加する操作を解析するために。
- 有限順序数を観察するために。
- (0)(1)(0)
- (1) を追加する操作を解析するために。
- (0)(1) へ辿り着くまでの挙動を確認するために。
- (0)(1)(1)(0)
- (1) を追加する操作を解析するために。
- バシク行列システムの加法性を観察するために。
- (0)(1)(2)(0)
- (1) を追加する操作を解析するために。
- バシク行列システムの加法性を観察するために。
- (0,0)(1,1)(0,0)
- (0,0)(1,1) へ辿り着くまでの挙動を確認するために。
- (0,0)(1,1)(1,0)(2,1)(1,0)
- (1,0)(2,1) を追加する操作を解析するために。
- バシク行列システムの連続性を観察するために。
- (0,0)(1,1)(1,1)(1,0)
- (1,1) を追加する操作を解析するために。
- (0,0)(1,1)(2,0)(1,0)
- (1,1) を追加する操作を…
小さいWQOによる巨大数
この記事では、比較的弱い整半順序の反上昇列を使っていくつか数や関数を定義し、その上限を求める。
- 1 \(\mathbb N^2\)の直積順序による悪列
- 1.1 定義
- 1.2 評価
- 2 \([\mathbb N]^2\)の直積順序による悪列
- 2.1 定義
- 2.2 評価
- 3 降順な正整数の有限列のHigman順序による悪列
- 3.1 定義
\(\mathbb N^2\)の直積順序を用いて関数を定義する。後々必要になるので、\(\mathbb N^2\)に対して有限個の\(\mathbb N\)(の部分集合)を直和した順序集合まで拡張して議論する。
\((n_0,\cdots,n_{k-1})\)を自然数の有限列とする。集合\(\mathbb N^2 + \mathbb N_{\ge(n_0,\cdots,n_{k-1})}\)を、\(\{(a,b,c) \in \mathbb N^3 \mid a = 0 \lor (a = 1 \land b < k \land c \ge n_b)\}\)として定める。これは、\(\mathbb N^2\)に対して、各\(i < k\)についての\(n_k\)以上の自然数全体の集合を直和したものである。元\((0,a,b)\)を\((a,b)\)、\((1,a,b)\)を\(b^{(a)}\)と略記する。
集合\(\mathbb N^2 + \mathbb N_{\ge(n_0,\cdots,n_{k-1})}\)において、順序\((x_0,x_1,x_2) \preceq (y_0,y_1,y_2)\)を、「\(x_0 = y_0 = 0\)かつ\(x_1 \le y_1\)かつ\(x_2 \le y_2\)」または「\(x_0 = y_0 = 1\)かつ\(x_1 = y_1…
tree(3)を少しまとめる
\(\textrm{tree}(3)\)は\(844\)兆以上であることがわかっている。一般に、\(\textrm{tree}(k)\)の下限を求めるのは(もちろん大きい下限ほど難しいが)比較的容易である。実際にそのような列の構成法を述べればよいからだ。
しかし、\(\textrm{tree}(k)\)の上限を求めるのはそこまで容易ではない。極大順序型を調べるのはまだしも、そこから少ない頂点数で非自明なほど大きい極大順序型をもつような手法が存在する可能性を否定できないからだ。
\(\textrm{tree}(3)\)に限って言えば、少ない手数で極大順序型が十分小さくなる(具体的には\(10\)手以内に\(\omega^3\)程度になる)。今回は、\(\textrm{tree}(3)\)の条件を守りつつ、それぞれの木の並べ方について極大順序型が\(\omega^3\)以下になるまで並べてみる。
- 1 極大順序型の制限(\(\omega^3\)以下)
- 1.1 \(t_1 = (()()()),\ t_2 = ((())(()))\)の場合
- 2 極大順序型の制限(\(\omega^2 \times 2\)以下)
- 2.1 \(t_1 = (()()()),\ t_2 = (()(()()))\)
- 2.2 \(t_1 = (()()()),\ t_2 = (((()()))),\ t_3 = (((())())())\)
- 2.3 \(t_1 = (()()()),\ t_2 = (((()()))),\ t_3 = (((())(())))\)
- 2.4 \(t_1 = (()()()),\ t_2 = (((()()))),\ t_3 = ((()())(()))\)
- 2.5 \(t_1 = ((()())),\ t_2…
自作の数列
実際に定義して、値がこんな大きさだったら良いなを考えたやつ
(0) →1
(0,0(0)) →2
(0,0(0,0(0))) →3
(0,0(0,1)) →ω
(0,0(0,1,0)) →ω+1
(0,0(0,1,0,1)) →2ω
(0,0(0,1,1(0))) →ω^2
(0,0(0,1,1(0,0(0)))) →ω^3
(0,0(0,1,1(0,0(0,1)))) →ω^ω
(0,0(0,1,1(1))) →ε₀
(0,0(0,1,1(1,2))) →ε₁
(0,0(0,1,1,1)) →φ(1,φ(1,0))
(0,0(0,1,2)) →Γ₀
(0,0(0,0,1)) →φ(1,0,0)
(0,0,0(0))
(0,1) →ψ(Ω₁)
(0,1,2, ... ,n) →ψ(Ωω)
欲張りクリーク列についてのメモ
フリードマンのホームページには様々な原稿が公開されている。
とくに、上のページで
- 126. Invariant Maximality Reversals, Chapter 4 of the Invariant Maximality, Finite Free Choice, and Finite Games book under preparation. This is Chapter 4, the reversal.
- 127. Invariant Maximality Derivations, Chapter 3 of the Invariant Maximality, Finite Free Choice, and Finite Games book under preparation. This is the entire Chapter 3, as of October 16, 2025.
に注目する。(片方は.docxである！)
以降、\([−1,1]\)や\([−1,0)\)などは有理数の区間を表すと約束する。
- \(x,y \in \mathbb{Q}^k\)が順序同値とは、任意の\(1\le i,j≤k\)について、\(x_i
アトラクト表記
新定義。
ルール1 \(a\leftrightarrow b=a^b\)
ルール2 \(a\leftrightarrow 1=a\)
ルール3 \(1\leftrightarrow b=b\)
ルール4 \(a\leftrightarrow b \leftrightarrow 1=a\leftrightarrow b\)
ルール5 \(a\leftrightarrow b\leftrightarrow c=\underbrace{a\to_c a\to_c ... \to_c a\to_c a}_{b}\)（拡張チェーン）
ルール6 \(a\leftrightarrow b\leftrightarrow c\leftrightarrow d=a\leftrightarrow b\leftrightarrow (a^2\leftrightarrow b^2\leftrightarrow c^2\leftrightarrow (d-1))(d-1)\)
ルール7 \(a\leftrightarrow b\leftrightarrow c\leftrightarrow 1=a\leftrightarrow b\leftrightarrow c\)
2025-12-01 のメモ
メモです。
- 1 バシク行列システムの解析のシート
- 2 バシク行列システムの解析の始点
- 3 バシク行列システムの解析
- 4 支配
直後のリンクの先にあるシートで解析している。
https://docs.google.com/spreadsheets/d/1ElQ6Mcm5lFaLW466mOopcB1NvKpT40k10oaH6zHFt58/edit?usp=sharing
以下の行列を始点に選んでいる。
- ε
- 最小の順序数を観察するために。
- ()()()
- () を追加する操作を解析するために。
- 有限順序数を観察するために。
- (0)(1)(0)
- (1) を追加する操作を解析するために。
- (0)(1) へ辿り着くまでの挙動を確認するために。
- (0)(1)(1)(0)
- (1) を追加する操作を解析するために。
- バシク行列システムの加法性を観察するために。
- (0)(1)(2)(0)
- (1) を追加する操作を解析するために。
- バシク行列システムの加法性を観察するために。
- (0,0)(1,1)(0,0)
- (0,0)(1,1) へ辿り着くまでの挙動を確認するために。
- (0,0)(1,1)(1,0)(2,1)(1,0)
- (1,0)(2,1) を追加する操作を解析するために。
- バシク行列システムの連続性を観察するために。
- (0,0)(1,1)(1,1)(1,0)
- (1,1) を追加する操作を解析するために。
- (0,0)(1,1)(2,0)(1,0)
- (1,1) を追加する操作を解析するために。
- (0,0)(1,1)(2,1)(1,0)
- (1,1) を追加する操作を解析するために。
- (0,0)(1,1)(2,1)(1,1)(1,0)
- (1,1) を追加する操作を解析するために。
- Weiermann Function System における \( \vartheta ( \v…
WQO飲み場
自分の記事でWQO理論に関するものをまとめます。Friedmanが作った小さめの巨大数の多くはWQO理論が元になっています。
進捗の欄は現時点で特に問題がなければ〇に、そうでない場合は記事の状況を書きます。
また、大きさについては順序数や関数や自然数が入り混じってますが、それぞれ極大順序型、巨大関数、巨大数のどれに注目しているかを表しています。基本的に極大順序型は上限を、それ以外は下限を書いています。
距離の範囲の拡張と拡張された距離数列
\(\newcommand{\nat}{\mathbb{N}}\)
距離のとり方を拡張し、より広い範囲を1つの項として捉えることができるようにした。
今までのとり方
0,1,0,0,1
fan(p)を親とし、そこから右を増やす (p=max({-1}∪{i
疲れた
寒い
だからなんだって話だけど
今回作ったのは配列。
まあ簡単なもんだけど
名前は温情配列。温情はないけど。
\(|a,b|\)と表せる。
定義としてはこう。
\(|a,b|=\underbrace{a\to a\to ...\to a\to a}_{b^2}\) (if a=b)
例
\(|3,3|=\underbrace{3\to 3\to ...\to 3\to 3}_{9}\)
では\(a=b\)ではない場合はどうするのか。
\(a=b\)ではない状態を「間違いがある」という。
なので、間違いを正すために数式を書き換えなければいけない。
\(|1,2|=|1,1||2,2|\)とする。
\(|a,b|=|a,a||b,b|\)と定義できる。
ですが、この状態だと2つあるので、1つにまとめましょう。
\(|1,1||2,2|=|1,1||1,1||1,1||1,1||1,1|\)
これは、
\(|a,a||b,b|=\underbrace{|1,1||1,1|...|1,1||1,1|}_{a^2}\underbrace{|1,1||1,1|...|1,1||1,1|}_{b^2}\)
と定義することが可能。
ではまとめよう。
\(|1,1||1,1||1,1||1,1||1,1|=|5,5|\)
これは単純計算。\(1+1+1+1+1=5\)になるのと同じ。
あとは最初の定義どおりに計算する。
\(|5,5|=\underbrace{5\to 5\to ...\to 5\to 5}_{25}\)
これが巨大数を作る、温情配列だッ！！！
温情配列における\(|61,62|\)を温情配列数と定義します。
なんこれ
なんか作った
ネームは「the生姜焼きlord」。
意味は生姜焼きの主。
まあそんなことは置いとこう。
\(S(n)\)と置く。
\(n\)は生姜の個数だ。
これで求めなければいけないのは、「n個の生姜を使うときに作れる生姜焼きの最大の数」だ。
まあ100%ふざけてるんだけどね()
詳しいルール説明をしよう。
1:この関数では、解は\(n\)を上回らなければいけない。
2:生姜の個数をどう捉えるかは自由。生姜そのものと捉えてもいいし生姜チューブの個数と捉えてもいい。
3:生姜焼きには必ず生姜を入れなければならず、整数で答えなければならない。
4:厚さは考えない。
5:生姜焼きの肉の広さに制限はないが、整数しか使用できない。
なんこれ()
まあ遊びだと思ってください
追記：\(S(n) \sim \max \Bigg\{ k \in \mathbb{Z}^+ \;\Bigg|\; \exists \{u_1, u_2, \dots, u_k\} \subset \mathbb{R}^+, \sum_{i=1}^k u_i \le n \Bigg\}\)が類似式だそうです
ちなみに単位に関しては個でもgでも何でもいいです。制約はないです。
うぐぁ
巨大数って何を以て巨大数なんですかねって思ったことがある
巨大数がただの大きい数なのであればそれは\(∞\)で終わっちゃう気がするんだよね
それじゃ面白くないよね
結構かなりすごく曖昧な気がする
人によっては\(100\)でも巨大数だし\(G^{64}(4)\)（グラハム数）を大したことないっていう人もいるかもしれない
そんな事考えててもしょうがないけどね
葉がラベル付けされた二分木tree関数とtree(4)の下限
この記事では、\(\textrm{tree}(4)\)の下限を与える。
既に木原貴行氏によって\(f_{\varepsilon_0}(\textrm{グラハム数})\)という下限が求められており、また同氏によって\(f_{\varepsilon_{\omega^2}}(\textrm{グラハム数})\)という下限が予想されている。 (\(\textrm{tree}\)関数と\(\textrm{TREE}\)関数を勘違いしてる主張を除いて)証明が与えられていない主張も含めると、私が把握している限り、Hypcos氏の\(f_{\varepsilon_{\omega^2+\omega}}(10^{100})\)が最も大きい下限である。
この記事で与える下限は、それらよりも大きいものである。
記事タイトルにもあるように、\(\textrm{tree}(4)\)の下限を与える流れで、葉がラベル付けられた\(2\)分木版\(\textrm{tree}\)関数のようなものを考える。一見中途半端に見えるかもしれないが、適切に扱えば\(\textrm{tree}(4)\)の下限を求める際に役立つ。
また、この記事で扱う「木」は、断りのない限り空の木は含まない。また、根付きであり枝分かれの方向を区別しない。すなわちグラフとして同型なものは同一視する。
頂点の「高さ」は根からの距離として定義する。
- 1 葉がラベル付けられた\(2\)分木
- 2 \((\textrm{lbt}_{\omega^3},\le_\textrm{lbt})\)
- 2.1 枝分かれが高々\(1\)回しかない\(2\)分木
- 2.2 \((\omega^2 \times 2 + 1)\)-葉ラベル付き\(2\)分木
- 2.3 \(\textrm{tree}(4)…
なんかできた ばーじょん1
適当に作ってみた巨大数をここに書き下すお
\(SYG(n)\)です。TREE数列の延長線上にあります。
1.TREE数列のルールは引き継ぐ。
2.種類\(a\)と\(b\)からなどの元から存在する2種類の点によりできた枝の次の点は\(c\)となる（aとbが混ざり合う）
3.混合により生成された点は生成された時点で混合させなくても使用可能となる。
4.混合によりできた点は混合に使用できない。
5.混合は強制ではない。
おわり。
定義に問題等あればコメント下さい。
ローダー数のもう一つの拡張
諸事情により、pdfでゆるしてください。ユーザーブログ:KawamoYurase/ローダー数の再定式化やユーザーブログ:KawamoYurase/ローダー数の拡張の続編（？）となります。
2025-11-01 のメモ
メモです。
- 1 バシク行列システムの解析のシート
- 2 バシク行列システムの解析の始点
- 3 バシク行列システムの解析
- 4 Rocq のコードが GitLab で正常にシンタックスハイライトされない
- 5 Introduction to Homotopy Type Theory
- 6 後回し
直後のリンクの先にあるシートで解析している。
https://docs.google.com/spreadsheets/d/1ElQ6Mcm5lFaLW466mOopcB1NvKpT40k10oaH6zHFt58/edit?usp=sharing
以下の行列を始点に選んでいる。
- ε
- 最小の順序数を観察するために。
- ()()()
- () を追加する操作を解析するために。
- 有限順序数を観察するために。
- (0)(1)(0)
- (1) を追加する操作を解析するために。
- (0)(1) へ辿り着くまでの挙動を確認するために。
- (0)(1)(1)(0)
- (1) を追加する操作を解析するために。
- バシク行列システムの加法性を観察するために。
- (0)(1)(2)(0)
- (1) を追加する操作を解析するために。
- バシク行列システムの加法性を観察するために。
- (0,0)(1,1)(0,0)
- (0,0)(1,1) へ辿り着くまでの挙動を確認するために。
- (0,0)(1,1)(1,0)(2,1)(1,0)
- (1,0)(2,1) を追加する操作を解析するために。
- バシク行列システムの連続性を観察するために。
- (0,0)(1,1)(1,1)(1,0)
- (1,1) を追加する操作を解析するために。
- (0,0)(1,1)(2,0)(1,0)
- (1,1) を追加する操作を解析するために。
- (0,0)(1,1)(2,1)(1,0)
- (1,1) を追加する操作を解析するために。
- (0,0)(1,1)(2,1)(1,1…
ベクレーション・ネステッド・トレイン
ベクレーション・ネステッド・トレインはベクレミシェフの虫を多次元構造に拡張したものである。
多次元構造をいきなり見ても分からないと思うので、その前に２次元拡張であるベクレーションシャフトをお見せする。
また、ベクレーションシャフトの行列を横一直線にしか数値を並べないものにしたものがベクレミシェフの虫である。
＜ベクレーションシャフト＞
【概要】
・行列の数値で一番右の縦一直線を使うよ。
・その縦一直線の中の0じゃない数値の中で一番下の数値を1減らして、その1つ下の数値を今のステップ数に上書きした後で「悪い部分」の行列を今のステップ数個増やすことを繰り返す関数だよ。
・縦一直線の中で減らす数値より１つ以上上の部分を比較して、減らす数値がある縦一直線と違う縦一直線があれば、その縦一直線とそこから左は「良い部分」だよ。
・その部分が同じでも、減らす数値と同じ横一直線の中で減らす前の数値より小さい数値があれば、その数値がある縦一直線とそこから左は「良い部分」だよ。
・「良い部分」でない行列が「悪い部分」だよ。
・右端の縦一直線が全部0なら？ その縦一直線を消すだけだね。
【変形の細かい説明】
・この関数は1つの数取器と任意個のシャフトを初期値として始める。
・数取器は1つの変数を持ち、シャフトは任意個の変数を縦に並べたものである。
・シャフトの中で上からｎ番目にある数値の深度はｎである。
・★
・数取器の数値を1増やす。
・「最も右のシャフト」がなければ数取器の数値を出力して計算終了。
・「最も右のシャフト」に0でない数値が存在しないなら「最も右のシャフト」を消して★に戻る。
・「最も右のシャフト」で0ない数値の中で最も大きい深度を持つ数値をdとする。
・dの深度をDとする。
・「最も左のシャフト」の左に旗を立てる。
・「深…
Kruskal順序の極大順序型の上限
\(\textrm{tree}\)関数などのwell-defined性は、Kruskalの木定理という定理が基になっている。
Kruskalの木定理は、木の集合上の\(\land\)-埋め込みという順序が整半順序(あらゆる全順序化が整列する順序)であるという主張である。整半順序は、全順序化したときの順序型に最大値が存在して、このような順序型(極大順序型)を用いて整半順序の大きさを測ることが多い。
\(\land\)-埋め込みにも同様に極大順序型が存在するので、言うなれば\(\textrm{tree}\)関数の基盤となる整半順序構造の大きさを順序数で表せる。この記事では、極大順序型を細かく調べていく。
Friedmanによる\(\textrm{tree}\)関数は、木を単なる順序集合として扱っていたが、この記事では証明の都合上、自由代数のようにして扱う。枝分かれが順序付けられているかどうかに違いがあるが、この記事の順序による極大順序型はFriedmanによる極大順序型よりも大きいので、この記事で調べた上限はそのままFriedmanによる\(\land\)-埋め込み順序の極大順序型の上限としても問題ない。
有限個を除いた成分が\(0\)であるような可算順序数の\(\omega+1\)個組を受け取って可算順序数を返す写像\(\varphi_{\mathcal T} : \omega_1^{\omega+1} \to \omega_1\)を、以下のように超限再帰的に定義する。
- \(\varphi_{\mathcal T}(V)\)は、\(\max V\)より大きく、定義域を\(\omega_1^{\omega+1}\)の元のうち辞書式順序で\(V\)未満のものに制限した\(\varphi_{…
自作巨大数を作ってみた
ここに来る前に製作した、初めて作った関数を少し改良しただけなので、ミス等あるかもしれません。
至急ではないので、どなたか可能でしたら、ミス等の指摘・定義が大丈夫であれば解析をお願いします。
拡張系③→②→①→基本の順、それぞれの定義内では上から計算します。
全定義共通: a,b,c,…,y,z,m,nは2以上の自然数、Aは1個以上の2以上の変数
- 1 基本の定義
- 2 拡張系①
- 2.1 2段階拡張
- 2.2 3段階拡張
- 2.3 4段階拡張
- 3 拡張系②
X(a) = a
X(a,b) = ab
X(A,a,b) = X(A,X(A,X(A,X(…,X(A,X(A,a-1,b),b-1),…b-1),b-1),b-1) [X(A,a,b-1) 個の X]
X(1,A) = X(A)
X(A,1) = X(A)
X(A,1,A) = X(A,A)
X(a,b,c,…,y,z[n]) = X(X(a,b,c,…,y,z[n-1]),X(a,b,c,…,y,z[n-1]),X(a,b,c,…,y,z[n-1]),…,X(a,b,c,…,y,z[n-1]),X(a,b,c,…,y,z[n-1]))
X(a,b,c,…,y,z[1]) = X(a,b,c,…,y,z)
X(A[[…[n]…]]) = X(A[[…[X(A[n])]…]]) = X(A[[…[X(A[X(A[n])])]…]]) =…
X(A[n]2) = X(A[[…[n]…]])
X(A[n]x) = X(A[[…[n]x-1…]x-1]x-1) = X(A[[…[X(A[n]x-1)]…]x-1]x-1)
Xa(A) = となっている場合、そちらは後で計算するためここではそのまま>
探索方法に数列と同じアルゴリズムを使用できるψ関数の解析と計算例
\( \newcommand{\nat}{\mathbb{N}} \newcommand{\List}{\text{List}} \newcommand{\Type}{\text{Type}} \newcommand{\cons}{\text{cons}} \newcommand{\nil}{\text{nil}} \newcommand{\length}{\text{length}} \newcommand{\isEmpty}{\text{isEmpty}} \newcommand{\mem}{\text{mem}} \newcommand{\nthD}{\text{nthD}} \newcommand{\headD}{\text{headD}} \newcommand{\lastD}{\text{lastD}} \newcommand{\append}{\text{append}} \newcommand{\concat}{\text{concat}} \newcommand{\drop}{\text{drop}} \newcommand{\take}{\text{take}} \newcommand{\slice}{\text{slice}} \newcommand{\tale}{\text{tale}} \newcommand{\headList}{\text{headList}} \newcommand{\init}{\text{init}} \newcommand{\lastList}{\text{lastList}} \newcommand{\splitAt}{\text{splitAt}} \newcommand{\reverse}{\text{revers…
探索方法に数列と同じアルゴリズムを使用できるψ関数
\( \newcommand{\nat}{\mathbb{N}} \newcommand{\List}{\text{List}} \newcommand{\Type}{\text{Type}} \newcommand{\cons}{\text{cons}} \newcommand{\nil}{\text{nil}} \newcommand{\length}{\text{length}} \newcommand{\isEmpty}{\text{isEmpty}} \newcommand{\mem}{\text{mem}} \newcommand{\nthD}{\text{nthD}} \newcommand{\headD}{\text{headD}} \newcommand{\lastD}{\text{lastD}} \newcommand{\append}{\text{append}} \newcommand{\concat}{\text{concat}} \newcommand{\drop}{\text{drop}} \newcommand{\take}{\text{take}} \newcommand{\slice}{\text{slice}} \newcommand{\tale}{\text{tale}} \newcommand{\headList}{\text{headList}} \newcommand{\init}{\text{init}} \newcommand{\lastList}{\text{lastList}} \newcommand{\splitAt}{\text{splitAt}} \newcommand{\reverse}{\text{revers…
2025-10-01 のメモ
メモです。
- 1 バシク行列システムの解析のシート
- 2 バシク行列システムの解析の始点
- 3 バシク行列システムの解析
- 4 より分かりやすいモナドの呼び方
- 5 等価性による公理
- 6 高階帰納型の表現について
- 7 ラムダ計算の正規形
- 8 impredicative universe
- 9 Homotopy Type Theory と計算
直後のリンクの先にあるシートで解析している。
https://docs.google.com/spreadsheets/d/1ElQ6Mcm5lFaLW466mOopcB1NvKpT40k10oaH6zHFt58/edit?usp=sharing
以下の行列を始点に選んでいる。
- ε
- 最小の順序数を観察するために。
- ()()()
- () を追加する操作を解析するために。
- 有限順序数を観察するために。
- (0)(1)(0)
- (1) を追加する操作を解析するために。
- (0)(1) へ辿り着くまでの挙動を確認するために。
- (0)(1)(1)(0)
- (1) を追加する操作を解析するために。
- バシク行列システムの加法性を観察するために。
- (0)(1)(2)(0)
- (1) を追加する操作を解析するために。
- バシク行列システムの加法性を観察するために。
- (0,0)(1,1)(0,0)
- (0,0)(1,1) へ辿り着くまでの挙動を確認するために。
- (0,0)(1,1)(1,0)(2,1)(1,0)
- (1,0)(2,1) を追加する操作を解析するために。
- バシク行列システムの連続性を観察するために。
- (0,0)(1,1)(1,1)(1,0)
- (1,1) を追加する操作を解析するために。
- (0,0)(1,1)(2,0)(1,0)
- (1,1) を追加する操作を解析するために。
- (0,0)(1,1)(2,1)(1,0)
- (1,1) を追加する操作を解析するために。
- (0…
雛形 (2025-09-30)
書きかけ
原始数列の階差数列を、別の角度で発展させてみたい
与えられた非負整数の数列\(S = (S_1,S_2,\ldots,S_k)\)に対し、\(S[n]\)を次のように定める。
はじめに、次の条件をすべて満たす\((p,q)\)の組を探索する:
- \(S_p=0\)
- \(S_q=0\)または\(q=k+1\)
- \(1\leq p
二分木に制限したtree関数
Kruskalの木定理を制限すれば、1分木(列)間の埋め込み順序や2分木間の\(\land\)-埋め込み順序を用いた\(\textrm{tree}\)関数が得られるはずである。
列の埋め込み順序はいわゆるHigmanの補題とよばれるものであり、こちらの記事で下限の評価などを行っている。
\(2\)分木の埋め込み順序はもう少し複雑であり、ラベルなしでも極大順序型が\(\varepsilon_0\)はある。これを用いて\(2\)分木に制限した\(\textrm{tree}\)関数の増大度を見積もることも可能だろう。
今回は、序盤の具体的な値に対してある程度精密な評価を与えようと思う。
- 1 定義
- 2 \(\textrm{tree}_2(1)\)
- 3 \(\textrm{tree}_2(2)\)
- 4 \(\textrm{tree}_2(3)\)
- 5 \(\textrm{tree}_2(4)\)
- 6 \(\textrm{tree}_2(5)\)
- 6.1 \(\{1,2\}\)-列の木への翻訳
- 6.2 \(\{1,2\}\)-列の木への翻訳その2
- 6.3 \(\{1,2\}\)-列の木への翻訳その3
- 7 ブロック部分列との関係
- 7.1 \(((())(()))\)禁止元の列
- 7.2 \(2\)分木列の埋め込み不能列による関数
- 7.3 \(\textrm{med}\)と\(n\)の関係
- 7.4 頂点数の制限が\(n\)関数によって与えられる\(2\)分木の埋め込み不能列
- 7.5 具体例
- 8 \(\textrm{tree}_2(2^k-1)\)の下限
- 8.1 前準備
- 8.2 順序数から順序数列、\(2\)分木への変換
- 8.3 頂点数の評価
- 9 後書き
\(k\)を自然数とし、以下を満たす根付き二分木の有限列\(\{T_i\}_{1 \le i \le l}\)を考える。
- \(T…
埋め込み階層
埋め込み階層（うめこみかいそう）は通常の埋め込み\(f^n(x)\)を拡張した、ハイパー埋め込み（ハイパーうめこみ）を更に階層化したものである。現段階では1以上の整数から1以上の整数への写像の埋め込みについてのみ定義されている。なおここでの「埋め込み」は幾何学の用語ではなく、写像の反復合成を意味する用語である。例えば\(f^n(x)\)なら写像\(f(x)\)がn回、自身に埋め込まれていると考える。
- 1 ハイパー埋め込み
- 1.1 冪乗的埋め込み
- 1.2 テトレーション的埋め込み
- 1.3 ハイパー埋め込み
- 2 埋め込み階層 (第1階層から第N階層まで)
- 2.1 第1階層
- 2.2 第2階層
- 2.3 第3階層
- 2.4 第N階層
- 3 埋め込み階層 (第1,2階層から第M,N階層まで)
- 3.1 第1,2階層
- 3.2 第2,2階層
- 3.3 第N,2階層
- 3.4 第1,3階層
- 3.5 第N,3階層
- 3.6 第1,N階層
- 3.7 第M,N階層
- 4 埋め込み階層 (第1,1,2階層から第M,N,O,P階層まで)
- 4.1 第1,1,O階層
- 4.2 第1,N,O階層
- 4.3 第M,N,O階層
- 4.4 第1,1,1,P階層
- 4.5 第1,1,O,P階層
- 4.6 第1,N,O,P階層
- 4.7 第M,N,O,P階層
- 5 埋め込み階層 (一般)
写像の埋め込みにハイパー演算的な概念を持ち込むことによって埋め込みを拡張する。
ハイパー埋め込みでは通常の埋め込みを冪乗的埋め込みであると捉える。
\[f^n(x):=\underbrace{f(f(\cdots(f(f}_n(x)\cdots)\]
通常の埋め込みを冪乗的埋め込みであると捉えたことによりテトレーション的埋め込みを考えることができる。
\[^nf(x):=\underbrace{f^{f^{f^{.^{.^{f(x)}.}.}(x)}(x)}(x)}_n\] …
森の順序埋め込みによる順序
木構造を用いる急増大関数は、有名なものだと\(\textrm{tree}\)などがある。これは『Kruskalの木定理』と呼ばれる整半順序に関する定理を用いて定義される。
根付き木を1つの順序集合とみなしたときの、「根付き木同士(つまり順序集合同士)の間に順序と下限を埋め込む写像が存在する」という関係についてKruskalの木定理は述べているが、これを少し簡略化して、「根付き木同士の間に順序を埋め込む写像が存在する」という関係にしたらどうなるだろうか？
本記事では、このようなKruskalの木定理の亜種とその順序型について述べる。また、これを用いて急増大関数を定義し、他のいくつかの関数との比較を行う。
先ほどは木について議論すると述べたが、今後の議論のしやすさのために、より拡張した『森』という概念を用いて議論する。
なお、『森』は定義の流儀が文献によってかなり異なるので、本記事における定義を明確化しておこう。
濃度が\(n\)の集合上の二項関係は高々有限なので、各\(n < \omega\)に対して\(n\)を台集合とする森は数え上げられる。このとき、双方に順序埋め込み可能(つまり順序同型)なものが存在する場合は1つだけを数えることにしよう。
こうすることで、森全体(の同型による代表元を全て集めたもの)を自然数で番号付けできる。この集合を\(\mathcal F\)とおく。同型な森に関する議論をいちいち行うのは面倒なので、以降はこの\(\mathcal F\)の元についてのみ議論を行う。
- 証明
この順序埋め込みによる順序\(\le_{\textrm{ord}}\)の整半順序性を示すこと自体は、Kruskalの木定理を弱めるだけなので簡単である。しかし、今回は極大順序型まで求めたい。そこで、…
超限配列数
超限配列数とは、超限階層数の拡張である。
集合\(\text{On}\)と集合\(\text{TR}\)は、文字\(0\)と\(\omega\)と\((\)と\()\)と\(,\)と\(+1\)のみからなる文字列の集合である。以下で同時に再帰的に定める。
- \(\alpha=0\)ならば、\(\alpha\in\text{On}\)
- \(\exists\alpha’(\alpha’+1=\alpha)\)ならば、\(\alpha\in\text{On}\)
- \(\alpha=\omega\)ならば、\(\alpha\in\text{On}\cap\text{TR}\)
- \(\exists (a_0,a_1,…a_n,b_0,b_1,…b_n)\in\text{On}^{2n+2}((a_0,a_1,…,a_n)(b_0,b_1,…,b_n)=\alpha)\)ならば、\(\alpha\in\text{On}\cap\text{TR}\)
写像\([]: \text{TR}\times\mathbb{N}\rightarrow\text{On}, (\alpha,m)\mapsto\alpha[m]\)
を以下で再帰的に定める。
- \(\alpha=\omega\)ならば、
- \(m=0\)ならば、\(\alpha[m]=0\)
- \(\exists m’(m’+1=m)\)ならば、\(\alpha[m]=\alpha[m’]+1\)
- \(\exists (a_0,a_1,…a_n,b_0,b_1,…b_n)\in\text{On}^{2n+2}((a_0,a_1,…,a_n)(b_0,b_1,…,b_n)=\alpha)\)ならば、
- \(\exists m(b_m=0)\)ならば、\(\alpha[m]=…
数列システムとψ系表記
- 1 第1章 概要
- 2 第2章 お気持ち
- 3 第3章 表記とユーティリティ関数
- 3.1 表記
この記事では、1つの表記に対し2つの基本列を定め、それらが等価であることを示す。
第2章ではこの表記のお気持ちを述べる。第3章で表記とユーティリティ関数を用意し、第4章と第5章でそれぞれ基本列を定義する。第6章でそれらが等価であることを示し、第7章で考察を述べる。
この表記は自然数のペアの列で表される。表記\( A \)に対し、\( A \)に\( (d, s) \)を追加したものは\( A \)に対応するBuchholz's ψの表記の「後ろから\( d \)番目の\( ) \)の直前に\( + \psi_s(0) \)を追加したもの」に対応してほしい。
しかし、順序数に対してそのような操作はill-definedであるため、あくまでこれはお気持ちである。
- \( T = (\mathbb{N}^2)^{ 1 \)ならば、
- もし\( \operatorname{br}_t = -1 \)なら、\( t[n]_{\mathrm{B}} = t_0 t_1 \cdots t_{l-2} \frown \operatorname{Transpose}($n, d_{l-1}) \)である。
- もし\( \operatorname{br}_t \neq 0 \)なら、
- もし\( s_{l-1} = 0 \)なら、
- \( G = t_0 t_1 \cdots t_{\operatorname{br}_t - 1} \)とする。
- \( B = t_{\operatorname{br}_t} \cdots t_{l-2} \)とする。
- \( t[n]_{\mathrm{B}} = G \frown (B * n) \)である。
- そうでな…
- もし\( s_{l-1} = 0 \)なら、
原始数列、ふぃっしゅ数ver5、systemTの話
- 1 書きかけの記事です
- 2 前置き
- 3 はじめに
- 4 systemTについて
- 4.1 ラムダ式
- 4.2 関数適用、\(\beta\)変換
- 4.3 systemT
- 5 systemT上で巨大関数を作る
- 5.1 巨大関数
- 6 一旦ここまで
これから話す内容については眉に唾をつけて見てほしい。
この記事を見ている人に対しては、巨大数には複数の異なるアプローチがあって、それの構造について一風変わった視点で見ることができるというような、そんな変な知識を持っていただければ幸いである。
原始数列はバシク氏が作成した数列系巨大数である。巨大関数としての強さは\(\varepsilon_0\)程度である。
ふぃっしゅ数ver5はふぃっしゅっしゅ氏が作成した関数である。巨大関数としての強さは\(\varepsilon_0\)程度である。
systemTという型付きラムダ計算の体系がある。証明論的な強さは\(\varepsilon_0\)である。
これらが同じ構造を持つという話がしたい。
systemTは単純型付きラムダ計算における一体系である。
ラムダ計算、(単純)型付きラムダ計算については、詳しい話をしているサイトや動画などがあるのでそちらを見てもらい、式変形などのイメージを持ってもらったほうがいいとは思うが、この記事の中でも軽く触れておく。
ラムダ計算とは、私は「関数における代入という操作を明示させた記法」という認識でいる。
ラムダ計算の特徴といえば、ラムダ式であろう。
１次変数関数\[f(x)=x+5\]があるとする。これは関数\(f:\mathbb{N}\rightarrow \mathbb{N}\)に対して自然数\(x\)を代入すれば\(x+5\)が返ってくるということであるが、これをラムダ式で表現すると \[f \ = \ \lambda …
Baum数列
- 1 初めに
- 2 tree数列の数列化
- 2.1 例
- 3 TREE数列の数列化
- 3.1 例
最近ふとtreeないしTREEのことをよく目にし、何となくでtree数列の数列化を思いついたので、メモ書き
tree数列の数列化において、いくつかの規則を定める
- 根は必ず0となり、1つの数列に出てくる0は1回のみ
- 最も左の葉から数列化させる
以下の木を数列化させる
(ただし、vはノード、^は茎とし、同じ親を持つノードは+で区切る)
例1 v^((v^v)+v^(v+v+v))
数列化 (0,1,2,1,2,2,2)
例2 v^(v+v^(v+v^(v+v)))
数列化 (0,1,1,2,2,3,3)
また、tree(2)の全ての木を数列化させると
- (0,1,1)
- (0,1,2,3)
- (0,1,2)
- (0,1)
- (0)
である。
TREE数列の数列化において、いくつかの規則を定める
- 根は必ず0となり、1つの数列に出てくる0は1回のみ
- 最も左の葉から数列化させる
- ノードに着くラベルは自然数のラベルとし、必ず1つのノードに1つのみラベルがつく
- ノードとラベルを1つの自然数のペアとして扱う
以下のラベル付き木を数列化させる
(ただし、v_{i}は自然数\(i\)がついたノード、^は茎とし、同じ親を持つノードは+で区切る)
例1 v_{3}^((v_{1}^v_{2})+v_{3}^(v_{2}+v_{1}+v_{1}))
数列化 (0,3)(1,1)(2,2)(1,3)(2,2)
超限階層数
超限階層数とは、Warlter545が考えた数である。
- 1 定義
- 1.1 集合Onと集合TR
- 1.2 基本列
- 1.3 急増化関数
- 1.4 限界関数
- 1.5 命名
- 2 余談
これら2つを以下で再帰的の定める。ただし、要素は文字列とする。
- \(\alpha=0\)ならば、\(\alpha\in\text{On}\)
- \(\alpha=\omega\)ならば、\(\alpha\in\text{On}\wedge\alpha\in\text{TR}\)
- \(\exists\alpha’\in\text{On}(\alpha’+1=\alpha)\)ならば、\(\alpha\in\text{On}\)
- \(\exists(\alpha’,\beta,\gamma)\in\text{On}^3(f^\beta_\gamma(\alpha’)=\alpha)\)ならば、\(\alpha\in\text{On}\wedge\alpha\in\text{TR}\)
関数\([]:\text{TR}\times\mathbb{N}\rightarrow\text{On}, (\alpha,n)\mapsto\alpha[n]\)
を以下で再帰的に定める。
- \(\alpha=\omega\)ならば、
- \(n=0\)ならば、\(\alpha[n]=0\)
- \(\exists n’(n’+1=n)\)ならば、\(\alpha[n]=\alpha[n’]+1\)
- \(\exists (\alpha’,\beta,\gamma)(f^\beta_\gamma(\alpha’)=\alpha)\)ならば、
- \(\beta=0\)ならば、\(\alpha[n]=\alpha’\)
- \(\beta=0+1\)ならば、
- \(\gamma=0\)ならば、\(\alph…
2025-09-01 のメモ
メモです。
- 1 バシク行列システムの解析のシート
- 2 バシク行列システムの解析の始点
- 3 バシク行列システムの解析
- 4 ペア数列システムの停止性
- 5 私の判断基準
- 6 well-defined
- 7 二次元空間における計算モデル
- 8 メタ数学での型理論の優位性
- 9 Traversable
- 10 Parametricity
- 11 ライセンス
直後のリンクの先にあるシートで解析している。
https://docs.google.com/spreadsheets/d/1ElQ6Mcm5lFaLW466mOopcB1NvKpT40k10oaH6zHFt58/edit?usp=sharing
以下の行列を始点に選んでいる。
- ε
- 最小の順序数を観察するために。
- ()()()
- () を追加する操作を解析するために。
- 有限順序数を観察するために。
- (0)(1)(0)
- (1) を追加する操作を解析するために。
- (0)(1) へ辿り着くまでの挙動を確認するために。
- (0)(1)(1)(0)
- (1) を追加する操作を解析するために。
- バシク行列システムの加法性を観察するために。
- (0)(1)(2)(0)
- (1) を追加する操作を解析するために。
- バシク行列システムの加法性を観察するために。
- (0,0)(1,1)(0,0)
- (0,0)(1,1) へ辿り着くまでの挙動を確認するために。
- (0,0)(1,1)(1,0)(2,1)(1,0)
- (1,0)(2,1) を追加する操作を解析するために。
- バシク行列システムの連続性を観察するために。
- (0,0)(1,1)(1,1)(1,0)
- (1,1) を追加する操作を解析するために。
- (0,0)(1,1)(2,0)(1,0)
- (1,1) を追加する操作を解析するために。
- (0,0)(1,1)(2,1)(1,0)
- (1,1) を追加する操作を解析するために。
- (0…
Higmanの補題を用いた巨大数
数列数列やFriedmanのblock subsequenceなど、有限離散順序から作った列の埋め込みによる整半順序はいくらか存在します。
これらの巨大数のwell-defined性は、『Higmanの補題』という、整半順序から新たに大きい整半順序を生み出せるという言明が元になっています。整半順序には様々あり、例えば整列順序、整半順序同士の直和や直積によって得られた順序、そしてHigmanの補題によって得られた整半順序などです。
しかし、現状Higmanの補題のみを用いた急増大関数には、高々有限離散順序についてHigmanの補題を用いるだけでwell-defined性が証明できてしまう関数しかありません。工夫さえすれば、もっと複雑な整半順序とHigmanの補題を用いた関数や、Higmanの補題を反復したような関数が得られます。
今回は、そのような巨大関数を構成するための一般的な手法と、その具体例をいくつか述べます。
- 1 block subsequence
- 1.1 定義
- 1.2 通常の悪列への帰着
- 2 整半順序集合と有限部分集合の族
(数列数列の執筆時、「Higmanの補題を用いた巨大数を調べたけどなかったから僕が先駆者だ！」みたいなことどっかで口走ったけど普通にFriedmanがやってました。先行研究の確認は大事。)
Friedmanのblock subsequence theoremは、海外ではそこそこ知名度があるようですが日本ではあまり議論されてません。日本語で明確に大きさについての説明がなされている文献もなさそうなので、ここで明示させてもらいます。
まずは定義を述べましょう。
自然数の有限列\(\{a_i\}_{1 \le i \le N}\)が、任意の\(1 \le i < j \le n…
C関数強化案
3作目です。
また、新しい案が思いついたため、以下に定義します。
- 1 動作規則郡\(X_{n}\)
- 2 計算可能郡\(Y_{n}\)
- 3 \(C_{2}(n)\)関数
- 4 最後に
- \(X_{0}\)を今までのルール0〜31までの全てのルールが入った集合とする
- \(X_{k+1}\)を考える
- \(X_{1}\)を\(X_{0}\)と計算可能郡\(Y_{0}\)を計算可能な\(X_{0}\)以外のルールが入った集合とする
- 同様に\(X_{k+1}\)の時も\(X_{k}\)と計算可能郡\(Y_{k}\)を計算可能な\(X_{k}\)以外のルールが入った集合とする
- このとき、ルールは0と1のみからなる任意の長さの演算子でよい
- \(Y_{0}\)を\(X_{0}\)で計算できるような数列全体の集合とする
- \(Y_{k+1}\)を考える
- \(Y_{1}\)を\(X_{1}\)で計算可能な数列の集合とする
- 同様に\(Y_{k+1}\)を\(X_{k+1}\)で計算可能な数列の集合とする
- 長さnの0と1のみからなる数列を考え、それを演算子ごとに区切る
- 入力を無限個の1に固定し、任意の場所から演算を行えるとする
- この時、\(X_{n}\)に含まれるルール全てで計算し、最も大きいものをこの関数の値とする
以上の定義を踏まえ、\(C_{2}(10^{100})\)をこの巨大数の値とする
この関数を作るにあたり、アドバイスやアイデアを下さった甘露東風氏に感謝を申し上げます
"WELL-PARTIAL ORDERING AND HIERARCHIES"の和訳
有限種記号列の埋め込み順序の極大順序型を求める論文、"WELL-PARTIAL ORDERING AND HIERARCHIES"の和訳です。
英語は苦手なので、細かいニュアンスまでは訳せていません。また、勉強メモとしての側面が大きいため自分用に見やすく色々と脚色されてます。ご了承ください。
- 1 §1. 導入
- 2 §2. 整半順序の基本的な性質
- 3 §3. \(o(X,\preceq)\)の計算
- 4 一般化されたHigmanの補題
再帰関数論において、関数のクラスを階層づける手法は基本的に以下のような手順が用いらる。 まず、基本関数のクラス\(I\)(主に後者関数や定数関数などが属する)を定義し、関数から新たに関数を構成する操作\(F\)(関数合成、原始再帰作用素など)を用意する。 関数のクラス\(C\)と、関数から新たに関数を構成する操作\(F\)が与えられたとき、\(C\)に属する関数達と関数構成操作\(F\)のみによって得られる関数全体のクラスを\(FC\)と表す。このような手法で、関数のクラス\(C\)を\(FC\)に拡張できる。 \(F\)とはまた別の関数を構成する操作\(G\)があったとき、\(C\)が操作\(G\)に閉じていたとしても、\(FC\)が操作\(G\)に閉じているとは限らない。よって、\(FC\)を\(GFC\)などに拡張できる。このように、基本関数のクラス\(I\)に対して関数構成操作の閉包を取ることで得られる関数全体のクラスを作る、ということを繰り返すことで、関数クラスの族\(\mathfrak F\)が得られる。関数階層は、この関数クラス族\(\mathfrak F\)の部分族として表される。 Grzegorczyk、Ritche、Cleaveなどの関数階層は、…
C関数(循環タグシステム)の動作規則模索
C関数を更に強くする試みです
- 1 動作規則
- 2 関数\(C_1(n)\)
- 3 \(C_k´(n)\)関数
- 4 最後に
以下の動作規則をルール0とする。
\begin{align*}
0 &= \begin{cases}
\text{0に変え左に1つずれる} &(1の場合) \\
\text{演算を停止させる} &(その他の場合)
\end{cases} \\
10 &= \begin{cases}
\text{0に変え左に1つずれる} &(1の場合) \\
\text{何もせず左に1つずれる} &(その他の場合)
\end{cases} \\
11 &= \begin{cases}
\text{何もせず左に1つずれる} &(1の場合) \\
\text{1に変え左に1つずれる} &(その他の場合)
\end{cases} \\
\end{align*}
このとき、動作規則の左右を入れ替えていくことでルール0からルール31まで作ることが出来る。
また、左に1つずれることを0、右に1つずれることを1とした時、\((0,0,0,0,0)\)とも表すことが出来る
以下に例を表す
\begin{align*}
0 &= \begin{cases}
\text{0に変え右に1つずれる} &(1の場合) \\
\text{演算を停止させる} &(その他の場合)
\end{cases} \\
10 &= \begin{cases}
\text{0に変え左に1つずれる} &(1の場合) \\
\text{何もせず右に1つずれる} &(その他の場合)
\end{cases} \\
11 &= \begin{cases}
\text{何もせず右に1つずれる} &(1の場合) \\…
フィーは必ずしも正規でない
要旨
任意の \(G\) の正の元 \(g\) に対し \(g^{-1}Hg \subset H\) だが、 正規でない、 つまりある負の元 \(g_1\) に対し \(g_1^{-1}Hg_1 \not\subset H\) であるような全順序群 \(G\) の部分群 \(H\) の例を構成する。 \(\{a, b\}\) で生成される自由群 \(F\) を Magnus ordering の方法で Bi-ordering すると、 \(H = \langle b^{F_+} \rangle\)、 \(g_1 = a^{-1}\) が上記の例となることを示す。 そのための補題として、 \(F\) が \(X\) の生成する自由群、 \(x \in X\)、 \(U \subset x^F\) のとき、 ある \(x^F\) の部分集合が \(\langle U \rangle\) を自由に生成することを示す。
- 1 参考文献
\[ \newcommand{\oa}{\text{☆}} \newcommand{\ang}[1]{\langle #1 \rangle} \newcommand{\N}{\mathbb{N}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\Q}{\mathbb{Q}} \newcommand{\R}{\mathbb{R}} \newcommand{\1}{^{-1}} \newcommand{\e}{\epsilon} \newcommand{\ncl}[1]{\mathrm{N}(#1)} \newcommand{\floor}[1]{\lfloor #1 \rfloor} \newcommand{\of}[1]{\m…
木の埋め込み悪列についての補題
(「補題」と書くときに、主定理の中間素材にすぎないという意味と、色んな興味深い定理の中間素材として使えるという意味の2つがある気がしている。この2つを区別する単語がほしい。あと補題の補題って補題でもいいんだろうか？「補補題」にしたい気持ちもあるが補を2回取るともとに戻って「題」になってしまうんじゃないかという懸念もある。)
整半順序の悪列を用いた巨大数は色々とあり、その中でも木の埋め込み順序の悪列に対して頂点数で制限したものは非常に多い。
極大順序型が\(\omega^\omega\)などよりも十分大きいものについて、具体的に全順序化を与えてやってその順序型を下限に用いる、という手法がよく使われる。しかし、具体的に急増加関数やハーディ階層と比較しようとすると、関数の計算過程において現れる順序数が頂点数の制限に引っかかってないかを確かめるのが面倒である。
今回は、このような木の埋め込み順序の悪列を用いた巨大数に対して、頂点数の制限を軽減するための手法を書く。
目標としては、比較的少ない頂点数を削ることで、悪列に現れる木で許容される頂点数が矢印表記レベルの増大をするものに帰着させることである。おそらく二重指数やテトレーションレベルでも\(SVO\)辺りの基本列系を表現するには十分な頂点数なのだが、あえてそちらに制限する方が議論がややこしくなる気がする。
この議論はラベル付き木にも応用したいので、以降は空でない整半順序集合によってラベル付けされた木について考え、\(0\)をその整半順序集合の極小元とする。木\(T_0,T_1,\cdots,T_n\)について、根のラベルが\(0\)であり、根から\(T_0,T_1,\cdots,T_n\)へ辺が伸びている木を\((T_0,T_1,\cdo…
循環タグシステムのような何かを使った巨大数
最近循環タグシステム(cycle tag system)なるものを発見し、遊んでいたところこれで巨大数が作りたくなったので、作ることにしました。 恐らく循環タグシステムを用いた巨大数となっていると思います。
この関数では\((0),(10),(11)\)の3つの演算子で計算が行われます
ここでは以下のような演算が行われるとします。
\begin{align*}
0 &= \begin{cases}
\text{0に変え右に1つずれる} &(1の場合) \\
\text{演算を停止させる} &(その他の場合)
\end{cases} \\
10 &= \begin{cases}
\text{0に変え左に1つずれる} &(1の場合) \\
\text{何もせず右に1つずれる} &(その他の場合)
\end{cases} \\
11 &= \begin{cases}
\text{何もせず右に1つずれる} &(1の場合) \\
\text{1に変え左に1つずれる} &(その他の場合)
\end{cases} \\
\end{align*}
- \(0\)と\(1\)のみからなる長さnの数列を考える
- 長さnの数列を繋げ、演算子ごとに区切っていく
- 入力を無限個の1に固定し、任意の場所の1から演算を開始できるとする
- 演算が停止した時点の\(0\)の個数をこの関数の出力とする
この時、関数C(n)を使い、最も多くの0を描いたものをこの関数の値とする ただし、無限に演算が続くようなものは無視するとする
以上の定義を踏まえ\(C(10^{100})\)をこの巨大数の値とする。
例としてC(3)の値を求めてみる 長さ3の数列は
- \(0,0,0\)
- \(1,0,0\)
- \(0,1,0\)
- \(0,0,1\)
- \(0,1,…
戯言
下書きでもなんでもない、全然精査してないメモ書きです。つまるところタイトル通りです。
- 1 二分木の埋め込み順序
- 1.1 極大順序型
- 1.2 二分木版tree関数の下限
- 1.3 極大順序型
- 2 葉にラベルを許した二分木
- 2.1 表解析的なもの
- 2.2 \(\textrm{tree}(4)\)の下限
- 3 一般の木構造の埋め込み順序
ラベルなしの二分木の埋め込み順序が極大順序型\(\varepsilon_0\)ってのを見て納得できてなかったんだけど、やってること自体はDHさんがやってる木を二分木で表現する手法と全く同じであることに気づいた。
あとは左右の入れ替えをできなくするための工夫さえあればいい。
更に言えば\(CNF\)じゃなくても列の埋め込み順序の全順序化であればよかったりして、二分木のtree関数とか作るとこっちの方が\(\omega\)冪の増え方が倍になりちょっとお得。
毎回アイディア思いついては部屋に散らばった紙のどっかに書き殴っては失くすので、ここに書く。
- \(\textrm{tree}_2(1) = 2\)
- \(\textrm{tree}_2(2) = 5\)
- \(\textrm{tree}_2(3) \ge 16\)
- \(\textrm{tree}_2(4) \ge 844\textrm{兆}\)
\((()(()()))\)に埋め込めないものは分岐点が高々1つの木(YやVやIの形)であり、分岐点の高さ、分岐後の両枝の長さのうち短い方、長い方、の順で辞書式順序をとれば\(\omega^3\)に全順序化できる。
- \(\textrm{tree}_2(5) \ge f_\omega^3(4)\)
\(((())(()())),\ (((()))((()))),\ ((())((((())))))\)のように並べたあと、…