Semantyka logiczna 14. 12. 2010r

Niech M=<U, /_\> i M* - <U*, /_\*> będą jakimikolwiek interpretacjami tego samego języka

Def. 5) Homorfizm/izomorfizm interpretacji. Interpretacje M i M* są homorficzne wtw:

1. Istnieje funkcja h przekształcająca uniwersum U interpretacji M na uniwersum M* interpretacji M* (czyli h(U) = U*, a nadto
   

2. Dla każdego Predykatu P_iⁿ (rozważanego języka) oraz dla wszystkich elementów u1, …, un e U zachodzi równoważność:

/_\(P_iⁿ)(u1,..., un) ↔ /_\*(P_iⁿ(h(u1), …, h(un)):

3. Dla każdego symbolu funkcyjnego fⁿ_i (rozważanego języka) oraz dla wszystkich elementów u1, …, un e U zachodzi równość:

h(/_\(fⁿ_i)(u1,..., un)) = /_\*(f_iⁿ)(h(u1), ...h(un)):

4. dla każdej stałej indywiduowej ai, h(/_\(ai)) = /_\*(ai).
   
   Jeżeli ponadto funkcja h jest różnowartościowa, to mówimy, że interpretacje M i M* są izomorficzne.

Komentarze:
a) Niech h(ui) = kopia elementu ui wedle funkcji h. Wówczas równoważność w punkcie (2) powyższej definicji głosi, że relacja /_\(Pⁿ_i) zachodzi między elementami u1, …, un wtw relacja /_\*(P_iⁿ) zachodzi pomiędzy kopiami tych elementów wyznaczonymi przez funkcję h. Analogicznie można odczytać pozostałe dwa punkty.

(b) Jeżeli funkcja h ustala homomorfizm interpretacji M na interpretację M* (ale nie ustala izomorfizmu), to istnieją takie przedmioty u, v, w oraz relacja R = /_\(P), że zachodzi przypadek przedstawiony na rysunku (strzałka czarna reprezntuje relacje R):

<rysnek>

(c) każdy izomorfizm jest homorfizmem ale nie odwrotnie

Przykład: Niech T będzie teorią z identycznością, której język zawiera - oprócz zmiennych i stałych logicznych - następujący termin swoisty: < (predykat 2. argumentowy).
Aksjomatami pozalogicznymi teorii T są:

1. ~(x < x) [przeciwzwrotność]

2. x < y ^ y < z → y < x [przechodniość]

3. x = y v x < y v y < x [spójność]

4. x < y → 3z(x < z ^ z < y) [gęstość]

5. \-/x3y (x < y ) [nie istnieje element największy]

6. \-/x3y (y < x) [nie istnieje element najmniejszy]

Dla tej teorii można podać wiele izomorficznych interpretacji, przy których powzysze aksjomaty są prawdziwe, Oto trzy z nich:

N	Uniwersum	/_\n(=)	/_\n(<)
1	Zbiór liczb rzeczywistych R	Identyczność	Bycie mniejszą
2	Zbiór punktów na prostej P	Pokrywanie się	Leżenie na lewo
3	Zbiór punktów czasowych C	Równoczesność	Bycie wcześniejszym

Izomorfizm np. interpretacji (3) i (1) ustala funkcja h: C → R taka, że:

• h(C) = R oraz dla dowolnych c1, c2 e C jeżeli c != c2, to h(c1) != h(c2)

• dla dowolnych c1, c2 e C zachodzą równoważności:

/_\1(=)(c1, c2) ↔ /_\3(=)(h(c1),h(c2))

czyli chwile są równoczesne wtw przyporządkowane im liczby są równe:

/_\1(<)(c1, c2) ↔ …

Twierdzenie) Zasadnicze twierdzenie o izomorfizmie: Jeżeli h ustala izomorfizm (homorfizm) interpretacji M i M*, zaś <wn> jest dowolnym M-wartościowaniem, to:

1. h(Wm(t, <wn>)) = Wm*(t, <h(wn)>); [drugi obiekt jest kopią pierwszego]

2. <wn>SpłM A ↔ <h(wn)> SpłM* A;

3. Vr(M) = Vr(M*).

(dowód w Batogu - rozbite na trzy osobne twierdzenia)

Tautologie

Niech J będzie dowolnym językiem pierwszego rzędu (np. KRP):

def. 6) Tautologia/kontrtautologia:

1. Formuła A języka J jest tautologią wtw jest ona prawdziwa przy każdej interpretacji języka J; symbolicznie:

A e Taut ↔ \-/M (A e Vr(M)).

2. Formuła A języka J jest kontrautologia wtw jest ona fałszywa przy każdej interpretacji języka J;

symbolicznie:

A e Ktaut ↔ \-/M (A /e Vr(M)).

Wniosek: formuła A jest tautologią wtw dla każðej interpretacji M (języka J) oraz każdego wartościowania <w_n> zachodzi: <w_n> Spł_M A.

Def 7. Spełnialność. Formuła A języka J jest spełnialna wtw istnieją interpretacja M języka J oraz M-wartościowanie <wn> takie, że <wn> SpłM A. W przeciwnym przypadku mówimy, że formuła A jest niespełnialna.

Tautologie są zatem formuła spełnianymi przez dowolne wartościowania z uniwersum każdej interpretacji.

Aby wykazać, ze dana formuła jest tautologią, wystarczy pokazać, że jej negacja jest niespełnialna. Można to zrobić pokazując, że założenie o spełnialności negacji rozważanej formuły prowadzi - w oparciu o definicje spełniania i ewentualnie pewne twierdzenia - do sprzeczności.

Przykład:

Dowolna formuła postaci A → A jest tautologią.

Załóżmy, że ~(A → A) jest spełnialna. Wówczas istnieją interpretacja M i wartościowanie <wn>, takie że:

1. <wn>SpłM |~(A → A)|

2. ~(<wn>SpłM |A → A|) [na mocy def. spełniania]

3. ~(<wn> SpłM A → <wn> SpłM A) [na mocy def. Spełniania]

4. <wn> SpłM A [z uwagi na 3.]

5. ~(<wn> SpłM A) [z uwagi na 3; sprzeczność 4]

Twierdzenie 15. Arp _c Taut.

Słownie: wszystkie aksjomaty KRP są tautologiami.

Dla dowodu tego tw. Wystarczy pokazać, że negacje aksjomatów KRP są niespełnialne.

Twierdzenie 16. O trafności:

L _c Taut (gdzie L = Cn(Arp))

Słownie: wszystkie tezy KRP są tautologiami

Dowód. Na mocy tw. 15 i definicji tautologii:

Arp _c Vr(M), gdzie M jest dowolną interpretacją.

Wobec monotoniczności operacji Cn:

Cn(Arp) _c Cn(Vr(M)).

Ponieważ L = Cn(Arp) oraz Cn(Vr(M)) = Vr(M) (jest to twierdzenie 8) więc

L _c Vr(M),

A wobec dowolności interpretacji M otrzymujemy:

L _c Taut.

Twierdzenie 17) CnL(Vr(M)) = Vr(M).

Słownie: zbiór formuł prawdziwych przy interpretacji M jest teorią pierwszego rzędu (systemem dedukcyjnym).

Dowód: Ponieważ Arp _c Vr(M), więc Arp u Vr(M) = Vr(M). Zatem

CnL(Vr(M)) = Cn(Arp u Vr(M)) = Cn(Vr(M)) = Vr(M)

Konsekwencją powyższego twierdzenia oraz wcześniej udowodnionych zasad wyłączonego środka i (nie)sprzeczności jest następujące twierdzenie:

Tw. 18) Zbiór Vr(M) jest systemem dedukcyjnym niesprzecznym i zupełnym.

Def 8. (Model semantyczny) Niech X będzie dowolnym ale ustalonym zebiorem formuł języka J. Modelem semantycznym zbioru formuł X nazywamy każdą interpretację M języka J taką, że X _c Vr(M).

Dygresja. Każdy model jest interpretacją ale nie odwrotnie: nie każda interpretacja jest modelem danego zbioru formuł.

Korzystając z pojęcia modelu możemy zdefiniować pojęcie niesprzeczności następująco:

Def 9) (niesprzeczność/sprzeczność semantyczna). Zbiór formuł X nazywamy semantycznie niesprzecznym wtw istnieje dla niego model. W przeciwnym przypadku - tj. gdy nie istnieje dla niego model - mówimy, że jest on semantycznie sprzeczny.

Dygresja: Wcześniej wprowadzone pojęcie (nie)sprzeczności - odwołujące się do operacji CnL - można określić jako (nie)sprzeczność syntaktyczną.

Twierdzenia łączące pojęcie modelu semantycznego i niesprzeczności (syntaktycznej):

tw. 19) Dla dowolnego zbioru formuł X, jeżeli X posiada model, to X e NSP (tj. X jest syntaktycznie niesprzeczny).

Dowód. Załóżmy, ze X posiada model, powiedzmy M. Wówczas X _c Vr(M). Na mocy twierdzenia 18: Vr(M) e Nsp. Z kolei na mocy twierdzenia o dziedziczności niesprzeczności przez podzbiory: X e NSP.

/dziedziczność: Jeżeli X _c Y i Y e NSP, to X e NSP/

Komentarz: Twierdzenie to daje metodę dowodzenia niesprzeczności teorii poprzez wskazanie dla niej modelu. Innymi słowy, posiadanie przez teorię modelu jest sprawdzianem jej niesprzeczności. Jednak konstrukcja modelu dla jakiejś teorii wymaga zazwyczaj przyjęcia w metajęzyku założeń silniejszych niż zawarte w teorii.

Jest rzeczą interesującą, że twierdzenie to daje się odwrócić - uzyskujemy:

Tw 20. Twierdzenie Godla o istnieniu Modelu). Dla dowolnego zbioru formuł X, jeżeli X e NSP, to X posiada model przeliczalny (tj. taki, ze jego uniwersum jest równoliczne ze zbiorem liczb naturalnych).

Skomplikowany dowód tego twierdzenia znajduje się w: T. Batóg Podstawy logiki, str. 270 - 280.

Komentarz: tw. Powzysze wyrażają łącznie, że istnieje w matematyce jest niczym więcej niż (syntaktyczną) niesprzecznością - teza platonizmu. /platonicy sprowadzają istnienie w matematyce do niesprzeczności → obiekt istnieje o ile teoria go opisująca jest niesprzeczna; zbiory nieskończone: platonicy - istnienie aktualne; konstruktywiści - istnienie potencjalne [konstruktywiści: aby stwierdzić czy obiekt matematyczny istnieje trzeba podać jego konstrukcję]/.

Z powyższych twierdzeń uzyskujemy ciekawą informację na temat modeli:

Tw. 21) Dolne twierdzenie Lowenheima - Skolema) Jeżeli zbiór formuł X (danego języka pierwszego rzędu) ma model, to ma też model przeliczalny.

Komentarz: fakt ten jest dość zaskakujący dla naszej intuicji. Arytmetyka PA opisuje przeliczalny zbiór liczb naturalnych - nic dziwnego, że ma model przeliczalny. Rozważmy teraz system:

R = <R, =, <, +, *, 0, 1>,

gdzie R jest zbiorem liczb rzeczywistych ze znanymi relacjami, działaniami, zerem, jedynką.

System ten nie jest przeliczalny (mocy continuum). Rozważmy zbiór:

T_R = {A: A e Vr(R)}

Zbiór Tr e NSP. A zatem Tr ma model przeliczalny. Tak więc dla zbioru Tr, który może być nazwany teorią liczb rzeczywistych i opisuje nieprzeliczalny zbiór R, można znaleźć model przeliczalny - „za mały”. Podobne paradoksy (paradoksy Lowenheima - Skolema) można znaleźć we wszystkich teoriach pierwszego rzędu. Należy jednak zauważyć, że język teorii Tr jest przeliczalny - zawiera on przeliczalnie wiele symboli, w szczególności nazw. Nie wszystkie liczby są w nim jednoznacznie nazwane (stosownym termem domkniętym).

Tarski udowodnił, że:

Tw. 22 - górne twierdzenie Lowenheima - Skolema). Jeżeli zbiór formuł X (danego j. Pierwszego rzędu) ma model nieskończony, to ma model dowolnej mocy nieskończonej.

Komentarz: Dolne i górne twierdzenia stwierdzają łącznie, że logika 1. rzędu, nie wyróżnia żadnych mocy nieskończonych. Tak, więc teorie sformułowane w językach 1. rzędu, o ile mają model nieskończony, to nie mogą mieć modeli wyłącznie przeliczalnych (tj. o uniwersach równolicznych ze zbiorem liczb naturalnych) ani modeli np. wyłącznie mocy continuum (tj. uniwersach równolicznych ze zbiorem wszystkich liczb rzeczywistych).

Twierdzenie 23. Każdy model przeliczalny zbioru formuł X jest izomorficzny z pewnym modelem tego zbioru mającym jako uniwersum zbiór liczb naturalnych.

Z twierdzenia tego oraz tw. Godla o istnieniu modelu wynika, że każda niesprzeczna teoria 1. rzędu posiada model w zbiorze liczb naturalnych.

Tw. 24) (O zwartości - semantyczne). Jeżeli każdy skończony podzbiór formuł X ma model, to również cały zbiór X ma model.

Dowód. Załóżmy, że każdy skończony podzbiór zbioru formuł X ma model. Wtedy - na mocy tw. 19 - każdy skończony podzbiór zbioru formuł X jest niesprzeczny. Z uwagi na finitystyczność operacji CnL cały zbiór X musi być niesprzeczny. Stąd - na mocy twierdzenia Godla o istnieniu modelu - zbiór X ma model.

/finitystyczność: A e CnL(X) ↔ 3Y _c X(Y e Fin ^ A e CnL(Y)) /

---