A | B | C | D | E | F | G | H | CH | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
Gödelovy věty o neúplnosti jsou dvě důležité matematické věty, které mají zcela výsadní postavení v celé moderní matematické logice. Důležitou roli však hrají v celé matematice, zejména pak v teorii modelů, aritmetice (respektive teorii čísel) a v teorii množin. Dokázal je roku 1931 rakouský logik Kurt Gödel.
Gödelovy věty jsou velmi významné i z hlediska filosofie matematiky, stanovují totiž hranice axiomatické metody v matematice. Plyne z nich například neproveditelnost takzvaného Hilbertova programu, který si kladl za cíl vytvořit bezespornou, úplnou teorii, s efektivně zadatelnou množinou axiomů, v níž by bylo možné interpretovat aritmetiku přirozených čísel.
Klasické znění
Následující věty jsou formulovány velmi podobně tomu, jak je původně dokázal Kurt Gödel. Originální Gödelova terminologie i notace jsou ovšem v důsledku bouřlivého rozvoje matematické logiky následujícím po jeho objevu pro současného čtenáře téměř neproniknutelné. Proto jsou zde uvedené věty přeloženy do srozumitelnějšího jazyka moderní matematiky. Tímto překladem došlo sice k mírnému zesílení těchto vět, ne však k zesílení podstatnému. Pozdější zobecnění Gödelových vět jsou uvedena v dalších odstavcích.
První Gödelova věta o neúplnosti
Znění
Nechť T je rekurzivně axiomatizovaná teorie v jazyce aritmetiky obsahující Robinsonovu aritmetiku, taková, že struktura přirozených čísel je jejím modelem. Pak existuje sentence , která není v T dokazatelná ani vyvratitelná.
Formule z této věty má svůj vlastní název – Gödelova formule.
Význam
Označme na chvíli za rozumnou takovou axiomatickou teorii schopnou hovořit o přirozených číslech, jejich sčítání a násobení, v níž:
- není možné dokázat cokoli (např. nesmysly jako ), a zároveň takovou, že
- jsme schopni o každém tvrzení rozhodnout (v konečném čase), zda je, či není axiomem této teorie.
Každý jistě uzná, že oba tyto požadavky jsou skutečně „rozumné“ – jinak bychom totiž buďto mohli dokázat jakékoli nesmysly nebo bychom naopak ani nevěděli, jaké předpoklady můžeme v důkazech využít.
To, co jsme právě nazvali rozumná teorie, je jen poněkud méně přesně přeříkaný matematický termín bezesporná rekurzivně axiomatizovaná teorie v jazyce aritmetiky. Pokud navíc v takové rozumné teorii budou dokazatelné základní vlastnosti přirozených čísel (jako například ), znamená to, že tato teorie obsahuje Robinsonovu aritmetiku.
To, že struktura přirozených čísel je modelem této teorie, znamená, že nic z toho, co v naší teorii můžeme dokázat o přirozených číslech, neodporuje tomu „jak to skutečně je“.
Tedy tvrzení „teorie obsahuje Robinsonovu aritmetiku a přirozená čísla jsou jejím modelem“ znamená, že tato teorie skutečně hovoří o těch přirozených číslech, které známe, a ne o nějakých podivných jiných.
První Gödelova věta pak říká, že kdykoli máme rozumnou teorii hovořící o našich přirozených číslech, pak tato teorie není dostatečně silná, aby byla schopná dokázat o přirozených číslech vše. Tedy ideální teorie požadovaná v Hilbertově programu neexistuje.
Druhá Gödelova věta o neúplnosti
Znění
V Peanově aritmetice není dokazatelná ani vyvratitelná sentence , kde je formule, která ve struktuře přirozených čísel vyjadřuje skutečnost, že Peanova aritmetika je bezesporná.
Význam
První Gödelova věta říká, že v žádné rozumné teorii hovořící o přirozených číslech není dokazatelné vše. Druhá Gödelova věta dává konkrétní příklad takového nedokazatelného tvrzení pro Peanovu aritmetiku – je jím věta „Peanova aritmetika je bezesporná.“
Zobecnění a zesílení Gödelových vět
Klasifikace složitosti Gödelovy formule
První Gödelovu větu lze zesílit tvrzením, že tam definovaná Gödelova formule je formule (viz Aritmetická hierarchie). Z tohoto zesílení tedy plyne, že v teorii T splňující předpoklady první Gödelovy věty existuje nezávislá formule nejnižší možné složitosti ( je a tedy je ). Každá formule je totiž v takové teorii již dokazatelná nebo vyvratitelná (podle toho, zda ona nebo její negace platí v přirozených číslech – to plyne z věty o sigma úplnosti Robinsonovy aritmetiky).
Navíc lze dokázat, že Gödelova formule platí ve struktuře přirozených čísel.
Rosserova věta
Předpoklad o tom, že struktura přirozených čísel je modelem T je možné v První Gödelově větě vynechat. To říká Rosserova věta:
Nechť T je bezesporná rekurzivně axiomatizovatelná teorie v jazyce aritmetiky obsahující Robinsonovu aritmetiku. Pak existuje sentence , která není v T dokazatelná ani vyvratitelná.
Formule z této věty má svůj vlastní název – Rosserova formule.
Zobecněná věta o neúplnosti
Druhou Gödelovu větu lze zobecnit následujícím způsobem:
Nechť T je bezesporná rekurzivně axiomatizovatelná teorie a existuje interpretace teorie (viz teorie IΣ1) v T (k tomu stačí existence interpretace Peanovy aritmetiky v T). Pak v teorii T je nezávislá formule vyjadřující (formální) bezespornost teorie T.
Z takto zobecněné věty plyne například neúplnost libovolného rekurzivního rozšíření Zermelo-Fraenkelovy (a tedy též Gödel-Bernaysovy) teorie množin. Všechny konečné ordinály totiž tvoří obor interpretace Peanovy aritmetiky v teorii množin.
Nerozhodnutelnost bezesporných rozšíření Robinsonovy aritmetiky
Pomocí metod teorie vyčíslitelnosti lze dokázat tvrzení, jehož snadným důsledkem je první Gödelova věta. Toto tvrzení zní následovně:
Každé bezesporné rozšíření Robinsonovy aritmetiky je nerozhodnutelné (dokonce rekurzivně neoddělitelné). Je-li tedy rekurzivně axiomatizovatelné, je neúplné.
Toto tvrzení má svůj vlastní význam a neslouží pouze k pohodlnému důkazu první Gödelovy věty. Plyne z něj totiž například nerozhodnutelnost teorií okruhů, komutativních okruhů, oborů integrity, těles a těles charakteristiky nula.
Zajímavé příklady nezávislých tvrzení
V teorii množin
V teorii množin existuje velmi mnoho nezávislých tvrzení. Konkrétně v Zermelo-Fraenkelově axiomatizaci to jsou například následující:
- Axiom výběru
- Hypotéza kontinua
- Hypotéza singulárních kardinálů
- Martinův axiom
- Zobecněná hypotéza kontinua
- Diamantový princip
- Axiomy existence velkých kardinálů
V Peanově aritmetice
Po důkazu Gödelových vět se matematici snažili nalézt příklady konkrétních zajímavých matematických tvrzení, která jsou nedokazatelná v Peanově aritmetice. Ukázalo se, že jde o velmi obtížný problém. Díky práci L. Kirbiho a J. Parise je známo několik málo takových tvrzení. Jsou to:
- Různé silnější varianty Ramseyovy věty
- Goodsteinova věta
Odkazy
Literatura
- Kurt Gödel, Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme, I., Monatshefte für Mathematik und Physik 38: 173–98, 1931. (původní Gödelův článek)
- Vítězslav Švejdar, Logika – neúplnost, složitost a nutnost, Academia, Praha, 2002, ISBN 80-200-1005-X
- K. Devlin, Jazyk Matematiky, Argo, Praha 2003
- SMULLYAN, Raymond M. Navěky nerozhodnuto : úvod do logiky a zábavný průvodce ke Gödelovým objevům. Praha: Academia, 2003. 308 s. ISBN 80-200-1068-8.
Související články
- Löbova věta
- Diagonální lemma
- Hilbertův program
- Kurt Gödel
- Gödelova věta o úplnosti predikátové logiky
Externí odkazy
- Náčrt důkazu Gödelových vět – obsahuje všechny hlavní myšlenky, nikoli však technické detaily (anglicky)
- Martin Hirzel, On formally undecidable propositions of Principia Mathematica and related systems I. Archivováno 16. 9. 2004 na Wayback Machine., 2000. (ke stažení anglický překlad originálního Gödelova článku)
Text je dostupný za podmienok Creative Commons Attribution/Share-Alike License 3.0 Unported; prípadne za ďalších podmienok. Podrobnejšie informácie nájdete na stránke Podmienky použitia.
Antény
Chemické zdroje elektriny
Chladenie v elektrotechnike
Elektrická sústava automobilu
Elektrická trakcia
Elektrické prístroje
Elektrické súčiastky
Elektrické spotrebiče
Elektrické stroje
Čítanie (elektrotechnika)
Činný výkon
Štatistická dynamika
Živý vodič
Admitancia
Antiparalelné zapojenie
Asynchrónny motor
Blúdivý prúd
Bočník (elektrotechnika)
Diak (polovodičový prvok)
Displej s kvapalnými kryštálmi
Elektrická inštalácia
Elektrická rezonancia
Elektrická sila
Elektrická vodivosť
Elektrické zariadenie
Elektrický obvod
Elektrický zvonec
Elektroenergetika
Elektromer
Elektrometer
Elektromobil
Elektromotor
Elektromotorické napätie
Elektrotechnický náučný slovník
Elektrotechnika
Elektrotechnológia
Fázor
Faradayova klietka
Frekvencia (fyzika)
Graetzov mostík
Impedancia
Indukčnosť
Induktancia
Istič
Izolácia (elektrotechnika)
Izolant
Jadro vodiča
Jednobran
Jednosmerný prúd
Joulovo teplo
Katóda
Koaxiálny kábel
Kompenzácia účinníka
Konduktometria
Konektor (elektrotechnika)
Korónový výboj
Lanko (elektrotechnika)
Leptanie
Logické hradlo
Magnetická susceptibilita
Magnetizácia (veličina)
Merný elektrický odpor
Mobilné zariadenie
Napájací zdroj
Napäťový chránič
Napäťový násobič
Nortonova veta
Odpínač
Odpojovač
OLED
Olovený akumulátor
Paralelné zapojenie
Peltierov článok
Plošná hustota elektrického prúdu
Poistka (elektrotechnika)
Posuvný prúd
Prúdový chránič
Prenosové médium
Prieletový klystrón
Primárny elektrochemický článok
Reaktancia
Rekuperácia (dopravný prostriedok)
Relé
Reproduktorová výhybka
Rezistancia
Rozhranie (interface)
Sériové zapojenie
Seebeckov jav
Sekundárny elektrochemický článok
Settopbox
Skrat
Sonar
Spínač
Spínaný zdroj
Straty v mikropásikových vedeniach
Striedavý prúd
Stupeň ochrany krytom
Svetelná výbojka
Symetrizačný člen
Technická normalizácia
Tepelné relé
Tepelne vodivostný detektor
Termočlánok
Théveninova veta
Transformátor
Transformátor s fázovou reguláciou
Trojfázová sústava
Tuhá fáza (elektronika)
Tyratrón
Usmerňovač (elektrotechnika)
Uzemnenie
Uzol (vodiče)
Vírivý prúd
Výbojka
Varistor
Ventilátor
Vodič (elektrotechnika)
Voltov stĺp
Vstavaný systém
Zásuvka (elektrotechnika)
Zdroj (elektrotechnika)
Zisk antény
Text je dostupný za podmienok Creative
Commons Attribution/Share-Alike License 3.0 Unported; prípadne za ďalších
podmienok.
Podrobnejšie informácie nájdete na stránke Podmienky
použitia.
www.astronomia.sk | www.biologia.sk | www.botanika.sk | www.dejiny.sk | www.economy.sk | www.elektrotechnika.sk | www.estetika.sk | www.farmakologia.sk | www.filozofia.sk | Fyzika | www.futurologia.sk | www.genetika.sk | www.chemia.sk | www.lingvistika.sk | www.politologia.sk | www.psychologia.sk | www.sexuologia.sk | www.sociologia.sk | www.veda.sk I www.zoologia.sk