可換モノイド論/自然数
\(\newcommand{\ker}{\mathrm{ker}} \newcommand{\im}{\mathrm{im}} \newcommand{\nat}{\mathbb{N}} \) この記事においては、モノイドの最も基本的な例である自然数 $\mathbb{N}$ について導入し、また自然数上の合同関係について調べることでモノイドのいくつかの具体的な例を構成する。
$\mathbb{N}$
定義 1 (自然数のなすモノイド $\nat$)
自然数全体の集合に加法により演算を定めたものを $\nat$ と表記する。これはモノイドとなる。
$\mathbb{N}$ からの射
補題 2 (自然数モノイドの自由性)
モノイド $M$ において、次の対応 $f\colon \mathrm{Hom}_\mathsf{Mon}(\nat,M)\to \mathrm{Hom}_\mathsf{Set}(\{pt\},M)$ は全単射である。
- $g\colon \nat \to M$ について、$f(g)(pt)=g(1)$
証明
任意の写像 $h\colon \{pt\}\to M$ について、次のようにモノイドの射 $h'\colon \mathbb{N}\to M$ を定めることができる。
- $n \in \mathbb{N}$ について、$h'(n)=nh(pt)$
このとき、$f(h')=h$ が成り立つため、$f$ は全射である。
モノイドの射 $g,g'\colon \mathbb{N}\to M$ について、$g(1)=g'(1)$ であるならば、$g(n)=ng(1)=ng'(1)=g'(n)$ より、$g=g'$ が成り立つ。よって $f$ は単射である。□観察 3 (元と射の同一視)
モノイド $M$ について、補題 2に示した対応により $M$ の元からモノイドの射 $\nat \to M$ を構成することができる。この方法によって $\nat$ からモノイドへの射とモノイドの元とを同一視することがある。
$\mathbb{N}$ 上の合同関係
記法 4 ($\mathrm{Rel}(m=n)$)
$m\lt n \in \nat$ について、$\mathrm{Rel}(m=n)$ とは、以下のように定める $\nat$ 上の関係のことである。
- $a,b \in \nat$ について、$(a,b) \in \mathrm{Rel}(m=n)$ であることは、$a \lt b$ かつ $m\leq a$ かつ $n-m|b-a$ が成り立つか、$a=b$ が成り立つか、$b \lt a$ かつ $m \leq b$ かつ $n-m|a-b$ が成り立つことと同値
補題 5 ($\mathrm{Rel}(m=n)$ の合同関係性)
$m\lt n \in \nat$ について、$\mathrm{Rel}(m=n)$ は合同関係である。
証明
任意の $a,b \in \nat$ について $(a,a) \in \mathrm{Rel}(m=n)$ が成り立ち、また $(a,b) \in \mathrm{Rel}(m=n)$ ならば $(b,a) \in \mathrm{Rel}(m=n)$ であることは明らかである。
$a,b,c \in \nat$ について、$(a,b) \in \mathrm{Rel}(m=n)$ かつ $(b,c) \in \mathrm{Rel}(m=n)$ であったとする。このとき、$b=c$ の場合は明らかに $(a,c) \in \mathrm{Rel}(m=n)$ が成り立つ。$b\lt c$ かつ $a\lt b$ である場合について、$a\lt c$ でありかつ $m \leq a$ かつ $n-m|c-a$ が成り立つため、$(a,c) \in \mathrm{Rel}(m=n)$ が成り立つ。$b\lt c$ かつ $b\lt a$ である場合について、$m\leq b \lt a$ かつ $m\leq b\lt c$ であるため、$a$ と $c$ の大小関係に関わらず $(a,c) \in\mathrm{Rel}(m=n)$ が成り立つ。$c\lt b$ の場合についても同様の議論を行うことで推移律については示される。
$(a,b) \in \mathrm{Rel}(m=n)$ なる $a,b \in \nat$ と任意の自然数 $c$ について $(a+c,b+c) \in \mathrm{Rel}(m=n)$ であることを示す。$a=b$ の場合については明らか。$a\lt b$ の場合について、$a+c\lt b+c$ かつ $m \leq a+c$ かつ $n-m|(b+c)-(a+c)$ より $(a+c,b+c) \in \mathrm{Rel}(m=n)$ が成り立つ。$b\lt a$ の場合についても同様である。□定義 6 ($M(r,d)$)
自然数 $r$ と自然数 $1\leq d$ について、$M(r,d)$ とは合同関係 $\mathrm{Rel}(r=r+d)$ についての $\nat$ の商モノイドのことを指していう。
命題 7 ($\nat$ 上の合同関係)
$\nat$ 上の合同関係 $R$ は $\{(n,n) \in \nat^2|n \in \nat\}$ もしくはある自然数 $m \lt n$ について $\mathrm{Rel}(m=n)$ と一致する。
証明
$\nat$ 上の合同関係 $R$ を任意に取る。$R\neq\{(n,n) \in \nat^2|n \in \nat\}$ であるとする。このとき、$m \lt n$ なる $(m,n) \in R$ であって辞書式順序において最小のものを取る。このとき、$R=\mathrm{Rel}(m=n)$ なることを示す。
$\mathrm{Rel}(m=n)\subset R$ については明らかである。逆に $(m',n') \in R$ であるとする。$m'=n'$ の場合は $(m',n') \in \mathrm{Rel}(m=n)$ である。$m' \lt n'$ の場合は、$(m,n)$ の取り方より $m\leq m'$ が従う。$m'+a\cong m\ (\mathrm{mod}\ n-m)$ が成り立つような自然数 $a$ について、$(m'+a,n'+a) \in R$ であり、かつ $(m,m'+a) \in R$ が成り立つため、$m,n'+a$ が成り立つ。ここで、$n'-m'$ が $n-m$ の倍数でなければ、$m \lt n' ' \lt n$ であって $(n' ',n'+a)\in R$ なるものが存在する。よって $(m,n' ')\in R$ が成り立つため、$(m,n)$ の取り方に反し、矛盾する。従って $n'-m'$ は $n-m$ の倍数であるため $(m',n') \in \mathrm{Rel}(m=n)$ がなりたつ。$n' \lt m'$ の場合についても同様の議論により $(m',n') \in \mathrm{Rel}(m=n)$ が示されるため、$R\subset \mathrm{Rel}(m=n)$ が成り立つ。よって $R=\mathrm{Rel}(m=n)$ が成り立つ。 □単元生成モノイド
定義 8 (単元生成モノイド)
モノイド $M$ が単元生成であるとは、ある $m \in M$ によって $M$ が生成されることをいう。
補題 9 ($\nat$ からの全射)
モノイド $M$ が単元生成であることは、$\nat$ からのモノイドの全射が存在することと同値である。
証明
モノイド $M$ が単元生成であるとき、$m \in M$ であって $M$ を生成するものが存在する。このとき、$\nat\to M$ として $1$ を $m$ に充てる射を取れば、これは全射である。逆に $f\colon \nat\to M$ なる全射が存在するとき、$M$ は $f(1)$ で生成される。□
定理 10 (単元生成モノイドの分類)
単元生成モノイドはある自然数 $r$ と自然数 $1\leq d$ について $M(r,d)$ と同型であるか、もしくは $\nat$ と同型である。
information
情報源
- P. A. Grillet. "Commutative Semigroups". Springer, Netherlands (2001).
