Твердження, що стосуються елементів деякої повністю упорядкованої множини, можна доводити, використовуючи метод трансфінітної індукції, який є узагальненням методу математичної індукції й грунтується на теоремі про трансфінітну індукцію. Далі позначаємо відношення повного порядку через £, а вираз a<b означатиме, що а£b, але а¹b.
Теорема 14 (теорема про трансфінітну індукцію). Нехай <А,£>– повністю упорядкована множина, а0 – найменший елемент А, Р – деяка властивість (унарний предикат) на А. Нехай Р(а0)=1 та для довільного елементу а множини А з того, що Р(х)=1 для усіх х<а, випливає Р(а)=1. Тоді Р(х)=1 для усіх х з А.
Доведення. Припустимо, що твердження теореми не правильне. Тоді існує така непорожня підмножина В множини А (ВÌА), що Р(у)=0 для кожного у з В. Позначимо через b0 найменший елемент множини В. За нашим припущенням Р(b0)=0, тому а0¹b0 й а0<b0. За побудовою множини В Р(х)=1 для усіх тих елементів х множини А, для яких х<b0. Тоді за умовою теореми має бути Р(b0)=1, отже, маємо суперечність. Таким чином, теорему доведено.
Опишемо метод трансфінітної індукції. Нехай є повністю упорядкована множина <А,£> й задана властивість Р на А.
Базис індукції. Перевірити, чи виконується Р(а0)=1 для найменшого елементу а0 множини А. Якщо Р(а0)=1, перейти до наступного кроку, інакше завершити роботу (властивість Р не має місця для усіх елементів множини А).
Індукційний крок. Нехай а (а>а0) – деякий елемент множини А. Перевірити, чи випливає Р(а)=1 з того, що Р(х)=1 для усіх тих елементів х, що х<а (хÎА).
Якщо виконуються умови базису та індукційного кроку, то, спираючись на теорему про трансфінітну індукцію, можна зробити висновок, що Р(х)=1 для будь-якого елементу х множини А.
Метод математичної індукції, що використовується для доведення тверджень, котрі стосуються елементів множини N (або її підмножини), повністю упорядкованої відношенням £ (менше або дорівнює), є спеціальним випадком методу трансфінітної індукції. Суть методу така. Нехай є повністю упорядкована множина <А,£> (АÍN, £ – природний порядок на N) й задана властивість Р на А.
Базис індукції. Переконатися, що для найменшого елементу n0 множини А виконується Р(n0)=1.
Індукційний крок. Нехай k (k>n0) – деякий елемент множини А. Перевірити, чи випливає Р(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+» доведено.