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

Question

Изучая книжку Андерсона Дискретная математика и комбинаторика возникло несколько трудностей в понимании принципов индукции в разделе 3. 3.
1) В книге сформулировано два принципа индукции, которые принципиально отличаются тем, что в первом индуктивный переход для любого k: P (k) - P (k. А во втором: для любого 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 непонятно что именно нужно доказать. По условию необходимо доказать, что из принципа полного упорядочения следует второй принцип индукции. Хотя во втором принципе индукции речь идет об утверждениях P (n) , а в принципе полного упорядочения про какие-либо утверждения и их истинность ни слова не сказано.

Буду рад почитать ваши комментарии.

Answer 1

Не читайте только одну книгу, а заглядывайте в другие. Есть ещё разновидность конечная индукция (Кнут Искусство программирования )
Посмотрите Новиков Дискретная математика для программистов
Боле древня Рейнголльд, Нивергельд, Део Комбинаторные алгоритмы Теория и практика
Там и индукция и лемма Цермело и еще много всего, на чём вы впоследствии спотыкнётесь.