帰納法の表示方法
式の間の関係
M を2項演算 + が定義されている集合で、任意の M の元 x、y に対して
x + (y + 1) = (x + y) + 1
が成り立つような M の元 1 が存在するとします。
(x + y) + z を x + y + z と書くことにします。
N を 1 + 1 + … という形の元全体からなる集合とします。
このとき、N の元に対して次のような関係が成り立ちます。
(x + 1) + y = x + (y + 1)
(証明)
A + B = X + Y
という関係が成り立っているとすると、
(A + B) + 1 = (X + Y) + 1
となります。したがって
A + (B + 1) = X + (Y + 1)
が成り立ちます。
これを繰り返していくと、
次の第1の関係から第2の関係、
第2の関係から第3の関係、…を導くことができます。
(x + 1) + 1 = x + (1 + 1)
(x + 1) + 2 = (x + 1) + (1 + 1) = ((x + 1) + 1) + 1 = (x + (1 + 1)) + 1 = (x + 2) + 1 = x + (2 + 1)
(x + 1) + 3 = (x + 1) + (2 + 1) = ((x + 1) + 2) + 1 = (x + (2 + 1)) + 1 = (x + 3) + 1 = x + (3 + 1)
……
……
よって (x + 1) + y = x + (y + 1) が成り立ちます。
同様に、以下の関係が成り立ちます。
x + 1 = 1 + x
(証明)
1 + 1 = 1 + 1
2 + 1 = (1 + 1) + 1 = 1 + (1 + 1) = 1 + 2
3 + 1 = (2 + 1) + 1 = (1 + 2) + 1 = 1 + (2 + 1) = 1 + 3
……
……
加法の交換法則: x + y = y + x
(証明)
x + 1 = 1 + x
x + 2 = x + (1 + 1) = (x + 1) + 1 = (1 + x) + 1 = 1 + (x + 1) = (1 + 1) + x = 2 + x
x + 3 = x + (2 + 1) = (x + 2) + 1 = (2 + x) + 1 = 2 + (x + 1) = (2 + 1) + x = 3 + x
……
……
加法の結合法則: (x + y) + z = x + (y + z)
(証明)
(x + y) + 1 = x + (y + 1)
(x + y) + 2 = (x + y) + (1 + 1) = ((x + y) + 1) + 1 = (x + (y + 1)) + 1 = x + ((y + 1) + 1) = x + (y + (1 + 1)) = x + (y + 2)
(x + y) + 3 = (x + y) + (2 + 1) = ((x + y) + 2) + 1 = (x + (y + 2)) + 1 = x + ((y + 2) + 1) = x + (y + (2 + 1)) = x + (y + 3)
……
……
さらに M に2項演算 + が定義されていて、任意の M の元 x、y に対して
x * 1 = x
x * (y + 1) = (x * y) + x
が成り立つとします。
このとき、N の元に対して次のような関係が成り立ちます。
1 * x = x
(証明)
1 * 1 = 1
1 * 2 = 1 * (1 + 1) = (1 * 1) + 1 = 1 + 1 = 2
1 * 3 = 1 * (2 + 1) = (1 * 2) + 1 = 2 + 1 = 3
……
……
(x + 1) * y = (x * y) + y
(証明)
(x + 1) * 1 = x + 1 = (x * 1) + 1
(x + 1) * 2 = (x + 1) * (1 + 1) = ((x + 1) * 1) + (x + 1) = ((x * 1) + 1) + (x + 1) = ((x * 1) + x) + (1 + 1) = (x * (1 + 1)) + (1 + 1) = (x * 2) + 2
(x + 1) * 3 = (x + 1) * (2 + 1) = ((x + 1) * 2) + (x + 1) = ((x * 2) + 2) + (x + 1) = ((x * 2) + x) + (2 + 1) = (x * (2 + 1)) + (2 + 1) = (x * 3) + 3
……
……
分配法則1: x * (y + z) = (x * y) + (x * z)
(証明)
x * (y + 1) = (x * y) + x = (x * y) + (x * 1)
x * (y + 2) = x * (y + (1 + 1)) = x * ((y + 1) + 1) = (x * (y + 1)) + x = ((x * y) + (x * 1)) + x = (x * y) + ((x * 1) + x) = (x * y) + (x * (1 + 1)) = (x * y) + (x * 2)
x * (y + 3) = x * (y + (2 + 1)) = x * ((y + 2) + 1) = (x * (y + 2)) + x = ((x * y) + (x * 2)) + x = (x * y) + ((x * 2) + x) = (x * y) + (x * (2 + 1)) = (x * y) + (x * 3)
……
……
分配法則2: (x + y) * z = (x * z) + (y * z)
(証明)
(x + y) * 1 = x + y = (x * 1) + (y * 1)
(x + y) * 2 = (x + y) * (1 + 1) = ((x + y) * 1) + (x + y) = ((x * 1) + (y * 1)) + (x + y) = ((x * 1) + x) + ((y * 1) + y) = (x * (1 + 1)) + (y * (1 + 1)) = (x * 2) + (y * 2)
(x + y) * 3 = (x + y) * (2 + 1) = ((x + y) * 2) + (x + y) = ((x * 2) + (y * 2)) + (x + y) = ((x * 2) + x) + ((y * 2) + y) = (x * (2 + 1)) + (y * (2 + 1)) = (x * 3) + (y * 3)
……
……
x * 1 = 1 * x
(証明)
1 * 1 = 1 * 1
1 * 2 = 1 * (1 + 1) = (1 * 1) + 1 = 1 + 1 = 2
1 * 3 = 1 * (2 + 1) = (1 * 2) + 1 = 2 + 1 = 3
……
……
乗法の交換法則: x * y = y * x
(証明)
x * 1 = 1 * x
x * 2 = x * (1 + 1) = (x * 1) + x = (1 * x) + x = (1 + 1) * x = 2 * x
x * 3 = x * (2 + 1) = (x * 2) + x = (2 * x) + x = (2 + 1) * x = 3 * x
……
……
乗法の結合法則: (x * y) * z = x * (y * z)
(証明)
(x * y) * 1 = x * y = x * (y * 1)
(x * y) * 2 = (x * y) * (2 + 1) = ((x * y) * 2) + (x * y) = (x * (y * 2)) + (x * y) = (x * (y * 2)) + (x * y) = x * ((y * 2) + y) = x * (y * (2 + 1)) = x * (y * 2)
(x * y) * 3 = (x * y) * (3 + 1) = ((x * y) * 3) + (x * y) = (x * (y * 3)) + (x * y) = (x * (y * 3)) + (x * y) = x * ((y * 3) + y) = x * (y * (3 + 1)) = x * (y * 3)
……
……
証明の表示方法
この章では、前の章で行った証明を見やすく記述することを考えていきます。
[仮定] x + (y + 1) = (x + y) + 1
(x + 1) + y = x + (y + 1)
(証明)
(x + 1) + (1 + 1 + … + 1 + 1) に[仮定]を適用すると、
((x + 1) + (1 + 1 + … + 1)) + 1 となります。
さらに繰り返し[仮定]を適用すると、
(x + 1) + 1 + 1 + … + 1 + 1 となります。
これに[仮定]を適用すると、
(x + (1 + 1)) + 1 + … + 1 + 1 となります。
さらに繰り返し[仮定]を適用すると、
x + ((1 + 1 + 1 + … + 1) + 1) となります。
これをまとめると、
| | (x + 1) + (1 + 1 + … + 1 + 1) |
| = | ((x + 1) + (1 + 1 + … + 1)) + 1 |
| | …… |
| = | (x + 1) + 1 + 1 + … + 1 + 1 |
| = | (x + (1 + 1)) + 1 + … + 1 + 1 |
| | …… |
| = | x + ((1 + 1 + … + 1 + 1) + 1) |
となります。
同様に以下の関係が成り立ちます。
x + 1 = 1 + x
(証明)
(1 + … + 1) + 1 = 1 + (1 + … + 1)
加法の交換法則: x + y = y + x
(証明)
x + (1 + … + 1) = (1 + … + 1) + x
加法の結合法則: (x + y) + z = x + (y + z)
(証明)
(x + y) + (1 + … + 1) = x + (y + (1 + … + 1))
仮定: x * 1 = x
x * (y + 1) = (x * y) + x
1 * x = x
(証明)
1 * (1 + … + 1) = (1 * 1) + … + (1 * 1) = 1 + … + 1
(x + 1) * y = (x * y) + y
(証明)
(x + 1) * (1 + … + 1) = ((x + 1) * 1) + … + ((x + 1) * 1)
= (x + 1) + … + (x + 1) = (x + … + x) + (1 + … + 1) = (x * (1 + … + 1)) + (1 + … + 1)
分配法則1: x * (y + z) = (x * y) + (x * z)
(証明)
x * ((1 + … + 1) + (1 + … + 1)) = x * ((1 + … + 1 + 1 + … + 1))
= (x * 1) + … + (x * 1) + (x * 1) + … + (x * 1) = (x * (1 + … + 1)) + (x * (1 + … + 1))
分配法則2: (x + y) * z = (x * z) + (y * z)
(証明)
((1 + … + 1) + (1 + … + 1)) * z = ((1 + … + 1 + 1 + … + 1)) * z
= (1 * z) + … + (1 * z) + (1 * z) + … + (1 * z) = ((1 + … + 1) * z) + ((1 + … + 1) * z)
x * 1 = 1 * x
(証明)
(1 + … + 1) * 1 = (1 * 1) + … + (1 * 1) = 1 * (1 + … + 1)
乗法の交換法則: x * y = y * x
(証明)
x * (1 + … + 1) = (x * 1) + … + (x * 1) = x + … + x
乗法の結合法則: (x * y) * z = x * (y * z)
(証明)
(x * y) * (1 + … + 1) = ((x * y) * 1) + … + ((x * y) * 1) = (x * y) + … + (x * y)
帰納法を含む等式
この章では、集合 N を、
- N の元 x に対して x' を対応させる写像をもち
- N の元 0 が存在して
- N = {0, 0', 0'', …}
となるものとします。
さらに、N は2項演算 + をもち
x + 0 = x
x + y' = (x + y)'
が成り立っているとします。
ここで、x + y' = (x + y)' の両辺を見ると、
「'」がついている以外は同じ形になっています。
このとき、x + y^ = (x + y)^ と書くことにします。
([意味] x に 「'」が n 個ついていることを、便宜上 x(n)
と書くことにすると、x + y^ = (x + y)^ の意味は、
「任意の自然数 n に対して x + y(n) = (x + y)(n)
となる」ということなります)
さらに、この記法に関して
x^' = x'^
が成り立っているとします。
このとき、N の元に対して次のような関係が成り立ちます。
0 + x = x
(証明)
0 + 0^ = (0 + 0)^ = 0^
x + y' = x' + y → x + y^ = x^ + y
(証明)
x + 0^' = (x + 0^)' = (x + 0)^' = x^' = x'^ = (x' + 0)^ = x' + 0^
加法の交換法則: x + y = y + x
(証明)
x + 0^ = (x + 0)^ = x^ = 0 + x^ = 0^ + x
加法の結合法則: (x + y) + z = x + (y + z)
(証明)
(x + y) + 0^ = ((x + y) + 0)^ = (x + y)^ = x + y^ = x + (y + 0)^ = x + (y + 0^)
さらに、N は2項演算 + をもち
x * 0 = 0
x * y' = (x * y) + x
が成り立っているとします。
このとき、N の元に対して次のような関係が成り立ちます。
0 * x = 0
(証明)
0 * x' = (0 * x) + 0 = 0 * x → 0 * x^ = 0 * x
0 * 0^ = 0 * 0 = 0
x * 0' = x
(証明)
x * 0' = (x * 0) + x = 0 + x = x
0' * x = x
(証明)
0' * x' = (0' * x) + 0' = ((0' * x) + 0)' = (0' * x)' → 0' * x^ = (0' * x)^
0' * 0^ = (0' * 0)^ = 0^
分配法則1: x * (y + z) = (x * y) + (x * z)
(証明)
(x * y') + (x * z) = (x * y) + x + (x * z) = (x * y) + (x * z')
→ (x * y^) + (x * z) = (x * y) + (x * z^)
x * (y + 0^) = x * (y + 0)^ = x * y^ = (x * y^) + (x * 0) = (x * y) + (x * 0^)
分配法則2: (x + y) * z = (x * z) + (y * z)
(証明)
(x + y) * z' + (x * w) + (y * w) = (x + y) * z + (x + y) + (x * w) + (y * w)
= (x + y) * z + (x * w') + (y * w')
→ (x + y) * z^ + (x * w) + (y * w) = (x + y) * z + (x * w^) + (y * w^)
(x + y) * 0^ = (x * 0^) + (y * 0^)
x' * y = (x * y) + y
(証明)
(x' * y') + (x * z) + z
= (x' * y) + x' + (x * z) + z
= (x' * y) + ((x * z) + x) + z'
= (x' * y) + (x * z') + z'
→ (x' * y^) + (x * z) + z = (x' * y) + (x * z^) + z^
x' * 0^ = (x * 0^) + 0^
乗法の交換法則: x * y = y * x
(証明)
(x * y') + (z * x)
= (x * y) + x + (z * x)
= (x * y) + (z' * x)
x * 0^ = 0^ * x
乗法の結合法則: (x * y) * z = x * (y * z)
(証明)
((x * y) * z') + (x * (y * w))
= ((x * y) * z) + (x + y) + (x * (y * w))
= ((x * y) * z) + (x * (y + (y * w)))
= ((x * y) * z) + (x * (y * w'))
→ ((x * y) * z^) + (x * (y * w)) = ((x * y) * z) + (x * (y * w^))
((x * y) * 0^) = (x * (y * 0^))