Принцип обобщенной индукции

Пусть X – вполне упорядоченное относительно < множество, а S(х) – некоторое высказывание, касающееся элемента х из X. Если требуется доказать справедливость S(х) для всех х, принадлежащих X, то необходимо:

1) доказать, что справедливо S(х0), где х0 – наименьший элемент в X;

2) доказать для всех х в X, удовлетворяющих условию х0 < х, что если справедливо S (у) для всех у < х, то справедливо и S(х).

Отметим, что если X – множество положительных целых чисел, а отношение < имеет обычный смысл, то принцип обобщенной индукции идентичен принципу строгой индукции

Чтобы убедиться в действенности принципа обобщенной индукции как метода доказательства, предположим, что S(х) – некоторое высказывание, для которого уже доказаны оба положения. Мы хотим сделать вывод о том, что S(х) справедливо для любых х в X. Предположим, что это не так. Пусть множество А = {х: х принадлежит X и S(х) ложно}. Если S(х) не справедливо для всех х в X, то А – непустое подмножество X. Так как X вполне упорядочено, то известно, что А содержит наименьший элемент а0. По определению это наименьший элемент X, для которого S(х) не справедливо. Таким образом, S(у) справедливо для всех у (если они есть), удовлетворяющих условию у < а0. Если а0 – наименьший элемент в X, то S(а0) справедливо, что следует из первого положения. В противном случае из справедливости S(у) для всех у < а0 и второго положения вытекает, что S(а0) справедливо. Но это противоречит предположению, что а0 принадлежит А и S(а0) ложно. Единственный способ устранить это противоречие – считать А пустым множеством, т.е. в X нет элементов, для которых высказывание S(х) ложно.