Ответ спасен из Яндекс.Кью
Это, во-первых, интуитивно очевидно. Утверждение верно для N=1. Раз оно верно для N=1, значит, верно и для N=2. Раз оно верно для N=2, значит и для N=3. И так далее -- эта цепочка никогда не прерывается и проходит через каждое натуральное число.
Во-вторых, можно это попробовать доказать от обратного, например, так. Предположим, что утверждение справедливо не для всех натуральных чисел. Из всех натуральных чисел, для которых оно неверно, найдётся самое маленькое. Обозначим его N__.__ N > 1, т.к. для N=1 утверждение верно. Значит, N-1 тоже натуральное число, для которого утверждение уже верно. Применяя к нему шаг индукции, мы приходим к противоречию.
Я понимаю, что это было банально, поэтому перейдем к чему-то более интересному.
В-третьих, в аксиоматике Пеано индукция просто является аксиомой (точнее, набором аксиом). Зная это, можно догадаться, что оба рассуждения выше не могут быть её доказательствами. На самом деле утверждения, выделенные курсивом, эквивалентны аксиоме индукции, т.е. просто другие способы её сформулировать.
Теперь мы переходим к действительно интересному вопросу: можно ли построить аксиоматику арифметики, в которой индукции нет, а всё остальное похоже на "обычную арифметику", например, 2+2=4 и вообще арифметические операции устроены привычным образом?
Ага, можно. Аксиоматика Пеано без аксиом индукции называется Robinson arithmetic, поэтому то, что нас интересует, будет называться models for Robinson arithmetic. Да, они существуют (до того, как отвечать на этот вопрос, я об этом не знал -- отвечать на хорошие вопросы полезно!)
Мы можем объявить все кардинальные числа (грубо говоря, все возможные разновидности бесконечностей) "натуральными числами", доопределить сложение и умножение так, чтобы они работали и для них, после чего убедиться, что вся аксиоматика Робинсона выполнена, а индукция не работает.
В принципе, может так оказаться, что наш мир именно таков, хотя я и не очень в это верю. Мало ли что там физики внутри сингулярностей найдут, например? Это будет означать, что индукция в нашем мире на самом-то деле неверна. Но она все же останется верна для всего, что мы можем измерить или проверить за конечное время и в этом смысле останется полезным способом рассуждений.