Twierdzenie o pełności, czyli dlaczego każdy niesprzeczny system aksjomatów ma model

W matematyce używamy metody aksjomatycznej, to znaczy przyjmujemy pewne założenia wyjściowe, zwane aksjomatami, i zgodnie z pewnymi przyjętymi regułami rozumowania wyprowadzamy z nich wnioski. Dlatego fundamentalne jest zagadnienie, jakie tezy matematyczne wynikają z jakich aksjomatów. Szczególnym przypadkiem tego zagadnienia było na przykład rozważane przez wiele wieków pytanie, czy tak zwany piąty postulat Euklidesa wynika z pozostałych aksjomatów jego geometrii. Ostatecznie okazało się, że nie, co doprowadziło do powstania geometrii nieeuklidesowych.

Jak uzasadnić, że jakieś twierdzenie T wynika z danego zbioru aksjomatów A? Co do zasady jest to proste: można po prostu udowodnić T, przyjmując A jako założenia. Jak natomiast pokazać, że T nie wynika z A? Zwykle robi się to, konstruując strukturę matematyczną spełniającą wszystkie aksjomaty A – coś takiego nazywamy modelem dla A – w której twierdzenie T nie jest prawdziwe. To prowadzi do pytania, czy możliwa byłaby niepokojąca sytuacja pośrednia, w której ani nie da się udowodnić T za pomocą A, ani nie da się zbudować modelu dla A, w którym T nie zachodzi.

Otóż jeśli dobrze zdefiniujemy pojęcie aksjomatu i reguły rozumowania, to taka sytuacja jest niemożliwa. Mówi o tym tak zwane twierdzenie o pełności: każdy system aksjomatów, za którego pomocą nie da się udowodnić sprzeczności, ma model. Łatwo z tego wynika, że jeśli z A nie da się udowodnić T, to istnieje model dla A, który zarazem nie jest modelem dla T. Na wykładzie spróbujemy wyjaśnić znaczenie twierdzenia o pełności i opowiedzieć o tym, jak się go dowodzi.