集合論の言葉による二項演算の表現

前々回は写像を集合論の言葉で定義し、使えるようにした。二項演算はこの写像として定義できるので、今回は二項演算を定義する。これによって、以前定義した自然数に足し算などの演算を与えることができる。

二項演算

二項演算とは、「2つのモノを与えると、モノがちょうど一つだけ返るようなモノ」である。例えばこれから定義する自然数の足し算は、2と3を与えると5が返り、5と1を与えると6が返る。このような言い回しにすると、ほとんど写像と同じであることがわかる。

写像と違うのは与えるモノが2つであるということだが、これは以前導入した順序対を使うことで一つにできる。つまり、上の「2と3を与えると5が返る」を「$\langle 2,3\rangle$ を与えると 5 が返る」と考えるのである。こうすると二項演算は「一つの順序対を与えると、モノがちょうど一つだけ返るようなモノ」となり、つまり直積集合からの写像ということになる。この考えを元に次のように二項演算を定義する。

定義$x$, $y$, $z$ を集合とし、$f:x\times y\to z$ とする。このとき、$f$ を二項演算とよぶ。記法の簡略化として $f(\langle a,b\rangle)$ のことを $f(a,b)$ とも書く。

とくに、$x=y=z$ であるとき、 $f$ を $x$ 上の二項演算とよぶ。

二項演算に対応する演算子を定めることができ、$\cdot$ が $f$ に対応する演算子であるとき、$f(a,b)$ のことを $a\cdot b$ と書く。

自然数の加法

具体例として、自然数の加法 (足し算) を集合論の言葉で定義していく。上の定義のとおり、写像として定義するのだが、写像は二項関係であるので二項関係として次のように定義する (注: 内包的記法を使ってもう少しスマートに定義する方法がないものかと悩んでおります)

定義$\omega$ 上の二項演算 $f$ を\[\{\langle \langle x,y\rangle, z \rangle \in (\omega\times\omega)\times\omega \mid \text{$(x\times\{\omega\})\cup(\{\omega\}\times y)$ から $z$ への全単射が存在する}\}\]と定める。この演算には演算子 $+$ を用いる。

以上の定義より、自然数 $x$, $y$, $z$ について $x+y=z$ であることは、$(x\times\{\omega\})\cup(\{\omega\}\times y)$ から $z$ への全単射が存在することである (注: この定義で二項関係 $f$ が写像になっていることの証明は省略し、ペアノの公理で再帰的に定義される加法に一致することの証明は後にする)

演算の具体例を見てみよう。たとえば $2+3$ について考えてみる。このとき、$(2\times\{\omega\})\cup(\{\omega\}\times 3)$ は\[\{\langle 0,\omega \rangle, \langle 1,\omega \rangle, \langle \omega,0 \rangle, \langle \omega,1 \rangle, \langle \omega,2 \rangle\}\]である。これとの全単射がある自然数と言えば\[\{0,1,2,3,4\}\]であり、つまり 5 である。よって $f(\langle 2,3\rangle)=5$ であり\[2+3=5\]ということになる。

自然数の乗法

続いて自然数の乗法も定義する。

定義$\omega$ 上の二項演算 $g$ を\[\{\langle \langle x,y\rangle, z \rangle \in (\omega\times\omega)\times\omega \mid \text{$x\times y$ から $z$ への全単射が存在する}\}\]と定める。この演算には演算子 $\cdot$ を用いる。また、紛らわしくない場合は $a\cdot b$ のことを省略して $ab$ と書いてもよいことにする。

以上の定義より、自然数 $x$, $y$, $z$ について $x\cdot y=z$ であることは、$x\times y$ から $z$ への全単射が存在することである (注: この定義で二項関係 $g$ が写像になっていることの証明は省略し、ペアノの公理で再帰的に定義される乗法に一致することの証明は後にする)

演算の具体例を見てみよう。たとえば $2\cdot3$ について考えてみる。このとき、$2\times 3$ は\[\{\langle 0,0 \rangle, \langle 1,0 \rangle, \langle 0,1 \rangle, \langle 1,1 \rangle, \langle 0,2 \rangle, \langle 1,2 \rangle\}\]である (注: $\times$ は自然数の掛け算ではなく直積集合の記号である)。これとの全単射がある自然数と言えば\[\{0,1,2,3,4,5\}\]であり、つまり 6 である。よって $g(\langle 2,3\rangle)=6$ であり\[2\cdot 3=6\]ということになる。

自然数の演算の性質

ここまでで自然数の加法と乗法を定義した。それらの性質について、ここでは証明は省略するが、自然数の演算に期待される以下のことが実際に成り立つ。

定理

  1. $a+0=0+a=a$
  2. $a+(\text{$b$の次の数})=\text{$(a+b)$の次の数}$
  3. $a\cdot 0 = 0\cdot a = 0$
  4. $a\cdot(\text{$b$の次の数})=ab+a$

(証明) 1 を示す。$\{\omega\}\times\emptyset=\emptyset$ であるので\[(a\times\{\omega\})\cup(\{\omega\}\times\emptyset)=a\times\{\omega\}=\{\langle x,\omega\rangle\mid x\in a\}\]であり、写像 $f:a\to (a\times\{\omega\})\cup(\emptyset\times\{\omega\})$ を\[x\mapsto\langle x,\omega\rangle\]で定めると $f$ は全単射である。よって $a+0=a$。同様に $0+a=a$。

2 を $b$ についての数学的帰納法で示す。写像 $g_0: a\cup\{a\}\to(a\times\{\omega\})\cup(\{\omega\}\times\{0\})$ を\[g_0:x\mapsto\left\{\begin{array}{ll} \langle x,\omega\rangle & \text{if $x\in a$} \\ \langle \omega, 0\rangle  & \text{otherwise} \end{array}\right.\]と定めると $g_0$ は全単射であるので $\text{$(a+0)$の次の数}=a+(\text{$0$の次の数})$。

固定された $b$ について $a+(\text{$b$の次の数})=\text{$(a+b)$の次の数}$ とすると、全単射 $g:(a+b)\cup\{a+b\}\to(a\times\{\omega\})\cup(\{\omega\}\times (b\cup\{b\}))$ が存在する。また、この仮定より\[\text{$(a+(b$の次の数$))$の次の数}=\text{$(a+b)$の次の数の次の数}\]である。ここで $g':(a+b)\cup\{a+b\}\cup\{(a+b)\cup\{a+b\}\}$ $\to (a\times\{\omega\})\cup(\{\omega\}\times (b\cup\{b\}\cup\{b\cup\{b\}\}))$ を\[g':x\mapsto\left\{\begin{array}{ll} g(x) & \text{if $x\in (a+b)\cup\{a+b\}$} \\ \langle \omega, b\cup\{b\}\rangle  & \text{otherwise} \end{array}\right.\]と定めると $g'$ は全単射であるので\[\text{$(a+b)$の次の数の次の数}=a+(\text{$b$の次の数の次の数})\]である。よって\[\text{$(a+(b$の次の数$))$の次の数}=a+(\text{$b$の次の数の次の数})\]であり、2 が示せた。

3 を示す。$a\times 0=0\times a=\emptyset$ であるから $a\cdot 0=0\cdot a=0$。

4 を $b$ についての数学的帰納法で示す。1 と 3 より $a\cdot 0+a=a$。一方で\[a\to a\times\{0\}; x\mapsto\langle x,0\rangle\]は全単射だから $a=a\cdot(\text{$0$の次の数})$。したがって $a\cdot(\text{$0$の次の数})=a\cdot 0+a$。

固定された $b$ について $a\cdot(\text{$b$の次の数})=ab+a$ とすると、全単射 $h:(ab+a)\to a\times(b\cup\{b\})$ が存在する。また、この仮定より\[a\cdot(\text{$b$の次の数})+a=(ab+a)+a\]である。ここで $h': ((ab+a)\times\{\omega\})\cup(\{\omega\}\times a)\to a\times(b\cup\{b\}\cup\{b\cup\{b\}\})$ を\[h':x\mapsto\left\{\begin{array}{ll} h(y) & \text{if $x=\langle y,\omega\rangle$} \\ \langle y, b\cup\{b\}\rangle & \text{if $x=\langle \omega,y\rangle$}\end{array}\right.\]と定めると $h'$ は全単射であるので\[(ab+a)+a=a\cdot(\text{$b$の次の数の次の数})\]である。よって\[a\cdot(\text{$b$の次の数})+a=a\cdot(\text{$b$の次の数の次の数})\]であり、4が示せた。

いま確認した性質は、自然数の論理として知られるペアノ算術などで加法と乗法の定義として採用されている性質で、これらを満たすことから、ここで定義した加法と乗法はペアノ算術のそれと一致するといえる。そのため、ペアノ算術の結論として、ここでは証明しないが以下の結論を得ることができる。

  • $a\cdot 1=1\cdot a=a$
  • 結合的であり、つまり $(a+b)+c=a+(b+c)$, $(ab)c=a(bc)$
  • 可換であり、つまり $a+b=b+a$, $ab=ba$
  • 乗法は加法に分配し、つまり $a(b+c)=ab+ac$, $(a+b)c=ac+bc$
  • 加法は単射的であり、つまり $a+c=b+c$ ならば $a=b$
  • 乗法は単射的であり、つまり $ac=bc$, $c\neq 0$ ならば $a=b$

集合の直和

二項演算に直接かかわるものではないが、今回直和を利用したのでそれについて述べておく。2つの集合の直積は以前定義したとおりだが、2つの集合の直和というものもある。$x$ と $y$ の直和とは、直積と直積の和集合として\[(x\times\{\ast\})\cup(\{\ast\}\times y)\]と表すことができる。この $\ast$ は $x\cap y$ に属さないモノなら何でもよい。今回の記事では加法の定義のために $\ast$ を $\omega$ としてこの直和を利用している。

通常の和集合 $x\cup y$ との違いは、$x$ に属するモノと $y$ に属するモノを異なるモノとして区別できる点にある。たとえば $x=\{0,1\}$, $y=\{1,2\}$ とすると、$x$ に属する 1 と $y$ に属する 1 は同じモノなので、和集合をつくると\[x\cup y=\{0,1,2\}\]となり、2つの1は同一視される。一方で、直和については $\ast\not\in x\cap y$ より $\langle 1,\ast\rangle$ と $\langle \ast, 1\rangle$ は異なるモノなので、直和を作ると\[(x\times\{\ast\})\cup(\{\ast\}\times y)=\{\langle 0,\ast\rangle,\langle 1,\ast\rangle,\langle \ast,1\rangle,\langle \ast,2\rangle\}\]となり、$x$ に属する 1 と $y$ に属する 1 を異なるモノとして扱うことができる。

異なるモノなので、写像 $h$ を作る際に $h(\langle 1,\ast\rangle)$ と $h(\langle \ast, 1\rangle)$ は異なるモノとして定義することができ、これが加法の定義で「全単射が存在する」としている部分に効いてくる。もし直和でなく単に和集合を使うと\[2\cup3=\{0,1,2\}\]との全単射が存在するのは\[3=\{0,1,2\}\]なので\[2+3=3\]ということになってしまう。