スケッチ #290

Dyckのprodiscrete二義性 ## Trigger *Topoi of automata II* の conjecture「任意の language class \(C\) に対し \(\mathcal T(C)\simeq\mathbf{Cont}(M_C)\) となる canonical prodiscrete monoid \(M_C\) がある」を，Morgan Rogers の topological monoid action topos の構成と本文の Dyck exampleで監査した． ## Result \(\Sigma=\{a,b\}\)，\(D\) を Dyck language，\(F_D\subseteq\Xi\) を syntactic topos \(\mathcal T(D)\) の internal filter とする．すると \[ F_D\cap\Xi^2=\{\top\}. \] したがって，\(\mathcal T(D)\) を表現する prodiscrete monoid \(P\) と dense monoid homomorphism \(\Sigma^*\to P\) は存在しない．よって「任意の \(C\) で prodiscrete」は偽である． 一方，Rogers の canonical constructionは internal filter全体を使う inverse limit \[ M_F:=\varprojlim_{\rho\in F}U(\Sigma^*/\rho) \] であり，各 \(\Sigma^*/\rho\) は discrete **set** として使われる．thread \(\alpha,\beta\) の積は \[ (\alpha\beta)_\rho=[a_\rho b_{\rho*a_\rho}]_\rho \] で与えられる．この \(M_F\) は dense imageをもつ complete powder monoidで \[ \mathcal E_F\simeq\mathbf{Cont}(M_F). \] prodiscreteになる必要十分条件は \(F\) が two-sided congruences の basisをもつことである． language class \(C\) については次が同値である． 1. \(\mathcal T(C)\) が prodiscrete monoid action toposとして表示できる． 2. \(F_C\) が two-sided congruences の basisをもつ． 3. 各 \(L\in C\) の syntactic congruence \[ \equiv_L=\bigwedge_{w\in\Sigma^*}(\sim_L*w) \] が \(F_C\) に属する． 特に \(C\subseteq\mathrm{Reg}\) なら成立し，representing monoidは profinite．一文字 alphabetでもすべての right congruenceがtwo-sidedなので成立する． ## Dyck proof Dyck filterは有限集合 \(S\subseteq\mathbb N\) に対する finite meets \[ \tau_S=\bigwedge_{k\in S}\sim_k \] の upward closureで生成される．\(\sigma\in F_D\cap\Xi^2\) とし，\(n=\max S\) で \(\tau_S\leq\sigma\) とする．quotient monoidで \(\alpha=[a]\)，\(\beta=[b]\) と置くと，有限深さの同一視から \[ \beta^{n+1}=\beta^{n+1}\alpha,\qquad \beta^{n+1}=\beta^{n+2},\qquad 1=\alpha^{n+1}\beta^{n+1} \] を得る．第一式と第三式から \(\alpha=1\)，さらに第二式と第三式から \(\beta=1\)．よって quotient monoidは trivialで \(\sigma=\top\)． 仮に prodiscrete \(P=\varprojlim_iP_i\) が \(\mathcal T(D)\) を表すなら，各 projection kernel \(\ker(\Sigma^*\to P_i)\) は \(F_D\cap\Xi^2\) に属するためすべて \(\top\)．従って \(\Sigma^*\to P\) は trivialとなり，Dyckをrecognizeできない．矛盾． ## Concrete representing monoid Dyckの syntactic monoidは bicyclic monoid \[ B=\langle\alpha,\beta\mid\alpha\beta=1\rangle. \] Rogers completionは概念的に \[ B\sqcup\{\infty\} \] で，\(\infty\) は absorbing，その neighborhood basisは \[ U_k=\{\infty\}\cup\{\beta^i\alpha^j\mid i>k\}. \] これは jointly continuousな complete powder monoidで \(\mathbf{Cont}(B\sqcup\{\infty\})\simeq\mathcal T(D)\) だが，非自明な open two-sided congruenceを持たず prodiscreteでない． ## Significance non-locally-finite側で失敗する本質は「finite meetしか許されない filter」と「syntactic congruenceを得るために必要な infinite meet」の差である．regular/orbit-finite側では orbitが有限なのでこの差が消え，powderはprofiniteへ退化する．Dyckはこの境界を完全に可視化する running exampleである． ## Goal 現行原稿の prodiscrete conjectureを削除し，Rogersの complete powder construction，two-sided-basis criterion，Dyck counterexampleを theoremとして置き換える． ## Correction: two meanings of prodiscrete ここで `prodiscrete monoid` という語には区別すべき二つの意味がある． 1. **algebraic / strict sense**: discrete monoids の projective limitとして TopMon 内で得られる monoid（Rogers, Definition 2.19）．各 coordinate projection は monoid homomorphismである． 2. **topological sense**: topological monoid whose underlying topological space carries a prodiscrete topology，すなわち discrete sets の projective limit topologyをもつもの．coordinate objects は monoidsである必要がない． Rogers の canonical completion \[ L_F=\varprojlim_{\rho\in F}U(\Sigma^*/\rho) \] は任意の internal filter \(F\) に対して **常に後者**である．Rogers の Theorem 3.20 は canonical representative が prodiscrete topologyを持つと述べ，Remark 3.21 はそれが一般には Definition 2.19 の意味での prodiscrete monoidではないことを区別している． 従って上の Result の「Dyckを表現する prodiscrete monoid は存在しない」は，**Definition 2.19 の strict senseに限った主張**として読む．Dyck syntactic toposは，underlying topologyが prodiscreteな complete powder monoid \(B\sqcup\{\infty\}\) によって実際に表現される．失敗するのは「discrete monoids の pro-object」としての表示であり，「prodiscrete topologyを持つ topological monoid」としての表示ではない． この区別により，現行原稿の conjectureは用語を定義すれば次のように整理される． - weak/topological senseでは任意の language classに対して真（Rogers construction）． - strict/algebraic senseでは two-sided congruence basisを持つ場合に限り真で，Dyckは反例． - regular/orbit-finiteの場合はさらに profinite monoidになる．