Математическая индукция

редактировать
Не путать с индуктивными рассуждениями.

Математическая индукция может быть неформально проиллюстрирована ссылкой на последовательный эффект падения домино.

Математическая индукция - это метод математического доказательства. По сути, он используется для доказательства того, что утверждение P ( n) выполняется для любого натурального числа n  = 0, 1, 2, 3,... ; то есть общее утверждение представляет собой последовательность бесконечного числа случаев P (0), P (1), P (2), P (3),.... Неформальные метафоры помогают объяснить эту технику, например, падение домино или подъем по лестнице:

Математическая индукция доказывает, что мы можем подняться по лестнице сколь угодно высоко, доказывая, что мы можем подняться на нижнюю ступеньку ( основание) и что с каждой ступеньки мы можем подняться на следующую ( ступеньку).

-  Конкретная математика, стр. 3 на полях.

Доказательство по индукции состоит из двух корпусов. Первый, базовый случай (или базис), доказывает утверждение для n = 0 без каких-либо знаний о других случаях. Второй случай, шаг индукции, доказывает, что если утверждение верно для любого данного случая n = k, то оно должно выполняться и для следующего случая  n = k + 1. Эти два шага устанавливают, что утверждение верно для любого натурального числа n.. Базовый вариант не обязательно начинать с п = 0, но часто с п = 1, и, возможно, с каким - либо фиксированное натуральное число п = N, установление истины заявления для всех натуральных чисел п ≥ N.

Метод может быть расширен для доказательства утверждений о более общих хорошо обоснованных структурах, таких как деревья ; это обобщение, известное как структурная индукция, используется в математической логике и информатике. Математическая индукция в этом расширенном смысле тесно связана с рекурсией. Математическая индукция - это правило вывода, используемое в формальных доказательствах, и это основа большинства доказательств правильности компьютерных программ.

Хотя его название может предполагать иное, математическую индукцию не следует путать с индуктивными рассуждениями, используемыми в философии (см. Проблема индукции ). Математический метод исследует бесконечно много случаев, чтобы доказать общее утверждение, но делает это с помощью конечной цепочки дедуктивных рассуждений с участием переменной n, которая может принимать бесконечно много значений.

СОДЕРЖАНИЕ
  • 1 История
  • 2 Описание
  • 3 Примеры
    • 3.1 Сумма последовательных натуральных чисел
    • 3.2 Тригонометрическое неравенство
  • 4 варианта
    • 4.1 Индукционная основа, отличная от 0 или 1
      • 4.1.1 Пример: формирование долларовых сумм по монетам
    • 4.2 Индукция на более чем одном счетчике
    • 4.3 Бесконечный спуск
    • 4.4 Индукция префикса
    • 4.5 Полная (сильная) индукция
      • 4.5.1 Пример: числа Фибоначчи
      • 4.5.2 Пример: разложение на простые множители
      • 4.5.3 Пример: пересмотр долларовых сумм
    • 4.6 Прямая-обратная индукция
  • 5 Пример ошибки индуктивного шага
  • 6 Формализация
  • 7 Трансфинитная индукция
  • 8 Связь с принципом хорошего порядка
  • 9 См. Также
  • 10 заметок
  • 11 Источники
    • 11.1 Введение
    • 11.2 История
История

В 370 г. до н.э. Платоновский « Парменид» мог содержать ранний пример неявного индуктивного доказательства. Противоположная итеративная техника - обратный отсчет, а не вверх - встречается в парадоксе соритов, где утверждалось, что если 1000000 песчинок образуют кучу, а удаление одной песчинки из кучи оставляет ее кучей, то одна песчинка. (или даже без зерен) образует кучу.

В Индии первые неявные доказательства с помощью математической индукции появляются в « циклическом методе » Бхаскары и в аль-Фахри, написанном аль-Караджи около 1000 г. н.э., который применил его к арифметическим последовательностям для доказательства биномиальной теоремы и свойств треугольника Паскаля..

Однако ни один из этих древних математиков явно не высказал гипотезы индукции. Другой подобный случай (вопреки тому, что написал Вакка, как тщательно показал Фройденталь) был случай Франческо Моролико в его Arithmeticorum libri duo (1575), который использовал эту технику, чтобы доказать, что сумма первых n нечетных целых чисел равна n 2.

Самым ранним строгим применением индукции был Герсонид (1288–1344). Первая явная формулировка принципа индукции была дана Паскалем в его « Арифметическом треугольнике» (1665). Другой француз, Ферма, широко использовал родственный принцип: косвенное доказательство бесконечным спуском.

Гипотеза индукции также использовалась швейцарцем Якобом Бернулли, и с тех пор она стала широко известной. Современная формальная трактовка этого принципа появилась только в XIX веке у Джорджа Буля, Августа де Моргана, Чарльза Сандерса Пирса, Джузеппе Пеано и Ричарда Дедекинда.

Описание

Простейшая и наиболее распространенная форма математической индукции предполагает, что утверждение, содержащее натуральное число n (то есть целое число n ≥ 0 или 1), выполняется для всех значений n. Доказательство состоит из двух шагов:

  1. Начальный или базовый случай: доказать, что утверждение справедливо и для 0 или 1.
  2. Шаг индукции, индуктивный шаг, или шаг случай: доказать, что для каждого п, если утверждение верно для п, то оно справедливо для п + 1. Другими словами, предположим, что утверждение верно для некоторого произвольного натурального числа n, и докажем, что утверждение верно для n + 1.

Гипотеза индуктивного шага о том, что утверждение верно для определенного n, называется индукционной гипотезой или индуктивной гипотезой. Чтобы доказать индуктивный шаг, нужно принять предположение индукции для n, а затем использовать это предположение, чтобы доказать, что утверждение верно для n + 1.

Авторы, которые предпочитают определять натуральные числа, начинающиеся с 0, используют это значение в базовом случае; те, кто определяет натуральные числа, чтобы начать с 1, используют это значение.

Примеры

Сумма последовательных натуральных чисел

С помощью математической индукции можно доказать следующее утверждение P ( n) для всех натуральных чисел n.

п ( п ) :     0 + 1 + 2 + + п знак равно п ( п + 1 ) 2 . {\ Displaystyle P (n) \!: \ \ 0 + 1 + 2 + \ cdots + n \, = \, {\ frac {n (n + 1)} {2}}.}

Это устанавливает общую формулу для суммы натуральных чисел, меньших или равных данному числу; фактически бесконечная последовательность операторов:,, и т.д. 0 знак равно ( 0 ) ( 0 + 1 ) 2 {\ Displaystyle 0 = {\ tfrac {(0) (0 + 1)} {2}}} 0 + 1 знак равно ( 1 ) ( 1 + 1 ) 2 {\ Displaystyle 0 + 1 = {\ tfrac {(1) (1 + 1)} {2}}} 0 + 1 + 2 знак равно ( 2 ) ( 2 + 1 ) 2 {\ Displaystyle 0 + 1 + 2 = {\ tfrac {(2) (2 + 1)} {2}}}

Предложение. Для любого, п N {\ Displaystyle п \ в \ mathbb {N}} 0 + 1 + 2 + + п знак равно п ( п + 1 ) 2 . {\ displaystyle 0 + 1 + 2 + \ cdots + n = {\ tfrac {n (n + 1)} {2}}.}

Доказательство. Пусть P ( n) - утверждение. Доказательство проводится индукцией по n. 0 + 1 + 2 + + п знак равно п ( п + 1 ) 2 . {\ displaystyle 0 + 1 + 2 + \ cdots + n = {\ tfrac {n (n + 1)} {2}}.}

Базовый случай: покажите, что утверждение верно для наименьшего натурального числа n = 0.

P (0) явно верно: 0 знак равно 0 ( 0 + 1 ) 2 . {\ Displaystyle 0 = {\ tfrac {0 (0 + 1)} {2}} \,.}

Индуктивный шаг: покажите, что для любого k ≥ 0, есливыполняется P ( k), то P ( k +1) также выполняется.

Предположим предположение индукции, что для конкретного k выполняется единственный случай n = k, что означает, что P ( k) истинно:

0 + 1 + + k   знак равно   k ( k + 1 ) 2 . {\ displaystyle 0 + 1 + \ cdots + k \ = \ {\ frac {k (k {+} 1)} {2}}.}

Следует, что:

( 0 + 1 + 2 + + k ) + ( k + 1 )   знак равно   k ( k + 1 ) 2 + ( k + 1 ) . {\ displaystyle (0 + 1 + 2 + \ cdots + k) + (k {+} 1) \ = \ {\ frac {k (k {+} 1)} {2}} + (k {+} 1).}

Алгебраически правая часть упрощается как:

k ( k + 1 ) 2 + ( k + 1 )   знак равно   k ( k + 1 ) + 2 ( k + 1 ) 2   знак равно   ( k + 1 ) ( k + 2 ) 2   знак равно   ( k + 1 ) ( ( k + 1 ) + 1 ) 2 . {\ displaystyle {\ begin {align} {\ frac {k (k {+} 1)} {2}} + (k {+} 1) amp; \ = \ {\ frac {k (k {+} 1) +2 (k {+} 1)} {2}} \\ amp; \ = \ {\ frac {(k {+} 1) (k {+} 2)} {2}} \\ amp; \ = \ { \ frac {(k {+} 1) ((k {+} 1) +1)} {2}}. \ end {align}}}

Приравнивая крайнюю левую и правую части, мы заключаем, что:

0 + 1 + 2 + + k + ( k + 1 )   знак равно   ( k + 1 ) ( ( k + 1 ) + 1 ) 2 . {\ displaystyle 0 + 1 + 2 + \ cdots + k + (k {+} 1) \ = \ {\ frac {(k {+} 1) ((k {+} 1) +1)} {2}}.}

То есть утверждение P ( k + 1) также выполняется, устанавливая индуктивный шаг.

Заключение: Поскольку и базовый случай, и индуктивный шаг были доказаны как истинные, математической индукцией утверждение P ( n) выполняется для любого натурального числа n.

Тригонометрическое неравенство

Индукция часто используется для доказательства неравенств. В качестве примера мы докажем это для любого действительного и натурального числа. | грех п Икс | п | грех Икс | {\ Displaystyle | \! \ грех nx | \ leq п | \! \ грех х |} Икс {\ displaystyle x} п {\ displaystyle n}

На первый взгляд может показаться, что более общая версия для любых действительных чисел может быть доказана без индукции; но случай показывает, что это может быть ложным для нецелых значений. Это предполагает, что мы исследуем утверждение специально для естественных значений, а индукция - самый удобный инструмент. | грех п Икс | п | грех Икс | {\ Displaystyle | \! \ грех nx | \ leq n \, | \! \ грех х |} п , Икс {\ displaystyle n, x} п знак равно 1 2 , Икс знак равно π {\ textstyle п = {\ гидроразрыва {1} {2}}, \, x = \ pi} п {\ displaystyle n} п {\ displaystyle n}

Предложение. Для любого,. Икс р , п N {\ Displaystyle х \ in \ mathbb {R}, п \ in \ mathbb {N}} | грех п Икс | п | грех Икс | {\ Displaystyle | \! \ грех nx | \ leq n \, | \! \ грех х |}

Доказательство. Зафиксируйте произвольное действительное число, и пусть будет утверждение. Мы вводим в курс дела. Икс {\ displaystyle x} п ( п ) {\ Displaystyle P (п)} | грех п Икс | п | грех Икс | {\ Displaystyle | \! \ грех nx | \ leq n \, | \! \ грех х |} п {\ displaystyle n}

Базовый случай: расчетподтверждается. | грех 0 Икс | знак равно 0 0 знак равно 0 | грех Икс | {\ Displaystyle | \! \ грех 0x | = 0 \ Leq 0 = 0 \, | \! \ грех х |} п ( 0 ) {\ Displaystyle P (0)}

Индуктивный шаг: мы показываем следствиедля любого натурального числа. Предположим гипотезу индукции: для данного значенияверенединственный случай. Используя формулу сложения углов и неравенство треугольника, получаем: п ( k ) п ( k + 1 ) {\ displaystyle P (k) \ подразумевает P (k {+} 1)} k {\ displaystyle k} п знак равно k 0 {\ Displaystyle п = к \ geq 0} п ( k ) {\ Displaystyle P (k)}

| грех ( k + 1 ) Икс | знак равно | грех k Икс потому что Икс + грех Икс потому что k Икс | (сложение углов) | грех k Икс потому что Икс | + | грех Икс потому что k Икс | (неравенство треугольника) знак равно | грех k Икс | | потому что Икс | + | грех Икс | | потому что k Икс | | грех k Икс | + | грех Икс | ( | потому что т | 1 ) k | грех Икс | + | грех Икс | (гипотеза индукции )   знак равно   ( k + 1 ) | грех Икс | . {\ displaystyle {\ begin {array} {rcll} | \ sin (k {+} 1) x | amp; = amp; | \ sin kx \, \ cos x + \ sin x \, \ cos kx \, | amp; {\ text {(сложение углов)}} \\ amp; \ leq amp; | \! \ sin kx \, \ cos x | + | \! \ sin x \, \ cos kx | amp; {\ text {(неравенство треугольника)}} \\ amp; = amp; | \! \ sin kx | \, | \! \ cos x | + | \! \ sin x | \, | \! \ cos kx | amp; \\ amp; \ leq amp; | \! \ sin kx | + | \! \ sin x | amp; (\, | \! \ cos t | \ leq 1) \\ amp; \ leq amp; k \, | \! \ sin x | + | \! \ sin x | amp; { \ text {(гипотеза индукции}}) \\ amp; \ = \ amp; (k {+} 1) \, | \! \ sin x |. amp; \ end {array}}}

Неравенство между крайними левыми и правыми величинами показывает, что это правда, что завершает индуктивный шаг. п ( k + 1 ) {\ Displaystyle P (к {+} 1)}

Заключение: предложениеверно для всех натуральных чисел. ∎ п ( п ) {\ Displaystyle P (п)} п {\ displaystyle n}

Варианты

На практике доказательства по индукции часто строятся по-разному, в зависимости от точного характера доказываемого свойства. Все варианты индукции являются частными случаями трансфинитной индукции; см. ниже.

Индукционная база, отличная от 0 или 1

Если кто-то хочет доказать утверждение не для всех натуральных чисел, а только для всех чисел n, больших или равных определенному числу b, то доказательство по индукции состоит из следующего:

  1. Показывая, что утверждение верно, когда n = b.
  2. Показывая, что если утверждение верно для произвольного числа n ≥ b, то то же самое утверждение верно и для n + 1.

Это можно использовать, например, чтобы показать, что 2 n ≥ n + 5 для n ≥ 3.

Таким образом можно доказать, что некоторое утверждение P ( n) выполняется для всех n ≥ 1 или даже для всех n ≥ −5. Эта форма математической индукции на самом деле является частным случаем предыдущей формы, потому что если доказываемое утверждение - это P ( n), то доказательство его с помощью этих двух правил эквивалентно доказательству P ( n + b) для всех натуральных чисел n с базовый случай индукции 0.

Пример: формирование долларовых сумм по монетам

Предположим, бесконечный запас 4- и 5-долларовых монет. Индукция может быть использована для доказательства того, что любая сумма в долларах больше или равная 12 может быть образована комбинацией таких монет. Пусть S ( k) обозначает утверждение « k долларов могут быть образованы комбинацией 4- и 5-долларовых монет ». Доказательство того, что S ( k) истинно для всех k ≥ 12, может быть получено индукцией по k следующим образом:

Базовый случай: показать, что S ( k) выполняется для k = 12, просто: возьмите три 4-долларовые монеты.

Шаг индукции: учитывая, что S ( k) выполняется для некоторого значения k ≥ 12 ( предположение индукции), докажите, что S ( k + 1) также выполняется:

Предположим, что S ( k) истинно для некоторого произвольного k ≥ 12. Если есть решение для k долларов, которое включает хотя бы одну 4-долларовую монету, замените ее 5-долларовой монетой, чтобы получить k + 1 доллар. В противном случае, если используются только 5-долларовые монеты, k должно быть кратно 5, то есть не менее 15; но тогда мы можем заменить три монеты по 5 долларов на четыре монеты по 4 доллара, чтобы получить k + 1 доллар. В любом случае S ( k + 1) истинно.

Следовательно, по принципу индукции S ( k) выполняется для всех k ≥ 12, и доказательство завершено.

В этом примере, хотя S ( k) также выполняется, приведенное выше доказательство не может быть изменено для замены минимальной суммы в 12 долларов на любое меньшее значение m. Для m = 11 базовый случай на самом деле неверен; при m = 10 второй случай на этапе индукции (замена трех 5-долларовых монет на четыре 4-долларовых) не сработает; не говоря уже о еще меньшем m. k { 4 , 5 , 8 , 9 , 10 } {\ textstyle к \ in \ {4,5,8,9,10 \}}

Индукция на более чем одном счетчике

Иногда желательно доказать утверждение, включающее два натуральных числа, n и m, повторяя процесс индукции. То есть доказывается базовый случай и индуктивный шаг для n, и в каждом из них доказываются базовый случай и индуктивный шаг для m. Смотрите, например, доказательство коммутативности сопровождая добавление натуральных чисел. Возможны и более сложные аргументы с участием трех и более счетчиков.

Бесконечный спуск

Основная статья: Бесконечный спуск

Метод бесконечного спуска - это разновидность математической индукции, которую использовал Пьер де Ферма. Он используется, чтобы показать, что некоторая инструкция Q ( n) ложна для всех натуральных чисел n. Его традиционная форма состоит в том, чтобы показать, что если Q ( n) истинно для некоторого натурального числа n, то оно также верно и для некоторого строго меньшего натурального числа m. Поскольку не существует бесконечных убывающих последовательностей натуральных чисел, эта ситуация была бы невозможна, тем самым показывая (от противного), что Q ( n) не может быть истинным ни для какого n.

Справедливость этого метода может быть проверена с помощью обычного принципа математической индукции. Используя математическую индукцию по утверждению P ( n), определенному как « Q ( m) ложно для всех натуральных чисел m, меньших или равных n », следует, что P ( n) выполняется для всех n, что означает, что Q ( n) ложно для любого натурального числа n.

Индукция префикса

Наиболее распространенная форма доказательства с помощью математической индукции требует на этапе индукции доказательства того, что

k ( п ( k ) п ( k + 1 ) ) {\ Displaystyle \ forall k (P (k) \ to P (k + 1))}

после чего принцип индукции «автоматизирует» n применений этого шага для перехода от P (0) к P ( n). Это можно было бы назвать «индукцией предшественника», потому что каждый шаг доказывает что-то о числе из чего-то о предшественнике этого числа.

Вариант, представляющий интерес с точки зрения вычислительной сложности, - это «префиксная индукция», в которой на индуктивном шаге доказывается следующее утверждение:

k ( п ( k ) п ( 2 k ) п ( 2 k + 1 ) ) {\ Displaystyle \ forall k (P (k) \ to P (2k) \ land P (2k + 1))}

или эквивалентно

k ( п ( k 2 ) п ( k ) ) {\ Displaystyle \ forall k \ left (P \ left (\ left \ lfloor {\ frac {k} {2}} \ right \ rfloor \ right) \ к P (k) \ right)}

Затем принцип индукции «автоматизирует» log n применений этого вывода при переходе от P (0) к P ( n). Фактически, это называется «префиксной индукцией», потому что каждый шаг доказывает что-то о числе из чего-то о «префиксе» этого числа, образованном путем усечения младшего бита его двоичного представления. Его также можно рассматривать как применение традиционной индукции по длине этого двоичного представления.

Если традиционная индукция предшественника интерпретируется вычислительно как n- шаговый цикл, то префиксная индукция будет соответствовать log- n- шаговому циклу. Из-за этого доказательства, использующие префиксную индукцию, «более конструктивны», чем доказательства, использующие предшествующую индукцию.

Индукция по предшественнику может тривиально имитировать индукцию по префиксу для того же оператора. Индукция префикса может имитировать индукцию предшественника, но только за счет усложнения инструкции (добавление ограниченного универсального квантора ), поэтому интересные результаты, связывающие индукцию префикса с вычислением за полиномиальное время, зависят от полного исключения неограниченных кванторов и ограничения чередования. ограниченных универсальных и экзистенциальных кванторов, разрешенных в утверждении.

Можно пойти еще дальше: нужно доказать

k ( п ( k ) п ( k ) ) {\ Displaystyle \ forall k \ left (P \ left (\ left \ lfloor {\ sqrt {k}} \ right \ rfloor \ right) \ к P (k) \ right)}

после чего принцип индукции «автоматизирует» log log n приложений этого вывода при переходе от P (0) к P ( n). Эта форма индукции аналогичным образом использовалась для изучения логарифмических параллельных вычислений.

Полная (сильная) индукция

Другой вариант, называемый полной индукцией, индукцией курса значений или сильной индукцией (в отличие от которого основная форма индукции иногда называется слабой индукцией), упрощает доказательство индуктивного шага с помощью более сильной гипотезы: утверждение доказывается при предположение, которое выполняется для всех натуральных чисел меньше, чем ; напротив, основная форма только предполагает. Название «сильная индукция» не означает, что этот метод может доказать нечто большее, чем «слабая индукция», а просто относится к более сильной гипотезе, используемой в индуктивном шаге. п ( м + 1 ) {\ Displaystyle P (м + 1)} п ( п ) {\ Displaystyle P (п)} п {\ displaystyle n} м + 1 {\ displaystyle m + 1} п ( м ) {\ Displaystyle P (м)}

Фактически, можно показать, что эти два метода фактически эквивалентны, как объясняется ниже. В этой форме полной индукции все еще необходимо доказать базовый случай, и может даже потребоваться доказать дополнительные базовые случаи, например, до того, как будет применен общий аргумент, как в приведенном ниже примере числа Фибоначчи. п ( 0 ) {\ Displaystyle P (0)} п ( 1 ) {\ Displaystyle P (1)} F п {\ displaystyle F_ {n}}

Хотя только что описанная форма требует доказательства базового случая, в этом нет необходимости, если можно доказать (предполагая для всех ниже) для всех. Это частный случай трансфинитной индукции, описанный ниже, хотя он больше не эквивалентен обычной индукции. В этой форме базовый случай включается в случай, когда он доказывается без каких-либо других предположений; этот случай, возможно, придется рассматривать отдельно, но иногда тот же аргумент применяется для и, что делает доказательство более простым и элегантным. В этом методе, однако, важно убедиться, что доказательство не подразумевает это неявно, например, говоря «выберите произвольный » или предполагая, что набор из m элементов имеет элемент. п ( м ) {\ Displaystyle P (м)} п ( п ) {\ Displaystyle P (п)} п {\ displaystyle n} м 0 {\ Displaystyle м \ geq 0} м знак равно 0 {\ displaystyle m = 0} п ( 0 ) {\ Displaystyle P (0)} п ( п ) {\ Displaystyle P (п)} м знак равно 0 {\ displaystyle m = 0} м gt; 0 {\ displaystyle mgt; 0} п ( м ) {\ Displaystyle P (м)} м gt; 0 {\ displaystyle mgt; 0} п lt; м {\ Displaystyle п lt;м}

Полная индукция эквивалентна обычной математической индукции, описанной выше, в том смысле, что доказательство одним методом может быть преобразовано в доказательство другим. Предположим, что имеется доказательство по полной индукции. Позвольте значить « справедливо для всех таких, что ». Тогда верно для всех тогда и только тогда, когда верно для всех, и наше доказательство легко трансформируется в доказательство с помощью (обычной) индукции. С другой стороны, если бы оно было доказано с помощью обычной индукции, доказательство уже фактически было бы доказано с помощью полной индукции: доказывается в базовом случае, без каких-либо предположений, и доказывается на этапе индукции, на котором можно предположить все более ранние случаи, но нужно использовать только случай. п ( п ) {\ Displaystyle P (п)} Q ( п ) {\ Displaystyle Q (п)} п ( м ) {\ Displaystyle P (м)} м {\ displaystyle m} 0 м п {\ Displaystyle 0 \ Leq м \ Leq п} Q ( п ) {\ Displaystyle Q (п)} п {\ displaystyle n} п ( п ) {\ Displaystyle P (п)} п {\ displaystyle n} п ( п ) {\ Displaystyle P (п)} Q ( п ) {\ Displaystyle Q (п)} п ( п ) {\ Displaystyle P (п)} п ( 0 ) {\ Displaystyle P (0)} п ( п + 1 ) {\ Displaystyle P (п + 1)} п ( п ) {\ Displaystyle P (п)}

Пример: числа Фибоначчи

Полная индукция наиболее полезна, когда для каждого индуктивного шага требуется несколько экземпляров индуктивной гипотезы. Например, полная индукция может использоваться, чтобы показать, что

F п знак равно φ п - ψ п φ - ψ {\ Displaystyle F_ {п} = {\ гидроразрыва {\ varphi ^ {n} - \ psi ^ {n}} {\ varphi - \ psi}}}

где это п - го числа Фибоначчи, (далее золотое сечение ) и корни полинома. Используя тот факт, что для каждого, указанная выше идентичность может быть проверена прямым вычислением, если предполагается, что оно уже выполняется для обоих и. Для завершения доказательства идентичность должна быть проверена в двух базовых случаях: и. F п {\ displaystyle F_ {n}} φ знак равно 1 + 5 2 {\ textstyle \ varphi = {{1 + {\ sqrt {5}}} \ более 2}} ψ знак равно 1 - 5 2 {\ textstyle \ psi = {{1 - {\ sqrt {5}}} \ более 2}} Икс 2 - Икс - 1 {\ displaystyle x ^ {2} -x-1} F п + 2 знак равно F п + 1 + F п {\ Displaystyle F_ {n + 2} = F_ {n + 1} + F_ {n}} п N {\ displaystyle n \ in {\ mathbb {N}}} F п + 2 {\ textstyle F_ {n + 2}} F п + 1 {\ textstyle F_ {n + 1}} F п {\ textstyle F_ {n}} п знак равно 0 {\ displaystyle n = 0} п знак равно 1 {\ textstyle n = 1}

Пример: разложение на простые множители

Другое доказательство по полной индукции использует гипотезу, что утверждение верно для всех меньших более тщательно. Рассмотрим утверждение, что «каждое натуральное число больше 1 является произведением (одного или нескольких) простых чисел », что является частью фундаментальной теоремы арифметики о « существовании ». Для доказательства шага индукции предположение индукции состоит в том, что для данного утверждения утверждение верно для всех меньших. Если простое число, то это, безусловно, произведение простых чисел, а если нет, то по определению это произведение:, где ни один из множителей не равен 1; следовательно, ни один не равен, и поэтому оба больше 1 и меньше чем. Гипотеза индукции теперь применима к и, поэтому каждое из них является произведением простых чисел. Таким образом, это продукт произведений простых чисел и, следовательно, сам продукт простых чисел. п {\ displaystyle n} п gt; 1 {\ displaystyle ngt; 1} п gt; 1 {\ displaystyle ngt; 1} м {\ displaystyle m} м знак равно п 1 п 2 {\ displaystyle m = n_ {1} n_ {2}} м {\ displaystyle m} м {\ displaystyle m} п 1 {\ displaystyle n_ {1}} п 2 {\ displaystyle n_ {2}} м {\ displaystyle m}

Пример: пересмотр долларовых сумм

Мы постараемся доказать тот же пример, что и выше, на этот раз с сильной индукцией. Утверждение остается прежним:

S ( п ) : п 12 а , б N . п знак равно 4 а + 5 б {\ Displaystyle S (п): \, \, п \ geq 12 \ к \, \ существует \, a, b \ in \ mathbb {N}. \, \, n = 4a + 5b}

Однако будут небольшие различия в структуре и предположениях доказательства, начиная с расширенного базового случая:

Базовый случай: покажите, что верно для. S ( k ) {\ Displaystyle S (к)} k знак равно 12 , 13 , 14 , 15 {\ displaystyle k = 12,13,14,15}

4 3 + 5 0 знак равно 12 4 2 + 5 1 знак равно 13 4 1 + 5 2 знак равно 14 4 0 + 5 3 знак равно 15 {\ Displaystyle {\ begin {align} 4 \ cdot 3 + 5 \ cdot 0 = 12 \\ 4 \ cdot 2 + 5 \ cdot 1 = 13 \\ 4 \ cdot 1 + 5 \ cdot 2 = 14 \\ 4 \ cdot 0 + 5 \ cdot 3 = 15 \ конец {выровнено}}}

Базовый случай верен.

Гипотеза индукции: для некоторых предположение верно для всех с. j gt; 15 {\ displaystyle jgt; 15} S ( м ) {\ Displaystyle S (м)} м {\ displaystyle m} 12 м lt; j {\ Displaystyle 12 \ Leq м lt;j}

Индуктивный шаг: Докажите, что верно. S ( j ) {\ Displaystyle S (j)}

Выбор и наблюдение, которое показывает, что это верно, с помощью индуктивной гипотезы. То есть сумма может быть образована некоторой комбинацией монет и долларов. Затем, просто добавив долларовую монету к этой комбинации, вы получите сумму. То есть держит. QED м знак равно j - 4 {\ displaystyle m = j-4} 15 lt; j 12 j - 4 lt; j {\ displaystyle 15 lt;j \ to 12 \ leq j-4 lt;j} S ( j - 4 ) {\ Displaystyle S (j-4)} j - 4 {\ displaystyle j-4} 4 {\ displaystyle 4} 5 {\ displaystyle 5} 4 {\ displaystyle 4} j {\ displaystyle j} S ( j ) {\ Displaystyle S (j)}

Прямая-обратная индукция

Основная статья: прямая-обратная индукция

Иногда удобнее вывести обратный вывод, доказывая утверждение для, учитывая его справедливость для. Однако доказательства действительности утверждения ни для одного числа недостаточно, чтобы установить базовый случай; вместо этого нужно доказать утверждение для бесконечного подмножества натуральных чисел. Например, Огюстен Луи Коши сначала использовал прямую (регулярную) индукцию, чтобы доказать неравенство среднего арифметического и геометрического для всех степеней двойки, а затем использовал обратную индукцию, чтобы показать это для всех натуральных чисел. п - 1 {\ displaystyle n-1} п {\ displaystyle n}

Пример ошибки индуктивного шага
Основная статья: Все лошади одного цвета

Индуктивный шаг должен быть доказан для всех значений n. Чтобы проиллюстрировать это, Джоэл Коэн предложил следующий аргумент, цель которого - доказать математической индукцией, что все лошади одного цвета :

  • Базовый вариант: в наборе только одна лошадь будет только одного цвета.
  • Индуктивный шаг: предположите в качестве индукционной гипотезы, что в любой группе лошадей есть только один цвет. А теперь посмотрите на любую партию лошадей. Количество их:. Рассмотрим множества и. Каждая представляет собой набор только лошадей, поэтому внутри каждой только один цвет. Но эти два набора пересекаются, поэтому среди всех лошадей должен быть только один окрас. п {\ displaystyle n} п + 1 {\ displaystyle n + 1} 1 , 2 , 3 , , п , п + 1 {\ Displaystyle 1, \; 2, \; 3, \; \ dotsc, \; n, \; n + 1} { 1 , 2 , 3 , , п } {\ textstyle \ left \ {1, \; 2, \; 3, \; \ dotsc, \; n \ right \}} { 2 , 3 , 4 , , п + 1 } {\ textstyle \ left \ {2, \; 3, \; 4, \; \ dotsc, \; n + 1 \ right \}} п {\ displaystyle n} п + 1 {\ displaystyle n + 1}

Базовый случай тривиален (поскольку любая лошадь того же цвета, что и она сама), а индуктивный шаг верен во всех случаях. Однако логика индуктивного шага неверна из-за утверждения, что «два набора перекрываются» неверно (есть только лошади до удаления и после удаления, наборы по одной лошади не перекрываются). п знак равно 1 {\ displaystyle n = 1} п gt; 1 {\ displaystyle ngt; 1} п знак равно 1 {\ displaystyle n = 1} п + 1 знак равно 2 {\ Displaystyle п + 1 = 2}

Формализация

В логике второго порядка можно записать « аксиому индукции» следующим образом:

п ( п ( 0 ) k ( п ( k ) п ( k + 1 ) ) п ( п ( п ) ) ) {\ Displaystyle \ forall P {\ Bigl (} P (0) \ land \ forall k {\ bigl (} P (k) \ to P (k + 1) {\ bigr)} \ to \ forall n {\ bigl (} P (n) {\ bigr)} {\ Bigr)}},

где P (.) - переменная для предикатов, содержащих одно натуральное число, а k и n - переменные для натуральных чисел.

Другими словами, базовый случай P (0) и шаг индукции (а именно, что предположение индукции P ( k) влечет P ( k + 1)) вместе означают, что P ( n) для любого натурального числа n. Аксиома индукции утверждает справедливость вывода, что P ( n) выполняется для любого натурального числа n из базового случая и индуктивного шага.

Первый квантор в аксиоме распространяется на предикаты, а не на отдельные числа. Это квантор второго порядка, что означает, что эта аксиома сформулирована в логике второго порядка. Аксиоматизирующая арифметическая индукция в логике первого порядка требует схемы аксиом, содержащей отдельную аксиому для каждого возможного предиката. В статье Аксиомы Пеано содержится дальнейшее обсуждение этого вопроса.

Аксиома структурной индукции для натуральных чисел была впервые сформулирована Пеано, который использовал ее для определения натуральных чисел вместе со следующими четырьмя другими аксиомами:

  1. 0 - натуральное число.
  2. Функция-последователь s каждого натурального числа дает натуральное число ( s ( x) = x + 1).
  3. Функция преемника инъективна.
  4. 0 не в диапазоне от х.

В теории множеств ZFC первого порядка количественная оценка по предикатам не допускается, но все же можно выразить индукцию количественной оценкой по множествам:

А ( 0 А k N ( k А ( k + 1 ) А ) N А ) {\ Displaystyle \ forall A {\ Bigl (} 0 \ in A \ land \ forall k \ in \ mathbb {N} {\ bigl (} k \ in A \ to (k + 1) \ in A {\ bigr) } \ to \ mathbb {N} \ substeq A {\ Bigr)}}

A можно читать как набор, представляющий предложение и содержащий натуральные числа, для которых утверждение верно. Это не аксиома, а теорема, учитывая, что натуральные числа определяются на языке теории множеств ZFC аксиомами, аналогичными аксиомам Пеано.

Трансфинитная индукция
Основная статья: Трансфинитная индукция

Один вариант принципа полной индукции может быть обобщен для утверждений об элементах любого хорошо обоснованного множества, то есть множества с иррефлексивным отношением lt;, которое не содержит бесконечных убывающих цепочек. Каждый набор, представляющий порядковое число, хорошо обоснован, набор натуральных чисел является одним из них.

Применительно к хорошо обоснованному набору трансфинитную индукцию можно сформулировать как один шаг. Чтобы доказать, что утверждение P ( n) выполняется для каждого порядкового числа:

  1. Покажите для каждого порядкового числа n, что если P ( m) выполняется для всех m lt; n, то P ( n) также выполняется.

Эта форма индукции, применяемая к набору порядковых чисел (которые образуют хорошо упорядоченный и, следовательно, хорошо обоснованный класс), называется трансфинитной индукцией. Это важный метод доказательства в теории множеств, топологии и других областях.

Доказательства по трансфинитной индукции обычно различают три случая:

  1. когда n - минимальный элемент, т. е. нет элемента меньше n ;
  2. когда n имеет прямого предшественника, т. е. набор элементов, которые меньше n, имеет наибольший элемент;
  3. когда n не имеет прямого предшественника, т.е. n является так называемым предельным порядковым номером.

Строго говоря, в трансфинитной индукции нет необходимости доказывать базовый случай, потому что это пустой частный случай утверждения, что если P истинно для всех n lt; m, то P истинно для m. Это пусто верно именно потому, что не существует значений n lt; m, которые могли бы служить контрпримерами. Таким образом, частные случаи являются частными случаями общего случая.

Отношение к принципу хорошего порядка

Принцип математической индукции обычно формулируется как аксиома натуральных чисел; см. аксиомы Пеано. В контексте других аксиом Пеано он строго сильнее, чем принцип хорошего порядка. Предположим следующее:

  • Трихотомия аксиома: Для любых натуральных чисел п и т, п меньше или равна т тогда и только тогда, когда т не меньше п.
  • Для любого натурального числа п, п + 1, больше, чем п.
  • Для любого натурального числа n не может быть натурального числа между n и n + 1.
  • Натуральное число не может быть меньше нуля.

Затем можно доказать, что индукция, учитывая перечисленные выше аксиомы, влечет принцип хорошего порядка. Следующее доказательство использует полную индукцию и первую и четвертую аксиомы.

Доказательство. Предположим, что существует непустое множество натуральных чисел S, в котором нет наименьшего элемента. Пусть Р ( п) является утверждение, что п не в S. Тогда Р (0) верно, так как если бы это было ложно, то 0 является наименьшим элементом S. Кроме того, пусть n - натуральное число, и предположим, что P ( m) истинно для всех натуральных чисел m, меньших n + 1. Тогда, если P ( n + 1) ложно, n + 1 находится в S, таким образом, являясь минимальным элементом в S, противоречие. Таким образом, P ( n + 1) верно. Следовательно, по принципу полной индукции P ( n) выполняется для всех натуральных чисел n ; поэтому S пусто; противоречие. QED

« Числовая линия » для множества {(0, n): n ∈ ℕ} ∪ {(1, n): n ∈ ℕ}. Цифры относятся ко второму компоненту пар; первый может быть получен по цвету или местоположению.

С другой стороны, множество {(0, n): n ∈ ℕ} ∪ {(1, n): n ∈ ℕ}, показанное на рисунке, хорошо упорядочено лексикографическим порядком. Более того, за исключением аксиомы индукции, он удовлетворяет всем аксиомам Пеано, где константа Пеано 0 интерпретируется как пара (0,0), а функция преемника Пеано определяется на парах как succ ( x, n) = ( x, n + 1) для всех x ∈ {0,1} и n ∈ℕ. В качестве примера нарушения аксиомы индукции определим предикат P ( x, n) как ( x, n) = (0, 0) или ( x, n) = ( succ ( y, m)) для некоторого y ∈ {0,1} и m ∈ℕ. Тогда базовый случай P (0,0) тривиально верен, как и ступенчатый случай: если P ( x, n), то P ( succ ( x, n)). Однако P не верно для всех пар в наборе.

Аксиомы Пеано с принципом индукции однозначно моделируют натуральные числа. Замена принципа индукции на принцип хорошей упорядоченности позволяет создавать более экзотические модели, удовлетворяющие всем аксиомам.

В нескольких книгах и источниках ошибочно напечатано, что принцип хорошего порядка эквивалентен аксиоме индукции. В контексте других аксиом Пеано это не так, но в контексте других аксиом они эквивалентны; в частности, принцип хорошего порядка подразумевает аксиому индукции в контексте первых двух перечисленных выше аксиом и

  • Каждое натуральное число равно 0 или n + 1 для некоторого натурального числа n.

Распространенная ошибка во многих ошибочных доказательствах - это предположение, что n - 1 - единственное и точно определенное натуральное число, свойство, которое не подразумевается другими аксиомами Пеано.

Смотрите также
Примечания
использованная литература

Вступление

История

Последняя правка сделана 2024-01-01 11:34:42
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте