Трансфінітна індукція

Твердження, що стосуються елементів деякої повністю упорядкованої множини, можна доводити, використовуючи метод трансфінітної індукції, який є узагальненням методу математичної індукції й грунтується на теоремі про трансфінітну індукцію. Далі позначаємо відношення повного порядку через £, а вираз a<b означатиме, що а£b, але а¹b.

Теорема 14 (теорема про трансфінітну індукцію). Нехай <А,£>– повністю упорядкована множина, а₀ – найменший елемент А, Р – деяка властивість (унарний предикат) на А. Нехай Р(а₀)=1 та для довільного елементу а множини А з того, що Р(х)=1 для усіх х<а, випливає Р(а)=1. Тоді Р(х)=1 для усіх х з А.

Доведення. Припустимо, що твердження теореми не правильне. Тоді існує така непорожня підмножина В множини А (ВÌА), що Р(у)=0 для кожного у з В. Позначимо через b₀ найменший елемент множини В. За нашим припущенням Р(b₀)=0, тому а₀¹b₀ й а₀<b₀. За побудовою множини В Р(х)=1 для усіх тих елементів х множини А, для яких х<b₀. Тоді за умовою теореми має бути Р(b₀)=1, отже, маємо суперечність. Таким чином, теорему доведено.

Опишемо метод трансфінітної індукції. Нехай є повністю упорядкована множина <А,£> й задана властивість Р на А.

Базис індукції. Перевірити, чи виконується Р(а₀)=1 для найменшого елементу а₀ множини А. Якщо Р(а₀)=1, перейти до наступного кроку, інакше завершити роботу (властивість Р не має місця для усіх елементів множини А).

Індукційний крок. Нехай а (а>а₀) – деякий елемент множини А. Перевірити, чи випливає Р(а)=1 з того, що Р(х)=1 для усіх тих елементів х, що х<а (хÎА).

Якщо виконуються умови базису та індукційного кроку, то, спираючись на теорему про трансфінітну індукцію, можна зробити висновок, що Р(х)=1 для будь-якого елементу х множини А.

Метод математичної індукції, що використовується для доведення тверджень, котрі стосуються елементів множини N (або її підмножини), повністю упорядкованої відношенням £ (менше або дорівнює), є спеціальним випадком методу трансфінітної індукції. Суть методу така. Нехай є повністю упорядкована множина <А,£> (АÍN, £ – природний порядок на N) й задана властивість Р на А.

Базис індукції. Переконатися, що для найменшого елементу n₀ множини А виконується Р(n₀)=1.

Індукційний крок. Нехай k (k>n₀) – деякий елемент множини А. Перевірити, чи випливає Р(k+1)=1 з того, що Р(k)=1.

Наведемо приклад застосування методу математичної індукції. Покажемо, що для будь-якого цілого додатного числа n виконується: 1+…+n=n(n+1)/2. У даному випадку розглядається властивість, подана у вигляді рівності, на повністю упорядкованій множині <N⁺,£>. Найменшим елементом цієї множини є число 1. Отже, маємо.

Базис індукції. Перевіряємо, чи виконується задана рівність для n=1, тобто чи правильна рівність 1=(1(1+1))/2. Легко перевірити, що рівність виконується.

Індукційний крок. Припустимо, що задана рівність виконується для деякого цілого додатного числа k, k>1, тобто 1+…+k=k(k+1)/2. Покажемо, що тоді задана рівність виконується й для числа k+1, тобто 1+…+k+(k+1)=((k+1)((k+1)+1))/2. Маємо:

1+…+k+(k+1)=(1+…+k)+(k+1)=(k(k+1))/2+(k+1)=(k+1)((k+2)/2)= =((k+1)((k+1)+1))/2.

Отже, твердження «1+…+n=n(n+1)/2 для будь-якого n з N⁺» доведено.