Wykład piętnasty

(Materiał uzupełniający)

Temat XV

Metalogika

Semantyczne zagadnienia metalogiki

Podstawowe pojęcia semantyczne:

- system dedukcyjny

- teza systemu dedukcyjnego

- system aksjomatyczny

- antynomia semantyczna

- spełnianie

- prawda, wyrażenie prawdziwe

- model systemu/teorii

- wynikanie logiczne

- pełność systemu = zupełność (semantyczna)

1. Antynomie semantyczne i ich analiza

Paradoks logiczny

Paradoks logiczny jest pozornie poprawnym rozumowaniem, które prowa­dzi do sprzeczności lub też do konkluzji niezgodnych z doświadczeniem lub ze „zdrowym rozsądkiem”. Najbardziej interesujące paradoksy starożytne pocho­dzą ze szkoły megarejskiej (IV w. p.n.e.). Najsłynniejszym spośród nich jest Eubulidesowy paradoks kłamcy. Eubulides, współczesny Arystotelesowi, przypi­sał Epimenidesowi z Krety zdanie: Wszyscy Kreteńczycy kłamią. Analiza „popra­wionej” wersji wypowiedzi Epimenidesa prowadzi do sprzeczności. Rozważmy zdanie oznaczone (Epi):

„Zdanie (Epi) jest fałszywe”.

Wskazane zdanie jest prawdziwe, jeśli to, co głosi jest prawdą, a zatem, gdy jest fałszywe. Z kolei, jeśli (Epi) jest fałszywe, to nie jest tak, jak stwierdza, a więc jest prawdziwe. Wniosek: (Epi) jest prawdziwe wtedy i tylko wtedy, gdy jest fałszywe.

G. Malinowski Logika ogólna, s. 12

Wersja paradoksu kłamcy (por. podrozdz. 1.1):

Zdanie tu napisane jest fałszywe.

Jeśli napisane zdanie jest prawdziwe, to głosi prawdę, a zatem jest fałszywe. Jeśli zaś jest fałszywe, to nie jest tak, jak głosi, a więc jest prawdziwe. Sprzeczność.

G. Malinowski Logika ogólna, s. 20

---------------------------

Inne paradoksy logiczne

Paradoks golibrody: golibroda goli tych i tylko tych, którzy sami się nie golą. Czy golibroda goli się samemu ?

Paradoks ciotki: ciotka lubi tych, co nie lubią siebie. Czy ciotka siebie lubi ?

Antynomie semantyczne

Antynomia (gr. αντινοµια antinomia) to sprzeczność zachodząca między dwoma twierdzeniami, z których każde wydaje się równie prawdziwe i uzasadnione.

Antynomiami semantycznymi są antynomie, w sformułowaniu których występują terminy semantyczne, odnoszące zwroty języka do oznaczanej przez nie rzeczywistości.

Antynomia kłamcy

Pochodząca od Eubulidesa antynomia kłamcy w sformułowaniu pochodzącym od

J. Łukasiewicza:

R Zdanie napisane w ramce R nie jest prawdziwe.

Wewnętrzną sprzeczność powyższego zdania można wyprowadzić łącznie z napisu zawartego w ramce R oraz z definicja zdania prawdziwego następująco. Niech (a) oznacza:

(a) Zdanie napisane w ramce R = „Zdanie napisane w ramce R nie jest prawdziwe.”

Prawdziwość (a) opiera się na spostrzeżeniu (wzrokowym), że zdanie napisane w ramce R jest identyczne z tym którego nazwa (w cudzysłowie) znajduje się z prawej strony przesłanki (a). Natomiast (b) – wersja klasycznej definicji prawdy – jest określeniem zdania prawdziwego:

(b) Zdanie „p” jest prawdziwe wtedy i tylko wtedy, gdy p (w skrócie: „p” jest prawdziwe ≡ p)

Jeśli w (b) podstawimy za zmienną zdaniową p zdania napisanego w ramce R, otrzymujemy:

(c) „Zdanie napisane w ramce R nie jest prawdziwe” jest prawdziwe ≡

Zdanie napisane w ramce R nie jest prawdziwe.

Wstawiając, na podstawie reguły zastępowania, za lewą stronę równoważności (c) identyczną z nią część (a) [część ciemnoczerwoną za niebieską], otrzymujemy:

Zdanie napisane w ramce R jest prawdziwe ≡ Zdanie napisane w ramce R nie jest prawdziwe.

Antynomia kłamcy jest antynomią pojęcia prawdziwości.

Inne antynomie semantyczne:

Antynomia pojęcia denotowania (antynomia Berry’ego)

Przez wyrażenie będziemy rozumieli wyrażenie języka polskiego zapisane zgodnie z obowiązującymi zasadami ortografii. Ma więc sens mówienie o liczbie liter dowolnego wyrażenia. Na przykład wyrażenie czcze gadanie zawiera 12 liter. Weźmy teraz pod uwagę te wyrażenia, które są nazwami pewnych liczb naturalnych, np.

- sto dwadzieścia siedem

- liczba naturalna, której kwadrat jest równy 25

- liczba słoni znajdujących się w Polsce dnia 23 lutego 1989 roku

Wszystkich wyrażeń jest nieskończenie wiele, ale wyrażeń zawiera­jących dokładnie 1000 liter jest tylko skończenie wiele: jest ich co najwyżej tyle, ile wynosi liczba wszystkich liter podniesiona do potęgi 1000. Skończona jest także liczba wszystkich wyrażeń zawierających co najwyżej 1000 liter. Wynika stąd, że i liczba wyrażeń co najwyżej tysiącliterowych nazywających liczby naturalne jest skończona. Muszą zatem istnieć liczby naturalne, których nie można nazwać za pomocą takich wyrażeń, a wśród nich istnieje najmniejsza. Oznaczmy ją sobie przez m. Tak więc m jest najmniejszą liczbą naturalną, której nie można nazwać za pomocą żadnego wyrażenia zawierającego nie więcej niż tysiąc liter. Jednak wyrażenie:

najmniejsza liczba naturalna, której nie można nazwać za pomocą żadnego wyrażenia zawierającego co najwyżej tysiąc liter

nazywa właśnie liczbę m, a ma tylko 104 litery. Otrzymaliśmy zatem sprzeczność.

Antynomia wyrazów heterologicznych (antynomia Grellinga)

Pewne wyrazy posiadają tę własność, którą same wyrażają (oznaczają). Na przykład przymiot­nik polski sam jest polski, a przymiotnik wielosylabowy sam jest wielosylabowy. Jednak przymiotnik jednosylabowy nie jest jednosylabowy, a przy­miotnik francuski nie jest francuski. Ogólnie wyraz heterologiczny to taki i tylko taki wyraz, który nie oznacza siebie, tzn. który nie posiada tej własności, którą sam wyraża. Heterologiczny jest np. wyraz „Kraków”, gdyż nie oznacza siebie - sam ten wyraz nie jest Krakowem.

Zbadajmy teraz, czy wyraz: heterologiczny sam jest czy nie jest heterologiczny. Gdyby ten wyraz był heterologiczny, to nie oznaczałby siebie, a więc nie miałby własności, którą sam wyraża, czyli nie byłby heterologiczny. Gdyby natomiast ten wyraz nie był heterologiczny, znaczyłoby to, że oznacza siebie, czyli miałby własność, którą wyraża, byłby więc heterologiczny.

Ta antynomia była znana już średniowieczu jako: vox non appellans se – wyraz, który nie nazywa siebie.

- Antynomia pojęcia spełniania (A. Tarski)

- Antynomia pojęcia określania (definiowania) zbioru lub własności przez funkcję zdaniową (antynomia Richarda).

Analiza antynomii semantycznych; język i metajęzyk

W antynomiach semantycznych występują wyrażenia należące do pewnego języka, w których to wyrażeniach pojawiają się terminy dotyczące wyrażeń tego samego języka. Antynomie semantyczne pokazują, że taki system (język), który zawiera w sobie terminy dotyczące wyrażeń do niego należących, jest systemem sprzecznym.

Aby uniknąć antynomii semantycznych, przyjmuje się (za S. Leśniewskim), rozróżnienie między językiem a metajęzykiem. Przy tym odróżnieniu te terminy semantyczne, które odnoszą się do wyrażeń danego języka, należą do jego metajęzyka.

A. Tarski podał metodę poprawnego definiowania terminów semantycznych, tj. terminów w metasystemie M_J (metajęzyku) dotyczących wyrażeń systemu J (języka). Mianowicie:

1) Dla każdego wyrażenia systemu J istnieje w metajęzyku M_J wyrażenie z nim równoznaczne.

2) Dla każdego wyrażenia języka J istnieje w metajęzyku M_J` jego nazwa.

Język i metajęzyk

Ogólnie można powiedzieć tak: jeżeli J₁ jest jakimkolwiek językiem, to za metajęzyk w stosunku do tego języka można przyjąć dowolny język J₂ nadający się do mówienia o języku J₁: o wyrażeniach języka J₁, o zbiorach wyrażeń języka J₁, o związkach pomiędzy wyrażeniami języka J₁ itd. Meta­język J₂ musi więc zawierać nazwy wyrażeń języka J₁ , nazwy przynajmniej niektórych zbiorów wyrażeń języka J₁ itd. Typowymi przykładami pojęć metajęzykowych są: pojęcie formuły zdaniowej języka J₁, pojęcie zdania języka J₁ , pojęcie dowodu i konsekwencji.

Z metajęzykiem mamy zatem do czynienia zawsze wtedy, gdy prowadzone są badania nad jakimś językiem i sformułowaną w nim teorią. Trzeba bowiem w takim przypadku starannie odróżniać język, o którym mówimy, a więc język badany czy też przed­miotowy, oraz język, w którym mówimy, a więc właśnie metajęzyk czy też - jak mówią niektórzy - język podmiotowy. Analogicznie należy odróżnić teorię badaną, przedmiotową i metateorię. Wszystkie antynomie semantyczne miały swe źródło w nieodróżnianiu języka badanego i metajęzyka. One to głównie spowodowały konieczność stosownego odróżnienia. W sposób wyraźny odróżnienie to przeprowadził polski logik A. Tarski (1901 - 1983) w swojej słynnej - choć niewielkiej - książce Pojęcie prawdy w językach nauk dedukcyjnych (Warszawa 1933). On też wprowadził termin metajęzyk.

Tadeusz Batóg Dwa paradygmaty matematyki, s. 63

Wnioski z antynomii semantycznych dla matematyki

Wnioski, które należało wyciągnąć z antynomii semantycznych na użytek matematyki i które wyciągnięto, były następujące: Język dowolnej teorii matematycznej musi być wydzielony z całości języka naturalnego i w tym sensie musi on być sztuczny. Do takiego języka można włączyć wyrażenia o charakterze logicznym (spójniki międzyzdaniowe, kwantyfikatory), zmienne jednego lub wielu rodzajów reprezentujące przedmioty badane w danej teorii, wreszcie pojęcia różnych kategorii (nazwy indywidualne, predykaty, symbole funkcyjne itp.) odnoszące się do tych przedmiotów. Pojęcia lingwistyczne (syntaktyczne i semantyczne) odnoszące się do wyrażeń takiego wyspec­jalizowanego, sztucznego języka muszą się znaleźć poza tym językiem. W ten sposób język teorii matematycznej traci uniwersalność, która jest tak charak­terystyczna dla języka potocznego; jego zdolność wyrażania zostaje w ten sposób zmniejszona na tyle, że antynomię semantyczne znikają, równocześnie jednak jest ona na tyle duża, iż nie przeszkadza to w normalnym formułowaniu wyników badań matematycznych.

Względy powyższe doprowadziły ostatecznie do odróżnienia języka danej teorii i tzw. metajęzyka, czyli języka, w którym wypowiada się twierdzenia o wyrażeniach owego języka teorii. Wszelkie pojęcia lingwistyczne (takie jak choćby pojęcia zdania i oznaczania) należą do metajęzyka: tu są określane i tu ustala się związki pomiędzy nimi. Sam termin „metajęzyk” wprowadził do nauki A. Tarski (1901 - 1983) w roku 1933.

Tadeusz Batóg Dwa paradygmaty matematyki, s. 55

2. Ważniejsze pojęcia semantyczne

L. Borkowski Logika formalna, ss. 371 - 382

Dla określenia ważnych pojęć semantycznych przyjmujemy:

S – system (język) przedmiotowy, oraz

M_S – metasystem (metajęzyk) zawierający terminy dotyczące wyrażeń systemu (języka) S. M_S spełnia przy tym warunki (Tarskiego):

1) Dla każdego wyrażenia systemu S istnieje w metasystemie M_S wyrażenie z nim równoznaczne.

2) Dla każdego wyrażenia systemu S istnieje w metasystemie M_S jego nazwa.

Przez dziedzinę (M) będziemy rozumieć uporządkowany układ

< A; a₁, a₂, … a_k; R₁, R₂, … R_m> złożony z:

a) pewnego zbioru A,

b) pewnych przedmiotów a₁, a₂, … a_k należących do zbioru A oraz

c) relacji R₁,R₂, ..., R_m zachodzących między elementami zbioru A.

Najważniejsze pojęcia semantyczne dotyczące wyrażeń systemu S można zdefiniować przy pomocy pojęcia spełniania wyrażeń systemu S.

Pojęcie spełniania dla funkcji zdaniowej F(x) przez przedmiot a określa się następująco.

Definicja

a spełnia funkcję zdaniową F(x) ≡F(a)

Znaczy to, że jakiś przedmiot a spełnia daną funkcję zdaniową F gdy zachodzi stan rzeczy symbolizowany przez F(a). Przykłady:

Przedmiot (liczba) spełnia 3 funkcję zdaniową F(x): x + 2 = 5, bowiem zachodzi

F(3): 3 + 2 = 5.

Wrocław spełnia funkcję zdaniową F(x): x jest miastem, bo zachodzi

F(Wrocław): Wrocław jest miastem.

W zależności od ilości zmiennych wolnych występujących w danej funkcji zdaniowej mówimy – odpowiednio - o spełnianiu tej funkcji przez jeden przedmiot, przez dwa przedmioty itd. Dla ujednolicenia takich sformułowań będziemy mówić o spełnianiu tej funkcji przez pewien ciąg (uporządkowany układ) przedmiotów. Np. Ciąg liczb: 2, 3 spełnia w dziedzinie liczb wymiernych funkcję zdaniową F(x, y, z) = $\bigvee_{}^{}\text{y\ }$(x< y< z)

przy podstawieniach x = 2, z = 3; istnieje bowiem liczba wymierna y zawarta między 2 a 3.

Przy pomocy pojęcia spełniania wyrażeń systemu S definiujemy pojęcie wyrażenia prawdziwego systemu S w dziedzinie M.

Definicja

Wyrażenie E systemu S jest prawdziwe w dziedzinie M wtedy i tylko wtedy, gdy każdy przedmiot (ciąg przedmiotów),należących do zbioru A dziedziny M, spełnia w M wyrażenie E.

Tak rozumiane pojęcie wyrażenia prawdziwego oznacza zachodzenie w dziedzinie M stanu rzeczy, który to wyrażenie opisuje.

Wy­rażeniami prawdziwymi według tego określenia mogą być zarówno funkcje zdaniowe jak i zdania. Wyrażenia zdaniowe systemu S, które nie są wyrażeniami prawdziwymi w dziedzinie M nazywać będziemy wyrażeniami fałszywymi systemu S w dziedzinie M.

Przy pomocy pojęcia prawdziwości wyrażeń systemu S w dziedzinie M określa

semantyczne pojęcie modelu systemu aksjomatycznego S:

Dziedzina M jest modelem systemu (teorii) S wtedy i tylko wtedy, gdy każda teza systemu S jest wyrażeniem prawdziwym w dziedzinie M.

Modelem systemu S jest więc każda i tylko taka dziedzina, w której prawdziwe są wszystkie tezy systemu S.

Zbiór wyrażeń prawdziwych systemu S w dziedzinie M oznaczymy przy pomocy symbolu E(M). A więc:

H jest wyrażeniem zdaniowym (systemu S) prawdziwym w dziedzinie M ≡ H E(M)

O zbiorze E(M) wyrażeń systemu S prawdziwych w dziedzinie M można udowodnić następujące twierdzenia:

(1) Zbiór E(M) wyrażeń prawdziwych w dziedzinie M jest systemem ze względu
na operację odrywania (jak też ze względu na relacje określone przez inne reguły

logiczne).

Reguły te bowiem od wyrażeń prawdziwych w M pro wadzą do wyrażeń prawdziwych w M.

(2) Zbiór E(M) wyrażeń prawdziwych w dziedzinie M jest zbiorem niesprzecznym.

Wynika to stąd, że dwa wyrażenia sprzeczne nie mogą być zarazem prawdziwe w M.

(3) Zbiór E(M) zdań prawdziwych w dziedzinie M jest zbiorem zupełnym.

Wynika to z metalogicznego prawa wyłączonego środka.

Mówiąc o prawdziwości wyrażeń systemów logicznych mamy na myśli prawdziwość
tych wyrażeń w każdym niepustym zbiorze.

Definicja. Wyrażenie systemu logicznego, które jest prawdziwe w każdej niepustej dziedzinie, nazywa się prawem logicznym lub tautologią.

Przy pomocy pojęcia prawdziwości określa się pojęcie pełności systemu aksjomatycznego:

System S jest pełny wtedy i tylko wtedy, gdy każde wyrażenie prawdziwe systemu S jest tezą systemu S.

Zamiast terminu „pełność systemu” używa się też terminu „zupełność semantyczna

systemu”.

W r. 1930 K. Gödel udowodnił, że węższy rachunek predykatów jest systemem pełnym. Każde więc wyrażenie prawdziwe tego systemu, tj. każde wyrażenie tego systemu praw­dziwe w każdym niepustym zbiorze, jest tezą tego systemu.

Takie systemy (teorie) - oparte na węższym rachunku predykatów - w których oprócz stałych logicznych występują tylko zmienne nazwowe i stałe predykaty specyficzne, nazywa się systemami (teoriami) elementarnymi lub standardowymi.

Twierdzenie Gödla o pełności węższego rachunku predykatów jest równoważne następującemu twierdzeniu:

Dla każdego niesprzecznego systemu standardowego istnieje dzie­dzina M, będąca modelem tego systemu.

Twierdzenie Skolema-Löwenheima głosi, że

Każdy niesprzeczny system standardowy (elementarny) ma model przeliczalny.

Twierdzenie to ma daleko idące konsekwencje, gdyż wynika z niego, że istnieje przeliczalny model dla systemów aksjomatycznej teorii mnogości Zermelo-Fraenkla-Skolema.

3. Twierdzenie Gödla (o niepełności)

W r. 1931 K. Gödel w pracy Űber formal unentscheidbare Sätze der Principia Mathematica und verwandter systeme (O formalnie nierozstrzygalnych zdaniach systemu Principia Mathematica i pokrewnych systemów) udowodnił słynne twierdzenie, zwane twierdzeniem Gödla. Twierdzenie to (w sformułowaniu wzmocnionym następnie przez Rossera) głosi, że

Każdy niesprzeczny system aksjomatyczny zawierający arytmetykę liczb naturalnych

jest niepełny.

A więc, istnieją zdania prawdziwe tego systemu, które nie dają się w nim udowodnić.

Dowód (szkic) [Materiał pomocniczy do tego dowodu został podany niżej, patrz punkt: Do dowodu twierdzenia Gödla]

W dowodzie tego twierdzenia korzysta Gödel z tzw. arytmetyzacji syntaksy. Polega ona na tym, że przyporządkowujemy wzajemnie jednoznacznie symbolom i wyrażeniom systemu S liczby naturalne, będące numerami tych wyrażeń, a zbiorom wyrażeń i re­lacjom zachodzącym między wyrażeniami przyporządkowujemy wzajemnie jednoznacznie zbiory liczb, będących numerami tych wyrażeń, i relacje zachodzące między numerami tych wyrażeń. Na gruncie tego przyporządkowania pewne zdania arytmetyczne, oprócz zwykłej interpretacji arytmetycznej mają także interpretację syntaktyczną, dotyczącą wyrażeń.

Korzystając z takiej arytmetyzacji syntaksy konstruuje Gödel w pewnym systemie S, zawierającym arytmetykę liczb naturalnych, pewne zdanie G. Zdanie to w interpretacji syntaktycznej głosi o sobie, że nie jest ono tezą systemu S.

Gödel dowodzi, że jeśli system S jest niesprzeczny, to ani zdanie G ani negacja zdania G nie są tezami systemu S. Zdanie G jest jednak zdaniem arytmetycznym systemu S, które w interpretacji arytmetycznej głosi, że pewna liczba naturalna, będąca numerem zdania G, nie należy do klasy tych liczb naturalnych, które są numerami tez systemu S.

A więc w rozważanym systemie S, za­wierającym arytmetykę liczb naturalnych,_; istnieje zdanie arytmetyczne G, takie, że ani zdanie G ani jego negacja nie są tezami systemu S. Jedno z tych dwóch zdań sprzecznych jest prawdziwe. W istocie prawdziwe jest zdanie G: w interpretacji syntaktycznej głosi ono o sobie, że nie jest tezą systemu S i faktycznie nie jest tezą tego systemu. Definiując w metasystemie systemu S pojęcie prawdziwości metodą Tarskiego, można udowodnić w tym metasystemie, że zdanie G jest zdaniem prawdziwym systemu S. A więc istnieją zdania prawdziwe systemu S, które nie są tezami systemu S. System S jest więc systemem niepełnym.

Tej niepełności systemu S nie można usunąć dołączając zdanie G do aksjomatów i systemu S. Dla tak bowiem rozszerzonego systemu można znowu metodą wprowadzoną i przez Gödla skonstruować inne zdanie G₁ które w tym rozszerzonym systemie pełni taką samą rolę jak zdanie G w systemie S, które więc nie jest tezą rozszerzonego systemu, choć jest jego zdaniem prawdziwym, i którego negacja również nie jest tezą rozszerzonego systemu.

Znaczenie twierdzenia Gödla

Twierdzenie Gödla odnosi się do wszystkich niesprzecznych systemów aksjomatycznych, które zawierają arytmetykę liczb naturalnych, a więc do systemu aksjomatycznej teorii mnogości, czy też do systemów logiki nie opartych na teorii typów, w których można zbudować arytmetykę liczb naturalnych – przy założeniu niesprzeczności tych systemów. W szczególności aksjo­matyczny system arytmetyki liczb naturalnych (z działaniami dodawania i mnożenia) jest systemem niepełnym.

Twierdzenie Gödla można też sformułować jako twierdzenie stwierdzające, że

Zbiorem nieaksjomatyzowalnym jest zarówno zbiór zdań prawdziwych arytmetyki liczb naturalnych jak również zbiór wyrażeń prawdziwych każdego systemu logiki zawierającego arytmetykę liczb naturalnych.

Zdanie G, o którym była powyżej mowa, jest równoważne zdaniu stwierdzającemu niesprzeczność systemu S. Jeśli więc system S, zawierający arytmetykę liczb naturalnych, jest niesprzeczny, to niesprzeczności systemu S nie można udowodnić w systemie S. Stąd wynika, że jeśli niesprzeczność takiego systemu S można udowodnić w systemie S, to system S jest sprzeczny. W ten sposób Kleene i Rosser udowodnili sprzeczność pewnego systemu Churcha.

Twierdzenie Gödla należy do najdonioślejszych odkryć logicznych XX wieku . Wywarło ono wielki wpływ na kierunek badań nad systemami dedukcyjnymi.

Twierdzenie Gödla wykazuje, że nie można utożsamiać pojęcia tezy logicznej i pojęcia prawdziwego wyrażenia systemu logiki, tj. prawdziwego wyrażenia zbudowanego ze stałych logicznych i zmiennych. W pewnych uboższych systemach logicznych, które są systemami pełnymi, oba te pojęcia mogą mieć ten sam zakres. Np. w rachunku zdań czy też węższym rachunku predykatów każde i tylko prawdziwe wyrażenie takiego systemu jest jego tezą. Jednakże w bogatszych systemach logicznych, do których stosuje się twier­dzenie Gödla, zakresy obu tych pojęć nie pokrywają się. Każda teza logiczna takiego sys­temu jest wyrażeniem prawdziwym tego systemu, ale nie odwrotnie. Istnieją wyrażenia prawdziwe takiego systemu, tj. wyrażenia prawdziwe w każdym niepustym zbiorze, które nie są jego tezami.

Do dowodu twierdzenia Gödla

Zdanie Gödla – G

Φ_i – i–y dowód w systemie S

{Φ_i} – ciąg wszystkich dowodów w systemie S

F_j – j–ta formuły zdaniowa jednoargumentowa systemu S

{F_i} – ciąg wszystkich formuł zdaniowych jednoargumentowych systemu S

Zdanie G – zdanie Gödla, o którym jest mowa w szkicu dowodu, ma postać: F_k(k).

Zachodzi przy tym:

F_k(w) = ∼ ∃x [Φ_x dowodzi F_w(w)]

Zdanie Gödla F_k(k) oznacza, że nie można go dowieść. Gdyby można było go dowieść, byłoby fałszywe, a system byłby sprzeczny, więc jest prawdziwe, choć nie można go dowieść.

Arytmetyzacja syntaksy

Wyrażeniom danego systemu można wzajemnie jednoznacznie przyporządkować liczby naturalne, które nazwiemy numerami tych wyrażeń przy danym przyporządkowaniu. Przyporządkowanie takie można np. ustalić w ten sposób, że symbolom systemu przyporządkujemy wzajemnie jednoznacznie liczby naturalne, będące ich numerami. Zbiór symboli jest bowiem zbiorem przeliczalnym, a więc istnieje relacja wzajemnie jedno­znaczna przyporządkowująca symbolom systemu liczby naturalne. Wyrażenia zdaniowe systemu są pewnymi specjalnymi skończonymi ciągami symboli. Każdemu wyrażeniu zdaniowemu można więc wzajemnie jednoznacznie przyporządkować skończony ciąg liczb, będących numerami symboli, z których jest zbudowane to wyrażenie. Otóż każdemu skończonemu ciągowi liczb naturalnych k₁, k₂, …, k_n można wzajemnie jednoznacznie przyporządkować liczbę naturalną p^k₁¹, p^k₂², …, p^k_nⁿ, gdzie liczby p₁, p₂, … , p_n są kolejnymi liczbami pierwszymi w ciągu liczb pierwszych poczynając od liczby 2. W ten sposób każdemu wyrażeniu zdaniowemu danego systemu odpowiada wzajemnie jednoznacznie liczba naturalna będąca numerem tego wyrażenia.

L. Borkowski Logika formalna, s. 317

Arytmetyzacja języka

Aczkolwiek pojęcie obliczalności w zastosowaniu do zbiorów napisów ma przejrzysty sens intuicyjny, to jednakże celowe wydaje się, by móc ściśle sprowadzić pojęcie obliczalności zbioru napisów do po­jęcia obliczalności zbioru liczb. (Ewentualnie można też starać się o to, żeby odwrotnie: obliczalność zbiorów liczb umieć sprowadzić do intuicyjnie jasnego pojęcia obliczalności zbiorów napisów). Sprowadzenie obliczalności zbiorów napisów do obliczalności zbiorów liczb dokonuje się za pomocą tzw. arytmetyzacji języka. Arytmetyzacją nazywamy efektywne ponu­merowanie wszystkich wyrażeń języka badanej teorii za pomocą liczb naturalnych. Numerację taką opiszemy w zastosowaniu do języka teorii Ar, którą zajmiemy się obecnie nieco bliżej.

Chcąc w wygodny sposób każdemu wyrażeniu przyporządkować pewną liczbę, najpierw przyporządkowujemy pewne liczby podstawowym zna­kom teorii, a następnie dowolne wyrażenia, czyli ciągi skończone znaków podstawowych, przyporządkowujemy liczbom za pomocą rozwinięć liczb na czynniki pierwsze. A więc dziewiętnastu znakom podstawowym teorii Ar (Ar – zbiór numerów twierdzeń arytmetyki) przyporządkowujemy pierwszych 19 liczb:

( ) ∃ ∀ ∼  → ∨ ∧ ≡ 0 S    <  + • P = x I ,

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

Jeśli a jest jednym z powyżej wypisanych 19 znaków podstawowych to przez nr (a) oznaczmy przyporządkowaną mu liczbę napisaną powyżej bezpośrednio pod znakiem a. A więc nr(→)  =  6, nr(∧)  =  8. Każdemu wyrażeniu A będącemu ciągiem symboli podstawowych

A = a₀ a₁ ...,a_n

przyporządkowujemy numer Nr (A) będący liczbą postaci

Nr(A) = 2 ^nr(a0⁾ • 3 ^nr(a1⁾ • … • p_n ^nr(ann⁾ •

A więc wyrażeniu x_I = 0 odpowiada liczba

Nr(‘x_I = 0’) = 2¹⁷• 3¹⁸• 5¹⁶• 7¹⁰.

Podobnie: Nr (‘P (x, x) > 0’) = 2¹⁵• 3¹• 5¹⁷• 7¹⁹• 11¹⁷• 13²• 17¹²• 19¹⁰

Dla każdego wyrażenia A złożonego z symboli podstawowych je numer Nr (A) jest więc łatwy do obliczenia. Funkcja Nr jest obliczalna w intuicyjnym sensie i wzajemnie jednoznacznie przekształca wyrażeń w pewien podzbiór liczb naturalnych. Zamiast mówić o obliczalności pewnego zbioru wyrażeń możemy przeto mówić o obliczalności zbioru ich numerów.

A. Grzegorczyk Zarys logiki matematycznej, ss. 392 - 393

[Więcej na temat dowodu twierdzenia Gödla w: Materiały dydaktyczne, Witold Marciszewski Szkic uzasadnienia Twierdzenia Gödla o nieusuwalnej niezupełności arytmetyki liczb naturalnych.]

Koniec materiału: Do dowodu twierdzenia Gödla

Wynikanie logiczne a wyprowadzalność (konsekwencja) - dalsze aplikacje twierdzenia Gödla

Implikacja a konsekwencja (wyprowadzalność)

Implikacja i wyprowadzalność. Pomiędzy wieloma pojęcia­mi, którymi zajmuje się logika matematyczna, pojęcie konsekwencji odgrywa szczególnie ważną rolę. Jest ono podstawowe dla metodologii poznawania pośredniego, ponieważ ona za­wsze je zakłada. W dzisiejszej klasycznej logice matematycznej odróżnia się przynajmniej dwa pojęcia konsekwencji: implika­cję i wyprowadzalność. Implikacja jest o tyle pojęciem absolu­tnym, o ile może ona istnieć między dwoma zdaniami bez żad­nego odniesienia do systemu aksjomatycznego; przeciwnie wy­prowadzalność, musi ona zawsze być rozważana w relacji do jakiegoś systemu aksjomatycznego.

Logika matematyczna oferuje jeszcze inne, podobne pojęcie, mianowicie pojęcie wyprowadzalności. Mówi się że, B jest wyprowadzalne z A w systemie S wtedy i tylko wtedy, gdy S za­wiera aksjomaty i reguły, które pozwalają pokazać, że gdy A na­leży do S, to także B należy do S. Następujący prosty przykład może unaocznić różnicę między implikacją a wyprowadzalnością. Niech to będzie klasyczny sylogizm:

1. Wszyscy ludzie są śmiertelni.

2. George Boole był człowiekiem.

3. George Boole był śmiertelny.

Ponieważ tutaj (2) i (3) są prawdziwe, to przesłanka mniejsza (2) implikuje wniosek (3) . Jednak wyłącznie z (2) w ramach zwykłej logiki nie da się wyprowadzić (3). (3) da się wyprowa­dzić tylko z obu wcześniejszych zdań, tzn. z (1) i (2). (3) jest zatem implikowane przez (2), ale nie jest wyprowadzalne wy­łącznie z (2).

J. M. Bocheński Współczesne metody myślenia, ss. 90 – 92

Zdania analityczne w sensie semantycznym i syntaktycznym

Mówiąc o modelach systemów standardowych (elementarnych) braliśmy pod uwagę dziedziny utwo­rzone z pewnego zbioru A oraz pewnych elementów zbioru A i pewnych relacji zachodzą­cych między elementami zbioru A. Przyporządkowanie Q jest przyporządkowaniem odpo­wiednich elementów takiej dziedziny pozalogicznym stałym nazwowym i stałym predykatom takiego systemu.

W systemach opartych na bogatszych rachunkach logicznych, np. na rachunku predykatów n-go rzędu, mogą występować stałe pozalogiczne (specy­ficzne) różnych wyższych kategorii składniowych. Mówiąc o modelach takich systemów mamy na myśli dziedziny utworzone z pewnego zbioru A oraz relacji i zbiorów wyższych typów, które można uzyskać wychodząc od zbioru A. A więc np. elementami takiej dzie­dziny mogą być pewne podzbiory zbioru A, relacje zachodzące między podzbiorami zbioru A, zbiory takich relacji, itp. Mówiąc poniżej o dziedzinie, będziemy mieli na myśli tak ogólniej rozumianą dziedzinę. Przyporządkowanie Q jest przyporządkowaniem elementów takiej dziedziny i stałych pozalogicznych danego systemu. Ponadto mówiąc poniżej o dzie­dzinie M będziemy mieli na myśli dziedzinę niepustą, tj. taką dziedzinę M, ze zbiór A tej dziedziny jest zbiorem niepustym. Posługując się takim pojęciem dziedziny można określić semantyczne pojęcie zdania analitycznego:

H jest zdaniem analitycznym w sensie semantycznym ≡ $\bigwedge_{\ M,\ \ Q}^{}{H E(M,\ Q)}$

Zdania analityczne w sensie semantycznym są to te i tylko te zdania, które są prawdzi­we w każdej niepustej dziedzinie M przy każdym przyporządkowaniu Q elementów dziedziny M i stałych pozalogicznych danych zdań, a więc które są prawdziwe w każdej niepustej dziedzinie przy każdym sposobie rozumienia występujących w nich stałych pozalogicznych.

Zdaniami analitycznymi w tym sensie są prawdziwe wyrażenia systemów logiki i ich podstawienia zawierające stałe pozalogiczne.

Z twierdzenia Gödla wynika, że istnieją zdania analityczne w sensie semantycznym, które nie są zdaniami analitycznymi w sensie syntaktycznym. W myśl tego twierdzenia zbiór zdań analitycznych w sensie semantycznym jest zbiorem nieaksjomatyzowalnym. Natomiast każde zdanie analityczne w sensie syntaktycznym jest zdaniem analitycznym w sensie semantycznym.

Pojęcie zdania analitycznego w sensie semantycznym można uważać za pewien odpowiednik pochodzącego od Leibniza pojęcia zdania, które jest „prawdziwe w każdym możliwym świecie”. Definicję zdań analitycznych w sensie semantycznym można mianowicie uważać za definicję precyzującą w pewien sposób sens terminu „zdanie prawdziwe w każdym możliwym świecie”.

Logiczny schemat wnioskowania i wynikanie logiczne

Formalnym schematem wnioskowania nazywa się taki schemat wnioskowania, w którego przesłankach i wniosku występują tylko stałe i zmienne logiczne.

Niezawodnym schematem wnioskowania nazywa się taki schemat wnioskowania, który – przy tych samych podstawieniach za zmienne w przesłankach i we wniosku – prowadzi od prawdziwych przesłanek zawsze do prawdziwego wniosku.

Logicznym schemat wnioskowania nazywa się taki schemat wnioskowania, który jest zarazem formalny i niezawodny.

Ważne pojęcie wynikania logicznego można określić przy pomocy pojęcia schematu logicznego w następujący sposób:

Ze zdań Z₁, Z₂, ..., Z_n wynika logicznie zdanie Z wtedy i tylko wtedy, gdy zdania

Z₁, Z₂, ..., Z_n podpadają jako przesłanki, zaś zdanie Z jako wniosek pod jakiś schemat logiczny, tj. gdy podstawiając w jakimś schemacie formalnym i niezawodnym te same stałe za te same zmienne otrzymamy z jego przesłanek zdania Z₁, Z₂, ..., Z_n, zaś z jego wniosku zdanie Z.

Powyższą definicję pojęcia wynikania logicznego można dokładniej i precyzyjniej przy pomocy wprowadzonych wyżej pojęć sformułować w jeden z dwóch następujących sposobów:

1) Zdanie H wynika logicznie ze zdań klasy K ≡ $\ \bigwedge_{\ M,\ \ Q\ }^{}{\lbrack K \subset E(M,\ Q)}\mathbf{\rightarrow}H E(M,\ Q)$]

2) Zdanie H wynika logicznie ze zdań H₁, ... , H_n ≡ $\bigwedge_{}^{}{M,\ Q}\ $[‘H₁∧ ... ∧ H_n → H’ E(M,  Q)]

Pierwsza z tych definicji mówi, że jakieś zdanie względnie formuła wynika ze zbioru zdań względnie formuł zdaniowych K, jeżeli przy każdym przyporządkowaniu Q elementów dziedziny M w którym wszystkie zdania (formuły) należące do K są prawdziwe, również to zdanie (formuła) jest prawdziwe.

Pierwsza definicja wynikania logicznego stanowi pewne sformułowanie definicji Tarskiego z r.1936, druga zaś podaje pewne sformułowanie definicji Ajdukiewicza z r. 1934. Jeśli K jest skończoną klasą zdań, to obie definicje są równoważne.

Na podstawie definicji Tarskiego można mówić o wynikaniu zdania z nieskończonej klasy zdań, natomiast w definicji Ajdukiewicza mówi się tylko o wynikaniu zdania ze skończonej klasy zdań.

Pojęcie wynikania logicznego a po­jęcie wyprowadzalności według reguł logicznych

Semantyczne pojęcie wynikania logicznego należy odróżniać od syntaktycznego po­jęcia wyprowadzalności (konsekwencji) według reguł logicznych. Przyjmując zastrzeżenia dotyczące reguły podstawiania i dołączania kwantyfikatora ogólnego, podawane w sformu­łowaniu twierdzenia o dedukcji, można stwierdzić, że:

Zdanie H jest wyprowadzalne (jest konsekwencją) według reguł logicznych ze zdań

H₁, ... , H_n wtedy i tylko wtedy, gdy implikacja ‘H₁∧ ... ∧ H_n → H’ jest tezą logiczną.

Ponieważ pojęcia tezy logicznej nie można utożsamiać z pojęciem prawdziwego wy­rażenia systemu logiki, więc też i pojęcia wyprowadzalności według reguł logicznych nie można utożsamiać z pojęciem wynikania logicznego. Prawdziwa jest (z zastrzeżeniami formułowanymi w twierdzeniu o dedukcji) następująca implikacja:

Jeśli zdanie H jest wyprowadzalne według reguł logicznych ze zdań ze zdań H₁, ... , H_n, to zdanie H wynika lo­gicznie ze zdań ze zdań H₁, ... , H_n.

Implikacja ta wynika z podanej wyżej równoważności oraz stąd, że każda teza logiczna jest prawdziwym wyrażeniem systemu logiki. Implika­cja odwrotna w ogólnym sformułowaniu nie jest prawdziwa. Prawdziwe są tylko pewne szczególne przypadki implikacji odwrotnej. Z twierdzenia o pełności dla węższego ra­chunku predykatów wynika, że implikacja odwrotna jest prawdziwa dla wyrażeń systemów standardowych (elementarnych), opartych na tym rachunku. Dla wyrażeń takich syste­mów jest więc prawdą, że:

Zdanie H jest wyprowadzalne według reguł logicznych (z odpowiednimi zastrzeżeniami) ze zdań ze zdań H₁, ... , H_n ≡ zdanie H wynika lo­gicznie ze zdań ze zdań H₁, ... , H_n.

Natomiast dla bogatszych systemów logicznych, do których stosuje się twierdzenie Gödla, jak również dla systemów opartych na takich systemach logicznych, implikacja odwrotna nie jest prawdziwa. Na podstawie tez rachunku zdań skonstruowane metodą po­daną przez Gödla zdanie G takiego systemu jest równoważne np. implikacji ‘H ∨ ~H → G’. Ponieważ G jest zdaniem prawdziwym, więc implikacja ta jest również zdaniem prawdzi­wym. Implikacja ta nie jest jednak tezą. Gdyby bowiem była ona tezą, to również zdanie G byłoby tezą. Zdanie G nie jest jednak tezą. A więc zdanie G nie jest wyprowadzalne ze zdania

‘H ∨ ~H ’, chociaż wynika logicznie ze zdania ‘H ∨ ~H ’.

Z definicji wynikania logicznego i zdań analitycznych w sensie semantycznych wynika następujący wniosek:

Każde zdanie analityczne w sensie semantycznym wynika logicznie z dowolnego zdania.

Znaczenie współczesnych pojęć i twierdzeń semantycznych

Zdefiniowanie w logice współczesnej pojęć semantycznych, w szczególności pojęcia zdania prawdziwego w sensie klasycznej koncepcji prawdy, z wykluczeniem antynomii semantycznych posiada doniosłe znaczenie filozoficzne. Pojęcia te należą bowiem do podstawowych pojęć z teorii poznania lub przynajmniej są odpowiednikami takich po­jęć.

Równie doniosłe znaczenie mają pewne wyniki badań nad systemami dedukcyjnymi, a w szczególności twierdzenie Gödla o niepełności bogatszych systemów logicznych. W artykule Problemat idealizmu transcendentalnego w sformułowaniu semantycznym z r. 1937 K. Ajdukiewicz przeprowadza krytykę stanowiska idealizmu transcendentalnego korzystając z tego wyniku Gödla wykazującego, że nie można utożsamiać pojęcia zdania prawdziwego z pojęciem tezy systemu. W artykule Epistemologia i semiotyka z r. 1948 tenże autor przeprowadza krytykę argumentów idealizmu metafizycznego, zarówno obiektywnego jak i subiektywnego, opartych na rozważaniach epistemologicznych, z za­kresu teorii poznania. W krytyce tej korzysta Ajdukiewicz z twierdzeń o warunkach, które musi spełniać metajęzyk (metasystem), by można w nim było podać adekwatne (merytorycznie trafne) definicje terminów „zdanie prawdziwe”, „oznaczanie” dla wy­rażeń danego języka (systemu). Artykuły te stanowią jeden z przykładów korzystania z wyników logiki współczesnej przy formułowaniu i rozwiązywaniu pewnych klasycznych zagadnień filozoficznych. Świadczy to o tym, że pewne wyniki współczesnej logiki for­malnej posiadają znaczenie wykraczające daleko poza zakres tej specjalności.

L. Borkowski Logika formalna, s. 382

4. Teoria modeli

Modele teorii aksjomatycznych

A. Grzegorczyk Zarys logiki matematycznej, ss. 225 - 229

Teorie matematyczne buduje się w różnych celach. Niektóre teorie matematyczne są budowane z myślą uchwycenia cech wspólnych wielu dziedzin matematycznych. Takimi są np. teoria grup, teoria struktur. Istnieje jednak spora ilość teorii matematycznych, z których każda jest budowana z intencją opisania tylko jednej dziedziny matematycznej. Takimi są między innymi najważniejsze teorie klasycznej matematyki: arytmetyka liczb naturalnych i arytmetyka liczb rzeczywistych. Tworząc aksjomatykę arytmetyki liczb naturalnych chcemy w niej wypowiedzieć pewne cechy liczb naturalnych, które uważamy za charakterystyczne. Chcielibyśmy, aby aksjomaty arytmetyki liczb naturalnych były speł­nione jedynie przez dziedzinę liczb naturalnych. Podobnie, tworząc aksjo­matykę teorii liczb rzeczywistych chcemy znaleźć takie aksjomaty dla mnożenia i dodawania, żeby aksjomaty te były spełnione jedynie przez mnożenie i dodawanie w dziedzinie liczb rzeczywistych.

Takiej intencji nie mamy np. budując teorię grup. Aksjomaty teorii grup spełnia zarówno dodawanie wśród liczb całkowitych, jak i dodawanie wśród liczb rzeczywistych. Spełnia je również mnożenie wśród liczb wymiernych różnych od zera. Spełnia je też wiele innych działań o bardziej skompli­kowanych definicjach, np. różnica symetryczna dwóch zbiorów

A ÷B = (A B)∪(B − A ) 

wśród podzbiorów pewnego zbioru. Każda z wy­mienionych dziedzin spełnia aksjomaty teorii grup, czyli jest, jak się to mówi, modelem teorii grup.

Dział matematyki jakim jest teoria modeli i zajmuje się związkiem między teoriami matematycznymi a ich modelami, czyli takimi dziedzinami, które spełniają aksjomaty teorii. Zapoznając się z tym działem najpierw przeanalizujemy pojęcia spełniania i modelu i podamy ścisłe definicje tych pojęć. Następnie wyprowadzimy najważniejsze twierdzenie w tym dziale mówiące, że każda niesprzeczna teoria ma model przeliczalny. W końcu zauważymy, że każda teoria, ma wiele bardzo różnych modeli. Teoria budowana z intencją opisania jednej konkretnej dziedziny matematycznej nigdy nie spełnia tego zadania. Istnieje zawsze dużo rozmaitych dziedzin matematycznych, w których spełnione są aksjomaty teorii. A więc arytmetyka liczb naturalnych nie opisuje jednoznacznie liczb naturalnych. Podobnie nie robi tego żadna klasyczna teoria matematyczna. Badania nad modelami rzucają więc ciekawe światło na rolę i wartość poznawczą teorii matematycznych.

Pojęcie spełniania

Teoria spełniania i modeli bywa też nazywana semantyką logiczną. Semantyką najogólniej zwie się naukę zajmującą się związkiem między językiem a rzeczywistością, do której wyrażenia języka się odnoszą. Na terenie metamatematyki związek między językiem a rzeczywistością ujmujemy jako związek między teorią matematyczną a dziedziną, którą teoria opisuje. Podstawową relacją, jaka zachodzi między wyrażeniami teorii a dziedzinami matematycznymi, jest relacja spełniania.

Relacja spełnia­nia wiąże przedmioty bardzo między sobą odległe, jest relacją między wyrażeniem z języka badanego a dziedziną matematyczną i ciągiem przedmiotów z tej dziedziny.

Oznaczenia:

𝔐 - dziedzina matematyczna; 𝔐 = < X ; f, g, … , h; a, b,..., c; p , q , . . . , r >, gdzie:

X – zbiór

f, g, … , h –funkcje

a, b,..., c – elementy X

p , q , . . . , r –relacje

α(x, y, ..., z) – zdanie (wyrażenie o) zmiennych wolnych x, y, ..., z zawierające symbole predykatywne P, Q,.., R i symbole funkcyjne F, G,..., H, gdzie:

F, G,..., H – nazwy funkcji f, g, … , h z 𝔐

P, Q,.., R – nazwy relacji p , q , . . . , r z 𝔐

Definicja spełniania

Wyrażenie α(x, y, ..., z) jest spełnione w dziedzinie 𝔐 = < X ; f, g, … , h; a, b,..., c; p , q , . . . , r > przez elementy a, b,..., c wtedy i tylko wtedy, gdy elementy a, b,...,c; relacje p , q , . . . , r oraz funkcje f, g, … , h tak się zachowują wzbiorze X, jak opisuje to zdanie α(x, y, ..., z).

Na przykład liczby 2, 3, 5 spełniają wyrażenie x⊕y = z w dziedzinie liczb naturalnych < N, + > przy rozumieniu symbolu   ⊕  jako nazwy funkcji dodawania, ponieważ liczby te zachowują się tak, jak opisuje to zdanie x⊕y = z, jeśli przyjmiemy, że x, y, z są odpowiednio nazwami liczb 2, 3, 5, a ⊕ jest nazwą dodawania. Istotnie, prawdą bowiem jest, że 2 + 3  =  5. Podobnie 2, 3, 6 spełniają to samo wyrażenie w dziedzinie < N, • > przy rozumieniu ⊕ jako nazwy mnożenia, ponieważ 2 • 3  =  6.

Jeśli wyrażenie α nie zawiera zmiennych wolnych, wówczas także możemy do niego stosować pojęcie spełniania. Wystarczy wtedy mówić, że wyrażenie α jest spełnione w dziedzinie  𝔐 przy rozumieniu symboli stałych jako nazw odpowiednich predykatów i funkcji, nie trzeba nato­miast dodawać, przez jakie przedmioty wyrażenie α jest w tej dziedzinie spełnione, skoro żadne zmienne nie występują w a jako wolne.

Pojęciem prawdziwości pewnego zdania w pewnej dziedzinie już operowaliśmy, nie podając jednak ścisłej definicji. Powyższe przykłady pokazują, że prawdziwość jest szczególnym przypadkiem spełniania, mianowicie jest identyczna ze speł­nianiem, gdy rozważane wyrażenie jest zdaniem, czyli nie zawiera zmien­ny wolnych. To rozumienie pojęcia prawdy i spełniania odpowiada klasycznemu filozoficznemu pojęciu prawdy, jako zgodności naszych poglądów (twierdzeń) z rzeczywistością, czyli ze stanem rzeczy w pewnej dziedzinie, do której poglądy nasze się odnoszą.

Język badany a metajęzyk

Aby mieć właściwy pogląd na rolę pojęć spełniania, prawdy i modelu musimy odróżnić język badany i język, w którym przeprowadzamy obecne badania, czyli meta­język.

Językiem badanym jest tu dla nas język krl. Zakładamy, że są w nim uwzględnione wszystkie stałe symbole mate­matyczne. O tym języku, o zdaniach w nim sformułowanych mamy zamiar wypowiadać pewne twierdzenia. Twierdzenia te i ich dowody muszą być również zapisane za pomocą pewnych napisów, tworzących pewien mniej lub bardziej sformalizowany język. Ten właśnie język, w którym mamy zamiar wypowiadać i dowodzić różnych twierdzeń dotyczących wyrażeń krl, zwiemy metajęzykiem. Niektórzy logicy język badany zwą językiem przedmiotowym, a język, w którym się bada język przedmiotowy zwą językiem podmiotowym.

Język podmiotowy (metajęzyk), aby służyć badaniom metalogicznym, musi za­wierać przede wszystkim nazwy wyrażeń języka przedmiotowego: nazwy napisów pojedynczych, nazwy pewnych klas wyrażeń, nazwy relacji między wyrażeniami. Terminy odnoszące się do napisów języka badanego to pierwsza grupa terminów, które muszą koniecznie występować w języku podmiotowym. Jeśli w języku podmiotowym chcemy zajmować się nie tylko składnią języka badanego, czyli opisywaniem kształtów jego wy­rażeń, ale chcemy też się zajmować związkiem między kształtami wyra­żeń i rzeczywistością (matematyczną), do której wyrażenia te się odnoszą, to język podmiotowy musi zawierać również pewne terminy odnoszące się do matematycznej rzeczywistości. Jeśli chcemy móc przy tym mówić o różnych dziedzinach matematycznych, to język podmiotowy musi zawierać wszystkie pojęcia teorii mnogości.

Przeprowadziwszy ogólnie odróżnienie języka badanego od metajęzyka rozważmy przykłady. Oto zdanie:

(1) Formuła $\bigwedge_{}^{}x,\ $y (x⊕y = y⊕x) jest spełniona w dziedzinie < N, + > przy rozumieniu symbolu funkcyjnego ⊕ jako nazwy funkcji dodawania +

ma sens ten sam, co zdanie następujące:

(2) $\bigwedge_{}^{}x,\ y\ (x,\ y$ N → x + y  = y  + x)

Na gruncie języka podmiotowego, czyli metajęzyka, zdania (1) i (2) są równoważne. Ściślej mówiąc, równoważność zdań (1) i (2) jest twier­dzeniem metalogiki. Oba zdania są zdaniami w metalogice. W zdaniu (1) zawarta jest część postaci

(3) $\bigwedge_{}^{}x,\ $y (x⊕y = y⊕x)

Wzór (3) zawarty w zdaniu (1) należy do języka badanego (przedmiotowego). Jest on zdaniem w języku badanym, natomiast w metajęzyku nie jest zdaniem, tylko nazwą zdania z języka badanego. Chcąc uwypuklić to, że wzór równokształtny z (3) zawarty w zdaniu (1) gra tam rolę tylko nazwy pewnej formuły, moglibyśmy w tym celu wziąć wzór w cudzysłów. Nie jest to jednak konieczne, ponieważ poprzedzamy go terminem „formuła”. Naturalne jest, że po terminie „formuła” umieszcza się nazwę pewnej for­muły lub opis pewnej formuły. Zdanie (1) jest przecież równoważne zdaniu:

(4) Formuła (3) jest spełniona w dziedzinie < N, + > przy rozumieniu symbolu ⊕ jako nazwy funkcji +.

Pojęcie prawdy i modelu. Własności zbioru zdań prawdziwych w modelu

A. Grzegorczyk Zarys logiki matematycznej, ss. 244

Pojęcie prawdy

Jest rzeczą zupełnie naturalną, że o wyrażeniu ze zmiennymi wolnymi na ogół nie możemy powiedzieć, czy jest prawdziwe lub fałszywe, gdyż prawdziwość jego zależy od tego, jak będziemy rozumieli zawarte w nim zmienne wolne. Natomiast wyrażenia bez zmiennych wolnych wypowia­dają pewną myśl zamkniętą, która jest albo prawdziwa, albo fałszywa, Jednakże ponieważ powszechnie jest przyjęte, aby formuły ze zmiennymi wolnymi również występowały jako twierdzenia teorii matema­tycznych, przeto też i pojęcie prawdy definiuje się dla dowolnych formuł poprawnie zbudowanych, zawierających zmienne wolne.

Definicja (Tarski [92]).

Wyrażenie A jest prawdziwe w dziedzinie 𝔐 = < X ; p₁, … , p_n > (symbolicznie:

A  E(𝔐)) przy rozumieniu predyka­tów P₁, ... P_n jako nazw relacji p₁, … , p_n wtedy i tylko wtedy, gdy każdy ciąg przedmiotów zbioru X spełnia A w 𝔐.

Pojęcia niesprzeczności, zupełności i modelu

A. Grzegorczyk Zarys logiki matematycznej, ss. 248 – 252; ss. 269 - 275

Na przykładzie zbioru E(𝔐) zdań prawdziwych w pewnej dziedzinie 𝔐 łatwo jest pokazać zastosowanie pewnych ważnych pojęć metalogicznych. Przede wszystkim mamy tu na myśli pojęcia niesprzeczności i zupełności. Od dawna logicy, matematycy i filozofowie zastanawiali się nad zagadnie­niami niesprzeczności i zupełności wiedzy. Teoria jest niesprzeczna, gdy odpowiedzi, które daje, nie wykluczają się wzajemnie. Teoria jest zupełna, gdy daje odpowiedź na każde zagadnienie, które sformułujemy w jej języku. Jest oczywiste, że pragniemy wiedzy niesprzecznej. Wiedza sprzeczna nie jest bowiem żadną wiedzą, skoro przeczy temu, co sama kiedy indziej twierdzi. Również chcielibyśmy mieć wiedzę zupełną, czyli umieć rozwiązać każde zagadnienie. Z rozważań tego typu wyrosły definicje niesprzeczności i zupełności stosujące się do ścisłych teorii (matema­tycznych).

Definicja. Zbiór zdań X jest sprzeczny wtedy i tylko wtedy, gdy istnieje takie zdanie A, że A  Cn(X) i  ′A′  Cn(X) */*. Gdy zdania takiego nie ma, zbiór X nazywamy niesprzecznym.

Definicja. Zbiór X jest zupełnym zbiorem zdań zawierających ter­miny stałe P₁, . . . , P_n wtedy i tylko wtedy, gdy dla każdego zdania A zawiera­jącego jako symbole stale jedynie symbole spośród P₁, . . . , P_n prawdą jest, że

(1) A X lub  ′A′  X.

*/* Wyrażenia oznaczone apostrofami są zawsze wyrażeniami z języka przedmiotowego. Przy stosowaniu tej samej symboliki logicznej do języka przedmiotowego jak i do metajęzyka służą one do odróżnienia wyrażeń z obu języków. Np. wyrażenie A Z może oznaczać albo, że negacja wyrażenia A należy do zbioru Z, albo: nieprawda, że wyrażenie A należy do zbioru Z. Zapis ‘A′  Z oznacza tylko pierwszą możliwość. < koniec przypisu

Jeśli zbiór (teoria) X nie jest zbiorem zupełnym, nazywamy go (ją) wtedy niezupełnym. Jeśli teoria jest niezupełna, wówczas dla pewnego zdania A prawdziwe jest zaprzeczenie zdania (1), czyli zdanie

A∉ X i ′A′ ∉ X.

Takie zdanie, które samo nie należy do pewnej teorii i którego zaprzeczenie rów­nież nie należy do tej teorii, zwie się zdaniem niezależnym od tej teorii. Teoria jest więc zupełna wtedy i tylko wtedy, gdy nie istnieją zdania niezależne od niej, sformułowane w jej języku. A dla każdej teorii niezu­pełnej istnieją zdania niezależne.

Jeśli rozważany zbiór zdań X nie jest teorią, wówczas określając pojęcie zdania niezależnego musimy się odwołać do zbioru konsekwencji. W ogólnym przypadku definicja ma więc postać:

Definicja. Zdanie A jest niezależne od zbioru X wtedy i tylko wtedy, gdy

A∉ Cn(X) i ′A′ ∉ Cn(X).

Tak ściśle zdefiniowane pojęcia zdania niezależnego oraz zupełności i niesprzeczności teorii matematycznych są przedmiotem badań metalogiki. Wymienimy kilka prostych własności tych pojęć.

Twierdzenia teorii modeli

Niesprzeczność i zupełność

Twierdzenie 1

Jeśli X ⊂ Y i Y jest niesprzeczny, to X jest niesprzeczny .

Dowód. Gdyby X był sprzeczny, to istniałoby zdanie A takie, że A Cn(X) i ′A′  Cn(X). Ponieważ X ⊂ Y, to Cn(X) ⊂ Cn(Y). Zatem byłoby: A Cn(Y) i ′A′  Cn(Y).

Twierdzenie 1 stwierdza, że podzbiór (podteoria) teorii niesprzecznej również jest niesprzeczna ; innymi słowy, że nie może być tak, iż niesprzeczna teoria zawiera jako swoją część pewną teorię sprzeczną.

Twierdzenie 2

Jeśli  ′A′ ∉ Cn(X), to zbiór X ∪{A} jest nie­sprzeczny.

Dowód (niewprost). Gdyby zbiór X ∪{A} był sprzeczny, znaczyłoby to, że dla pewnego zdania B zachodziłoby: ′B  B′  Cn(X ∪{A})

a więc zgodnie z twierdzeniem o dedukcji byłoby: ′A→(B  B)′ Cn(X )

Ponieważ rozpatrujemy konsekwencje oparte o krl, to:

′ {[A→(B  B^′)]}→A)}′ Cn(X )

Na mocy reguły odrywania zachodziłoby więc: ′ A′ Cn(X )

co jest sprzeczne z założeniem twierdzenia.

Istotnie, X ∪{A} byłby - w przypadku, gdyby ′A′  Cn(X) - ­sprzeczny.

Każdy niesprzeczny i niezupełny zbiór zdań można więc nieco powiększyć i otrzymać zbiór większy nadal niesprzeczny. Jak zobaczymy, powtarzając ten zabieg nieskończoną ilość razy można dojść w końcu do systemu niesprzecznego i zupełnego.

Twierdzenie 3

Niesprzeczny zbiór X zdań zawierających symbole stałe P₁, ... P_n jest zupełny wtedy i tylko wtedy, gdy każdy większy od niego zbiór zdań zawierających symbole P₁, ... P_n jest sprzeczny.

Dowód. Niech dla zupełnego zbioru zdań X, Y oznacza zbiór zdań zawierający X jako podzbiór właściwy. Ponieważ zachodzi X ⊂ Y i X ≠ Y, to istnieje takie zdanie A˚ zawierające symbole stałe P₁, ... P_n, że A˚ Y i A˚∉ X. Ponieważ X jest zupełny, to dla każdego zdania A o symbolach P₁, ... P_n jest A  X lub  ′A′  X. Z zupełności zbioru X wynika zatem, że ′A′ X . Ale X ⊂ Y, więc ′A′ Y. Zbiór Y jest więc sprzeczny.

Implikacja odwrotna wynika z twierdzenia 2. Gdyby bowiem zbiór X był niezupełny, to istniałby pewien zbiór Y większy od X, taki, że Y =X∪{A˚}, gdzie A˚∉ Cn(X) i ′A′ ∉ Cn(X). Zbiór Y byłby więc, zgodnie z twierdzeniem 2, niesprzeczny.

Pojęcia zupełności i niesprzeczności stosuje się również i do rachun­ków bezkwantyfikatorowych, np. do rachunków zdaniowych. Korzystając z własności pojęcia zupełności wyrażonej w twierdzeniu 3 niesprzeczność możemy zdefiniować następująco:

Definicja*. Zbiór X niesprzeczny jest zupełny wtedy i tylko wtedy, gdy każdy większy od niego zbiór wyrażeń języka przedmiotowego jest sprzeczny.

Definicja tego typu jest ogólniejsza (niż podana wyżej definicja niesprzeczności), zawiera w sobie bowiem tylko pojęcie konsekwencji i pojęcia teorii mnogości. Może więc być stosowana do rachunków bezkwantyfikatorowych.

Twierdzenie 4

Zbiór zdań T jest niesprzeczny wtedy i tylko wtedy, gdy istnieje takie zdanie A, że

A∉ Cn(T)

Innymi słowy, zbiór jest sprzeczny wtedy i tylko wtedy, gdy każde zdanie jest jego konsekwencją.

Teoria sprzeczna jest więc zupełna, a każda niezupełna teoria jest niesprzeczną.

Twierdzenie 5

Zbiór E (𝔐) wszystkich zdań prawdziwych w niepustej dziedzinie 𝔐 przy ustalonym rozumieniu predykatów jest zupełny i niesprzeczny.

Twierdzenia 1 i 5 razem dają metodę dowodzenia niesprzeczności dowolnej teorii. Wystarczy bowiem, jeśli teoria T jest zawarta w zbiorze wszystkich zdań prawdziwych w pewnej dziedzinie 𝔐, żeby była niesprzeczna. Jest to jedyna metoda dowodzenia niesprzeczności jakiegoś zbioru zdań. Dziedzinę 𝔐 nazywa się wtedy modelem teorii X.

Definicja modelu

Dziedzina 𝔐 = < X ; p₁, … , p_n > jest zwana modelem dla zbioru zdań Z o stałych

P₁, ... P_n jest wtedy i tylko wtedy, gdy Z  ⊂ 𝔐, czyli gdy wszystkie zdania zbioru zdań są prawdziwe w dziedzinie 𝔐 przy rozumieniu termintów P₁, ... P_n jako nazw relacji

p₁, … , p_n.

Twierdzenie 6

Jeśli istnieje model dla zbioru zdań Z, to zbiór Z jest niesprzeczny.

Dowód. Niech dziedzina 𝔐 będzie modelem dla zbioru zdań Z. Zachodzi więc Z  ⊂ 𝔐 (z definicji modelu). Zgodnie z twierdzeniem 5 zbiór E (𝔐) jest niesprzeczny. Zatem zbiór Z , na mocy twierdzenia 1, także jest niesprzeczny.

W naszym systemie metalogiki zawierającym całą teorię mnogości można określić różne dziedziny matematyczne (określone we wprowadzeniu) i dowieść, że są modelami dla pewnych teorii matema­tycznych, i w ten sposób możemy otrzymać dowody niesprzeczności.

Naszkicowane powyżej dowody niesprzeczności pewnych prostych teorii matematycznych nie mają jednak z intuicyjnego punktu widzenia wartości absolutnej. Są one bowiem zbudowane na gruncie metalogiki zawierającej w sobie całą teorię mnogości, a więc na gruncie teorii, która zawiera w sobie, jako swoje drobne fragmenty, odpowiedniki wszystkich teorii powyżej wymienionych. Dowód niesprzeczności pewnej teorii uzyskujemy więc w teorii znacznie mocniejszej od teorii rozważanej. Można pokazać, że jest to jedyna możliwość dowodu niesprzeczności pewnej teorii. Nie można dowieść niesprzeczności teorii mocniejszej na gruncie teorii słabszej lub równoważnej teorii badanej. Chcąc się przekonać o niesprzeczności owej teorii mocniejszej za pomocą ścisłego dowodu, musielibyśmy sięgnąć do teorii jeszcze mocniejszej. Wiara w niesprzeczność podstawowych teorii matematycznych opiera się więc na dedukcyjnym doświadczeniu wielu pokoleń matematyków, którzy na sprzeczność się nie natknęli, oraz na pewnej intuicyjnej przejrzystości podstawowych matematycznych pojęć.

Twierdzenie (K. Gödel [16]). Każdy niesprzeczny zbiór zdań T ma model przeliczalny.

Twierdzenie to można też wypowiedzieć również następująco:

Każdy niesprzeczny zbiór zdań ma model w zbiorze liczb naturalnych.

Twierdzenie Gödla pozwala dowieść wielu implikacji odwrotnych do twier­dzeń poprzednio udowodnionych i podać wobec tego warunki konieczne i dostateczne dla pewnych związków logicznych. Tak np. twierdzenie Gödla pozwala wzmocnić twierdzenie 6 do postaci równoważności:

Twierdzenie 7

Zbiór zdań Z jest niesprzeczny wtedy i tylko wtedy, gdy istnieje model dla zbioru Z.

Z twierdzenia Gödla i twierdzenia 7 wynika:

Twierdzenie (L. Löwenheim [45], Th. Skolem [83])

Zbiór zdań Z ma pewien model wtedy i tylko wtedy, gdy ma model przeliczalny.

Twierdzenie Löwenheima–Skolema bywa uważane za para­doksalne, pokazuje bowiem, że zwykłe metody wnioskowania nie pozwa­lają na wyróżnienie dziedzin nieprzeliczalnych. Teoria liczb rzeczywistych, o ile nie wykraczamy poza zwykłe metody logiczne i zwykłą symbolikę, ma zawsze pewien model przeliczalny, choćby zawierała bardzo mocne aksjomaty. Podobnie teoria mnogości mówi o zbiorach dowolnie wyso­kiej mocy, a ma model przeliczalny. Oczywiście te przeliczalne modele teorii mnogości czy teorii liczb rzeczywistych są bardzo dziwne, nie odpowiadają intencjom teorii, jednakże spełniają aksjomaty. Paradoks ten jest zwany paradoksem Skolema-Löwenheima.

Wymienione teorie mają oczywiście również modele nieprzeliczalne. Zbiór nieprzeliczalny liczb rzeczywistych jest oczywiście modelem teorii liczb rzeczywistych. Można nawet dowieść twierdzenia mocniejszego, że każdy niesprzeczny zbiór zdań, jeśli ma model przeliczalny, to ma też modele dowolnie wysokiej mocy.

Definicja

Zbiór zdań T jest zbiorem (teorią) pełną jeśli zawiera wszystkie zdania prawdziwe w każdej dziedzinie, czyli gdy składa się z samych tauto­logii logicznych.