Czytaj więcej"/> Drukuj
Aksjomat indukcji to 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) ^ ( An T(n)=>T(n+1)) => An T(n) } \]
Gdzie An oznacza: "dla każdego n" => to wynikanie (implikacja) ^ oznacza "i". Tak wyrażony aksjomat indukcji nie spełnia jednak założeń rozlicznych podejść, a w tym np. analizy Goedla 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) ^( T(1)=>T(2) ) => T(2) ^ ... ^ ... \]
w której to notacji nie został użyty nieograniczony a wiec nieobliczalny (nierekurencyjny) kwantyfikator ogólny, zaś wszystkie zdania są 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.
Jako ciekawostkę można nadmienić, że 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)=>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).

Literatura

Materiał wydrukowany z portalu zgapa.pl dnia 2019-12-13 12:32:20