インテジャーズ

インテジャーズ

数、特に整数に関する記事。

butchi氏の準加算について

日曜数学者のbutchi氏が準加算なるものを考察していらっしゃるため、ここにまとめを作っておきます。議論の場となれば幸いです。

注意 当ブログでは基本的に自然数といえば正の整数を意味していますが、この記事においては0以上の整数を自然数とよぶことにし、自然数全体のなす集合を\mathbb{N}で表します。\mathbb{N}に関するPeano算術は仮定します。

Motivation n, mを正の整数とするとき、
\underbrace{n+\cdots +n}_{m} = n \times m
\underbrace{n\times \cdots \times n}_{m} = n^m
が成り立つ。n \uparrow m := n^mとして、
\underbrace{n\uparrow \cdots \uparrow n}_{m} = n \uparrow \! \uparrow m
\underbrace{n\uparrow \! \uparrow \cdots \uparrow \! \uparrow n}_{m} = n \uparrow \! \uparrow \! \uparrow m
とどんどん新しい演算を定義できる(Knuthの記号*1)。

それでは、逆方向に向かって

\underbrace{n\oplus \cdots \oplus n}_{m} = n + m -①
を満たすような\oplusを考えることができるであろうか?

この\oplusのことをbutchi氏は準加算と呼んでます。以下、準加算の暫定的な定義を与え、その基本性質を列挙しましょう。

Knuthの記号のときと違って、①だけでは\mathbb{N}上の二項演算は即座には定まらない点が難しい点です。ここでは、交換法則と分配法則が成り立つような定義を試みています。

命題1 次の条件を満たすような写像f\colon \mathbb{N} \times \mathbb{N} \to \mathbb{N}が一意的に存在する。

  1. f(0, 0) = 2
  2. f(0, n)=f(0, n)  = n+1 (n \geq 1)
  3. f(n+1, m+1) = f(n, m)+1 (\forall n, m \in \mathbb{N})

証明. fの定義が二重帰納的に定まる定義になっているため、一意性も存在性も明らかである(Peano算術は既知であることに注意)。 Q.E.D.

定義1 n, m \in \mathbb{N}に対し、n \oplus m
n \oplus m := f(n, m)
により定める。

命題2(交換法則) 任意のn, m \in \mathbb{N}に対してn\oplus m=m \oplus nが成り立つ。

証明. fの定義によりf(n, m)=f(m, n). Q.E.D.

命題3(分配法則) 任意の自然数n, m, l \in \mathbb{N}に対して、
(n\oplus m)+l = (n+ l) \oplus (m+l)
が成り立つ。

証明. lに関する帰納法で証明する。l=0のときは明らか。lで成立すると仮定すると、

\begin{equation}\begin{split} (n\oplus m)+(l+1) &= ((n\oplus m)+l)+1 \\ &= ( (n+l)\oplus (m+l) )+1  \ (\text{帰納法の仮定}) \\ &= ( (n+l)+1)\oplus ( (m+l)+1)  \ (f\text{の定義}) \\ &= (n+(l+1) )\oplus (m+(l+1) )\end{split}\end{equation}

l+1のときも成立することがわかった。 Q.E.D.

実は、準加算は簡単にexplicitに計算できます:

命題4(準加算の明示公式) 任意のn, m \in \mathbb{N}に対して
\displaystyle n\oplus m = \begin{cases}n+1 & (n>m) \\ n+2 & (n=m) \\ m+1 & (n < m) \end{cases}
が成り立つ。

証明. n > mのとき。n=m+kなる正の整数kが一意に存在する。このとき、分配法則より

\begin{equation}\begin{split}n\oplus m &= (m+k)\oplus m \\ &= (k\oplus 0) +m \\ &= k+1+m \\ &= n+1\end{split}\end{equation}

を得る。n < mのときも同様(あるいは交換法則からわかる)。

n=mのとき、分配法則より

n\oplus n = (0\oplus 0) + n = 2+n = n+2.

Q.E.D.

n\oplus n = n\oplus (n+1) = (n+1) \oplus nが成り立ちます(加法のときとは異なり、f(n, m)のどちらかの成分を固定して得られる写像は単射ではない)。

また、上記命題4を用いれば\oplusを実数体上定義される演算に拡張できます(交換法則と分配法則はそのまま成り立つ)。

命題5 結合法則は成り立たない。

証明. 1\oplus (1\oplus 0) = 1 \oplus 2 = 3であるが、(1\oplus 1)\oplus 0 = 3 \oplus 0 = 4である。 Q.E.D.

欲しかったのは次の性質です:

定義2 nを自然数、m2以上の整数とする。このとき、\underbrace{n\oplus \cdots \oplus n}_m
\underbrace{n\oplus \cdots \oplus n}_{m+1}:=n\oplus (\underbrace{n\oplus \cdots \oplus n}_m)
と帰納的に定義する。

命題6 nを自然数、m2以上の整数とする。このとき、
\underbrace{n\oplus \cdots \oplus n}_{m} = n+m
が成り立つ。

証明. mに関する帰納法で証明する。m=2のときは命題5で既に示している。mで正しいと仮定すると、

\begin{equation}\begin{split}\underbrace{n\oplus \cdots \oplus n}_{m+1}&=n\oplus (\underbrace{n\oplus \cdots \oplus n}_m) \\ &= n\oplus  (n+m) \\ &= n+m+1 \ (\text{命題5より}) \end{split}\end{equation}

m+1のときも成り立つことがわかる。 Q.E.D.

系(準加算の双対性) n, m2以上の整数とする。このとき、
\underbrace{n\oplus \cdots \oplus n}_m = \underbrace{m \oplus \cdots \oplus m}_n
が成り立つ。

以下の命題は安直には準準加算のようなものは考えられないことを示しています:

命題7 任意の整数kに対して、二項演算
\oplus^2 \colon \mathbb{Z}_{\geq k} \times \mathbb{Z}_{\geq k} \longrightarrow \mathbb{Z}
であって、
\underbrace{n\oplus^2 \cdots \oplus^2 n}_m = n \oplus m -②
が任意の\mathbb{Z}_{\geq k}の元n, m(ただし、m \geq 2)に対して成り立つようなものは存在しない。ここで、\underbrace{n\oplus^2 \cdots \oplus^2 n}_mは定義2と同様に定義されるものとする。

証明. そのような\oplus^2が存在したと仮定する。k \geq 2としてよい。②より

\underbrace{k \oplus^2 \cdots \oplus^2 k}_k = k \oplus k = k+2 -③.

③より

\underbrace{k \oplus^2 \cdots \oplus^2 k}_{k+1} = k \oplus^2 (k+2) -④.

一方、②より

\underbrace{k \oplus^2 \cdots \oplus^2 k}_{k+1} = k \oplus (k+1) = k+2 -⑤.

④、⑤より

k \oplus^2 (k+2)  = k+2 -⑥

が成り立つ。⑤より

\underbrace{k \oplus^2 \cdots \oplus^2 k}_{k+2} = k \oplus^2 (k+2) -⑦.

一方、②より

\underbrace{k \oplus^2 \cdots \oplus^2 k}_{k+2} = k \oplus (k+2) = k+3 -⑧.

⑦、⑧より

k \oplus^2 (k+2)  = k+3 -⑨

を得る。⑥、⑨より

k+2=k+3

となるが、これは矛盾である。 Q.E.D.

*1:Knuthの記号は結合法則を満たさないことに注意。