Twierdzenia Gödla

Twierdzenia Gödla to dwa kluczowe wyniki w logice matematycznej i metamatematyce, które zostały udowodnione przez Kurta Gödla w 1931 roku:

Twierdzenie o niezupełności arytmetyki
Twierdzenie o niedowodliwości niesprzeczności

Oba twierdzenia mają istotne znaczenie dla filozofii matematyki i są odpowiedzią na próbę formalizacji matematyki przy użyciu aksjomatów i reguł wnioskowania, co było celem m.in. Davida Hilberta.

Kontekst

Główne pojęcia związane z twierdzeniami Gödla obejmują:

Język – zbiór termów tworzonych zgodnie z regułami.
System formalny – zbiór aksjomatów i reguł wnioskowania, który generuje podzbiór zdań.
System formalny niesprzeczny – system, w którym nie można jednocześnie udowodnić zdania i jego zaprzeczenia.
System formalny zupełny – system, w którym można dowieść każdego prawdziwego zdania lub jego zaprzeczenia.

Twierdzenia Gödla

Pierwsze, o niezupełności

Twierdzenie o niezupełności stwierdza, że każdy niesprzeczny system formalny pierwszego rzędu, który zawiera aksjomaty Peana, jest niezupełny. Oznacza to, że nie ma sposobu, aby taki system objął wszystkie prawdziwe twierdzenia arytmetyki.

Drugie, o niedowodliwości niesprzeczności

Drugie twierdzenie głosi, że w żadnym niesprzecznym systemie formalnym pierwszego rzędu z aksjomatami Peana nie można dowieść jego własnej niesprzeczności. Dowód tego wymaga szerszego systemu.

Zarys dowodu

Gödel wprowadził przyporządkowanie liczb do predykatów arytmetyki, co pozwala na analizę dowodów w systemach formalnych. Kluczowym elementem jest konstrukcja zdania Gödla, które stwierdza, że nie ma dowodu dla siebie samego, co prowadzi do wniosku o niezupełności systemu.

Wnioski

Twierdzenia Gödla można uogólnić na różne systemy formalne, które zawierają arytmetykę liczb naturalnych. Dodawanie kolejnych twierdzeń G₀, G₁, itd. pokazuje, że zawsze istnieją nowe niezależne zdania.