Математическая индукция vs полная математическая индукция

[Padawan]

Почему почти ни в каких учебниках наряду с математической идукцией не упоминается её вариант - полная математическая индукция (такое название в википедии), состоящий в том что
1) Устанавливается справедливость $P(1)$
2) исходя из предполагаемой справедливости $P(1), P(2),\ldots , P(n)$ устанавливается справедливость $P(n+1)$

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

[venco]

Padawan в сообщении #349402 писал(а):

Почему почти ни в каких учебниках наряду с математической идукцией не упоминается её вариант - полная математическая индукция (такое название в википедии), состоящий в том что
1) Устанавливается справедливость $P(1)$
2) исходя из предполагаемой справедливости $P(1), P(2),\ldots , P(n)$ устанавливается справедливость $P(n+1)$

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

А смысл? Определите $P'(n) \equiv P(1), P(2), \ldots, P(n)$, и полная индукция сведётся к обычной.

[Padawan]

А вообще, кто какие варианты идукции знает?
Я вспомнил такой
1) $P(1)$ 2) $P(n)\to P(2n)$ 3) $P(n)\to P(n-1)$

-- Пт сен 03, 2010 21:28:10 --

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

[Dandan]

Если интересна навороченная индукция - почитайте доказательство теоремы Рамсея (в общем случае) http://en.wikipedia.org/wiki/Ramsey's_theorem. Там некоторое свойство доказывается для любого набора $(n_1, n_2,...,n_k), n_i \in \mathbb N $

-- Пт сен 03, 2010 18:53:47 --

но вообще есть простые утверждения, которые (в некотором смысле) с помощью обычной индукции доказать невозможно, а можно доказать только с помощью трансфинитной индукции. Например теорема Гудстейна http://en.wikipedia.org/wiki/Goodstein's_theorem

[bot]

Padawan в сообщении #349402 писал(а):

Хотелось бы конкретный пример, на котором это преимущество видно.

Разложимость натурального на простые, к примеру.

[Doil-byle]

Padawan в сообщении #349402 писал(а):

Хотелось бы конкретный пример, на котором этго приемущество видно. Видимо это должно быть какое-то неравенство.

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

P.S. На сколько я знаю, определение обычной индукции таково: "Если мн-во натуральных чисел $M$ содержит единицу и вместе с каждым натуральным числом $a$ содержит следующее за ним число $s(a)$, то мн-во $M$ совпадает со мн-вом $N$" (мн-вом всех натуральных чисел), - собственно, это аксиома Пеано.
Потом на основе этой аксиомы формулируется полная индукция - та, что у Вас обычная. (Ну она как бы доказывается). А та индукция, которая у Вас полная, доказывается на основе теоремы о том, что в любом подмн-ве натуральных чисел найдётся наименьшее натуральное число. В той книжке, которую читал я, две предложенные Вами индукции назывались разными формами полной математической индукции. Но я от приятеля слышал, что та индукция, где берётся база, предполагается верность утверждения для n и доказывается для $n+1$ - это слабая полная индукция. А та, где берётся база, предполагается верность утверждения для всех $n_0<n$ и доказывается для $n$ - сильная полная индукция.
P.P.S. Есть математическая индукция по сумме чисел, например. Да и много их, наверное. Мне в математической индукции не нравится то, что с помощью неё иногда можно получить доказательство утверждения, но не понять, почему же оно истинно, откуда оно взялось? Например, я совсем не понял, откуда взялась формула для бинома Ньютона, когда доказывал по индукции, а когда увидел комбинаторное доказательство - сразу всё стало понятно.

[LaTeXScience]

Doil-byle в сообщении #540490 писал(а):

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

А как книга называется?

[Padawan]

Doil-byle в сообщении #540490 писал(а):

P.P.S. Есть математическая индукция по сумме чисел, например. Да и много их, наверное. Мне в математической индукции не нравится то, что с помощью неё иногда можно получить доказательство утверждения, но не понять, почему же оно истинно, откуда оно взялось? Например, я совсем не понял, откуда взялась формула для бинома Ньютона, когда доказывал по индукции, а когда увидел комбинаторное доказательство - сразу всё стало понятно.

Да, я тоже индукцию не люблю... Явно несколько шагов описываю обычно, а потом индукционный, либо же просто говорю и так далее. Оно как-то человечнее, ближе к тому, как мысль в голове развивается.

[epros]

Padawan в сообщении #349402 писал(а):

На первый взгляд полная математическая -- более сильный метод доказательства, чем обычная.

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

Более сильный метод - это трансфинитная индукция вообще, т.е. если выбрать какое-то другое отношение порядка.

[Padawan]

epros
Спасибо, venco полтора года назад уже пояснил это.

[epros]

Padawan в сообщении #560187 писал(а):

epros
Спасибо, venco полтора года назад уже пояснил это.

Да, точно. Извиняюсь за повтор. Просто я ещё раз хотел обратить внимание на то, что фокус с заменой $P(1) \wedge P(2) \wedge \dots \wedge P(n)$ на $ P'(n)$ - мета-теоретический.

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

-- Вс апр 15, 2012 11:06:38 --

Да, и ещё кстати: последнее - это самое трудно доказуемое и интуитивно неочевидное. Например, насколько я понимаю, то, что последовательности Гудстейна упорядочены таким образом, что любое их множество имеет минимальный элемент, недоказуемо в арифметике первого порядка. И именно это не позволяет доказать теорему Гудстейна в арифметике первого порядка.

[Doil-byle]

LaTeXScience в сообщении #560132 писал(а):

Doil-byle в сообщении #540490 писал(а):

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

А как книга называется?

Основания арифметики, Демидов И.Т. Эту книжку также очень легко найти в окрытом для скачивания виде.