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)\)となるはず。 

疑問

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

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

広告ブロッカーが検出されました。


広告収入で運営されている無料サイトWikiaでは、このたび広告ブロッカーをご利用の方向けの変更が加わりました。

広告ブロッカーが改変されている場合、Wikiaにアクセスしていただくことができなくなっています。カスタム広告ブロッカーを解除してご利用ください。