Niesprzeczność

Niesprzeczność – brak sprzeczności teorii logicznej. Można go zdefiniować semantycznie albo syntaktycznie. Definicja semantyczna postuluje, że teoria jest niesprzeczna, jeśli posiada model. Odpowiada to pojęciu niesprzeczności w tradycyjnej logice Arystotelesa, aczkolwiek w dzisiejszej logice matematycznej używa się w zamian określenia spełnialności. Definicja syntaktyczna mówi, że teoria jest niesprzeczna, jeśli nie ma takiej formuły $P,$ że zarówno $P,$ jak i jej zaprzeczenie można wyprowadzić z aksjomatów danej teorii za pomocą powiązanego z nią systemu dedukcji.

Jeśli dane definicje semantyczne i syntaktyczne są równoważne, to mówi się, że dana logika jest zupełna. Zupełność rachunku zdań została wykazana przez Paula Bernaysa w 1918 roku i Emila Posta w 1921 roku, podczas gdy zupełność rachunku kwantyfikatorów została udowodniona przez Kurta Gödla w 1930 r. Silne logiki, takie jak rachunek predykatów drugiego rzędu, nie są zupełne.

Wczesny rozwój teorii dowodu był napędzany chęcią podania skończonych dowodów niesprzeczności dla całej matematyki w ramach programu Hilberta. Postulatami programu Hilberta wstrząsnęło twierdzenie Gödla o niedowodliwości niesprzeczności, które uzmysłowiło matematykom, że dostatecznie bogate teorie dowodzenia nie pozwalają na wykazanie niesprzeczności samych siebie (przy założeniu, że są one rzeczywiście niesprzeczne).

Pomimo iż niesprzeczność można wykazać za pomocą teorii modeli, to często robi się to, opierając się wyłącznie na syntaktyce, bez odnoszenia się do modeli.

Formuły

Zbiór formuł $\Phi$ rachunku predykatów pierwszego rzędu jest niesprzeczny, symbolicznie $\operatorname {Con} \Phi ,$ wtedy i tylko wtedy, gdy nie ma formuły $\phi$ takiej, że $\Phi \vdash \phi$ i $\Phi \vdash \lnot \phi .$ W przeciwnym razie $\Phi$ jest sprzeczny i piszemy $\operatorname {Inc} \Phi .$

Następujące zdania są równoważne:

$\operatorname {Inc} \Phi$
Dla każdego $\phi ,\;\Phi \vdash \phi .$

Każdy spełnialny zbiór formuł jest niesprzeczny, przy czym zbiór formuł $\Phi$ jest spełnialny wtedy i tylko wtedy, gdy istnieje model ${\mathfrak {I}},$ taki że ${\mathfrak {I}}\vDash \Phi .$

Dla każdego $\Phi$ i $\phi {:}$

jeśli nie $\Phi \vdash \phi ,$ to $\operatorname {Con} \Phi \cup \{\lnot \phi \};$
jeśli $\operatorname {Con} \Phi$ i $\Phi \vdash \phi ,$ to $\operatorname {Con} \Phi \cup \{\phi \};$
jeśli $\operatorname {Con} \Phi ,$ to $\operatorname {Con} \Phi \cup \{\phi \}$ lub $\operatorname {Con} \Phi \cup \{\lnot \phi \}.$

Niesprzeczność i zupełność arytmetyki

W teoriach arytmetyki, takich jak arytmetyka Peana, zachodzi dogłębna zależność pomiędzy niesprzecznością danej teorii i jej zupełnością. Teoria jest zupełna, jeśli dla każdej formuły $\phi$ w jej języku przynajmniej jedna z formuł $\phi$ lub $\neg \phi$ jest logiczną konsekwencją danej teorii.

Arytmetyka Presburgera jest układem aksjomatycznym liczb naturalnych z dodawaniem, który jest zarówno niesprzeczny, jak i zupełny.

Twierdzenie Gödla o niezupełności pokazuje, że żadna dostatecznie silna efektywna teoria arytmetyki nie może być jednocześnie zupełna i niesprzeczna. Twierdzenie Gödla obejmuje arytmetykę Peana (PA) i prostą arytmetykę rekurencyjną (PRA), lecz nie arytmetykę Presburgera.

Ponadto drugie twierdzenie Gödla o niezupełności pokazuje, że dostatecznie silna efektywna teoria arytmetyki jest niesprzeczna wtedy i tylko wtedy, gdy nie ma w niej dowodu dla specyficznego zdania, zwanego zdaniem Gödla danej teorii. Zdanie to jest sformalizowanym stwierdzeniem, iż dana teoria jest rzeczywiście niesprzeczna. Tak więc niesprzeczność dostatecznie bogatej, efektywnej, niesprzecznej teorii arytmetyki nigdy nie może zostać udowodniona w ramach takiej teorii. Ten sam wynik zachodzi dla efektywnych teorii obejmujących dostatecznie bogaty fragment arytmetyki – włącznie z takimi teoriami jak teoria mnogości Zermela-Fraenkla. W tych teoriach mnogości nie można wykazać prawdziwości ich wyrażeń Gödla, nawet zakładając ich niesprzeczność.

Zobacz też

Bibliografia

Andrzej Mostowski: Logika matematyczna. [dostęp 2012-12-07].
H.D. Ebbinghaus, J. Flum, W. Thomas: Mathematical Logic. (ang.).
W.S. Jevonss: Elementary Lessons in Logic. 1870. (ang.).