2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Математическая индукция vs полная математическая индукция
Сообщение03.09.2010, 19:03 
Заслуженный участник


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

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

 Профиль  
                  
 
 Re: Математическая индукция vs полная математическая индукция
Сообщение03.09.2010, 19:13 
Заслуженный участник


04/05/09
4582
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)$, и полная индукция сведётся к обычной.

 Профиль  
                  
 
 Re: Математическая индукция vs полная математическая индукция
Сообщение03.09.2010, 19:22 
Заслуженный участник


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

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

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

 Профиль  
                  
 
 Re: Математическая индукция vs полная математическая индукция
Сообщение03.09.2010, 19:49 


24/03/07
321
Если интересна навороченная индукция - почитайте доказательство теоремы Рамсея (в общем случае) 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

 Профиль  
                  
 
 Re: Математическая индукция vs полная математическая индукция
Сообщение28.09.2010, 19:24 
Заслуженный участник
Аватара пользователя


21/12/05
5903
Новосибирск
Padawan в сообщении #349402 писал(а):
Хотелось бы конкретный пример, на котором это преимущество видно.

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

 Профиль  
                  
 
 Re: Математическая индукция vs полная математическая индукция
Сообщение19.02.2012, 15:33 


05/09/11
364
Петербург
Padawan в сообщении #349402 писал(а):
Хотелось бы конкретный пример, на котором этго приемущество видно. Видимо это должно быть какое-то неравенство.

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

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

 Профиль  
                  
 
 Re: Математическая индукция vs полная математическая индукция
Сообщение15.04.2012, 00:33 
Заблокирован
Аватара пользователя


24/06/11

237
С планеты Земля
Doil-byle в сообщении #540490 писал(а):
В той книжке, которую читал я, две предложенные Вами индукции назывались разными формами полной математической индукции.

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

 Профиль  
                  
 
 Re: Математическая индукция vs полная математическая индукция
Сообщение15.04.2012, 00:37 
Заслуженный участник


13/12/05
4518
Doil-byle в сообщении #540490 писал(а):
P.P.S. Есть математическая индукция по сумме чисел, например. Да и много их, наверное. Мне в математической индукции не нравится то, что с помощью неё иногда можно получить доказательство утверждения, но не понять, почему же оно истинно, откуда оно взялось? Например, я совсем не понял, откуда взялась формула для бинома Ньютона, когда доказывал по индукции, а когда увидел комбинаторное доказательство - сразу всё стало понятно.

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

 Профиль  
                  
 
 Re: Математическая индукция vs полная математическая индукция
Сообщение15.04.2012, 09:12 
Заслуженный участник
Аватара пользователя


28/09/06
10413
Padawan в сообщении #349402 писал(а):
На первый взгляд полная математическая -- более сильный метод доказательства, чем обычная.
Это не совсем точно. Полная (трансфинитная?) индукция для естественного порядка на множестве натуральных чисел - эквивалентна мат. индукции. Правда эта эквивалентность вроде бы в рамках самой арифметики недоказуема, т.е. доказуема только мета-теоретически.

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

 Профиль  
                  
 
 Re: Математическая индукция vs полная математическая индукция
Сообщение15.04.2012, 09:25 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Математическая индукция vs полная математическая индукция
Сообщение15.04.2012, 09:40 
Заслуженный участник
Аватара пользователя


28/09/06
10413
Padawan в сообщении #560187 писал(а):
epros
Спасибо, venco полтора года назад уже пояснил это.
Да, точно. Извиняюсь за повтор. Просто я ещё раз хотел обратить внимание на то, что фокус с заменой $P(1) \wedge P(2) \wedge \dots \wedge P(n)$ на $ P'(n)$ - мета-теоретический.

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

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

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

 Профиль  
                  
 
 Re: Математическая индукция vs полная математическая индукция
Сообщение15.04.2012, 13:46 


05/09/11
364
Петербург
LaTeXScience в сообщении #560132 писал(а):
Doil-byle в сообщении #540490 писал(а):
В той книжке, которую читал я, две предложенные Вами индукции назывались разными формами полной математической индукции.

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

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 12 ] 

Модераторы: Модераторы, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group