Tekst źródłowy strony Aksjomat indukcji

{{dopracować|przypisy=2020-11}}
'''Aksjomat indukcji''' – [[aksjomat]], a właściwie nieskończony [[Zbiór przeliczalny|przeliczalny]] zbiór aksjomatów pierwszego rzędu, pozalogicznych rozważany zwłaszcza w teorii arytmetyki [[Liczby naturalne|liczb naturalnych]]. Jest on formalizacją zasady [[Indukcja matematyczna|indukcji matematycznej]].

Jego treść przedstawia się następująco:
: <math>(T(1) \wedge \forall n: T(n) \Rightarrow T(n+1)) \Rightarrow \forall n: T(n),</math>

gdzie <math>\forall n</math> oznacza: „dla każdego n” ⇒, to wynikanie ([[Implikacja logiczna|implikacja]]) <math>\wedge</math> 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 [[arytmetyka|arytmetyki]]. Problemem jest zupełna [[obliczalność|nieobliczalność]] [[relacja (matematyka)|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:
: <math>T(1) \wedge (T(1) \Rightarrow T(2)) \Rightarrow T(2) \wedge \ldots \wedge \ldots,</math>

w której to notacji nie został użyty '''nieograniczony''', a więc nieobliczalny ([[Rekurencja|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 <math>T(n)</math> dla każdego <math>n,</math> to twierdzenie <math>T(n)</math> 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 <math>T(n) \Rightarrow T(n+1)</math>), zapisanego za pomocą języka arytmetyki i obejmującego wszystkie możliwe wartości <math>n</math> (dla każdego n pojawia się pewien nowy element niewystępujący dla innych <math>n</math>).

== 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.

[[Kategoria:Aksjomaty matematyczne]]