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

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

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

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

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

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

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

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

История [ править ]

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

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

Однако ни один из этих древних математиков явно не высказал гипотезы индукции. Другой подобный случай (вопреки тому , что написано Вакка как Фрейденталя тщательно показал) ^[11] , что из Мавролико в его Arithmeticorum Либри дуэт (1575), который использовал технику , чтобы доказать , что сумма первых п нечетных целых чисел п ² .

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

Гипотеза индукции также использовалась швейцарцем Якобом Бернулли , и с тех пор она стала широко известной. Современная формальная трактовка принципа пришли только в 19 - м веке, с Джорджем Буля , ^[14] Огастес де Морган , Чарльз Сандерс Пирс , ^{[15] [16]} Пеано и Дедекинд . ^[8]

Описание [ править ]

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

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

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

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

Примеры [ править ]

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

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

${\ Displaystyle P (n) \!: \ \ 0 + 1 + 2 + \ cdots + n \, = \, {\ frac {n (n + 1)} {2}}.}$

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

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

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

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

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

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

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

${\ displaystyle 0 + 1 + \ cdots + k \ = \ {\ frac {k (k {+} 1)} {2}}.}$

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

${\ displaystyle (0 + 1 + 2 + \ cdots + k) + (k {+} 1) \ = \ {\ frac {k (k {+} 1)} {2}} + (k {+} 1 ).}$

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

${\ displaystyle {\ begin {align} {\ frac {k (k {+} 1)} {2}} + (k {+} 1) & \ = \ {\ frac {k (k {+} 1) +2 (k {+} 1)} {2}} \\ & \ = \ {\ frac {(k {+} 1) (k {+} 2)} {2}} \\ & \ = \ { \ frac {(k {+} 1) ((k {+} 1) +1)} {2}}. \ end {align}}}$

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

${\displaystyle 0+1+2+\cdots +k+(k{+}1)\ =\ {\frac {(k{+}1)((k{+}1)+1)}{2}}.}$

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

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

Тригонометрическое неравенство [ править ]

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

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

Предложение . Для любого, . ${\displaystyle x\in \mathbb {R} ,n\in \mathbb {N} }$${\displaystyle |\!\sin nx|\leq n\,|\!\sin x|}$

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

Базовый случай: расчетподтверждается. ${\displaystyle |\!\sin 0x|=0\leq 0=0\,|\!\sin x|}$${\displaystyle P(0)}$

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

${\displaystyle {\begin{array}{rcll}|\sin(k{+}1)x|&=&|\sin kx\,\cos x+\sin x\,\cos kx\,|&{\text{(angle addition)}}\\&\leq &|\!\sin kx\,\cos x|+|\!\sin x\,\cos kx|&{\text{(triangle inequality)}}\\&=&|\!\sin kx|\,|\!\cos x|+|\!\sin x|\,|\!\cos kx|&\\&\leq &|\!\sin kx|+|\!\sin x|&(\,|\!\cos t|\leq 1)\\&\leq &k\,|\!\sin x|+|\!\sin x|&{\text{(induction hypothesis}})\\&\ =\ &(k{+}1)\,|\!\sin x|.&\end{array}}}$

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

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

Варианты [ править ]

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

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

Основание индукции кроме 0 или 1 [ править ]

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

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

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

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

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

Предположим, бесконечный запас 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 .${\textstyle k\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 .

Индукция префикса [ править ]

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

${\displaystyle \forall k(P(k)\to P(k+1))}$

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

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

${\displaystyle \forall k(P(k)\to P(2k)\land P(2k+1))}$

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

${\displaystyle \forall k\left(P\left(\left\lfloor {\frac {k}{2}}\right\rfloor \right)\to P(k)\right)}$

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

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

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

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

${\displaystyle \forall k\left(P\left(\left\lfloor {\sqrt {k}}\right\rfloor \right)\to P(k)\right)}$

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

Полная (сильная) индукция [ править ]

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

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

Хотя только что описанная форма требует доказательства базового случая, в этом нет необходимости, если можно доказать P ( m ) (предполагая P ( n ) для всех нижних n ) для всех m ≥ 0 . Это частный случай трансфинитной индукции, описанный ниже. В этой форме базовый случай подпадает под случай m = 0 , где P (0) доказано без каких-либо других предположений P ( n ); этот случай, возможно, придется рассматривать отдельно, но иногда тот же аргумент применяется для m  = 0 и m > 0, делая доказательство более простым и элегантным. В этом методе, однако, важно убедиться, что доказательство P ( m ) не предполагает неявно, что m > 0 , например, говоря «выберите произвольное n < m », или предполагая, что набор из m элементов имеет элемент.

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

Пример: числа Фибоначчи [ править ]

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

${\displaystyle F_{n}={\frac {\varphi ^{n}-\psi ^{n}}{\varphi -\psi }}}$

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

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

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

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

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

${\displaystyle S(n):\,\,n\geq 12\to \,\exists \,a,b\in \mathbb {N} .\,\,n=4a+5b}$

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

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

${\displaystyle {\begin{aligned}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\end{aligned}}}$

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

Гипотеза индукции : для некоторых предположение верно для всех с .${\displaystyle j>15}$${\displaystyle S(m)}$${\displaystyle m}$${\displaystyle 12\leq m<j}$

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

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

Прямая-обратная индукция [ править ]

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

Пример ошибки на индуктивном шаге [ править ]

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

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

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

Формализация [ редактировать ]

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

${\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 первого порядка количественная оценка по предикатам не допускается, но все же можно выразить индукцию количественной оценкой по множествам:

${\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} \subseteq A{\Bigr )}}$

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

Трансфинитная индукция [ править ]

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

Применительно к хорошо обоснованному набору его можно сформулировать как один шаг:

1. Покажите, что если какое-то утверждение верно для всех m < n , то то же самое утверждение верно и для n .

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

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

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

Строго говоря, в трансфинитной индукции нет необходимости доказывать базовый случай, потому что это пустой частный случай утверждения, что если P истинно для всех n < m , то P истинно для m . Это пусто верно именно потому, что не существует значений n < 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, п ): п ∈ ℕ} ∪ {(1, п ): п ∈ ℕ} , как показано на рисунке, хорошо упорядоченная ^{[22] : 35lf} в лексикографическом порядке . Более того, за исключением аксиомы индукции, он удовлетворяет всем аксиомам Пеано, где константа Пеано 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 не верно для всех пар в наборе.

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

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

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

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

См. Также [ править ]

• Комбинаторное доказательство
• Индукционные пазлы
• Доказательство истощением
• Рекурсия
• Рекурсия (информатика)
• Структурная индукция
• Трансфинитная индукция

Заметки [ править ]

Ссылки [ править ]