Спирина, М.С. Дискретная математика

В теории функционально полных формальных систем мы упо­ минали, что система должна быть минимальной. Поэтому удобнее пользоваться одной аксиомой. Аксиома натуральных чисел. Любое непустое подмножество н а ­ туральных чисел имеет минимальный элемент. Минимальный эле­ мент самого множества N обозначается 1 и называется «едини­ цей». Операцию «следования за» будем обозначать не штрихом, а привычно: + 1, например 3 = 2 + 1 (аналог 3 = 2'). При такой аксиоматике математическая индукция будет уже не аксиомой, а теоремой математической индукции. Теорема. Если для множества Л с N выполнены условия: 1 е А и если из к е А следует к + 1 е А, то А = N. Предлагаем читателю самому доказать эту теорему с помощью аксиомы. Легче всего это сделать методом от противного. Полученный вывод замечателен тем, что в нем речь идет об абстрактных множествах. Фактически слова «утверждение спра­ ведливо» означают выполнение некоего свойства, а мы знаем, что задать характеристическое свойство все равно что задать мно­ жество. Поэтому-то две приведенные аксиоматики являются э к ­ вивалентными, так как из одной системы можно получить другую в качестве теоремы. Метод математической индукции чаще всего применяется к натуральным числам и счетным множествам для доказательства формул, неравенств, делимости натуральных чисел и комбина­ торных формул. л I Как быть, если по каким-то причинам утверждение не удается дока­ зать подобным методом? Даже если в результате применения МММ получается заведо­ мая ложь или упрощение не получается вовсе, то сначала нужно попытаться опровергнуть гипотезу логическим путем. Например, можно привести один факт, разоблачающий ее. Если это не полу­ чается, то нужно искать другие логически корректные методы до­ казательства утверждения, поскольку из ложной или неопреде­ ленной посылки может следовать все, что угодно. Задача 27. Доказать, что V n e N справедливо равенство: 1+ 4 + 7 +... + (Зя - 2) = . Решение. Проверим равенство при я = 1. Имеем 1= —^ ^ , 1 = 1 — значит, формула верна. Гипотеза: пусть формула справедлива для я = к. 1+ 4 + 7 +... + (Зк - 2) = — ^ ^ . Доказываем, что формула верна для я = к + 1, т.е. имеет место выражение 271