Aksjomat indukcji
Z Wikipedii
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:
,
gdzie 
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:
,
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.
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).
[edytuj] Literatura
- Roman Murawski, Funkcje rekurencyjne i elementy metamatematyki. Problemy zupełności, rozstrzygalności, twierdzenia Gödla, Wydawnictwo Naukowe UAM, Poznań 1990.
[edytuj] Zobacz też
| "Telefoniczne portfele" pojawiÄ… siÄ™ w Europie? |
|
"Telefoniczny portfel" - technologia umożliwiająca zdalne płatności przez telefon komórkowy może wkrótce pojawić się w Europie i USA. Promocję, rozpoczętą przez firmy technologiczne, wesprze japoński rząd.
|
| Bakterie, które lubią arsen |
|
W gorących wodach kalifornijskiego jeziora Mono Lake żyją bakterie, których pokarmem są silnie trujące związki arsenu - informuje "Science".
|
| Przyznano "wodnego Nobla" |
|
W sali Ratusza Sztokholmskiego, w obecności pary królewskiej, następczyni tronu księżniczka Victoria wręczyła w czwartek prof. Johnowi A. Allanowi z Wielkiej Brytanii przyznaną już po raz 18. nagrodę Stockholm Water Prize, zwaną popularnie "Wodnym Noblem".
|
| Gen raka jelita i marker jego złośliwości |
|
Udało się zidentyfikować gen związany z podwyższonym ryzykiem raka jelita grubego oraz białko, którego obecność wskazuje na szczególnie niebezpieczny rodzaj guza.
|
| Prekolumbijskie groby odkryto w Peru |
|
W Parku Archeologicznym Machu Picchu w peruwiańskim Cusco odkryto w jaskini ludzkie szczątki, pochowane wraz z wyrobami ceramicznymi i tekstylnymi z okresu prekolumbijskiego - donosi serwis internetowy ANDINA.
|