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

1 4. Если множество А содержит единицу и вместе с каждым чис­ лом а содержит следующее за ним число а \ то А содержит все натуральные числа: А = N. Эта аксиома дает возможность делать достоверные выводы на бесконечном множестве натуральных чи­ сел с помощью математической индукции, поэтому ее называют аксиомой математической индукции. Действительно, если истинно некоторое высказывание 7’(1), а из истинности Г(о) следует истинность Т(а + 1), причем 1 е А, а е А, а + 1= a' g А, где А — подмножество натуральных чисел, для которых истинно Т(п), то множество А совпадает со всем мно­ жеством натуральных чисел N и Т(п) истинно для всех натураль­ ных п. Вошедшая в употребление во всем мире система аксиом нату­ ральных чисел была предложена итальянским математиком и ло­ гиком, профессором Туринского университета Д. Пеано в статье «О понятии числа» в 1891 г. 5.6.4. Метод математической индукции Метод полной индукции имеет весьма ограниченную область применения в математике, поскольку большинство рассматрива­ емых множеств бесконечны: множество натуральных чисел, мно­ жество простых чисел, множество многогранников и т.д. Прове­ рить справедливость гипотезы напрямую при бесконечном мно­ жестве исследуемых объектов невозможно. В таких случаях применяется метод рассуждений, заменяющий полный перебор всех вариантов, который также дает достовер­ ный вывод. Этот метод носит название метода математической индукции (МММ). С помощью ММИ определяются сложение и умножение натуральных чисел, свойства этих операций, вводятся отношения «больше» и «меньше» и их свойства, доказываются делимость и формула для п -й степени бинома (бином Ньютона). Так, с помощью ММИ можно доказать одно из важнейших свойств натуральных чисел — свойство полной упорядоченности (в лю­ бом непустом подмножестве множества натуральных чисел есть наименьшее число). Смысл ММИ заключается в применении аксиомы Пеано в виде некоторого алгоритма. 1. Утверждение проверяется для некоторого начального элемен­ та, например для п = 1 . 2. Формулируется гипотеза о том, что утверждение справедли­ во для некоторого к е N. 3. Доказывается (устанавливается истинность утверждения), что если из того, что утверждение справедливо для произвольного к е N следует , что оно справедливо и для V/c + 1 е N, то оно справедливо для любого натурального числа: Vn е N. 270