Aksjomat indukcji

Aksjomat indukcji – aksjomat, a właściwie nieskończony przeliczalny zbiór aksjomatów pierwszego rzędu, pozalogicznych rozważany zwłaszcza w teorii arytmetyki liczb naturalnych. Jest on formalizacją zasady indukcji matematycznej.

Jego treść przedstawia się następująco:

$(T(1)\wedge \forall n:T(n)\Rightarrow T(n+1))\Rightarrow \forall n:T(n),$

gdzie $\forall n$ oznacza: „dla każdego n” ⇒, to wynikanie (implikacja) $\wedge$ oznacza „i”. Tak wyrażony aksjomat indukcji nie spełnia jednak założeń rozlicznych podejść, a w tym np. analizy Gödla niesprzeczności teorii matematycznych w szczególności arytmetyki. Problemem jest zupełna nieobliczalność relacji użytych do konstrukcji powyższego zdania: kwantyfikator ogólny „dla każdego n” nie da się bowiem zapisać jako funkcja obliczalna. Ponadto zdanie powyższe jest zdaniem drugiego rzędu z uwagi na użycie kwantyfikatora, co sprawia, że operuje ono obiektami niezdefiniowanymi w teorii (zbiorem liczb naturalnych n, z którego mamy wybierać wartości: nie można go skonstruować, zanim nie ustalimy listy aksjomatów i nie udowodnimy ich niesprzeczności).

Równoważnie aksjomat indukcji można zapisać jako koniunkcję zbioru aksjomatów w następującej postaci:

$T(1)\wedge (T(1)\Rightarrow T(2))\Rightarrow T(2)\wedge \ldots \wedge \ldots ,$

w której to notacji nie został użyty nieograniczony, a więc nieobliczalny (nierekurencyjny) kwantyfikator ogólny, wszystkie zdania są zaś pierwszego rzędu (wyrażają prawdy o zdefiniowanych wcześniej pojęciach pierwotnych arytmetyki, nie używając kwantyfikatora ogólnego). Uzyskujemy w ten sposób formalną poprawność sformułowania aksjomatu.

Aksjomaty indukcji są ważnym elementem teorii arytmetyki.

Znane są przykłady twierdzeń, w których chociaż znamy dowody twierdzenia $T(n)$ dla każdego $n,$ to twierdzenie $T(n)$ nie może być dowiedzione w ramach arytmetyki liczb naturalnych (jest niedowiedlne), gdyż każdy z tych dowodów jest prowadzony za pomocą innych narzędzi i nie da się ich sprowadzić do kroku indukcyjnego (a więc rozumowania wykazującego $T(n)\Rightarrow T(n+1)$), zapisanego za pomocą języka arytmetyki i obejmującego wszystkie możliwe wartości $n$ (dla każdego n pojawia się pewien nowy element niewystępujący dla innych $n$).

Zobacz też

• aksjomat nieskończoności
• indukcja matematyczna

Bibliografia

• Roman Murawski, Funkcje rekurencyjne i elementy metamatematyki. Problemy zupełności, rozstrzygalności, twierdzenia Gödla, Wydawnictwo Naukowe UAM, Poznań 1990.