Изучая книжку Андерсона "Дискретная математика и комбинаторика" возникло несколько трудностей в понимании принципов индукции в разделе 3.3.
1) В книге сформулировано два принципа индукции, которые принципиально отличаются тем, что в первом индуктивный переход для любого k: P(k) -> P(k+1). А во втором: для любого k: P(1), P(2), .... P(k-1) -> P(k). Также там утверждается, что эти принципы эквивалентны.
Если я правильно понял смысл, то второй принцип следует из первого итеративным применением индуктивного перехода первого принципа, т.е.:
(P(1) И P(1)->P(2)) -> P(2)
(P(2) И P(2)->P(3)) -> P(3)
...
(P(m-1) И P(m-1)->P(m)) -> P(m)
Первый принцип выглядит более простым в формулировке и тогда возникает вопрос: чем полезен второй принцип, если оба принципа эквиваленты? Первый принцип понятно как применять в доказательствах, а со вторым уже менее прозрачно.
2) В задаче 3.3 №23 непонятно что именно нужно доказать. По условию необходимо доказать, что из принципа полного упорядочения следует второй принцип индукции. Хотя во втором принципе индукции речь идет об утверждениях P(n), а в принципе полного упорядочения про какие-либо утверждения и их истинность ни слова не сказано.
Буду рад почитать ваши комментарии.
Естественные науки
Принцип математической индукции и наименьший элемент подмножества натуральных чисел
1) посмотри доказательство теоремы 3.42 из той же книжки
2) используя утверждение "в каждом непустом множестве натуральных чисел есть минимальный элемент" доказать теорему "пусть некое утверждение P(n) верно для n=1, и из того, что оно верно для n, следует, что оно верно для n+1. тогда это утверждение P(n) верно для любого натурального числа."
hint: начало доказательства может быть примерно такое: пусть P верно не для любого натурального числа (несмотря на полезные свойства, что оно верно для n=1, и есть переход n->n+1). возьмем множество натуральных чисел, на которых оно не верно. тогда в этом множестве найдется минимальный элемент... и т.д.
2) используя утверждение "в каждом непустом множестве натуральных чисел есть минимальный элемент" доказать теорему "пусть некое утверждение P(n) верно для n=1, и из того, что оно верно для n, следует, что оно верно для n+1. тогда это утверждение P(n) верно для любого натурального числа."
hint: начало доказательства может быть примерно такое: пусть P верно не для любого натурального числа (несмотря на полезные свойства, что оно верно для n=1, и есть переход n->n+1). возьмем множество натуральных чисел, на которых оно не верно. тогда в этом множестве найдется минимальный элемент... и т.д.
Полная индукция для бесконечного множества - нет толку применять
Александр Максименко
94 146
Сергей Гусев
Чевой-то?
Не читайте только одну книгу, а заглядывайте в другие. Есть ещё разновидность "конечная индукция" (Кнут "Искусство программирования" )
Посмотрите Новиков "Дискретная математика для программистов"
Более древняя Рейнголльд, Нивергельд, Део "Комбинаторные алгоритмы Теория и практика"
Там и индукция и лемма Цермело и еще много всего, на чём вы впоследствии спотыкнётесь.
Посмотрите Новиков "Дискретная математика для программистов"
Более древняя Рейнголльд, Нивергельд, Део "Комбинаторные алгоритмы Теория и практика"
Там и индукция и лемма Цермело и еще много всего, на чём вы впоследствии спотыкнётесь.
Олег Боженко
90 337
чё?
Sherzod Qutlimuratov
76 344
На ММИ можно смотреть двояко:
1) Как на аксиому Пеано, аксиомы Пеано появились до аксоим Цермело-Френкеля, аксиоматическое определение натурального числа по Пеано писалось во времена наивной теории множеств.
2) Как на частный случай трансфинитной, или, в ещё болеем общем случае, нётеровской индукции. Для применения этих видов индукции к реальным задачкм уже нужны аксиомы Цермело-Френкеля и (обычно) выбора.
Два вида ММИ вам даны, чтоб вы в будущем стали косоглазым - одним глазом смотрели на Пеано, а другим - на Эмми Нётер и трансфинитную индукцию.
1) Как на аксиому Пеано, аксиомы Пеано появились до аксоим Цермело-Френкеля, аксиоматическое определение натурального числа по Пеано писалось во времена наивной теории множеств.
2) Как на частный случай трансфинитной, или, в ещё болеем общем случае, нётеровской индукции. Для применения этих видов индукции к реальным задачкм уже нужны аксиомы Цермело-Френкеля и (обычно) выбора.
Два вида ММИ вам даны, чтоб вы в будущем стали косоглазым - одним глазом смотрели на Пеано, а другим - на Эмми Нётер и трансфинитную индукцию.
Похожие вопросы
- Доказать методом математической индукции
- Доказать делимость методом математической индукции
- Чем отличается целые и натуральные числа?
- Где ошибка в доказательстве методом математической индукции утверждения, что в конечном множестве цветных мячиков>
- Существует ли ещё хотя бы одно натуральное число, кроме 27, которое обладает следующим свойством:
- В каком множестве больше элементов: во множестве натуральных чисел или в действительных? Какая из бесконечностей больше?
- Интуитивно как понять математический факт, что сумма всех натуральных чисел равна -1/12?
- Почему метод математической индукции работает?
- Может ли число составленное только из цифр 2 и 0 быть 2013 степенью некотрого натурального числа
- Найти наименьшее натуральное число, оканчивающееся цифрой 9, которое увеличивается в 4 раза при перенесении его...
Исходя из книги есть утверждение N5 (принцип полного упорядочения) и
N6 (по-сути это полная индукция) со структурой:
A (база индукции)
B (шаг индукции)
A & B -> C
-------------------------------
Заключаем C (некое утверждение справедливо для любого натурального числа).
Интерпретация "доказать полную индукцию с использованием принципа минимального элемента" выглядит более понятной:
A (база индукции)
B (шаг индукции)
N5 (принцип полного упорядочения)
A & B & N5 -> C
-------------------------------
Заключаем C (некое утверждение справедливо для любого натурального числа).
Получается, что N5 выступает как энтимема в N6.