Semantyka logiczna 07. 12. 2010r

Tw. 5) Semantyczne twierdzenie o odrywaniu:

Jeżeli (A → B) e Vr(M) i A e Vr(M), to B e Vr(M).

Dowód: Przypuśćmy, że:

• (A → B) e Vr(M), A e Vr(M) oraz

• B /e Vr(M) (zalożenie dowodu nie wprost)

Skoro B /e Vr(M), więc istnieje wartościowanie <wn> takie, że

(*) ~(<wn> Spł_MB)

Ponieważ jednak (A → B) e Vr(M), więc <wn> Spł_M|A → B|, a także

(**) <wn>Spł_MA → <wn> SpłM B.

Stąd oraz (*) wnosimy, że ~(<wn>) Spł_M A). A zatem /e Vr(M), wbrew jednemu z założeń twierdzenia.

Tw. 6) Semantyczne twierdzenie o generalizacji:

Jeżeli A e Vr(M), to |\-/xi(A)| e Vr(M).

Dowód: Niech <wn> będzie dowolnym M-wartościowaniem. Z definicji prawdy wynika bezpośrednio, że każdy ciąg spełnia formułę A, więc również w szczególności \-/u e U (<wn>(w/u)Spł_MA).

To jednak znaczy, że <wn>SpłM |\-/xi(A)| [punkt 4. definicji spełniania]. Stąd zaś - wobec dowolności ciągu <wn> - wnosimy, że |\-/xi(A)| e Vr(M).

Tw. 7) Jeżeli |\-/xi (A)| e Vr(M), to A e Vr(M).

Dowód: /analogicznie do poprzedniego/; <wn> niech będzie dowolnym M-wartościowaniem. Z definicji prawdy wynika, że <wn> Spł_M|\-/xi(A)|. Stąd na mocy definicji spełniania \-/u e U (<wn>(w/u)Spł_MA). Ale przecież wi e U, więc biorąc wi za u dostajemy wniosek, że <wn> Spł_MA. Wobec dowolności ciągu <wn> znaczy to, ze A e Vr(M).

/silne twierdzenie o generalizacji w oparciu o te dwa twierdzenia/

Tw. 8) Semantyczne twierdzenie o generalizacji - sile:
_

A e Vr(M) wtw A e Vr(M).

Na mocy tego twierdzenia funkcja zdaniowa jest prawdziwa, gdy jej uniwersalne domknięcie jest prawdziwe.

np. |3y Okrąża(x,y)| e Vr(M) ↔ |\-/x3y Okrąża(x,y)| e Vr(M) ↔ \-/u e U 3v e U(<u, v> e OKRĄŻA).

Tw. 8) Cn(Vr(M)) = Vr(M)

Słownie: zbiór formuł prawdziwych (przy danej interpretacji M) jest teorią.

Dowód:
/identyczność: x = y ↔ x _c y ^ y _c x /

1. Vr(M) _c Cn(Vr(M)). Na mocy zwrotności operacji Cn.

2. Cn(Vr(M)) _c Vr(M), czyli dla dowolnej formuły A, jeżeli A e Cn(Vr(M)), to A e Vr(M).
   Przypuśćmy więc, że A e Cn(Vr(M)). Znaczy, to że istnieje dowód (derywacja) formuły A w oparciu o zbiór Vr(M). Niech tym dowodem będzie ciąg formuł D1,..., Dn: oczywiście. Dk = A. Wykażemy, iż dla dowolnego i _< n, Di e Vr(M). Stosujemy w tym celu indukcje matematyczną względem wskaźnika i.

Krok wyjściowy: i = 1. D1 e Vr(M), bo jest jedną z formuł w oparciu o które przeprowadzamy dowód.

Założenie indukcyjne: Dla dowolnego i < k, gdzie l < k _< n, Di e Vr(M).

Pokażemy, że Dk e Vr(M).

Krok indukcyjny: Zgodnie z definicją dowodu rozważamy trzy przypadki w zależności od tego z jakiego tytuły formuła Dk weszła do dowodu D1, …, Dn.

1. Gdy Dk jest jedną z formuł w oparciu o które przeprowadzamy dowód to Dk e Vr(M).

2. Gdy Dk powstaje z pewnych formuł wcześniejszych w ciągu D1, …, Dn przez RO, to istnieją indeksy i, j < k takie, że Di = (Di → Dk). Na mocy założenia indukcyjnego:

Di e Vr(M), czyli (Dj → Dk) e Vr(M), oraz
Dj e Vr(M).
zaś na mocy semantycznego twierdzenia o odrywaniu:

Dk e Vr(M).

3. Gdy Dk powstaje z pewnej formuły wcześniejszej w ciągu D1, …, Dn przez RG to istnieją takie i oraz j < k, że Dk = \-/xi(Dj). Na mocy założenia indukcyjnego
   Dj e Vr(M)
   zaś na mocy semantycznego twierdzenia o generalizacji
   \-/xi(Dj) e Vr(M), czyli Dk e Vr(M).
   Ponieważ k _< n więc Dn e Vr(M), czyli A e Vr(M).

Tw. 9) Jeżeli A jest zdaniem, to A e Vr(M) wtw istnieje M-wartościowanie <wn> takie, że <wn>SpłM A.

Dowód: Jest to konsekwencja twierdzenia 4.

Tw. 10) Semantyczna zasada wyłączonego środka:

Jeżeli A jest zdaniem, to A e Vr(M) bądź (~A) e Vr(M)

Słownie: Z dwóch zdań wzajemnie sprzecznych jedno jest prawdziwe.

Dowód: Wystarczy pokazać - przy założeniu, iż A jest zdaniem - że jeśli A /e Vr(M), to (~A) e Vr(M).

A /e Vr(M) → ~\-/<wn>(<wn>SpłM A)

→ 3<wn> ~(<wn>SpłM A) [ N \-/ ]
→ 3<wn> (<wn>)SpłM |~A|)
→ (~A) e Vr(M) [twierdzenie 9]

Tw. 11) Semantyczna zasada niesprzecznosci:

A /e Vr(M) bądź (~A) /e Vr(M).

Słownie: z dwóch formuł wzajemnie sprzecznych przynajmniej jedna jest fałszywa.

Dowód: Wystarczy pokazać, że jeśli A e Vr(M), to (~A) /e Vr(M).

A e Vr(M) → \-/<wn>(<wn>SpłM A)

→ 3 <wn>(<wn>SpłM A) [bo U != (/) ]

→ ~\-/<wn> ~(<wn>SpłM A)

→ ~\-/<wn>(<wn> SpłM A)

→ ~\-/<wn>(<wn>Spł M |~A|)

→ (~A) /e Vr(M).

Rekapitulując, definicja Tarskiego ma następujące własności:

• jest sformułowana w metajęzyku

• jest merytorycznie trafna w sensie Konwencji T /można z niej wyprowadzić prawdziwość cząstkową/

• pokazuje w jaki sposób forma logiczna formuły/zdania wpływa na jej wartość logiczną

• unika antynomii semantycznych

• pociąga semantyczną zasadę wyłączonego środka i semantycznę zasadę (nie)sprzeczności.

• Tak definiuje zbiór zdań prawdziwych, że jest on systemem dedukcyjnym maksymalnie niesprzecznym (zostanie to udowodnione później, tw 18).

Ponadto zachodzi tzw. Twierdzenie o niedefiniowalności pojęcia prawdy: zbiór (wszystkich) prawd arytmetycznych nie jest arytmetycznie definiowalny.

Niech T będzie aksjomatyzowalną niesprzeczną teorią 1. rzędu zwierającą arytmetykę Peano (PA) a J_T jej językiem.

Tw. 12) Tarskiego o niedefiniowalności pojęcia prawdy: Nie istnieje formuła Tr(x) języka J_T definiująca zbiór zdań prawdziwych teorii T, tzn. taka, że dla dowolnego zdania A języka J_T,

T |- A ↔ Tr(|A|).

Dowód twierdzenia Tarskiego o niedefiniowalności prawdy opiera się na pomyśle arytmetyzacji (|A| jest nazwą kodu zdania A, a Tr(x) jest predykatem arytmetycznym) oraz następującym lemacie:

Lemat 13 (Kłamca) Przypuśćmy że istnieje w języku J_T formuła Tr(x) definiująca zbiór zdań prawdziwych. Wtedy teoria T jest sprzeczna.

Dygresja: Dowód lematu:

• wykorzystuje lemat przekątniowy - możemy zbudować zdanie „mówiące” o sobie samym, tylko, że nie jest prawdziwe

• powtarza najważniejsze składniki rozumowania występującego w antynomii kłamcy dla języka potocznego (stąd nazwa tego lematu).
  

Dygresja: ponieważ zbiór zdań dowodliwych jest arytmetycznie definiowalny a zbiór zdań prawdziwych nie jest, więc pierwszy jest podzbiorem właściwym drugiego. Stąd twierdzenie tarskiego o niedefiniowalności prawdy dotyka tego samego problemu co pierwsze tw. Godla o niezupełności: pojęcia prawdziwości i dowodliwości nie są równoważne w tym sensie, że istnieją zdania prawdziwe lecz niedowodliwe. W efekcie dowodliwość można uważać za sprawdzian prawdy (w sensie warunku wystraczjącego) ale nie można jej uważać za istotę prawdy (w sensie warunku koniecznego).

Problem (filozoficzny): z jakich przyczyn zbiór zdań prawdziwych jest niedefiniowalny? / w języku którym się posługujemy /

---