問い #154

Partisan games via Pfin×Pfin ## Trigger Hora, *Games as recursive coalgebras* のQuestion 5.3と旧HP Problems 5.0.4にある公開問題。`created` は論文の初公開日を代理値とし、正確な着想日は不明。 ## Idea To what extent is the theory of partisan games comprehended by replacing \(\mathcal{P}_{\mathrm{fin}}\) with \(\mathcal{P}_{\mathrm{fin}}\times\mathcal{P}_{\mathrm{fin}}\)? This corresponds to Question 5.3 of the games-as-recursive-coalgebras paper. ## Goal 旧原文のfunctorの置換によってpartisan gamesの理論をどこまで捉えられるかを明らかにする。 ## Personal context 旧タグは partisan game、finite powerset、recursive coalgebra。旧一覧以後の進展はこの移住では未確認であり、棚卸し待ちとして `status: dormant` とする。 ## References - [Ryuya Hora, *Games as recursive coalgebras: A categorical view on the Nim-sum*](https://arxiv.org/abs/2510.22886) ## Provenance - 旧ID: 5.0.4 - 旧分類: informal question - [旧出典 `scripts/site.js` 902–910行](https://github.com/hora-algebra/ryuya-hora-homepage/blob/1b8b74c2b3447bdc744a0cac256c5d5806588adc/scripts/site.js#L902-L910) - Ideaの2段落は旧HPのstatement / descriptionをそのまま保持した。 ## 2026-08-26 AI研究監査：recursive-coalgebraic 部分の回答 $F(X)=\mathcal P_{\mathrm f}(X)\times\mathcal P_{\mathrm f}(X)$ と置く．recursive $F$-coalgebra は，Left-option relation と Right-option relation を備えた finitely branching well-founded graph にほかならない．final recursive coalgebra（同値に initial $F$-algebra）は hereditarily finite pair \[ \{G^L\mid G^R\} \] 全体であり，short partisan game forms をそのまま回収する．Conway sum は両 option relation に関して componentwise に定義できる． さらに cofree $F$-coalgebraを使えば Conway sum の internal hom も impartial case と同様に，Left residual children と Right residual childrenを持つ labelled well-founded trees の部分 coalgebraとして明示できる． ただしこの replacement が直接捉えるのは game forms と exact option-preserving morphisms である．Conway order，dominated/reversible option の除去，Joyal の strategy morphisms，normal-play value quotient は追加構造であり，$\mathcal P_f\times\mathcal P_f$ だけからは自動的に出ない．したがって問いは「forms については完全，values/strategies については未完」と分解される． ## 2026-08-27 ChatGPT 追記案：partizan recursive coalgebra と surreal numbers $F(X)=\mathcal P_{\mathrm f}(X)\times\mathcal P_{\mathrm f}(X)$ と置くと，recursive $F$-coalgebra は有限分岐 well-founded な Left/Right option graph であり，その terminal recursive coalgebra（同値に initial $F$-algebra）は short partizan game forms \[ G=\{G^L\mid G^R\} \] 全体を与える．したがって，impartial case の ``finite-time game = recursive coalgebra''，universal recursion，Conway sum，negation はそのまま二色化して成立する． normal-play outcome も $F$-algebraへの hylomorphism として書ける．たとえば $O=\{0,1\}^2$ として，第一成分を ``Left が先手のとき Left が勝つ''，第二成分を ``Right が先手のとき Left が勝つ'' と読むと， \[ \alpha(S_L,S_R)=\left(\bigvee_{(p,q)\in S_L}q,\;\bigwedge_{(p,q)\in S_R}p\right) \] が $F$-algebra を定め，4 outcome classes $L,R,N,P$ を再帰的に回収する． 一方，$F$-coalgebra morphism は options を exact に保存する map であって，Joyal/Honsell--Lenisa 型の playing strategy ではない．また Conway order，dominated/reversible option の除去，canonical form は normal-play semantics と order を追加して初めて定まる．従って，$\mathcal P_f\times\mathcal P_f$ は game forms の syntax については完全だが，values/strategies については追加構造が必要である． partizan 側では ``forms と values'' を明確に分けるのがよい．short game forms の terminal recursion \[ \operatorname{RecCoalg}_F\to G_{\mathrm{sh}} \] の後に，Conway sum $+$ と normal-play outcome $o$ を用いて contextual indistinguishability \[ G\sim H\iff \forall K,\; o(G+K)=o(H+K) \] で割ると，standard short Conway game values の加法群 $\mathcal G_{\mathrm{sh}}$ が現れる．これは impartial case における Grundy/Bouton quotient の partizan analogue とみなせる． surreal numbers は terminal recursive coalgebra 全体ではなく，この value quotient の中の hereditary separated substructure である．game $x=\{x^L\mid x^R\}$ が number であるとは，全 options が numbers であり，任意の $x^L,x^R$ に対して $x^L<x^R$ が成り立つこと．short case では得られる numbers は dyadic rationals \[ \mathbf{No}_{\mathrm{sh}}\cong \mathbb Z[1/2] \] である．たとえば $*=\{0\mid0\}$ は game だが number ではない． full surreal numbers には $\omega=\{0,1,2,\dots\mid\}$ のような無限 option set と transfinite birthday が必要なので，$\mathcal P_f$ では足りない．概念的には \[ \mathcal P_f\rightsquigarrow \mathcal P_{\mathrm{small}} \] とし，initial chain を ordinal 全体にわたる transfinite construction に置き換える必要がある．proper-class size の問題を避けるなら universe/inaccessible cardinal $\kappa$ を固定して $\mathcal P_{<\kappa}$ を使う． 以上より，partizan analogue の基本図式は \[ \text{recursive coalgebras} \longrightarrow \text{short Conway forms} \longrightarrow \text{Conway game values} \supset \text{dyadic surreal numbers} \] である．full surreal theory へは small-powerset/transfinite extension が必要． ### Correction / caution 既存本文の ``cofree $F$-coalgebraを使えば Conway sum の internal hom も ... 明示できる'' という記述は現時点では theorem として扱わない方がよい．impartial case では abstract closedness は locally presentable category の議論から得られるが，concrete internal hom の明示は未解決問題として残っている．partizan case でも ``cofree coalgebra 内の最大部分coalgebra'' という候補構成は有望だが，要証明． ## 2026-08-27 補訂：成立範囲と surreal numbers ### 結論 \[ F(X)=\mathcal P_{\mathrm{fin}}(X)\times\mathcal P_{\mathrm{fin}}(X) \] と置く．この置換は **short partisan game forms と，その上の再帰計算**をほぼ完全に捉える．一方，Conway order，normal-play value quotient，canonical simplification，strategy morphism は，endofunctor 単独ではなく追加の semantics を必要とする． ### 1. recursive-coalgebraic layer $F$-coalgebra \[ X\longrightarrow \mathcal P_{\mathrm{fin}}(X)\times\mathcal P_{\mathrm{fin}}(X) \] は，各局面に有限個の Left options と Right options を与えた二色の finitely branching graph である．recursive であることは，option relation に無限下降列がないこと，すなわち全 play が有限時間で終わることに対応する． terminal recursive $F$-coalgebra（同値に initial $F$-algebra）は，遺伝的有限な式 \[ G=\{G^L\mid G^R\} \] 全体であり，short partisan Conway game forms を回収する．これは Hora, Proposition 5.4 の内容である． 任意の $F$-algebra \[ \alpha:\mathcal P_{\mathrm{fin}}(A)\times\mathcal P_{\mathrm{fin}}(A)\to A \] に対して，一意な hylomorphism \[ h(x)=\alpha(h[L_x],h[R_x]) \] が存在する．したがって「game value は algebra への hylomorphism」という主張は partisan case にそのまま残る． normal-play outcome の四値集合を $O=\{0,1\}^2$ とし，$(p,q)$ を「Left が先手なら勝つ」「Right が先手でも Left が勝つ」と解釈すると， \[ \alpha(S_L,S_R)=\left(\bigvee_{(p,q)\in S_L}q,\;\bigwedge_{(p,q)\in S_R}p\right) \] によって outcome は $F$-algebraから誘導される．空 join は $0$，空 meet は $1$ とする． Conway sum と negation も game forms 上で \[ (G+H)^L=(G^L+H)\cup(G+H^L),\qquad (G+H)^R=(G^R+H)\cup(G+H^R), \] \[ (-G)^L=-G^R,\qquad(-G)^R=-G^L \] として再帰的に定義できる． ### 2. forms と values / strategies の境界 $F$-coalgebra morphism は Left/Right options を厳密に保存し，さらに target option の path-lifting を要求する．これは play history 上で応答を選択する Joyal 型・Conway 型の strategy morphism とは異なる．したがって \[ \text{coalgebra morphism}\neq\text{strategy}. \] また，Conway order \[ G\le H \iff \bigl(\nexists G^L\colon H\le G^L\bigr) \ \&\ \bigl(\nexists H^R\colon H^R\le G\bigr) \] は well-founded recursion で定義できるが，これは normal-play semantics を選んだ後の追加構造である．dominated option の除去，reversible option の bypass，canonical form もこの order に依存する． ### 3. Bouton quotient は short Conway game values を回収する short game forms の集合を $\mathbb G$，Conway sum を $+$，四値 outcome を $o$ とする．$o$ の minimum monoid factorization が定める congruence は \[ G\equiv H \iff \forall K\in\mathbb G,\quad o(G+K)=o(H+K) \] である．これは normal-play の contextual equivalence / indistinguishability である．Honsell--Lenisa は well-founded Conway games 上で contextual equivalence が Conway order から定まる通常の game equivalence と一致することを示している．従って partisan 版 Bouton monoid \[ \mathcal B^{\mathrm{part}}_{+,o} \] は short Conway game values の加法 monoid と同型であり，negation が逆元を与えるので実際には ordered abelian group になる． 要するに \[ \boxed{\text{forms は terminal recursion，values は Bouton/contextual quotient}} \] という二段構造である． ### 4. surreal numbers は raw coalgebra ではなく subquotient short game forms から normal-play equality で割った short game values の群を $\mathcal G_{\mathrm{sh}}$ とする．その中で number は hereditary に 1. 全 Left/Right options が number であり， 2. 任意の $G^L,G^R$ に対して $G^L<G^R$ を満たすものとして切り出される．従って \[ \operatorname{RecCoalg}_{\mathcal P_{\mathrm{fin}}\times\mathcal P_{\mathrm{fin}}} \longrightarrow \mathbb G \longrightarrow \mathcal G_{\mathrm{sh}} \supset \mathbf{No}_{\mathrm{sh}}. \] finite options と finite birthday の範囲で得られる short surreal numbers は dyadic rationals \[ \mathbf{No}_{\mathrm{sh}}\cong\mathbb Z[1/2] \] である．例えば $0=\{\mid\}$，$1=\{0\mid\}$，$1/2=\{0\mid1\}$ は number だが，$*=\{0\mid0\}$ は separation condition を満たさず number ではない． full surreal class $\mathbf{No}$ に到達するには，有限 option を small option に置き換え，birthday を全 ordinal にわたって許す必要がある．したがって ordinary $\mathbf{Set}$ 上の $\mathcal P_{\mathrm{fin}}\times\mathcal P_{\mathrm{fin}}$-coalgebraでは不足し，class-sized または universe-relative な \[ \mathcal P_{\mathrm{small}}\times\mathcal P_{\mathrm{small}} \] の扱いが必要になる． ### 5. 以前の AI 監査への訂正 以前の追記にある > cofree $F$-coalgebraを使えば Conway sum の internal hom も明示できる という記述は，現時点では theorem として扱ってはならない．元論文は impartial category $\mathbf{Game}$ の monoidal closedness を local presentability から抽象的に示す一方，具体的 internal hom の記述を Question 5.7 として残している．partisan category \[ \mathbf{RecCoalg}_{\mathcal P_{\mathrm{fin}}\times\mathcal P_{\mathrm{fin}}} \] についても，同様の local-presentability / cocontinuity argument が移るかを別途証明する必要がある．cofree object $R(Y^X)$ のうち evaluation が game morphism となる最大 subcoalgebraを取る案は，有望な construction candidate ではあるが未証明である． ### 6. 次の研究課題 - $\mathbf{RecCoalg}_{\mathcal P_{\mathrm{fin}}\times\mathcal P_{\mathrm{fin}}}$ の local finite presentability と colimit creation を明記して証明する． - Conway sum がこの圏で symmetric monoidal closed になることを証明し，internal hom を具体計算する． - coalgebra morphisms，Joyal strategies，Honsell--Lenisa の play-based strategies の間を比較する． - Bouton quotient と short Conway game group の同型を定理として書き下す． - number subquotient と $\mathbb Z[1/2]$ の対応，さらに universe-relative な full surreal extension を形式化する． ## References added in this audit - Ryuya Hora, [*Games as recursive coalgebras: A categorical view on the Nim-sum*](https://arxiv.org/abs/2510.22886), especially Sections 5.2 and 5.4.1 and Appendix B. - Furio Honsell and Marina Lenisa, [*Conway Games, algebraically and coalgebraically*](https://arxiv.org/abs/1107.1351), especially Sections 2--4.