Aksjomat indukcji

Ten artykuł od 2020-11 zawiera treści, przy których brakuje odnośników do źródeł. Należy dodać przypisy do treści niemających odnośników do źródeł. Dodanie listy źródeł bibliograficznych jest problematyczne, ponieważ nie wiadomo, które treści one uźródławiają. Sprawdź w źródłach: Encyklopedia PWN • Google Books • Google Scholar • Federacja Bibliotek Cyfrowych • BazHum • BazTech • RCIN • Internet Archive (texts / inlibrary) Po wyeliminowaniu niedoskonałości należy usunąć szablon {{Dopracować}} z tego artykułu.

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:

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

gdzie ${\displaystyle \forall n}$ oznacza: „dla każdego n” ⇒, to wynikanie (implikacja) ${\displaystyle \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:

${\displaystyle 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 ${\displaystyle T(n)}$ dla każdego ${\displaystyle n,}$ to twierdzenie ${\displaystyle 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 ${\displaystyle T(n)\Rightarrow T(n+1)}$), zapisanego za pomocą języka arytmetyki i obejmującego wszystkie możliwe wartości ${\displaystyle n}$ (dla każdego n pojawia się pewien nowy element niewystępujący dla innych ${\displaystyle 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.