バシク行列のヒドラ表記

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

• ユーザーブログ:KurohaKafka/バシク行列のブーフホルツのヒドラを応用した表現 (KurohaKafka, 2017.5.24)

• バシク行列システムの解説（第２版）(Bashicu, 2017.6.25--2017.7.17, SlideShare)

• W. Buchholz, "An independence result for \(\Pi_1^1\)-\(\text{CA}\)+\(\text{BI}\)"

ヒドラ表記の例

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

ヒドラ表記の書きかた

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

ペア数列をヒドラ表記に変換する方法を一気に説明するとこれになります。

実際は以下の手順で書いていくと書きやすいです。まずは１行目の数字を高さにして空の丸を書いていきます。

次に２行目を見て丸の中にラベルを書いていきます。

次に枝を付けます。注目する子ノードに対して、「１階層低くかつ一番右にあるノード」を親ノードとして、子ノードと親ノードを枝でつなぎます。これを全部のノードに対して行うと完成です。

ペア数列システムの展開方法

ここからはペア数列の展開の方法を説明します。ラベル0の子が刈られると親は怒ってn倍に分裂します。

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

ペア数列システムとブーフホルツのヒドラの展開の違い

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

コピー先の最右の刈られた子がいた場所の処理

ブーフホルツのヒドラは、コピー先の最右の刈られた子がいた場所にはラベルがゼロの子が付きます。ペア数列では欠けたままになります。

伸び量

ペア数列はn+1倍に伸びますが、ブーフホルツのヒドラは毎回２倍になり、nに依存しません。(全てのラベルが ω 未満であるツリーの場合は、ブーフホルツのヒドラはブラケットが 1 であるペア数列と同様の動きになります。）

親のコピー先のラベル

ブーフホルツのヒドラの親のコピー先の位置のラベルは、刈られた子のラベル-1となります。ペア数列は、怒った親のラベルそのままになります。(ラベルが ω 未満であり、かつ、怒る親が常に子の (ラベル)-1 であるようなツリー(つまり標準形のペア数列と同じツリー）の場合には両者の動きはこの観点では同一になります）

ペア数列システムの集約

展開の逆である集約を表したのが左記です。無限にあって無駄な家族を１つにまとめ、まとめた証拠として子をひとつ付け加える操作を展開の逆の集約と考えると分かりやすいです。