Индукция это в математике: МАТЕМАТИЧЕСКАЯ ИНДУКЦИЯ – Метод математической индукции

Содержание

Индукция — Википедия

Материал из Википедии — свободной энциклопедии

Текущая версия страницы пока не проверялась опытными участниками и может значительно отличаться от версии, проверенной 8 января 2020; проверки требует 1 правка. Текущая версия страницы пока не проверялась опытными участниками и может значительно отличаться от версии, проверенной 8 января 2020; проверки требует 1 правка.

Инду́кция (из лат. inductio «выведение, наведение») — широко используемый в науке термин.

В логике
  • Индуктивное умозаключение — метод рассуждения от частного к общему.
    • Полная индукция — метод доказательства, при котором утверждение доказывается для конечного числа частных случаев, исчерпывающих все возможности.
    • Неполная индукция — наблюдения за отдельными частными случаями наводит на гипотезу, которая нуждается в доказательстве[1].
  • Математическая индукция — метод доказательства для последовательности натуральных чисел либо объектов, однозначно занумерованных натуральными числами.
В философии
В физике
В экономике
  • Индукция — это вид обобщения, связанный с предвосхищением результатов наблюдений и экспериментов на основе данных опыта. В индукции данные опыта «наводят» на общее, поэтому индуктивные обобщения рассматриваются обычно как опытные истины или эмпирические законы. Изучая финансово-хозяйственную деятельность ряда типичных российских предприятий, можно делать, например, выводы о закономерностях развития совокупности предприятий.
В юридических науках
  • Индуктивный метод — способ исследования и изложения, при котором от наблюдаемых частных фактов переходят к выделению принципов, общих положений теории, установлению закономерностей.
В медицине и биологии
В химии
  • Химическая индукция — совместное протекание двух химических реакций, из которых одна обусловливает или ускоряет вторую.

Обсуждение:Математическая индукция — Википедия

Материал из Википедии — свободной энциклопедии

Индукционный или индуктивный[править код]

я не слышал чтоб индукционный переход называли индуктивным, по-моему это ошибка. —Tosha 04:37, 29 Дек 2004 (UTC)

раз никто не против, я исправлю —Tosha 20:11, 7 Май 2005 (UTC)

Перевод с английской википедии[править код]

Я начал переводит с английской википедии. Буду потихоньку добавлять. Буду признателен, если кто-то подправить формулировки. Alexsmail 18:52, 3 мая 2008 (UTC)

Alexsmail, нужно писать по-русски, Вы этого не делаете! Если Вам нужно время подготовьте всё это в своей песочнице, (см. Википедия:Как править статьи). Я откатываю.—Тоша 11:11, 17 мая 2008 (UTC)
Я надеялся на то, что кто-нибудь будет меня подправлять. Ладно, не буду встревать в бессмысленную перепалку. Жалко, конечно, в английской вики такая качественная статья (точнее набор статей). Быть может кто-нибудь прочитает это обсуждение и подхватит эстафету. Если таковой найдётся и захочет моей помощи — пусть напишет на моей странице. Alexsmail 19:26, 20 мая 2008 (UTC)

Специально для анонима, пытающегося выкинуть требование истинности P1{\displaystyle P_{1}} из принципа полной матиндукции. Возмите в качестве всех Pi{\displaystyle P_{i}} одно и то же неверное утверждение, например, «2×2=5», и примените к этой последовательности принцип полной матиндукции в своей формулировке. Предпосылка будет верна и повлечет истинность всех утверждений в последовательности, что есть абсурд. Maxal 16:22, 13 января 2011 (UTC)

  • Специально для сделавшего надоедливый неграмотный троекратный откат подряд пользователя Maxal. Предлагаю внимательно вчитаться и вдуматься, а не заниматься ерундой. Если имеется пробел в математическом образовании, то следовало бы хотя бы самостоятельно попытаться понять, почему база индукции является частным случаем посылки в такой форме. Следующее предложение, которое тщательно без разбору удаляется, не зря обращает на это внимание.78.140.138.9 20:47, 13 января 2011 (UTC)
    • Приведите сначала свои реплики в соответствие с ВП:ЭП. Maxal 03:37, 14 января 2011 (UTC)
  • Посылка будет ложной при n=1{\displaystyle n=1}. Никакого абсурда нет.85.250.144.47 22:51, 13 января 2011 (UTC)
    • OK, убедили, но это чрезмерный формализм, который легко может ввести в заблуждение и нивелирует сущность полной матиндукции. Maxal 03:37, 14 января 2011 (UTC)
      • Непонимание какой-либо темы отдельными людьми нивелирует сущность этой темы? Нет уж! Кроме того, специально для недостаточно вдумчивых читателей сразу были добавлены дополнительные пояснения (а для ещё более невдумчивых их пришлось расширить). Да и удаление избыточного никогда не считалось чрезмерным формализмом. Более того, добавление ненужной базы индукции нивелирует логическую ценность полной матиндукции как не требующей базы. Хочу отметить, что если бы заблуждение выразилось лишь в единичной ошибке, исправление которой привело бы к обдумыванию, а не к настойчивым кратным откатам, то это было бы простительно.89.139.162.201 23:55, 14 января 2011 (UTC)
  • Всё ещё следующий текст некорректен: при n=1{\displaystyle n=1} импликация (∀i∈{1;…;n−1})Pi⟶Pn{\displaystyle (\forall i\in \{1;\dots ;n-1\})P_{i}\longrightarrow P_{n}} эквивалентна P1{\displaystyle P_{1}}.
    При n=1{\displaystyle n=1} {1;…;n−1}={1;…;0}=∅{\displaystyle \{1;\dots ;n-1\}=\{1;\dots ;0\}=\varnothing }, пустому множеству не принадлежит никакое i{\displaystyle i}, и из ничего вывести истину нельзя.
    —Basil Peace 19:49, 4 сентября 2013 (UTC)

Ошибка? Принцип полной математической индукции[править код]

(∀n∈N)((∀i∈{1;…;n−1})Pi⟶Pi+1)⟶(∀n∈N)Pn{\displaystyle (\forall n\in {\mathbb {N} }){\Big (}(\forall i\in \{1;\dots ;n-1\})P_{i}\longrightarrow P_{i+1}{\Big )}\longrightarrow (\forall n\in {\mathbb {N} })P_{n}}.

Разве не должно быть так: (∀n∈N)((∀i∈{1;…;n−1})Pi⟶Pn)⟶(∀n∈N)Pn{\displaystyle (\forall n\in {\mathbb {N} }){\Big (}(\forall i\in \{1;\dots ;n-1\})P_{i}\longrightarrow P_{n}{\Big )}\longrightarrow (\forall n\in {\mathbb {N} })P_{n}}.

математическая индукция — с русского на английский

См. также в других словарях:

  • МАТЕМАТИЧЕСКАЯ ИНДУКЦИЯ — полная математическая индукция (наз. в математике часто просто полной индукцией; в этом случае это понятие следует отличать от рассматриваемого в нематематич. формальной логике понятия полной индукции), – прием доказательства общих предложений в… …   Философская энциклопедия

  • МАТЕМАТИЧЕСКАЯ ИНДУКЦИЯ — МАТЕМАТИЧЕСКАЯ индукция, способ доказательства или определения некоторого свойства A для всех n случаев, основанный на переходе заключения о наличии свойства A от n к n+1. Математическая индукция состоит из двух этапов: установление A для… …   Современная энциклопедия

  • МАТЕМАТИЧЕСКАЯ ИНДУКЦИЯ — общий способ математического доказательства или определения некоторого свойства А для всех натуральных n, основанный на заключении от n к n+1. Математическая индукция состоит из двух этапов: а) установление А для некоторого начального n0; б)… …   Большой Энциклопедический словарь

  • Математическая индукция — МАТЕМАТИЧЕСКАЯ ИНДУКЦИЯ, способ доказательства или определения некоторого свойства A для всех n случаев, основанный на переходе заключения о наличии свойства A от n к n+1. Математическая индукция состоит из двух этапов: установление A для… …   Иллюстрированный энциклопедический словарь

  • МАТЕМАТИЧЕСКАЯ ИНДУКЦИЯ — МАТЕМАТИЧЕСКАЯ ИНДУКЦИЯ, метод, доказывающий, что математическое утверждение верно для любого положительного целого числа п, если выполняются два условия: 1) оно верно для основной величины, например, 1, и 2) если оно верно для значения k, то… …   Научно-технический энциклопедический словарь

  • Математическая индукция — Математическая индукция  один из методов математического доказательства, используется чтобы доказать истинность некоторого утверждения для всех натуральных чисел. Для этого сначала пров …   Википедия

  • математическая индукция — общий способ математического доказательства или определения некоторого свойства А для всех натуральных n, основанный на заключении от n к n + 1, математическая индукция состоит из двух этапов: а) установление А для некоторого начального n0;… …   Энциклопедический словарь

  • МАТЕМАТИЧЕСКАЯ ИНДУКЦИЯ — метод доказательства математич. утверждений, основанный на принципе математической индукции: утверждение (х), зависящее от натурального параметра х, считается доказанным, если доказано А(1) и для любого натурального пиз предположения, что верно… …   Математическая энциклопедия

  • Математическая индукция —         весьма общий способ математических доказательств и определений. Индуктивные доказательства основаны на так называемом принципе М. и., являющемся одной из основных математических аксиом. Пусть, например, требуется доказать для любого… …   Большая советская энциклопедия

  • МАТЕМАТИЧЕСКАЯ ИНДУКЦИЯ — общий спо соб матем. доказательства или определения нек рого свойства А для всех натуральных п, основанный на заключении от п к n +1, М. и. состоит из двух этапов: а) установление А для нек рого начального no; б) обоснование перехода от n к п + 1 …   Естествознание. Энциклопедический словарь

  • Индукция Математическая, Полная Математическая Индукция — а средство доказательства общих положений в матемантике и др. дедуктивных науках. Этот прием опирается на использованние двух суждений. Первое представляет собой единичное суждение и наз. базой индукции. В нем доказывается, что 1 обладает… …   Словарь терминов логики


Математическая индукция — это… Что такое Математическая индукция?

Dominoeffect.png

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

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

Формулировка

Предположим, что требуется установить справедливость бесконечной последовательности утверждений, занумерованных натуральными числами: .

Допустим, что

  1. Установлено, что верно. (Это утверждение называется базой индукции.)
  2. Для любого n доказано, что если верно , то верно . (Это утверждение называется индукционным переходом.)

Тогда все утверждения нашей последовательности верны.


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

Принцип полной математической индукции

Существует также вариация, так называемый принцип полной математической индукции. Вот его строгая формулировка:

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

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

Принцип полной математической индукции также эквивалентен аксиоме индукции в аксиомах Пеано.

История

Осознание метода математической индукции как отдельного важного метода восходит к Блезу Паскалю и Герсониду, хотя отдельные случаи применения встречаются ещё в античные времена у Прокла и Эвклида[1]. Современное название метода было введено де Морганом в 1838 году.

Примеры

Задача. Доказать, что, каковы бы ни были натуральное n и вещественное q ≠ 1, выполняется равенство

Доказательство. Индукция по n.

База, n = 1:

Переход: предположим, что

тогда

,

что и требовалось доказать.

Комментарий: верность утверждения в этом доказательстве — то же, что верность равенства

Вариации и обобщения

Примечания

  1. Nachum L. Rabinovih Раби Леви бен Гершом и происхождение метода математической индукции = Rabbi Levi ben Gershom and the origins of mathematical induction // Archive for History of Exact Sciences. — 1970. — В. 6. — С. 237-248.

Литература

Ссылки

  • Видео по методу математической индукции

Структурная индукция — Википедия

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

Изначально[⇨] метод использовался в математической логике, также нашёл применение[⇨] в теории графов, комбинаторике, общей алгебре, математической лингвистике, но наибольшее распространение как самостоятельно изучаемый метод получил в теоретической информатике[1], где применяется в вопросах семантики языков программирования, формальной верификации, вычислительной сложности, функционального программирования.

В отличие от нётеровой индукции — наиболее общей формы математической индукции, применяемой над произвольными фундированными множествами, — в понятии о структурной индукции подразумевается конструктивный характер, вычислительная реализация. При этом фундированность совокупности — свойство, необходимое для рекурсивной определяемости[2], таким образом, структурную рекурсию можно считать частным вариантом нётеровой индукции[1].

Использование метода встречается по крайней мере с 1950-х годов, в частности, в доказательстве теоремы Лося об ультрапроизведениях применяется индукция по построению формулы, при этом сам метод особым образом явно не назывался[3]. В те же годы метод применялся в теории моделей для доказательств над цепями моделей, считается, что появление термина «структурная индукция» связано именно с этими доказательствами[4]. Карри поделил все виды применения индукции в математике на два типа — дедуктивную индукцию и структурную индукцию, классическую индукцию над натуральными числами считая подтипом последней[5].

С другой стороны, не позднее начала 1950-х годов метод трансфинитной индукции уже распространялся на произвольные частично упорядоченные множества, удовлетворяющие условию обрыва возрастающих цепей (что эквивалентно фундированности[6]), в то же время Генкин отсылал к возможности индукции «в некоторых типах частично-упорядоченных систем»[7]. В 1960-е годы метод закрепился под наименованием нётеровой индукции (по аналогии с нётеровым кольцом, в котором выполнено условие обрыва возрастающих цепей идеалов)[8].

Явное определение структурной индукции, ссылающееся как на рекурсивную определимость, так и на нётерову индукцию, дано Бёрстоллом (англ. Rod Burstall) в конце 1960-х годов[9], и в литературе по информатике именно к нему относят введение метода[10][11].

В дальнейшем в информатике возникло несколько направлений, основывающихся на структурной индукции как базовом принципе, в частности, таковы структурная операционная семантика языков программирования Плоткина (англ. Gordon Plotkin)[12], серия индуктивных методов формальной верификации[13][14], структурно-рекурсивный язык запросов UnQL[15]. В 1990-е годы в теоретической информатике получил распространение метод коиндукции, применяемый над нефундированными (как правило, бесконечными) структурами и считающийся двойственным структурной индукции[16].

В связи с широким применением в теоретической информатике и немногочисленностью упоминаний в математической литературе, по состоянию на 2010-е годы считается, что выделение структурной индукции как особого метода в большей степени характерно для информатики, нежели для математики[17].

Наиболее общее определение[18][19] вводится для класса структур S{\displaystyle {\mathfrak {S}}} (без уточнения природы структур S∈S{\displaystyle S\in {\mathfrak {S}}}) с отношением частичного порядка между структурами ⊑{\displaystyle \sqsubseteq }, с условием минимального элемента S0{\displaystyle S_{0}} в S{\displaystyle {\mathfrak {S}}} и условием наличия для каждой S∈S{\displaystyle S\in {\mathfrak {S}}} вполне упорядоченной совокупности из всех строго предшествующих ей структур: ▽S={T∈S∣T⊏S}{\displaystyle \triangledown S=\{T\in {\mathfrak {S}}\mid T\sqsubset S\}}. Принцип структурной индукции в этом случае формулируется следующим образом: если выполнение свойства P{\displaystyle P} для S{\displaystyle {\mathfrak {S}}} следует из выполнения свойства для всех строго предшествующих ей структур, то свойство выполнено и для всех структур класса; символически (в обозначениях систем натурального вывода[en]):

∀T∈▽S:P(T)⇒P(S)∀S∈S:P(S){\displaystyle {\frac {\forall T\in \triangledown S:P(T)\Rightarrow P(S)}{\forall S\in {\mathfrak {S}}:P(S)}}}.

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

В литературе по информатике распространена и другая форма определения структурной индукции, ориентированная на рекурсию по построению[20], в ней S{\displaystyle {\mathfrak {S}}} рассматривается как класс объектов, определённых над некоторым множеством атомарных элементов A∈S{\displaystyle {\mathcal {A}}\in {\mathfrak {S}}} и набором операций {oi:Ski→S}{\displaystyle \left\{{\mathcal {o}}_{i}:{\mathfrak {S}}^{k_{i}}\to {\mathfrak {S}}\right\}}, при этом каждый объект S∈S{\displaystyle S\in {\mathfrak {S}}} — результат последовательного применения операций к атомарным элементам. В этой формулировке принцип утверждает, что свойство P{\displaystyle P} выполняется для всех объектов S∈S{\displaystyle S\in {\mathfrak {S}}}, как только имеет место для всех атомарных элементов и для каждой операции oi{\displaystyle {\mathcal {o}}_{i}} из выполнения свойства для элементов S1,…,Sik{\displaystyle S_{1},\dots ,S_{i_{k}}} следует выполнение свойства для oi(S1,…,Sik){\displaystyle {\mathcal {o}}_{i}(S_{1},\dots ,S_{i_{k}})}:

∀A∈A:P(A),∀i:(P(S1),…P(Sik⇒P(oi(S1,…,Sik))∀S∈S:P(S){\displaystyle {\frac {\forall A\in {\mathcal {A}}:P(A),\,\forall i:(P(S_{1}),\dots P(S_{i_{k}}\Rightarrow P({\mathcal {o}}_{i}(S_{1},\dots ,S_{i_{k}}))}{\forall S\in {\mathfrak {S}}:P(S)}}}.

Роль отношения частичного порядка ⊑{\displaystyle \sqsubseteq } из общего определения здесь играет отношение включения по построению: ∀j=1…ikSj⊑oi(S1,…,Sik){\displaystyle \forall _{j=1\dots i_{k}}S_{j}\sqsubseteq {\mathcal {o}}_{i}(S_{1},\dots ,S_{i_{k}})}[21].

Введение принципа в информатику мотивировалось рекурсивным характером таких структур данных, как списки и деревья[22]. Первый пример над списком, приводимый Бёрстоллом — утверждение о свойствах свёртки списков ⊛{\displaystyle \circledast } с элементами типа T{\displaystyle T} двухместной функцией ∗:T2→T{\displaystyle \ast :T^{2}\to T} и начальным элементом свёртки t∈T{\displaystyle t\in T} в связи с конкатенацией списков ∥{\displaystyle \shortparallel }:

(S1∥S2)⊛t=S1⊛(S2⊛t){\displaystyle (S_{1}\shortparallel S_{2})\circledast t=S_{1}\circledast (S_{2}\circledast t)}.

Структурная индукция в доказательстве этого утверждения ведётся от пустых списков — если S1=⊥{\displaystyle S_{1}=\bot }, то:

левая часть, по определению конкатенации: (⊥∥S2)⊛t=S2⊛t{\displaystyle (\bot \shortparallel S_{2})\circledast t=S_{2}\circledast t},
правая часть, по определению свёртки: ⊥⊛(S2⊛t)=S2⊛t{\displaystyle \bot \circledast (S_{2}\circledast t)=S_{2}\circledast t}

и в случае, если список непуст, и начинается элементом x{\displaystyle x}, то:

левая часть, по определениям конкатенации и свёртки: ((x::S1)∥S2)⊛t=x∗((S1∥S2)⊛t){\displaystyle ((x::S_{1})\shortparallel S_{2})\circledast t=x\ast ((S_{1}\shortparallel S_{2})\circledast t)},
правая часть, по определению свёртки и предположению индукции: (x::S1)⊛(S2⊛t)=x∗((S1∥S2)⊛t){\displaystyle (x::S_{1})\circledast (S_{2}\circledast t)=x\ast ((S_{1}\shortparallel S_{2})\circledast t)}.

Предположение индукции основывается на истинности утверждения для S1{\displaystyle S_{1}} и включении S1⊑x::S1{\displaystyle S_{1}\sqsubseteq x::S_{1}}.

В теории графов структурная индукция часто применяется для доказательств утверждений о многодольных графах (с использованием перехода от (k−1){\displaystyle (k-1)}-дольных к k{\displaystyle k}-дольным), в теоремах об амальгамировании графов[en], свойств деревьев и лесов[23]. Другие структуры в математике, для которых применяется структурная индукция — перестановки, матрицы и их тензорные произведения, конструкции из геометрических фигур в комбинаторной геометрии.

Типичное применение в математической логике и универсальной алгебре — структурная индукция по построению формул из атомарных термов, например, показывается, что выполнение требуемого свойства P{\displaystyle P} для термов A{\displaystyle A} и B{\displaystyle B} влечёт P(A∨B){\displaystyle P(A\vee B)}, P(A∧B){\displaystyle P(A\wedge B)}, P(¬A){\displaystyle P(\lnot A)} и так далее. Также по построению формул работают многие структурно-индуктивные доказательства в теории автоматов, математической лингвистике; для доказательства синтаксической корректности компьютерных программ широко используется структурная индукция по БНФ-определению языка (иногда даже выделяется в отдельный подтип — БНФ-индукция[24]).

  1. 1 2 Штеффен, Рютинг, Хут, 2018, p. 179.
  2. Рекурсия — статья из Математической энциклопедии. Н. В. Белякин
  3. J. Loś[pl]. Quelques remarques, théorèmes et problèmes sur les classes définissables d’algèbres // Studies in Logic and the Foundations of Mathematics. — 1955. — Vol. 16. — P. 98—113. — doi:10.1016/S0049-237X(09)70306-4.
  4. ↑ Гундерсон, 2011, p. 48.
  5. ↑ Карри, 1969, при этом указывая: «Обычная математическая индукция с настоящей точки зрения является структурной индукцией по системе самов; она так часто встречается <…> что стоит считать её третьим видом — натуральной индукцией».
  6. А. Г. Курош. Лекции по общей алгебре. — М.: Физматлит, 1962. — С. 21—22 (§5. Условие минимальности). — 399 с.
  7. Л. Генкин. О математической индукции. — М.: Физматгиз, 1962. — С. 36 (заключение). — 36 с.
  8. П. Кон. Универсальная алгебра. — М.: Мир, 1969. — С. 33—34. — 351 с.
  9. ↑ Бёрстолл, 1969.
  10. ↑ Tools and Notions for Program Construction. An Advanced Course / D. Néel (ed.). — Cambridge University Press, 1982. — С. 196. — 400 с. — ISBN 0-512-24801-9.
  11. О. А. Ильичёва. Формальное описание семантики языков программирования. — Ростов-на-Дону: ЮФУ, 2007. — С. 99—100. — 223 с.
  12. G. Plotkin. The origins of structural operational semantics // The Journal of Logic and Algebraic Programming. — 2004. — P. 3—15. — doi:10.1016/j.jlap.2004.03.009.
  13. Z. Manna, S. Ness, J. Vuillemin. Inductive methods for proving properties of programs // Communications of the ACM. — 1973. — Vol. 16, № 8. — P. 491—502. — doi:10.1145/355609.362336.
  14. C. Reynolds, R. Yeh. Induction as the basis for program verification // Proceedings of the 2nd international conference on Software engineering (ICSE ’76). — Los Alamitos: IEEE Computer Society Press, 1976. — С. 389.
  15. P. Buneman, M. Fernandez, D. Suciu. UnQL: a query language and algebra for semistructured data based on structural recursion // The VLDB Journal. — 2000. — Vol. 9, № 1. — P. 76—110. — doi:10.1007/s007780050084.
  16. R. Milner, M. Tofte. Co-induction in relational semantics // Theoretical Computer Science[en]. — Vol. 87, № 1. — P. 209—220.
  17. ↑ Гундерсон, 2011, p. 48: «In the rest of mathematics, the term “structural induction” is rarely used outside of computer science applications — as a friend once said, “it’s all just induction”».
  18. ↑ Бёрстолл, 1969, p. 42.
  19. ↑ Гундерсон, 2011, p. 42.
  20. ↑ Штеффен, Рютинг, Хут, 2018, pp. 177—178.
  21. ↑ Штеффен, Рютинг, Хут, 2018, pp. 178.
  22. ↑ Бёрстолл, 1969, p. 43, 45.
  23. ↑ Гундерсон, 2011, p. 49, 257, 384, 245.
  24. ↑ Штеффен, Рютинг, Хут, 2018, p. 214.
  • B. Steffen, O. Rüthing, M. Huth. Mathematical Foundations of Advanced Informatics. — Springer, 2018. — Vol. 1. Inductive Approaches. — ISBN 978-3-319-68396-6.
  • R. M. Burstall. Proving properties of programs by structural induction // The Computer Journal[en]. — 1969. — Vol. 12, № 1. — P. 41–48. — doi:10.1093/comjnl/12.1.41.
  • D. Gunderson. Handbook of Mathematical Induction. Theory and Applications. — Boca Raton: CRC, 2011. — 893 с. — ISBN 978-1-4200-9364-3.
  • Х. Карри. Основания математической логики. — М.: Мир, 1969. — 567 с.

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

Материал из Википедии — свободной энциклопедии

Dominoeffect.png

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

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

Формулировка

Предположим, что требуется установить справедливость бесконечной последовательности утверждений, занумерованных натуральными числами: P1,P2,…,Pn,Pn+1,…{\displaystyle P_{1},P_{2},\ldots ,P_{n},P_{n+1},\ldots }.

Допустим, что

  1. Установлено, что P1{\displaystyle P_{1}} верно. (Это утверждение называется базой индукции.)
  2. Для любого n доказано, что если верно Pn{\displaystyle P_{n}}, то верно Pn+1{\displaystyle P_{n+1}}. (Это утверждение называется индукционным переходом.)

Тогда все утверждения нашей последовательности верны.

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

Принцип полной математической индукции

Существует также вариация, так называемый принцип полной математической индукции. Вот его строгая формулировка:

Пусть имеется последовательность утверждений P1{\displaystyle P_{1}}, P2{\displaystyle P_{2}}, P3{\displaystyle P_{3}}, …{\displaystyle \ldots }. Если для любого натурального n{\displaystyle n} из того, что истинны все P1{\displaystyle P_{1}}, P2{\displaystyle P_{2}}, P3{\displaystyle P_{3}}, …{\displaystyle \ldots }, Pn−1{\displaystyle P_{n-1}}, следует также истинность Pn{\displaystyle P_{n}}, то все утверждения в этой последовательности истинны, то есть (∀n∈N)((∀i∈{1;…;n−1})Pi⟶Pn)⟶(∀n∈N)Pn{\displaystyle (\forall n\in {\mathbb {N} }){\Big (}(\forall i\in \{1;\dots ;n-1\})P_{i}\longrightarrow P_{n}{\Big )}\longrightarrow (\forall n\in {\mathbb {N} })P_{n}}.

В этой вариации база индукции оказывается излишней, поскольку является тривиальным частным случаем индукционного перехода. Действительно, при n=1{\displaystyle n=1} импликация (∀i∈{1;…;n−1})Pi⟶Pn{\displaystyle (\forall i\in \{1;\dots ;n-1\})P_{i}\longrightarrow P_{n}} эквивалентна P1{\displaystyle P_{1}}. Принцип полной математической индукции является прямым применением более сильной трансфинитной индукции.

Принцип полной математической индукции также эквивалентен аксиоме индукции в аксиомах Пеано.

История

Осознание метода математической индукции как отдельного важного метода восходит к Блезу Паскалю и Герсониду, хотя отдельные случаи применения встречаются ещё в античные времена у Прокла и Эвклида[1]. Современное название метода было введено де Морганом в 1838 году.

Примеры

Задача. Доказать, что, каковы бы ни были натуральное n и вещественное q ≠ 1, выполняется равенство

1+q+q2+⋯+qn=1−qn+11−q.{\displaystyle 1+q+q^{2}+\cdots +q^{n}={\frac {1-q^{n+1}}{1-q}}.}

Доказательство. Индукция по n.

База, n = 1:

1+q=(1−q)(1+q)1−q=1−q1+11−q.{\displaystyle 1+q={\frac {(1-q)(1+q)}{1-q}}={\frac {1-q^{1+1}}{1-q}}.}

Переход: предположим, что

1+q+⋯+qn=1−qn+11−q,{\displaystyle 1+q+\cdots +q^{n}={\frac {1-q^{n+1}}{1-q}},}

тогда

1+q+⋯+qn+qn+1=1−qn+11−q+qn+1={\displaystyle 1+q+\cdots +q^{n}+q^{n+1}={\frac {1-q^{n+1}}{1-q}}+q^{n+1}=}
=1−qn+1+(1−q)qn+11−q=1−qn+1+qn+1−q(n+1)+11−q=1−q(n+1)+11−q{\displaystyle ={\frac {1-q^{n+1}+(1-q)q^{n+1}}{1-q}}={\frac {1-q^{n+1}+q^{n+1}-q^{(n+1)+1}}{1-q}}={\frac {1-q^{(n+1)+1}}{1-q}}},

что и требовалось доказать.

Комментарий: истинность утверждения Pn{\displaystyle P_{n}} в этом доказательстве — то же, что истинность равенства

1+q+⋯+qn=1−qn+11−q.{\displaystyle 1+q+\cdots +q^{n}={\frac {1-q^{n+1}}{1-q}}.}

Вариации и обобщения

Примечания

  1. Nachum L. Rabinovih. Раби Леви бен Гершом и происхождение метода математической индукции = Rabbi Levi ben Gershom and the origins of mathematical induction // Archive for History of Exact Sciences. — 1970. — Вып. 6. — С. 237-248.

Литература

Ссылки

  • Видео по методу математической индукции

Принцип математической индукции — это… Что такое Принцип математической индукции?


Принцип математической индукции

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

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

Точное описание

Предположим, что требуется установить справедливость бесконечной последовательности утверждений, занумерованных натуральными числами:

Допустим, что

  1. Установлено, что P1 верно. (Это утверждение называется базой индукции.)
  2. Для любого n доказано, что если верно Pn, то верно Pn + 1. (Это утверждение называется индукционным переходом.)

Тогда все утверждения нашей последовательности верны.


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

Существует также вариация, так называемый принцип полной математической индукции. Вот его строгая формулировка:

Пусть имеется последовательность утверждений . Допустим, что

  1. Установлено, что P1 верно.
  2. Для любого натурального n доказано, что если верны все , то верно и Pn + 1. (Это утверждение называется индукционным переходом.)

Тогда все утверждения в этой последовательности верны.


Принцип полной математической индукции также эквивалентен аксиоме индукции в аксиомах Пеано.

Примеры

Задача. Доказать, что, каковы бы ни были натуральное n и вещественное q ≠ 1, выполняется равенство

Доказательство. Индукция по n.

База, n = 1:

Переход: предположим, что

тогда

,

что и требовалось доказать.

Комментарий: верность утверждения Pn в этом доказательстве — то же, что верность равенства

См. также

Вариации и обобщения

Литература

  • Н. Я. Виленкин Индукция. Комбинаторика. Пособие для учителей. М., Просвещение, 1976.—48 с
  • Л. И. Головина, И. М. Яглом Индукция в геометрии, «Популярные лекции по математике», Выпуск 21, Физматгиз 1961.—100 с.
  • Р. Курант, Г. Роббинс «Что такое математика?» Глава I, § 2.
  • И. С. Соминский Метод математической индукции. «Популярные лекции по математике», Выпуск 3, Издательство «Наука» 1965.—58 с.

Wikimedia Foundation. 2010.

  • Принцип локальности
  • Принцип максимума (уравнение теплопроводности)

Смотреть что такое «Принцип математической индукции» в других словарях:

  • Метод математической индукции — Математическая индукция в математике один из методов доказательства. Используется, чтобы доказать истинность некоего утверждения для всех натуральных чисел. Для этого сначала проверяется истинность утверждения с номером 1 база индукции, а затем… …   Википедия

  • ИНДУКЦИИ АКСИОМА — утверждение о справедливости для всех хнек рого предиката Р(х), определенного на множестве всех неотрицательных целых чисел, если выполняются следующие условия: 1) справедливо Р(0),2) для любого х, если верно Р(х), то верно и P(x+1). И. а.… …   Математическая энциклопедия

  • ИНТУИЦИОНИЗМ — (от позднелат. intuitio, от лат. intueor пристально смотрю) направление в обосновании математики и логики, согласно которому конечным критерием приемлемости методов и результатов этих наук является наглядно содержательная интуиция. Вся математика …   Философская энциклопедия

  • Трансфинитные числа — (от Транс… и лат. finitus ограниченный)         обобщённые порядковые числа. Определение Т. ч. опирается на понятие вполне упорядоченного множества (см. Упорядоченные и частично упорядоченные множества). Каждое конечное множество можно сделать… …   Большая советская энциклопедия

  • интуиционизм — направление в обосновании математики и логики, согласно которому конечным критерием приемлемости методов и результатов этих наук является наглядно содержательная интуиция. Вся математика должна опираться, согласно И., на интуитивное представление …   Словарь терминов логики

  • СОФИЗМ — (греч. sophisma хитрая уловка, измышление) рассуждение, кажущееся правильным, но содержащее скрытую логическую ошибку и служащее для придания видимости истинности ложному утверждению. С. является особым приемом интеллектуального мошенничества,… …   Философская энциклопедия

  • ТОЖДЕСТВА ПРОБЛЕМЫ — проблемы эквивалентности, проблемы иден тичности, проблемы равенства с л о в (англ. word problems) – задачи нахождения общего метода (алгоритма), позволяющего для произвольной пары элементов к. л. множества, в к ром определено отношение типа… …   Философская энциклопедия

  • Софизм — (от греч. sóphisma уловка, ухищрение, выдумка, головоломка)         умозаключение или рассуждение, обосновывающее какую нибудь заведомую нелепость, абсурд или парадоксальное утверждение, противоречащее общепринятым представлениям. Аристотель… …   Большая советская энциклопедия

  • Трансфинитная индукция —         способ математических доказательств, обобщающий обычный принцип математической индукции (См. Математическая индукция). См. Трансфинитные числа …   Большая советская энциклопедия

  • Софизм — (от греч. σόφισμα, «мастерство, умение, хитрая выдумка, уловка, мудрость»)  ложное высказывание, которое, тем не менее, при поверхностном рассмотрении кажется правильным. Софизм основан на преднамеренном, сознательном нарушении правил логики …   Википедия


Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *