W teorii mnogości , indukcja pozaskończona to rozszerzenie indukcji matematycznej na zbiory dobrze uporządkowane , czy też nawet na klasę liczb porządkowych .

Wstęp

Zarówno definicje indukcyjne jak i twierdzenie o indukcji matematycznej można porównać do rozumowań krok po kroku, gdzie kroki są ponumerowane liczbami naturalnymi . Np sedno dowodów indukcyjnych leży zawsze w podaniu uzasadnienia, że dla każdego ,

Możemy jednak sobie wyobrazić, że wykonaliśmy wszystkie kroki ponumerowane liczbami naturalnymi i chcemy kontynuować nasz proces. Ponieważ jedyną własnością liczb naturalnych potrzebną do rozumowań indukcyjnych jest, że każdy niepusty podzbiór ma element najmniejszy , naturalnym sposobem na kontynuację naszego procesu, jest deklaracja, że nasze kroki są numerowane przez kolejne elementy pewnego zbioru dobrze uporządkowanego. Ale przecież każdy zbiór dobrze uporządkowany jest porządkowo izomorficzny z pewną liczbą porządkową (której elementy to liczby porządkowe od niej mniejsze). Zatem możemy myśleć, że nasze kroki w procesie indukcyjnym są ponumerowane liczbami porządkowymi. Wówczas sedno rozszerzonych dowodów indukcyjnych (czyli dowodów przez indukcję pozaskończoną) leży w podaniu uzasadnienia, że dla każdej liczby porządkowej α,

Twierdzenia

Niech ON oznacza klasę liczb porządkowych. Poniższe twierdzenia można udowodnić w ZF (bez użycia aksjomatu wyboru ).

Twierdzenie o dowodzeniu przez indukcję

Przypuśćmy, że jest formułą języka teorii mnogości z jedną zmienną wolną x. Załóżmy również, że dla każdej liczby porządkowej α zachodzi implikacja

.

Wówczas jest prawdziwe, że .

Powyższe twierdzenie formułuje się też w następujący sposób: każda niepusta klasa liczb porządkowych ma element najmniejszy.

Dowód: Przypuśćmy, że istnieje taka liczba porządkowa α₀, że . Wówczas zbiór jest niepusty. Wiadomo, że każda niepusta podklasa klasy wszystkich liczb porządkowych ma element najmniejszy, więc niech β = minU. Jeśli γ < β, to również γ < α₀, a więc na mocy założenia . Pokazuje to, że . Na mocy założenia, zachodzi także – sprzeczność.

Twierdzenie o definicji indukcyjnej

Przypuśćmy, że jest klasą, która jest też funkcją. Wówczas istnieje jedyna funkcja (tak więc g jest też klasą) taka, że

.

Uwagi o stosowaniu

• W twierdzeniu o definicji indukcyjnej, funkcja f reprezentuje przepis na konstrukcję obiektu związanego z liczbą α przy założeniu, że skonstruowaliśmy już ciąg .
• W praktyce matematycznej, obydwa twierdzenia (zarówno o dowodzeniu jak i o definiowaniu indukcyjnym) są stosowane w odniesieniu do zbioru liczb porządkowych, często więc do liczb porządkowych mniejszych od pewnej ustalonej liczby . Wówczas w przypadku definicji indukcyjnej zarówno wyjściowa funkcja f jak i konstruowana funkcja g są zwykle zbiorami (a dziedziną tej ostatniej jest często właśnie liczba γ).
• Istnieją jednak sytuacje gdy indukcja jest robiona po wszystkich liczbach porządkowych. Tak się dzieje przy definiowaniu skali alefów , skali betów czy też uniwersum konstruowalnego (i przy wykazywaniu pewnych ich własności).
• Czasami, ze względu na różny charakter argumentacji, dowody indukcyjne są podzielone na różne rodzaje kroków, typowo następujące trzy:

Krok 0:   pokazujemy, że jest prawdziwe,

Krok następnikowy:   pokazujemy, że jeśli jest prawdziwe, to również zachodzi,

Krok graniczny:   pokazujemy, że jeśli α jest liczbą graniczną oraz jest prawdziwe, to również jest prawdziwe.

• Wprawdzie same twierdzenia o indukcji nie wymagają AC, to często w ich zastosowaniach zakłada się ten aksjomat. Jest to zwykle spowodowane faktem, że musimy przetłumaczyć problem dotyczący jakiegoś zbioru A na problem o liczbach porządkowych, a to tłumaczenie osiągamy przez ponumerowanie elementów A przy użyciu liczb porządkowych. (Innymi słowy, zwykle najpierw musimy dobrze uporządkować rozważany obiekt, do czego jest potrzebny aksjomat wyboru.)
• W twierdzeniu o definicji indukcyjnej, właściwie nie można wyrażać jedyności funkcji w języku ZFC. Formalnie, można udowodnić następujące schematy twierdzeń:

• (istnienie) Dla każdej klasy f (danej przez formulę φ_f(x,y)) można znaleźć klasę g (danej przez formulę φ_g) taką, że

Jeśli jest funkcją, to też g jest funkcją i

.

• (jedyność) Dla każdej klasy f, g, g' :

Jeśli i także ,

to g(α) = g'(α) dla każdego α. (W tym drugim schemacie używamy twierdzenia o dowodzeniu przez indukcję.)

Przykłady zastosowania indukcji pozaskończonej

Definicje indukcyjne:

• Konstrukcja zbioru Bernsteina ,
• Konstrukcja przestrzeni Novaka,
• Definicja hierarchii borelowskiej ,
• Definicja termów booleowskich ,
• Definicja skali alefów ,
• Definicja skali betów ,
• Definicje dodawania, mnożenia i potęgowania liczb porządkowych,
• Definicja klas Baire'a (dla funkcji pomiędzy przestrzeniami polskimi ),
• Definicja uniwersum konstruowalnego ,
• Definicja szerokości Cantora-Bendixsona przestrzeni rozproszonej .

Zobacz też

• ,
• indukcja matematyczna ,
• liczby porządkowe .