Как доказать что m * n = n * m ?

Возьмём систему аксиом Пеано для натуральных чисел: 0 принадлежит N и для любого x из N, S(x) тоже принадлежит N, где N — множество натуральных чисел, а S(x) — x + 1.

Сложение и умножение для таких чисел определено следующим образом:

• Сложение: x + 0 = x; x + S(y) = S(x + y)
• Умножение: x * 0 = 0; x * S(y) = x * y + x

[Лемма 1] Из этих аксиом выведем что для любого целого n, n * 0 = 0 * n = 0 (частный случай коммутативности умножения). Доказывать будем по индукции, где предположение P(n): n * 0 = 0 * n = 0, базис индукции — P(0) (очевидно из определения умножения), а шаг индукции — если P(n) истинно, то S(n) * 0 = 0, 0 * S(n) = 0 * n + 0 = 0, таким образом P(S(n)) тоже истинно, лемма доказана.

[Лемма 2] Докажем что для любого целого n, n + 0 = 0 + n = n (частный случай коммутативности сложения). Предположение P(n): n + 0 = 0 + n = 0; базис P(0): 0 + 0 = 0 + 0 = 0 (очевидно); шаг индукции — если n + 0 = 0 + n, то доказать что S(n) + 0 = 0 + S(n):

1. S(n) + 0 = S(n);
2. 0 + S(n) = S(0 + n) = S(n) (из P(n)), что и требовалось доказать.

[Лемма 3] Докажем что для любых целых n и m, S(n) + m = S(n + m). Пусть предположение P(n): для любого целого m, S(m) + n = S(m + n). Базис индукции — P(0): для любого целого m, S(m) + 0 = S(m + 0). S(m) + 0 = S(m) по определению сложения; S(m + 0) = S(m), опять-таки по определению сложения. Переходим к шагу индукции: если доказано P(n), докажем P(S(n)): S(m) + S(n) = S(m + S(n)).

1. S(m) + S(n) + S(S(m) + n) = S(S(m + n)) (по предположению индукции);
2. S(m + S(n)) = S(S(m + n)) (по определению сложения), что и требовалось доказать.

[Лемма 4] Докажем коммутативность сложения: для любых целых n и m, n + m = m + n. Предположение P(n): для любого целого m, n + m = m + n. Базис индукции — P(0): для любого целого m, 0 + m = m + 0, что было доказано в лемме 2. Теперь переходим к шагу индукции — докажем что если выполняется P(n), то P(S(n)) также выполняется, то есть для любого целого m, S(n) + m = m + S(n):

1. S(n) + m = S(n + m) (из леммы 3)
2. m + S(n) = S(m + n) = S(n + m) (из P(n)), что и требовалось доказать.

[Лемма 5] Докажем что для любых целых n и m, m + (n * m) = S(n) * m (частный случай дистрибутивности умножения по сложению). Доказательство снова по индукции, где предположение P(m): для любого n, m + (n * m) = S(n) * m; базис индукции — P(0): для любого n, 0 + n * 0 = S(n) * 0 (очевидно из определения сложения и умножения и коммутативности сложения); шаг индукции — если m + (n * m) = S(n) * m, то докажем что S(m) + (n * S(m)) = S(n) * S(m).

1. S(m) + (n * S(m)) = S(m) + n * m + n;
2. S(n) * S(m) = S(n) * m + S(n) = m + (n * m) + S(n) = S(m) + n * m + n, что и требовалось доказать.

[Лемма 6] Теперь докажем, собственно, коммутативность умножения, имея аксиомы Пеано и леммы выше. Доказывать будем, опять-таки, по индукции, где предположение P(n): для каждого целого m, n * m = m * n. Базис индукции — P(0), то есть для любого целого m, 0 * m = m * 0, это мы уже доказали выше в лемме 1. Переходим к шагу индукции: если P(n) доказано, то докажем P(S(n)): для каждого целого m, S(n) * m = m * S(n):

1. m * S(n) = m * n + m (по определению умножения);
2. m * n + m = m + m * n (из коммутативности сложения, лемма 4);
3. m + m * n = m + n * m (из предположения индукции, P(n));
4. m + n * m = S(n) * m (из дистрибутивности умножения по сложению, лемма 5), что и требовалось доказать.

Итак, мы доказали, что умножение коммутативно, иными словами произведение не зависит от порядка множителей. 7 * 2 = 2 * 7 — частный случай этого утверждения, так что оно, разумеется, тоже доказано.