モスコバキスの符号化補題

モスコバキス符号化補題は、記述集合論における補題であり、決定性公理（選択とは両立しない原理で、2人プレイの整数ゲームはすべて決定的であるという原理）の下で実数の集合を扱う。この補題は数学者ヤニス・N・モスコバキスにちなんで考案され、その名が付けられた。

この補題は一般に次のように表現される。

Γ を

実量化と

\land

に関して閉じた非自己双対点類とし、

≺ を

ω

ω

上

の階数

θ

\in ONの

Γ

-整基盤関係とします。

R \subseteq dom(≺) \times

ω

ω

が(\forall

x

\indom(≺))(\exists

y

)(

x

R

y

)

となるとします。このとき、 R の選択集合となる

Γ

-集合

A \subseteq dom(≺) \times

ω

ω

が存在し、これは次のようになります。

$(\forall α < θ)(\exists x \indom(≺), y)(| x | ≺ = α \land x A y)$ 。
$(\forall x, y)(x A y \to x R y)$ 。

証明は以下の通りである。矛盾に対して $θ$ が最小の反例であると仮定し、 $≺$ 、 $R$ 、および良好な普遍集合 $U \subseteq (ω ω) 3 を$ $($ $ω$ $ω$ $)$ $2$ の $Γ$ 部分集合に固定する。簡単に言うと、 $θ は$ 極限順序数でなければならない。 $δ$ $<$ $θ$ に対して、特性 (1) が $α$ $\leq$ $δ$ $に対してA =$ $U u$ を使用して成立し、特性 (2) が $A =$ $U uに対して成立する場合、$ $u$ $\in$ $ω$ $ω$ $はδ$ 選択集合をコードすると言える。ここで、 $x$ $\in dom(≺)$ を $x$ $\in dom(≺) \land |$ $x$ $| ≺ [\leq$ $δ$ $]$ に置き換える。 $θ$ の最小性により、すべての $δ$ $<$ $θ$ $に対してδ$ 選択集合が存在します。

ここで、プレイヤーIとII $が$ 点 $u 、 v\inωω を選択し$ $、$ $uが$ $δ1<θに対してδ1選択集合をコーディングし、vがδ2>δ1$ $に対して$ $δ2$ $選択$ 集合 $をコーディング$ する $ゲーム$ $を$ $しよ$ $う$ $。I$ $の$ $勝利$ 戦略 $は$ Σを $定義$ する。 $11$ $δ$ $<$ $θ$ $の任意の大きさに対してδ$ 選択集合を符号化する実数の集合 $B$ を定義する。次に

x A y \leftrightarrow (\exists w \in B) U (w, x, y)

,

これは簡単に機能します。一方、 $τが$ IIの勝利戦略であると仮定します。smn定理から、 $s :(ω ω) 2 \to ω ω$ が連続で、すべての $ϵ$ 、 $x$ 、 $t$ 、および $w$ に対して、

U (s (ϵ, x), t, w) \leftrightarrow (\exists y, z)(y ≺ x \land U (ϵ, y, z) \land U (z, t, w))

。

再帰定理により、 $U$ $($ $ϵ$ $0$ $,$ $x$ $,$ $z$ $) \leftrightarrow$ $z$ $=$ $τ$ $($ $s$ $($ $ϵ$ $0$ $,$ $x$ $))$ となるようなϵ $0 が存在する。$ $x$ $\in dom(≺)$ に対する $|$ $x$ $|$ $≺$ の直接的な帰納法から、

( \forall x \indom(≺))(\exists! z) U (ϵ 0, x, z)

,

そして

(\forall x \indom(≺), z)(U (ϵ 0, x, z) \to z は順序数 \geq| x | ≺) の選択セットをエンコードします

。

だから

x A y \leftrightarrow (\exists z \indom(≺), w)(U (ϵ 0, z, w) \land U (w, x, y))

.^[1]^[2]^[3]

参考文献

^ バビンコストーヴァ、リリヤナ (2011).集合論とその応用. アメリカ数学会. ISBN 978-0821848128。
^ 職長、マシュー;金森章弘（2005年10月27日）。集合論ハンドブック(PDF)。スプリンガー。 p. 2230.ISBN 978-1402048432。
^ Moschovakis, Yiannis (2006年10月4日). 「順序ゲームと遊び心のあるモデル」. Alexander S. Kechris, Donald A. Martin, Yiannis N. Moschovakis (編). Cabal Seminar 77 – 79: Proceedings, Caltech-UCLA Logic Seminar 1977 – 79 . Lecture Notes in Mathematics. Vol. 839. Berlin: Springer. pp. 169– 201. doi :10.1007/BFb0090241. ISBN 978-3-540-38422-9。

この数学関連の記事はスタブです。記事を拡張することでWikipediaに貢献できます。

[1] バビンコストーヴァ、リリヤナ (2011).集合論とその応用. アメリカ数学会. ISBN 978-0821848128。

[2] 職長、マシュー;金森章弘（2005年10月27日）。集合論ハンドブック(PDF)。スプリンガー。 p. 2230.ISBN 978-1402048432。

[3] Moschovakis, Yiannis (2006年10月4日). 「順序ゲームと遊び心のあるモデル」. Alexander S. Kechris, Donald A. Martin, Yiannis N. Moschovakis (編). Cabal Seminar 77 – 79: Proceedings, Caltech-UCLA Logic Seminar 1977 – 79 . Lecture Notes in Mathematics. Vol. 839. Berlin: Springer. pp. 169– 201. doi :10.1007/BFb0090241. ISBN 978-3-540-38422-9。