FANDOM


  • プレイヤーは前のプレイヤーが言った順序数より小さい順序数を言う
  • 0を言ったら終了

というルールのゲームは、必ず有限回で終了し、各ターンにてプレイヤーが言える順序数にをうまく制限すればターン数の上限が生まれる。

例​:2変数関数ゲーム

プレイヤーは下の3つの関数を組み合わせて表せる順序数を言うことができる。

ただし、kターン目で使用可能な関数の個数は合計k+n個までで、変数は1~k+nまでの自然数と\({\omega}\)である。

\(A({\alpha},{\beta})={\alpha+{\beta}}\)

\(B({\alpha},{\beta})={\alpha×{\beta}}\)

\(C({\alpha},{\beta})={\alpha^{\beta}}\)

例(n=1)

\(C({\omega},C({\omega},{\omega}))={\omega^{\omega^{\omega}}}\)・・・1ターン目なので、1+1個の関数を使える

\(C({\omega},C({\omega},C(3,3)))={\omega^{\omega^{27}}}\)・・・2ターン目なので、2+1個の関数と2+1以下の自然数を使える

\(C({\omega},C({\omega},B(4,B(3,2))))={\omega^{\omega^{24}}}\)・・・3ターン目なので、3+1個の関数と3+1以下の自然数を使える

\(C({\omega},B(C({\omega},A(B(5,4),3),5)))={\omega^{\omega^{23}×5}}\)・・・4ターン目なので、4+1個の関数と4+1以下の自然数を使える

nに対するターン数の上限を\(g(n)\)とすると\(g(n)\approx f_{\epsilon_0}(n)\)程度になる。

位相同型的埋め込み可能

ツリー数列やサブキュービックグラフ数は「位相同型的埋め込み可能」という概念でグラフの大小関係を定義し、順序数に対応させている。

以下の操作を「縮約」と呼ぶ。

  • 2次以下の頂点を消す(2次の頂点の場合辺を残す)
  • 辺を消す

グラフAを縮約してグラフBに変形できるとき、「AはBに位相同型的埋め込み可能である」という。

※グラフは「点と点のつながり」を表すものであるため、点の配置が異なっても辺のつながり方が同じならば同じグラフである。

「AはBに位相同型的埋め込み可能である」ということを「AはBより小さい」と解釈し、小さいグラフが前に来ないように制限することにより項数の上限ができる。

Tree

サブツリー関数

以下の性質を満たすグラフを「サブツリー」と命名する。

・すべての変に向きがある有効グラフである。

・辺とその向きに従って頂点間を移動するとき、1回以上の移動で元の頂点に戻ってこられる頂点は1つもない。

・辺とその向きに従って頂点間を移動するとき、まったく移動できない頂点がただ一つ存在する。

\(ST(n)\)を以下の性質を満たすサブツリーの列\(T_k\)の最大長とする。

・\(T_k\)の頂点の個数と次数は\(n+k\)以下である。

・\(k>l\)ならば、\(T_l\)は\(T_k\)に位相同型的埋め込み可能でない。

関数として成立しているかは不明だが、成立しているならシンプルサブキュービックグラフはすべて使えるので \(ST(n)≥SSCG(n)\)となるはず。 

多重配列列

※\(0∈\mathbb{N}\)

  • 集合\(x\)に対し、\(S(x)\)を「\(x\)の要素を要素とする有限配列全体からなる集合」とする。

例:\(x=\{0,1\}\)

\(S(x)=\{(0),(1),(0,0),(0,1),(1,0),(1,1),(0,0,0),・・・\}\)

  • \(X_n\)を以下の通り定める。
    • \(X_0=\mathbb{N}\)
    • \(X_n=S(\bigcup_{k<n}X_k)\)
    • \((A∈X_{n+1})∧¬(A∈X_n)⇔R(A)=n+1\)
  • 配列の大小関係を以下の通り定める。ただし、上にある規則ほど適用の優先度が高いとする。
    • \((A≤B)∧(B∈C)⇒A<C\)
    • \(L(A)<L(B)⇒A<B\)  ただし、\(L(A)\)は配列\(A\)の長さを表す。
    • \(A=(a_0,a_1,・・・a_n),B=(b_0,b_1,・・・b_n)\)\(∃m∈\mathbb{N}((a_m<b_m)∧(k<m⇒a_k=b_k))⇒A<B\)
    • \((A∈X_0)∧¬(B∈X_0)⇒A<B\)
  • \(A(n)\)を以下の条件を満たす列\(a_k\)の最大長として定める。
    • \(a_k\)は\(L(a_k)≤k+n\)かつ\(k+n\)以下の自然数で表せるような\(X_1\)の要素である。
    • \(k<m⇒a_k<a_m\)
  • \(B(n)\)を以下の条件を満たす列\(b_k\)の最大長として定める。
    • \(b_k\)は\(L(b_k)≤k+n\)かつ\(k+n\)以下の自然数で表せるような\(X_2\)の要素である。
    • \(k<m⇒b_k<b_m\)
  • \(C(n)\)を以下の条件を満たす列\(c_k\)の最大長として定める。
    • \(c_k\)は\(L(c_k)≤k+n\)かつ\(k+n\)以下の自然数で表せるような\(X_n\)の要素である。
    • \(k<m⇒c_k<c_m\)
  • \(D(n)\)を以下の条件を満たす列\(d_k\)の最大長として定める。
    • \(X=\bigcup_{i∈\mathbb{N}}X_i\)
    • \(d_k\)は\(R(d_k)<k+n\)かつ\(L(d_k)≤k+n\)かつ\(k+n\)以下の自然数で表せるような\(X\)の要素である。
    • \(k<m⇒d_k<d_m\)

\(A(n)\approx f_{\omega}(n)\)

\(B(n)\approx f_{\omega}(n)\)

\(C(n)\approx f_{\omega}(n)\)

\(D(n)≳f_{\psi_0({\Omega^{\omega}})}(n)?\)

絡み目数

以下の操作を絡み目Aに有限回適用して絡み目Bに変換可能であるとき、\(A≥B\)が成り立つとする。

ただし、操作を1回行う前に毎回交点数が最小になるように絡み目を整えなければならない。

  • 成分を削除する
  • 左右反転
  • 交点を以下のように変換する。
Link

\(Link(n)\)を以下の性質を満たす絡み目の列\(L_k\)の最大長とする。

  • \(a>b⇒¬(L_a≥L_b)\)
  • \(L_k\)の各成分の交点数と成分数は\(k+n\)以下

疑問

現時点で自分がよくわかっていないことを書いておく。

  • サブキュービックグラフ数の限界を表す列(サブキュービックグラフ数の強さを表す順序数の収束列に当たる列)は何か
  • グラフ列関数において使えるグラフの制限は何のためにあるのか
    • 制限がないと無限降下列ができてしまう
    • 制限しなくても関数として成立するが、証明されていない