Indukcja pozaskończona

Indukcja pozaskończona – rozszerzenie indukcji matematycznej na zbiory dobrze uporządkowane, m.in. 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. Na przykład sedno dowodów indukcyjnych leży zawsze w podaniu uzasadnienia, że dla każdego $n\in \mathbb {N} ,$ jeśli do kroku $n$ (wyłącznie) wszystko było dobrze, to stąd można wywnioskować, że na kroku $n$ też wszystko jest dobrze.

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 $\mathbb {N}$ 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 $\alpha ,$ jeśli do kroku $\alpha$ (wyłącznie) wszystko było dobrze, to stąd można wywnioskować, że na kroku $\alpha$ też wszystko jest dobrze.

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 $\varphi (x)$ jest formułą języka teorii mnogości z jedną zmienną wolną $x.$ Załóżmy również, że:

$(\forall \alpha )\ [((\forall \beta <\alpha )\ \varphi (\beta ))\Rightarrow \varphi (\alpha )].$

Wówczas jest prawdą, że $\varphi (\alpha )$ dla każdej liczby porządkowej $\alpha .$

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 $\alpha _{0},$ że $\sim \varphi (\alpha _{0}).$ Wówczas zbiór $U=\{\alpha \subseteq \alpha _{0}\colon \sim \varphi (\alpha )\}$ jest niepusty. Wiadomo, że każdy niepusty zbiór liczb porządkowych jest dobrze uporządkowany przez inkluzję, więc niech $\beta =\min(U).$ Z określenia $\beta$ wynika, że dla każdego $\gamma <\beta$ mamy $\gamma \not \in U,$ skąd wobec $\gamma \subseteq \alpha _{0}$ otrzymujemy $\varphi (\gamma ).$ Na mocy założenia wnioskujemy, że zachodzi również $\varphi (\beta ),$ a zatem $\beta \not \in U.$ Uzyskana sprzeczność kończy dowód.

Przy powyższym sformułowaniu twierdzenia nie jest potrzebne dodatkowe założenie, że prawdą jest $\varphi (\varnothing )$ – tzw. „zerowy krok indukcyjny”. Zdanie $\varphi (\varnothing )$ wynika z już przyjętego założenia dla $\alpha =\varnothing ,$ ponieważ wtedy poprzednik implikacji jest spełniony w sposób pusty, a więc i następnik $\varphi (\varnothing )$ musi być prawdziwy.

Twierdzenie o definicji indukcyjnej

Przypuśćmy, że $f\colon \mathbf {V} \longrightarrow \mathbf {V}$ jest klasą, która jest też funkcją. Wówczas istnieje jedyna funkcja $g\colon \mathbf {ON} \longrightarrow \mathbf {V}$ (tak więc $g$ jest też klasą) taka, że

$\left(\forall \alpha \in \mathbf {ON} \right)\left(g(\alpha )=f(g\upharpoonright \alpha )\right).$

Uwagi

• W twierdzeniu o definicji indukcyjnej, funkcja $f$ reprezentuje przepis na konstrukcję obiektu związanego z liczbą $\alpha$ przy założeniu, że skonstruowaliśmy już ciąg $\langle g(\beta ):\beta <\alpha \rangle .$
• 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 $\gamma \in \mathbf {ON} .$ 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 $\gamma$).
• 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 $\varphi (0)$ jest prawdziwe,

Krok następnikowy:   pokazujemy, że jeśli $\varphi (\beta )$ jest prawdziwe, to również $\varphi (\beta +1)$ zachodzi,

Krok graniczny:   pokazujemy, że jeśli $\alpha$ jest liczbą graniczną oraz $(\forall \beta <\alpha )(\varphi (\beta ))$ jest prawdziwe, to również $\varphi (\alpha )$ 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ę $\varphi _{f}(x,y)$) można znaleźć klasę $g$ (danej przez formulę $\varphi _{g}$) taką, że

Jeśli $f\colon \mathbf {V} \longrightarrow \mathbf {V}$ jest funkcją, to też $g$ jest funkcją $g\colon \mathbf {ON} \longrightarrow \mathbf {V}$ i

$\left(\forall \alpha \in \mathbf {ON} \right)\left(g(\alpha )=f(g\upharpoonright \alpha )\right).$

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

Jeśli $\left(\forall \alpha \in \mathbf {ON} \right)\left(g(\alpha )=f(g\upharpoonright \alpha )\right)$ i także $\left(\forall \alpha \in \mathbf {ON} \right)\left(g'(\alpha )=f(g'\upharpoonright \alpha )\right),$

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

Przykłady

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
• definicja indeksu Szlenka

Bibliografia

• Kenneth Kunen: Set theory. An introduction to independence proofs, „Studies in Logic and the Foundations of Mathematics”, 102. North-Holland Publishing Co., Amsterdam, New York 1980, ISBN 0-444-85401-0.

Linki zewnętrzne

• Eric W.E.W. Weisstein Eric W.E.W., Transfinite Induction, [w:] MathWorld, Wolfram Research  (ang.). [dostęp 2024-03-07].