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

Provenance

• 旧ID: 5.0.4
• 旧分類: informal question
• 旧出典 scripts/site.js 902–910行
• 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, especially Sections 5.2 and 5.4.1 and Appendix B.
• Furio Honsell and Marina Lenisa, Conway Games, algebraically and coalgebraically, especially Sections 2--4.

@misc{sumire:2610.00003:3:v1,
  author = {hora},
  title = {{Partisan games via Pfin×Pfin}},
  year = {2026},
  note = {SUMIRE:2610.00003/3, v1},
  url = {https://sumire.aiformath.jp/p/2610.00003/n/3/v/1}
}