13. Опять индукция

Теорема: Все натуральные числа равны между собой.

Доказательство. Необходимо доказать, что для любых двух натуральных чисел A и B выполнено равенство A = B. Переформулируем это в таком виде: для любого N > 0 и любых A и B, удовлетворяющих равенству max(A, B) = N, должно выполняться и равенство A = B.

Докажем это по индукции. Если N = 1, то A и B, будучи натуральными, оба равны 1. Поэтому A = B.

Предположим теперь, что утверждение доказано для некоторого значения k. Возьмем A и B такими, чтобы max(A, B) = k + 1. Тогда max(A–1, B–1) = k. По предположению индукции отсюда следует, что (A–1) = (B–1). Значит, A = B.