テトリス代数の覚書
はじめに
しーた
のすなるテトリス代数いふものを、AAGもしてみむとてするなり。
ということで、しーたさんのtwitterで明かされたテトリス代数の基礎の書き取り、解釈、補足、その他です。（もちろん許可は取ってます。）
功績はほとんどしーたさんらのものであり、わかりにくい部分はほとんど自分です。(訳書の冒頭のあれ)
自分の理解力と時間とやる気が足らなくてしっかり書けなかった部分をその後の流れにまとめたので、読者への演習問題にしておきます。（言いたいだけ）
定義
モノイド$(T,\cdot,0)$がテトリス代数であるとは、
・$ab=ac \Rightarrow b=c$ (左簡約律)
・$ab=0\Rightarrow a=0 \land b=0$ (0が既約)
を満たすことをいう。
※$ab=0,a=0$のとき$b=0$であるから、2つ目は$ab=0\Rightarrow a=0$と同値
テトリス代数$T$について、
可換モノイド$(T,+,0)$が和付きテトリス代数であるとは、
・$a+a=a$ (冪等性)
・$a(b+c)=ab+ac$ (左分配律)
・$\exists! x,\ ax=a+b$ (基本方程式の可解性)
を満たすことをいう。
特に、基本方程式の唯一解を$(b\mid a)$と表す。
関係$\leq_+$を$a\leq_+ b \Leftrightarrow a+b=b$で定めると、
$\leq_+$は半順序である。
(反射性)冪等性より
(反対称律)$a\leq_+b,\ b\leq_+a$なら、
$a+b=a=b$
(推移律)$a\leq_+b,\ b\leq_+c$なら、
$a+c=a+b+c=b+c=c$ $\square$
- $\leq_+$が全順序
- $\cdot$ が可換
- $\cdot$ が右分配的
について、(2)$\Rightarrow$(3)であって
発見されている例:
・(1)$\land$(2)$\land$(3)
・(1)$\land\ \lnot$(2)$\land$(3)
・$\lnot$(1)$\land$(2)$\land$(3)
・$\lnot$(1)$\land\ \lnot$(2)$\land\ \lnot$(3)存在性が未解決: 2/16 追記 存在性は肯定的に解決しました
・(1)$\land\ \lnot$(2)$\land\ \lnot$(3)
・$\lnot$(1)$\land\ \lnot$(2)$\land$(3)
テトリス代数は自明(元が唯一)または無限
自明でないとすると、$0$でない元$a$がとれる
$a^m=a^n\ (m< n)$とすると、$a^na^{m-n}=a^n0$より$a^{m-n}=0$
これは$a\ne 0$および$0$の既約性に反する$\square$
和付きと順序
テトリス代数$T$上の関係$\leq$を
$a\leq b\Leftrightarrow \exists x, b=ax$
と定めるとこれは半順序である。
特に、和付きテトリス代数$(T,+)$について、
$\leq$と$\leq_+$は等しく、$a+b=\sup\lbrace{a,b\rbrace}$である
（反射律）$a=a0$より$a\leq a$
（推移律）$a\leq b,b\leq c$のとき
ある$x,y$があって$b=ax, c=by$であるから、
$c=by=axy$ よって$a\leq c$
（反対称律） $a\leq b, b\leq a$のとき、
ある$x,y$があって$b=ax, a=by$であり、
$a=by=axy$ 左簡約性から$xy=0$
$0$の既約性から$x=0$ つまり$a=b$
和付きテトリス代数について、
$a+ax=a(0+x)=ax$であるから
$a\leq b\Leftrightarrow \exists x,ax=b$
$\Leftrightarrow \exists x,ax=a+b \land ax=b$
$\Leftrightarrow a+b=b \Leftrightarrow a\leq_+ b$
であるから, $\leq$と$\leq_+$は等しい.
定義から$a\leq_+ a+b, b\leq_+ a+b$であって、
$a\leq_+ c,b\leq_+ c$とすると、$a+c=b+c=c$
つまり、$a+b+c=a+c=c$ であるから $a+b\leq c$
よって$a+b=\sup\lbrace{a,b\rbrace}$
つまり、$T$が整除関係について上半束(任意の二元が最小上界を持つ順序)であることは、
ある和付きテトリス代数の乗法モノイドと一致することと同値(後述)であり、その和は一意である。
そこで以降は整除関係によって上半束であるテトリス代数を、単に「和付きテトリス代数」（もしくは上半テトリス代数）と呼ぶ。
また、単に$T$の順序といった場合、整除関係を表すことにする。
モノイド$(T,\cdot,0)$について、
これが和付きテトリス代数である必要十分条件は、
左簡約性をもち、整除関係によって上半束となることである。
必要性は明らか。
十分性について、
実際、$ab=0$とすると、$a\leq 0$であり、$a=a0$から$0\leq a$
よって$a=0$であるから$0$は既約
以下、$\sup$が和付きであることを示す
$\sup(a,a)=a$より冪等.
定義から$\sup(ab,ac)=abx=acy$であって$bx=cy$
つまり$a\sup(b,c)\leq abx= \sup(ab,ac)$
よって$\sup$の最小性から$\sup(ab,ac)=a\sup(b,c)$.
また、定義から$ax=\sup(a,b)$なる$x$は存在し、左簡約性から一意.
$\square$
モノイド$T$について
[1] 左簡約性
[2] $0$の既約性（$T\setminus\lbrace{0\rbrace}$の閉性）
[3] 整除関係が上半束
とすると、[1]$\land$[3]$\Rightarrow$[2]であり、
・[1]$\land$[2]$\Rightarrow$[3]
・[2]$\land$[3]$\Rightarrow$[1]
はそれぞれ反例が存在する。(次章で挙げる)
[1]のみ満たす例として、非自明群がある。
[2]$\Rightarrow$[1]の反例として有限半群のモノイド化がある
$\mathbb{N}$とテトリス
$F,G,P$と呼ばれる基本的なモノイドを定義する。（Pの演算はあとで導入する。）
$P=\mathcal{P}(\mathbb{N})$
$G=\lbrace{A\in P \mid \left| A^c \right|=\infty \rbrace}$
$F=\lbrace{A\in P \mid \left| A \right|<\infty \rbrace}$
とする。特に$F\subseteq G \subseteq P$である。
$A\in G$に対して、唯一の順序同型$\mathbb{N}\rightarrow A^c$を$\phi_A$と表し、
$G$上の演算$\cdot$を$\phi_{AB}=\phi_A \circ\phi_B$と定める
($\left|\phi_A\circ\phi_B(\mathbb{N})\right|=\left|\phi_A(\mathbb{N})\right|=\infty$)
補無限集合とテトリス代数
以降この節では、特に断りのない限り、文字は$G$の元とする
$AB=\phi_A(B)\cup A$(直和)であり、$(G,\cdot,\varnothing)$はテトリス代数
$\phi_{AB}(\mathbb{N})=(AB)^c$であり、
$\phi_A\circ\phi_B(\mathbb{N})=\phi_A(B^c)$
$=A^c\cap\phi_A(B)$ (全単射性より)
よって$AB=\phi_A(B)\cup A$.
特に$\phi_A(B)\subseteq A^c$より直和
$\phi_\varnothing={\rm id}$であり、単射写像の合成で定義されているので左簡約的なモノイド.
また、$\phi_A\circ\phi_B(\mathbb{N})=\mathbb{N}$のとき$\phi_A(\mathbb{N})=\mathbb{N}$であるから、$A=\varnothing$
よって、$(G,\cdot,\varnothing)$はテトリス代数$\square$
$F$は$G$の部分テトリス代数(部分モノイドかつテトリス)であり、
$F$は和付き、$G$は和付きでない。
$\left|A\right|,\left|B\right|\lt\infty$とすると
$\left|AB\right|=\left|\phi_A(B)\cup A\right|=\left|\phi_A(B)\right|+\left|A\right|=\left|A\right|+\left|B\right|<\infty$
よって$F$は積について閉じている。また、明らかに$\left|\varnothing\right|<\infty$
したがって、$F$は$G$の部分テトリス代数である。
ここで、$G$の整除関係が包含関係であること、
つまり$A\subseteq B \Leftrightarrow \exists X,B=AX$を示す。
$(\Rightarrow)$
$B\setminus A\subseteq A^c$だから$X=\phi_A^{-1}(B\setminus A)$とおけて、
$AX=\phi_A(X)\cup A=A\cup B$
$A\subseteq B$から$A\cup B=B$となる。
$(\Leftarrow)$
$B=AX=\phi_A(X)\cup A$より$A\subseteq B$
したがって、$F$は最小上界として和集合をもつので和付きであり、
$G$は最小上界を持たない二元(偶数全体と奇数全体など)があるため、和付きにならない。
$P$とカントール集合
以下、大文字は$P$の元、小文字は$\mathbb{N}$の元とする
$P$上の関数$v:P\to C$を
$$v(A)=\sum_{n\in A}\frac{2}{3^{n+1}}$$
で定義する. (ただし、$C$はカントール集合)
$v$は$\mathbb{N}$上の測度であり、全単射である。
以下、自然数$n$を$n$未満の自然数全体と同一視する.
まず、定義から明らかに$v(\varnothing)=0$である.
互いに空な集合列$\lbrace A_n\rbrace_{n\in\mathbb{N}}$とその和集合$A$について、
単調性から任意の$N$に対して次が成り立ち、正項級数であるから収束する
$$\sum_{n< N}v\left(A_n\right)=v\left(\bigcup_{n< N}A_n\right)\leq v(A)$$
また、$m\in\mathbb{N}$に対し$A\cap m$は有限だから、ある$N_m$があって
$$A\cap m\subseteq \bigcup_{n< N_m}A_n$$
$$\therefore v(A)=v(A\cap m)+v(A\setminus m)\leq v\left(\bigcup_{n< N_m}A_n\right)+\frac{1}{3^m}=\sum_{n< N_m}v\left(A_n\right)+\frac{1}{3^m}$$
よって$m\to\infty$で挟み撃ちの原理より完全加法性が言える
また、単射性は$m=A \triangle B$に対して$\left|v(A)-v(B)\right|\geq \frac{1}{3^m}$よりいえる$\square$
特にカントール集合がコンパクトであって、単調性および全単射性から$A_n$の集合論的収束と$v(A_n)$の収束は同値で、交換する.
その後の流れ
$\cdot:G\times G\to G$は$v$の誘導する距離について一様連続であり
よって$P$のコンパクト性および$G$の稠密性から、積は$P$上の一様連続な積に一意に拡張できる。
このとき$(P,\cdot,\varnothing)$はモノイドであり$\varnothing$が既約、上半束であることが示せるが、左簡約的ではない。実際、$\mathbb{N}\varnothing=\mathbb{N}\lbrace0\rbrace$が成立する。
