Необходимость сохранения инвариантов при мат. индукции?

Question

[floppa322]

Пусть P(k) утв., которое принимается истинным для n = k. И пусть P(k) = P1(k) ∧ P2(k) ∧ ... ∧ Pq(k), P(k) - конъюнкция утв. Pi. И также пусть при переходе от k к k+1 мы пользовались всеми Pi(k). Правильно ли я понимаю, что все Pi(k) должны быть истинными для k+1, иначе применив к базе b1 переход мы получим базу b2 без как минимум одного выполненного утверждения из-за чего нельзя будет совершить переход к b3 ?

Вопрос тупой, но хотелось бы узнать есть ли здесь какие-нибудь тонкости

Answer 1

[Wataru]

Очевидно, да. Чтобы доказать утверждение по индукции, вам надо из индукционного предположения P(k) доказать P(k+1). Если P(k+1) состоит из кучи частей Pi(k+1), то надо их все доказать. Ведь иначе у вас P(k+1) окажется истинным лишь частично, а значит вы индукционный шаг не доказали.
Если вам надо доказать, что "все овцы имеют 4 белые ноги", а вы выводите, только "у них 4 ноги", то вы не доказали исходное утверждение, ибо из "4 ноги" не следует "4 белых ноги". Может быть, у них 4 черных ноги.

Comments

[floppa322]

Спасибо за ответ