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

Автор темы Фома 
ОбъявленияПоследний пост
ОбъявлениеРаботодателям и кадровым агентствам: Размещение вакансий26.03.2008 03:07
ОбъявлениеРабота автором топиков и проектов на математическом треке Hyperskill24.09.2021 21:18
ОбъявлениеГранты для студентов и аспирантов мехмата и физфака МГУ на обучение в магистратуре Кембриджа 2022/202314.10.2021 12:28
18.05.2003 18:57
Фома
Метод математической индукции
Привет, народ!
Не знает ли кто-нибудь доказательство метода мат. индукции? И есть ли оно вообще в природе (или метод считается очевидным)? Если есть, бросьте пожалуйста ссылочку :)
18.05.2003 19:34
ММИ - это аксиома
ММИ - это аксиома. Одна из аксиом формальной арифметики
См., например, Э.Мендельсон "Введение в мат. логику" или более простую ( ;-)) - для знатоков) книжку Э.Ландау "Основы анализа".
18.05.2003 22:49
не обязательно(+)
можно имея аксиому о том, что в любом подмножестве из N есть наименьший элемент, доказать ММИ



Босс
18.05.2003 23:07
Верно :)
Но ведь это просто эквивалент, который Вы вправе положить в основание теории вместо одной из ее аксиом, коли он ей равносилен.
18.05.2003 23:14
Cхема аксиом
Объяснено вроде бы исчерпывающе, хотя можно добавить, что
в формальной арифметике (если ее рассматривать как теорию первого порядка) этот принцип выражается не одной
аксиомой, а счетной схемой таковых -- по понятным причинам.
18.05.2003 23:19
Про схему аксиом все верно, конечно :)
Но зачем детям забивать мозги формализмом?
19.05.2003 01:48
Ничего себе дети :-)
subj

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

В противном случае, например, можно подумать, что теория
натуральных чисел Th(N,=,+,*) конечно аксиоматизируема (а это не так,
поскольку она полна и неразрешима по теореме Тарского).
Или еще один вариант неправильного понимания: аксиома
индукции вовсе не утверждает что-то типа "для всех подмножеств
натурального ряда верно то-то и то-то...", она слабее.

Короче, намек задавшему исходный вопрос такой:
почитайте какие-нибудь хорошие книжки по классической логике,
там есть чему удивиться :-)
19.05.2003 10:36
Мне остается улыбнуться :)
Мне остается улыбнуться (по доброму) и нашим "дорогим детям" уточнить, что то, что во фразе Максима "можно подумать, что теория
натуральных чисел Th(N,=,+,*) конечно аксиоматизируема" слово "конечно" совершенно не случайно запятыми НЕ выделено.
;-)
19.05.2003 19:36
Мне тоже :-)
Да, действительно не случайно, хотя подобного
неправильного варианта толкования я сразу не заметил,
спасибо :-)
19.05.2003 22:44
Отлично!
Только что-то я долго на пустой желудок соображал в чем дело :)
И таки да, сначала прочел неверно :)
22.05.2003 16:04
Buket
А по жизни метод ми не работает?
Довольно известный пример:
Утв. Не существует бородатых людей.
Док. Индукцией по числу волос на лице.
Вы начнете махать руками и говорить, что бородатый человек не определен. :) Тогда переформулируем утверждение:
Утв. Ни одного человека в мире я интуитивно не воспринимаю как бородатого. (И доказательство аналогично)
Здесь не определено понятие "интуитивно воспринимать как бородатого", ну и что? Тем не менее, верно следующее (k - число волос):
при n=1 не воспринимаю,
если при n=k не воспринимаю, то при n=k+1 не воспринимаю.

Я считаю, здесь парадокс. Кто что думает?
{Аня привет :))}
22.05.2003 16:18
Нет здесь парадокса :)
К обычным возражениям добавлю лишь то, что Вы не только не определили бородатого человека, но и не доказали индуктивный переход (если воспользоваться аналогичным примером про "не кучу", то: почему не может случиться так, что 10000 камней - это еще не куча, а 10001 - уже куча?) :))))
22.05.2003 17:58
Buket
Допускаю, что есть :)
Рассмотрим не утверждение "На свете нет бородатых людей", а утверждение "Ни одного человека на свете я интуитивно не воспринимаю как бородатого". (не обязательно я, под словом "я" каждый может понимать себя)
Я считаю, что определять понятие "интуитивно воспринимать как бородатого" не обязательно, достаточно доказать индуктивный переход, и вот почему: если А->B и B->C, то A->C, даже если под A, B, C все понимают разные вещи. Например: из утверждений "все мымрики являются жмуриками" и "все жмурики красивы" следует утверждение "все мымрики красивы", как бы Вы не представляли себе мымриков, жмуриков и красоту (главное, чтобы хоть какой-то смысл эти понятия несли :)).
Вернемся к утверждению. Достаточно принять верными след. два утверждения:
1) Человека с одним волосом на лице я не воспринимаю как бородатого. (это верно)
2) Если при k волос я не воспринимаю человека как бородатого, то при k+1 волос я тоже не воспринимаю его как бородатого.
Докажем 2).
Ограничим число волос сверху (например, 200000), если нужно, для этого переформулируем утверждение. И для всех пар (k, k+1) перебором проверим индуктивный переход (я же не обязана проверять в порядке увеличения k ;)). Для любой пары (k, k+1) 2) верно.

Может, здесь все-таки парадокс? :))))))))
22.05.2003 18:20
Да нету его тут (парадокса)! НЕ-ТУ!!
> Рассмотрим не утверждение "На свете нет бородатых людей", а
> утверждение "Ни одного человека на свете я интуитивно не
> воспринимаю как бородатого". (не обязательно я, под словом
> "я" каждый может понимать себя)

Рассмотрим.

> Я считаю, что определять понятие "интуитивно воспринимать как
> бородатого" не обязательно, достаточно доказать индуктивный
> переход, и вот почему: если А->B и B->C, то A->C, даже если
> под A, B, C все понимают разные вещи. Например: из
> утверждений "все мымрики являются жмуриками" и "все жмурики
> красивы" следует утверждение "все мымрики красивы", как бы Вы
> не представляли себе мымриков, жмуриков и красоту (главное,
> чтобы хоть какой-то смысл эти понятия несли :)).

Совершенно верно! Вот только, милый Букет, какое это имеет отношение к последующему? :((

> Вернемся к утверждению. Достаточно принять верными след. два
> утверждения:
> 1) Человека с одним волосом на лице я не воспринимаю как
> бородатого. (это верно)
> 2) Если при k волос я не воспринимаю человека как бородатого,
> то при k+1 волос я тоже не воспринимаю его как бородатого.

Будьте осторожнее: если Вы именно ПРИМЕТЕ оба эти утверждения, то Вам ничего не останется, как согласитьс с тем, что ни одного человека Вы интуитивно не воспринимаете, как бородатого (даже Маркса с Энгельсом ;-))). [А в самом деле? Ну разве Маркс бородатый??? Да ну - несерьезно, разве ЭТО борода?! ;-)))) Ой, я кажется понял: Вы наверно воспринимаете Маркса бородатым неинтуитивно. Во, все: теперь все на своих местах! :))))]

> Докажем 2).

Попробуем :)

> Ограничим число волос сверху (например, 200000), если нужно,
> для этого переформулируем утверждение. И для всех пар (k,
> k+1) перебором проверим индуктивный переход (я же не обязана
> проверять в порядке увеличения k ;)). Для любой пары (k, k+1)
> 2) верно.

Вы УВЕРЕНЫ, что представили доказательство? А, по-моему, бесконечный перебор - это как-то не очень. :(( Или он конечный? Тогда пожалуйста: те у кого волос меньше 200001 не могут считаться (Вами,... интуитивно :)) бородатыми, а все остальные - извините, не знаем :). Вот сколько волос было в бороде Маркса? Наверно все же побольше: уж очень он смахивает на бородатого, вопреки всей этой интуиции :)).

> Может, здесь все-таки парадокс? :))))))))

Да нет его здесь. НЕТУ!!!
22.05.2003 18:53
Buket
Строго говоря, нет :( а жаль
Да, вот это "интуитивно воспринимать как" - это слабое место, потому что не определено, что это такое. С точки зрения математика это "я воспринимаю" не выдерживает никакой критики, и поэтому парадокса нет :) Сейчас я так интуитивно воспринимаю, а завтра по-другому, и вообще как это проверить - если меня спросить, я могу наврать :))
Но в остальном все чисто, по-моему. Перебор конечный (если хотите, будем доказывать утверждение "никакого человека с числом волос до 400000 я не восприимаю как бородатого" - у человека даже на голове редко бывает больше 150000 волос, я где-то читала :))
Мымрики со жмуриками - это было к тому, что если доказать индуктивный переход, бородатость определять не обязательно.

А еще я слышала, что метод ми не всегда работает (я здесь именно математику имею в виду), вроде бы иногда им можно доказать неверное утверждение (прошу без подколов, если честно доказывать :)). Пробовала в яндексе искать, но не нашла ничего. Ничего не знаете об этом?
22.05.2003 19:23
Ответ
> Да, вот это "интуитивно воспринимать как" - это слабое место, потому что не
> определено, что это такое. С точки зрения математика это "я воспринимаю" не
> выдерживает никакой критики, и поэтому парадокса нет :) Сейчас я так
> интуитивно воспринимаю, а завтра по-другому, и вообще как это проверить -
> если меня спросить, я могу наврать :))

Да нет, дело совершенно не в этом!!!

> Но в остальном все чисто, по-моему. Перебор конечный (если хотите, будем
> доказывать утверждение "никакого человека с числом волос до 400000 я не
> восприимаю как бородатого" - у человека даже на голове редко бывает больше
> 150000 волос, я где-то читала :))

Вот здесь у Вас явная ошибка. Множество натуральных чисел бесконечно и метод мат.индукции работает с ним, как именно с бесконечным множеством. Ну и что с того, что Вы проверите, что все пары (k, k+1) для k<4000...00000 (число нулей конечно) удовлетворяют условию задачи? Из этого никак не будет вытекать, что для каждого k из верности Вашего утверждения для этого самого k следует верность утверждения для k+1. {В нашем случае: из того, что k-волосатая борода не кажется Вам интуитивно бородой, никак не следует, что (k+1)-волосатая борода Вам таковой не покажется (как бы Вы ни определяли свои интуитивные восприятия)} А ведь нужно-то именно это доказать!! Именно в этом-то и состоит индуктивный переход!!

> А еще я слышала, что метод ми не всегда работает (я здесь именно математику
> имею в виду), вроде бы иногда им можно доказать неверное утверждение (прошу
> без подколов, если честно доказывать :)). Пробовала в яндексе искать, но не
> нашла ничего. Ничего не знаете об этом?

:))) Такого не может быть, поскольку ММИ, как было уже указано, является одной из аксиом. Все неверные "доказательства" методом МИ - это в той или иной степени приколы и подколки. Например:

Теорема: Не бывает кучи камней (никакое количество камней не является кучей).
"Доказательство" (методом мат. индукции):
Основание: Один камень - не куча.
Индуктивный переход: если k камней не куча, то добавление к ним еще одного камня не приведет к куче.
Все доказано. :))

Ошибка здесь подобна предыдущей (в теореме с бородами). Она двоякая. Как правило, обращают внимание лишь на то, что не дано определение кучи. Мне же хотелось уточнить, что при любом корректном определении кучи камней доказательство или не пройдет или будет честно доказано, что куч камней (таких, которые определены) не бывает. :)))
P.S. Извинте за мои многочисленные подколки - я ведь не со зла :)
22.05.2003 21:08
Н-да...
Дорогие коллеги, если кто-нибудь еще понимает, о чем
вообще идет дискуссия, то объясните и мне тоже.

А то такое чувство, что неожиданно оказался на форуме по
Теории Интуитивой Бороды, и самое интересное:
все произносимые слова знакомы, а суть происходящего
остается весьма загадочной :-))

> P.S. Извинте за мои многочисленные подколки - я ведь не со зла :)

Ну да, а выражение в стиле "глубокоуважаемый Букет" вообще просто
супер :-)
22.05.2003 21:17
Папрашу не передергивать ;)
> Ну да, а выражение в стиле "глубокоуважаемый Букет" вообще
> просто
> супер :-)

Не надо, Максим! Там было "милый Букет"!!!! :)))

> Дорогие коллеги, если кто-нибудь еще понимает, о чем
> вообще идет дискуссия, то объясните и мне тоже.
>
> А то такое чувство, что неожиданно оказался на форуме по
> Теории Интуитивой Бороды, и самое интересное:
> все произносимые слова знакомы, а суть происходящего
> остается весьма загадочной :-))

Да ничего нет там непонятного, глубокоуважаемый ( ;-)) ) Максим. Надо только вчитаться :)
22.05.2003 21:49
Это одно и то же
Alopex сказал(а) :

> Не надо, Максим! Там было "милый Букет"!!!! :)))
Вот я и говорю: "в стиле". По-моему это почти одно и то же...

> Да ничего нет там непонятного, глубокоуважаемый ( ;-)) )
Спасибо, хоть букетом не назвали :-))
22.05.2003 22:03
Ну я бы не сказал...
> Вот я и говорю: "в стиле". По-моему это почти одно и то же...

Х-м, я бы не сказал.

> Спасибо, хоть букетом не назвали :-))

Ну, если бы Ваш ник был Buket, то и Вас назвал бы :)
Извините, только зарегистрированные пользователи могут публиковать сообщения в этом форуме.

Кликните здесь, чтобы войти