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

Математическую индукцию можно неформально проиллюстрировать, обратившись к последовательному эффекту падающих костяшек домино . ^[1]^[2]

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

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

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

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

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

История

В 370 г. до н. э. « Парменид » Платона , возможно, содержал следы раннего примера неявного индуктивного доказательства, ^[5] однако, самое раннее неявное доказательство с помощью математической индукции было написано аль-Караджи около 1000 г. н. э., который применил его к арифметическим последовательностям , чтобы доказать биномиальную теорему и свойства треугольника Паскаля . Хотя оригинальная работа была утеряна, на нее позже ссылался аль-Самаваль аль-Магриби в своем трактате аль-Бахир фи'л-джабр (Блестящий в алгебре) около 1150 г. н. э. ^[6]^[7]

Кац говорит в своей истории математики

Другая важная идея, введенная аль-Караджи и продолженная аль-Самавалем и другими, заключалась в идее индуктивного аргумента для работы с определенными арифметическими последовательностями. Таким образом, аль-Караджи использовал такой аргумент для доказательства результата о суммах кубов целых чисел, уже известных Ариабхате [...] Однако аль-Караджи не сформулировал общий результат для произвольного n . Он сформулировал свою теорему для конкретного целого числа 10 [...] Тем не менее, его доказательство было явно разработано так, чтобы его можно было распространить на любое другое целое число. [...] Аргумент аль-Караджи по сути включает два основных компонента современного аргумента по индукции, а именно истинность утверждения для n = 1 (1 = 1 ³ ) и вывод истинности для n = k из истинности для n = k - 1. Конечно, этот второй компонент не является явным, поскольку в некотором смысле аргумент аль-Караджи является обратным; то есть он начинает с n = 10 и идет вниз к 1, а не идет вверх. Тем не менее, его аргумент в аль-Фахри является самым ранним сохранившимся доказательством формулы суммы для целых кубов . ^[8]

В Индии ранние неявные доказательства с помощью математической индукции появляются в « циклическом методе » Бхаскары . ^[9]

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

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

Гипотеза индукции также использовалась швейцарцем Якобом Бернулли , и с тех пор она стала широко известна. Современное формальное рассмотрение принципа появилось только в 19 веке, с Джорджем Булем , ^[13] Августом Де Морганом , Чарльзом Сандерсом Пирсом , ^[14]^[15] Джузеппе Пеано и Ричардом Дедекиндом . ^[9]

Описание

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

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

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

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

Примеры

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

Математическая индукция может быть использована для доказательства следующего утверждения $P (n)$ для всех натуральных чисел $n$ . $P(n)\!:\ \ 0+1+2+\cdots +n={\frac {n(n+1)}{2}}.$

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

Предложение. Для каждого, $n\in \mathbb {N}$ $0+1+2+\cdots +n={\tfrac {n(n+1)}{2}}.$

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

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

$P (0)$ очевидно истинен: $0={\tfrac {0(0+1)}{2}}\,.$

Шаг индукции: показать, что для любого $k \geq 0$ , если $P (k)$ выполняется, то $P (k + 1)$ также выполняется.

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

Алгебраически правая часть упрощается следующим образом: ${\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}}$

Приравнивая крайние левую и правую части, мы заключаем, что: То есть утверждение $P$ $($ $k$ $+ 1)$ также верно, что устанавливает шаг индукции. $0+1+2+\cdots +k+(k+1)={\frac {(k+1)((k+1)+1)}{2}}.$

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

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

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

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

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

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

Базовый вариант: Расчет подтверждает . $\left|\sin 0x\right|=0\leq 0=0\left|\sin x\right|$ $P(0)$

Шаг индукции: Мы показываем импликацию для любого натурального числа . Предположим гипотезу индукции: для данного значения единственный случай верен. Используя формулу сложения углов и неравенство треугольника , мы выводим: $P(k)\подразумевает P(k+1)$ $к$ $n=k\geq 0$ $P(k)$ ${\begin{aligned}\left|\sin(k+1)x\right|&=\left|\sin kx\cos x+\sin x\cos kx\right|&&{\text{(сложение углов)}}\\&\leq \left|\sin kx\cos x\right|+\left|\sin x\,\cos kx\right|&&{\text{(неравенство треугольника)}}\\&=\left|\sin kx\right|\left|\cos x\right|+\left|\sin x\right|\left|\cos kx\right|\\&\leq \left|\sin kx\right|+\left|\sin x\right|&&(\left|\cos t\right|\leq 1)\\&\leq k\left|\sin x\right|+\left|\sin x\right|&&{\text{(индукционная гипотеза}})\\&=(k+1)\left|\sin x\right|.\end{aligned}}$

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

Заключение: Предложение справедливо для всех натуральных чисел QED $P(n)$ $сущ.$

Варианты

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

Базовый вариант, отличный от 0 или 1

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

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

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

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

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

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

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

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

Следовательно, по принципу индукции, $S (k)$ справедливо для всех $k \geq 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$ .

Ограниченная математическая индукция

Если кто-то хочет доказать, что свойство $P$ справедливо для всех натуральных чисел, меньших или равных $n$ , то достаточно доказать, что $P$ удовлетворяет следующим условиям: ^[17]

$P$ справедливо для 0,
Для любого натурального числа $x,$ меньшего $n$ , если $P$ справедливо для $x$ , то $P$ справедливо для $x + 1.$

Введение префикса

Наиболее распространенная форма доказательства методом математической индукции требует доказательства на этапе индукции того, что $\forall k\,(P(k)\to P(k+1))$

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

Вариантом, представляющим интерес для вычислительной сложности, является «префиксная индукция», в которой на шаге индукции доказывается следующее утверждение: или, что эквивалентно, $\forall k\,(P(k)\to P(2k)\land P(2k+1))$ $\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]

Можно развить эту идею на шаг дальше: нужно доказать , после чего принцип индукции «автоматизирует» $log log$ $n$ применений этого вывода для перехода от $P$ $(0)$ к $P$ $($ $n$ $)$ . Эта форма индукции использовалась, аналогично, для изучения параллельных вычислений в режиме log-time. ^[^{необходима цитата}^] $\forall k\,\left(P\!\left(\left\lfloor {\sqrt {k}}\right\rfloor \right)\to P(k)\right)$

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

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

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

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

Эквивалентность с обычной индукцией

Полная индукция эквивалентна обычной математической индукции, как описано выше, в том смысле, что доказательство одним методом может быть преобразовано в доказательство другим. Предположим, что существует доказательство полной индукцией. Тогда это доказательство может быть преобразовано в обычное индукционное доказательство, предположив более сильную индуктивную гипотезу. Пусть будет утверждением « справедливо для всех таких, что » — это становится индуктивной гипотезой для обычной индукции. Затем мы можем показать и для предположения только и показать, что влечет . ^[19] $P(n)$ $Q(n)$ $P(m)$ $m$ $0\leq m\leq n$ $Q(0)$ $Q(n+1)$ $n\in \mathbb {N}$ $Q(n)$ $Q(n)$ $P(n)$

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

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

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

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

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

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

Мы попытаемся доказать тот же пример, что и выше, на этот раз с помощью сильной индукции . Утверждение остается прежним: $S(n):\,\,n\geq 12\implies \,\exists \,a,b\in \mathbb {N} .\,\,n=4a+5b$

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

Доказательство.

Базовый случай: Покажите, что справедливо для . $S(k)$ $k=12,13,14,15$ ${\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}}$

Базовый вариант сохраняется.

Шаг индукции: Дано некоторое , предположим, что выполняется для всех с . Докажите, что выполняется. $j>15$ $S(m)$ $m$ $12\leq m<j$ $S(j)$

Выбор и наблюдение показывает, что выполняется, по индуктивной гипотезе. То есть, сумма может быть образована некоторой комбинацией и долларовых монет. Тогда простое добавление долларовой монеты к этой комбинации дает сумму . То есть выполняется ^[20] QED $m=j-4$ $15<j\implies 12\leq j-4<j$ $S(j-4)$ $j-4$ $4$ $5$ $4$ $j$ $S(j)$

Индукция вперед-назад

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

Пример ошибки на шаге индукции

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

Базовый случай: в наборе, состоящем только из одной лошади, есть только один цвет.

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

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

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

В логике второго порядка можно записать « аксиому индукции» следующим образом: где $P$ $(\cdot)$ — переменная для предикатов, включающих одно натуральное число, а $k$ и $n$ — переменные для натуральных чисел . $\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 (0)$ и шаг индукции (а именно, что гипотеза индукции $P (k)$ подразумевает $P (k + 1)$ ) вместе подразумевают, что $P (n)$ для любого натурального числа $n$ . Аксиома индукции утверждает справедливость вывода того, что $P (n)$ выполняется для любого натурального числа $n$ из базового случая и шага индукции.

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

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

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

В теории множеств ZFC первого порядка квантификация по предикатам не допускается, но индукцию все еще можно выразить квантификацией по множествам: $A$ можно читать как множество, представляющее предложение и содержащее натуральные числа, для которых предложение верно. Это не аксиома, а теорема, учитывая, что натуральные числа определяются на языке теории множеств ZFC аксиомами, аналогичными аксиомам Пеано. См. построение натуральных чисел с использованием аксиомы бесконечности и схему аксиом спецификации . $\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 )}$

Трансфинитная индукция

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

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

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

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

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

когда $n$ — минимальный элемент, т.е. нет элемента меньше $n$ ;
когда $n$ имеет прямого предшественника, т.е. множество элементов, которые меньше $n,$ имеет наибольший элемент;
когда $n$ не имеет прямого предшественника, т.е. $n$ является так называемым предельным ординалом .

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

Связь с принципом благоустройства

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

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

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

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

" Числовая прямая " для множества

@media screen{html.skin-theme-clientpref-night .mw-parser-output div:not(.notheme)>.tmp-color,html.skin-theme-clientpref-night .mw-parser-output p>.tmp-color,html.skin-theme-clientpref-night .mw-parser-output table:not(.notheme) .tmp-color{color:inherit!important}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output div:not(.notheme)>.tmp-color,html.skin-theme-clientpref-os .mw-parser-output p>.tmp-color,html.skin-theme-clientpref-os .mw-parser-output table:not(.notheme) .tmp-color{color:inherit!important}} {(0, n): n \in N} \cup {(1, n): n \in N}

. Числа относятся ко второму компоненту пар; первый может быть получен из цвета или местоположения.

С другой стороны, множество , показанное на рисунке, является вполне упорядоченным ^[24]^{: 35lf} по лексикографическому порядку . Более того, за исключением аксиомы индукции, оно удовлетворяет всем аксиомам Пеано, где константа Пеано 0 интерпретируется как пара (0, 0), а функция преемника Пеано определяется на парах как $succ($ $x$ $,$ $n$ $) = ($ $x$ $,$ $n$ $+ 1)$ для всех и . В качестве примера нарушения аксиомы индукции определим предикат $P$ $($ $x$ $,$ $n$ $)$ как $($ $x$ $,$ $n$ $) = (0, 0)$ или $($ $x$ $,$ $n$ $) = succ($ $y$ $,$ $m$ $)$ для некоторых и . Тогда базовый случай $P$ $(0, 0)$ тривиально истинен, и поэтому шаг индукции: если $P$ $($ $x$ $,$ $n$ $)$ , то $P$ $(succ($ $x$ $,$ $n$ $))$ . Однако $P$ не является истинным для всех пар в наборе, поскольку $P$ $(1,0)$ является ложным. $\{(0,n):n\in \mathbb {N} \}\cup \{(1,n):n\in \mathbb {N} \}$ $x\in \{0,1\}$ $n\in \mathbb {N}$ $y\in \{0,1\}$ $m\in \mathbb {N}$

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

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

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

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

Смотрите также

Примечания

^ Мэтт ДеВос, Математическая индукция, Университет Саймона Фрейзера
↑ Херардо кон Диас, Математическая индукция. Архивировано 2 мая 2013 г. в Wayback Machine , Гарвардский университет.
^ Андерсон, Роберт Б. (1979). Доказательство корректности программ . Нью-Йорк: John Wiley & Sons. стр. 1. ISBN 978-0471033950.
^ Субер, Питер. «Математическая индукция». Earlham College. Архивировано из оригинала 24 мая 2011 года . Получено 26 марта 2011 года .
^ Ачерби 2000.
↑ Рашед 1994, стр. 62–84.
^ Математические знания и взаимодействие практик «Самое раннее неявное доказательство с помощью математической индукции было дано около 1000 г. в работе персидского математика Аль-Караджи»
^ Кац (1998), стр. 255
^ ab Cajori (1918), стр. 197: «Процесс рассуждения, называемый «математической индукцией», имел несколько независимых истоков. Он восходит к швейцарцу Якобу (Джеймсу) Бернулли, французам Б. Паскалю и П. Ферма и итальянцу Ф. Мавролику. [...] Читая немного между строк, можно найти следы математической индукции еще раньше, в трудах индусов и греков, как, например, в «циклическом методе» Бхаскары и в доказательстве Евклида того, что число простых чисел бесконечно».
↑ Рашед 1994, стр. 62.
^ Саймонсон 2000.
^ Рабинович 1970.
^ "Иногда требуется доказать теорему, которая будет истинной всякий раз, когда определенная величина n , которая в нее включена, будет целым числом, и метод доказательства обычно имеет следующий вид. 1-й . Доказывается, что теорема истинна, когда n = 1. 2 -й . Доказывается, что если теорема истинна, когда n — данное целое число, то она будет истинна, если n — следующее большее целое число. Следовательно, теорема истинна универсально. … Этот вид аргумента можно назвать непрерывным соритом " (Буль около 1849 г. Элементарный трактат по логике, не математический , стр. 40–41, перепечатано в Grattan-Guinness, Ivor and Bornet, Gérard (1997), George Boole: Selected Manuscripts on Logic and its Philosophy , Birkhäuser Verlag, Berlin, ISBN 3-7643-5456-9 )
↑ Пирс 1881.
^ Шилдс 1997.
^ Тед Сандстром, Математическое рассуждение , стр. 190, Пирсон, 2006, ISBN 978-0131877184
^ Smullyan, Raymond (2014). Руководство для начинающих по математической логике . Довер. стр. 41. ISBN 0486492370.
^ Бусс, Сэмюэл (1986). Ограниченная арифметика . Неаполь: Библиополис.
^ "Доказательство: Сильная индукция эквивалентна слабой индукции". Корнелльский университет . Получено 4 мая 2023 г.
^ . Шафии, Нилуфар. "Сильная индукция и хорошее упорядочение" (PDF) . Йоркский университет . Получено 28 мая 2023 г. .
^ "Прямая-обратная индукция | Brilliant Math & Science Wiki". brilliant.org . Получено 23 октября 2019 г. .
^ Коши, Огюстен-Луи (1821). Cours d'analyse de l'École Royale Polytechnique, première partie, Analyse algébrique, Архивировано 14 октября 2017 г. в Wayback Machine Paris. Доказательство неравенства арифметических и геометрических средних можно найти на страницах 457ff.
^ Коэн, Джоэл Э. (1961). «О природе математического доказательства». Opus .. Перепечатано в книге «Случайное блуждание в науке» (ред. Р. Л. Вебер), Crane, Russak & Co., 1973.
^ abcde Öhman, Lars–Daniel (6 мая 2019 г.). «Эквивалентны ли индукция и хорошее упорядочение?». The Mathematical Intelligencer . 41 (3): 33–40. doi : 10.1007/s00283-019-09898-4 .

Ссылки

Введение

Франклин, Дж.; Дауд, А. (2011). Доказательство в математике: Введение. Сидней: Kew Books. ISBN 978-0-646-54509-7.(Гл. 8.)
«Математическая индукция». Энциклопедия математики . EMS Press . 2001 [1994].
Гермес, Ганс (1973). Введение в математическую логику . Hochschultext. Лондон: Springer. ISBN 978-3540058199. ISSN 1431-4657. MR 0345788.
Кнут, Дональд Э. (1997). Искусство программирования, том 1: Фундаментальные алгоритмы (3-е изд.). Эддисон-Уэсли. ISBN 978-0-201-89683-1.(Раздел 1.2.1: Математическая индукция, стр. 11–21.)
Колмогоров, Андрей Н.; Фомин , Сергей В. (1975). Вводный реальный анализ. Silverman, RA (перевод, ред.). Нью-Йорк: Довер. ISBN 978-0-486-61226-3.(Раздел 3.8: Трансфинитная индукция, стр. 28–29.)

История

Ачерби, Фабио (август 2000 г.). «Платон: Парменид 149a7-c3. Доказательство полной индукцией?». Архив истории точных наук . 55 (1): 57–76. doi :10.1007/s004070000020. JSTOR 41134098. S2CID 123045154.
Bussey, WH (1917). «Происхождение математической индукции». The American Mathematical Monthly . 24 (5): 199–207. doi :10.2307/2974308. JSTOR 2974308.
Каджори, Флориан (1918). «Происхождение названия «Математическая индукция»". Американский математический ежемесячник . 25 (5): 197–201. doi :10.2307/2972638. JSTOR 2972638.
Фаулер, Д. (1994). «Могли ли греки использовать математическую индукцию? Использовали ли они ее?». Physis . 31 : 253–265.
Фрейденталь, Ганс (1953). «Zur Geschichte der vollständigen Induction». Международные архивы истории наук . 6 : 17–37.
Katz, Victor J. (1998). История математики: Введение . Addison-Wesley . ISBN 0-321-01618-1.
Пирс, Чарльз Сандерс (1881). «О логике чисел». American Journal of Mathematics . 4 (1–4): 85–95. doi :10.2307/2369151. JSTOR 2369151. MR 1507856.Перепечатано (CP 3.252–288), (W 4:299–309)
Рабинович, Нахум Л. (1970). «Раввин Леви Бен Гершон и истоки математической индукции». Архив истории точных наук . 6 (3): 237–248. doi :10.1007/BF00327237. MR 1554128. S2CID 119948133.
Рашед, Рошди (1972). «L'induction mathématique: al-Karajī, as-Samaw'al». Архив истории точных наук (на французском). 9 (1): 1–21. doi :10.1007/BF00348537. MR 1554160. S2CID 124040444.
Рашед, Р. (1994). «Математическая индукция: аль-Караджи и аль-Самаваль». Развитие арабской математики: между арифметикой и алгеброй. Boston Studies in the Philosophy of Science. Том 156. Springer Science & Business Media. ISBN 9780792325659.
Shields, Paul (1997). "Аксиоматизация арифметики Пирса". В Houser, Nathan; Roberts, Don D.; Evra, James Van (ред.). Исследования по логике Чарльза С. Пирса . Indiana University Press. стр. 43–52. ISBN 0-253-33020-3. МР 1720827.
Симонсон, Чарльз Г. (зима 2000 г.). «Математика Леви бен Гершона, Ралбаг» (PDF) . Бекхол Дерахеха Дэху . 10. Издательство Университета Бар-Илан: 5–21.
Унгуру, С. (1991). «Греческая математика и математическая индукция». Physis . 28 : 273–289.
Унгуру, С. (1994). «Охота на птиц после индукции». Physis . 31 : 267–272.
Вакка, Г. (1909). «Мавролик, первый открыватель принципа математической индукции». Бюллетень Американского математического общества . 16 (2): 70–73. doi : 10.1090/S0002-9904-1909-01860-9 . MR 1558845.
Ядегари, Мохаммад (1978). «Использование математической индукции Абу Камилом Шуджой ибн Асламом (850-930)». Isis . 69 (2): 259–262. doi :10.1086/352009. JSTOR 230435. S2CID 144112534.