Semantyka logiczna 04. 01. 2010r.
Niech X będzie zbiorem formuł języka J, a A niech będzie jedną z formuł tego języka.
Def. 10. Wynikanie semantyczne: Formuła A wynika semantycznie ze zbioru formuł X wtw każdy model zbioru X jest też modelem formuły A.
Oznaczanie:
X |= A czytamy: formuła A wynika semantycznie ze zbioru formuł X lub formuła A jest konsekwencją semantyczną zbioru formuł X.
X |=/= A czytamy: formuła A nie wynika semantycznie ze zbioru formuł X.
Symbolicznie:
X |= A ↔ \-/M (X _c Vr(M) → A e Vr(M))
X |= A ↔ ~3M (X _c Vr(M) ^ A /e Vr(M)).
Tw. 25:
_ _
{A1, …, An} |= B wtw implikacja A1 ^ … ^ An → B jest tautologią.
_ _
Dowód ( → ). Załóżmy, że {A1, …, An} |= B oraz - dla dowodu nie wprost - że (A1 ^ … ^ An → B) /e Taut.
Wtedy istnieją interpretacja M oraz M-wartościowanie <wn> takie, że
_
<wn> SpłM Ai dla dowolnego l _< i _< n
~(<wn> SpłM B).
_ _
Skoro każde (domknięcie) Ai jest zdaniem (l _< i _< n) więc na mocy Tw. 9: Ai e Vr(M),
zaś na mocy Tw. 7 (o generalizacji):
Ai e Vr(M) (gdzie l _< i _< n).
Z punktu (2) otrzymujemy:
B /e Vr(M)
Wobec (3) i (4): {A1, …., An} |=/= B. Sprzeczność.
_ _
( ← ) Załóżmy, że (A1 ^ … ^ An → B) e Taut. Oraz - dla dowodu nie wprost - że {A1, …, An} |=/= B.
Istnieje wtedy interpretacja M taka, że:
Ai e Vr(M) dla każdego l _< i _< n
B /e Vr(M)
_ _
Skoro jednak (A1 ^ … ^ An → B) e Taut. Mamy więc
Ai /e Vr(M) dla pewnego...
/niedokończone/
Przykład: pokażemy, że: {P(x)} |= \-/x(Px). Jes tak ponieważ implikacja \-/xP(x) → \-/xP(x) jest tautologią. Zauważmy, że implikacja P(x) → \-/xP(x) nie jest tautologią.
Skoro domknięcia formuł są zdaniami, więc
tw. 26: Jeżeli A1, …, An są zdaniami to {A1, …, An} |= B wtw implikacja A1 ^ … ^ An → B jest tautologią.
/uproszczona wersja tw. O dedukcji (semantyczne twierdzenie o dedukcji)/.
Tw. 27 (o logicznej prawdziwości) (/) |= A wtw A e Taut.
Idea: tautologię to formuły uznawane bezwarunkowo.
Dowód ( → ) Załóżmy, że (/) |= A. Znaczy to, że dla dowolnej interpretacji M, jeżeli (/) _c Vr(M), to A e Vr(M).
Oczywiście (/) _c Vr(M) (bo zbiór pusty zawiera się w każdym zbiorze). Wnosimy stąd, że dla każdej interpretacji M, A e Vr(M), czyli A e Taut.
( ← ) Załóżmy, że A e Taut. Oraz - dla dowodu nie wprost - że (/) |=/= A.
Istnieje wtedy interpretacja M taka, że (/) _c Vr(M) oraz A /e Vr(M), co jest niemożliwe gdyż w myśl założenia A e Taut. (czyli formuła A jest prawdziwa przy każdej interpretacji).
Zachodzi również następujące twierdzenie:
Tw. 28: Jeżeli A e Taut. To dla dowolnego zbioru formuł X, X |= A.
/tautologie to formuły wynikające z dowolnych zbiorów formuł, również z pustego/
Każda tautologia wynika semantycznie z dowolnego zbioru formuł (w tym zbioru pustego).
Dowód tego tw. Korzysta z tw. Poprzedniego. Wymaga ponadto pokazania, że wynikanie semantyczne ma własność finitystyczności, czyli: X |= A wtw istnieje skończony podzbiór Y zbioru X taki, ze X |= Y.
Tw. 29. Silne tw. O pełności KRP. X |= A wtw A e CnL(X).
Dowód ( → ) Załóżmy, że X |= A oraz - dla dowodu nie wprost - że A /e CnL(X). Wtedy - na mocy syntaktycznego tw. O generalizacji - otrzymujemy:
_
A /e CnL(X). Oprzemy się teraz na tw. (por. tw. 5 o niesprzeczności):
Jeżeli A jest zdaniem i A /e CnL(X), to X u {~A} e NSP.
_
Wnosimy na jego podstawie, że X u {~A} e NSP. Z uwagi na tw. Godla o istnieniu modelu zachodzi wtedy:
_ _
X u {~A} _c Vr(M). Znaczy to, że X _c Vr(M) i (~A) e Vr(M).
_ _
Skoro (~A) e Vr(M) więc na mocy Semantycznej zasady niesprzeczności: A /e Vr(M), zaś na mocy semantycznego tw. O generalizacji: A /e Vr(M). Znaczy to, że intepretacja M jest modelem zbioru formuł X, ale nie jest modelem formuły A, czyli X |=/= A, wbrew założeniu twierdzenia.
( ← ) Załóżmy, że A e CnL(X) oraz X _c Vr(M), gdzie M jest dowolną interpretacją. Wykażemy, że w tej sytuacji A e Vr(M). Na mocy twierdzenia o monotoniczności: CnL(X) _c CnL(Vr(M)), zaś na mocy tego, że CnL(Vr(M)) = Vr(M): CnL(X) _c Vr(M). Skoro A e CnL(X), to także A e Vr(M). Znaczy to, że każdy model zbioru X jest też modelem formuły A, czyli X |= A.
Dygresja. Twierdzenie to pozwala zastąpić pojęcie wynikania syntaktycznego pojęciem wynikania semantycznego i na odwrót. Umożliwia to opuszczenie dowodu, że jakaś formuła wynika semantycznie, jeśli wiadomo, że wynika syntkaktycznie. Ponadto wszystkie sformułowane wcześniej tw. O własnościach operacji CnL można przeformułować tak, aby dotyczyły |= (np. tw. O finitystyczności). W praktycznym stosowaniu logiki nie istnieje potrzeba odróżniania między wynikaniem syntaktycznym a wynikaniem semantycznym /obie są ekwiwalentne/; odróżnienie jest ważne dla badań metalogicznych.
Udowodnimy jeszcze tzw. słabe tw. O pełności KRP, w myśl którego pojęcia tezy i tautologii KRP są równozakresowe (każda teza jest tautologią i każda tautologia jest tezą). Oprzemy się przy tym na następującym lemacie:
_
Lemat 30: Jeżeli A /e L, to istnieje interpretacja M taka, że (~A) e Vr(M).
_
Dowód. Założmy, że A /e L, czyli A /e CnL( (/) ). Stąd (/) u {~A} e NSP (na mocy tw. 5 o niesprzeczności), czyli
_
{~A} e NSP.
_ _
Z uwagi na tw. Godla o istnieniu modelu mamy: {~A} _c Vr(M), czyli ~A e Vr(M).
Tw. 31. Słabe tw. O pełności KRP.
Dla dowolnej formuły A języka KRP:
A e Taut. wtw A e L.
Innymi słowy Taut. = L
(L - tezy).
Dowód ( → ) Załóżmy, że A e Taut. Oraz dla dowodu nie wprost założmy, że A /e L, czyli A /e CnL( (/) ).
_
Na mocy lematu 30 istnieje interpretacja M taka, że (~A) e Vr(M). Ponieważ A e Taut. Więc A e Vr(M), dla dowolnej intepretacji M, zaś na mocy semantycznego tw. O generalizacji:
_
A e Vr(M). Znaczy to, że Vr(M) jest sprzecznym zbiorem zdańm co jak wiadomo jest wykluczone.
( ← ) zostało już udowodnione jako tw. O trafności (aksjomatyki KRP).
Teoria kategoryczna:
Teoria T jest kategoryczna wtw dowolne dwa jej modele standardowe są izomorficzne.
Tylko teorie zupełne o modelach skończonych mogą być w tym sensie kategoryczne.
Takie których uniwersum jest zb. Nieskończonym mają modele wysokich mocy są niekategoryczne.
Teoria T jest kategoryczna w mocy a wtw teoria T ma model standardowy o mocy a i dowolne dwa modele standardowe teorii T o mocy a są izomorficzne.
Krytyka semantyki ekstensjonalnej:
Aksjomat wyboru:
Jeśli istnieje niepusty zbiór z niepustymi podzbiorami to istnieje zbiór B, który ma po jednym elemencie wspólnym z podzbiorami zbioru A.
/tw. O dobrym uporządkowaniu/
Platonicy uznają ten aksjomat.
Konstruktywiści nie uznają istnienia zbiorów obiektywnie tylko, że są konstruowane przez podmiot.
/Zbiór istnieje o ile znamy metodę jego konstrukcji/.
Odrzucają istnienie aktualne zbiorów nieskończonych /istnieją wyłącznie istnienie potencjalne/;
Odrzucają aksjomat wyboru bo uznaje się istnienie zbioru, ale nie podaje się konstrukcji zbioru.
Brauer, Heyting - konstruktwyiści.
/pytanie o to czy matematycy są odkrywcami czy twórcami/.
Inna krytyka semantyki ekstensjonalnej: związana z redukcją /np. relacje do par indywiduów, itp./; zarzuca się redukowanie bogactwa świata do indywiduów i zbiorów wyłącznie; uważa się, że istnienie zbiorów indywiduów i własność to dwa różne obiekty. Jeżeli dwa przedmioty są równe pod pewnym względem [ta sama klasa abstrakcji] to musi istnieć coś co jest im wspólne, jest to własność; dla ekstensjonalisty czymś wspólnym jest klasa abstrakcji.