Aksjomat indukcji
Aksjomat indukcji to zbiór aksjomatów pierwszego rzędu, które są pozalogiczne i szczególnie istotne w teorii arytmetyki liczb naturalnych. Stanowi on formalizację zasady indukcji matematycznej.
Treść aksjomatu indukcji można sformułować w następujący sposób:
(
T(1)
∧
∀n:
T(n) ⇒ T(n + 1)
)
⇒
∀n:
T(n),
gdzie
∀n oznacza „dla każdego n”, a ⇒ to symbol implikacji.
∧ oznacza „i”. Taki zapis aksjomatu indukcji nie spełnia jednak założeń wielu podejść, w tym analizy Gödla dotyczącej niesprzeczności teorii matematycznych, szczególnie arytmetyki. Problemem jest całkowita nieobliczalność relacji używanych w powyższym sformułowaniu: kwantyfikator ogólny „dla każdego n” nie może być przedstawiony jako funkcja obliczalna. Dodatkowo, powyższe zdanie jest zdaniem drugiego rzędu ze względu na obecność kwantyfikatora, co powoduje, że odnosi się do obiektów, które nie są zdefiniowane w teorii (jak zbiór liczb naturalnych n, z którego wybieramy wartości: nie można go skonstruować, dopóki nie ustalimy listy aksjomatów i nie udowodnimy ich niesprzeczności).
Aksjomat indukcji można również sformułować jako koniunkcję zbioru aksjomatów w następującej postaci:
T(1) ∧ (T(1) ⇒ T(2)) ⇒ T(2) ∧ … ∧ … ,
w której to notacji nie zastosowano nieograniczonego kwantyfikatora ogólnego, a wszystkie zdania są pierwszego rzędu (wyrażają prawdy o wcześniej zdefiniowanych pojęciach pierwotnych arytmetyki, nie korzystając z kwantyfikatora ogólnego). Dzięki temu uzyskujemy formalną poprawność sformułowania aksjomatu.
Aksjomaty indukcji stanowią kluczowy element teorii arytmetyki.
Istnieją przykłady twierdzeń, w których, mimo że znamy dowody tezy
T(n) dla każdego n,
to twierdzenie
T(n)
nie może być udowodnione w ramach arytmetyki liczb naturalnych (jest niedowiedlne), ponieważ każdy z tych dowodów opiera się na innych narzędziach i nie można ich sprowadzić do kroku indukcyjnego (a więc rozumowania wykazującego
T(n) ⇒ T(n + 1)
), zapisanego w języku arytmetyki, który obejmuje wszystkie możliwe wartości n (dla każdego n pojawia się pewien nowy element, który nie występuje dla innych n).
Zobacz też
Bibliografia
Roman Murawski, Funkcje rekurencyjne i elementy metamatematyki. Problemy zupełności, rozstrzygalności, twierdzenia Gödla, Wydawnictwo Naukowe UAM, Poznań 1990.
Loading ...