Pytania egzaminacyjne - Semantyka logiczna

1. Pojęcie języka pierwszego rzędu. Język KRP.

2. Definicja pojęcia dowodu.

3. Definicja pojęcia konsekwencji logicznej i podstawowe jej własności.

4. Syntaktyczne twierdzenie o odrywaniu i generalizacji.

5. Treść twierdzenia o dedukcji dla KRP (przynajmniej szkic dowodu).

6. Definicja pojęcia teorii pierwszego rzędu; pojęcie tezy; przykłady teorii pierwszego rzędu: KRP, KRPI, AR.

7. Definicja pojęcia niesprzeczności. Twierdzenia charakteryzujące pojęcie niesprzeczności. Ogólna metoda dowodów niesprzeczności teorii.

8. Definicja pojęcia niezależności. Treść twierdzeń łączących pojęcia niezależności i niesprzeczności, i ich znaczenie.

9. Definicja pojęcia zupełności. Twierdzenia charakteryzujące pojęcie zupełności (np. twierdzenie łączące pojęcia zupełności i niesprzeczności).

10. Treść pierwszego i drugiego twierdzenia Gödla o niezupełności arytmetyki i ich znaczenie.

11. Pojęcie interpretacji semantycznej języka pierwszego rzędu.

12. Definicja pojęcia wartościowania termów.

13. Definicja pojęcia spełniania formuły przez ciąg przedmiotów.

14. Definicja pojęcia prawdy. Twierdzenia charakteryzujące pojęcie prawdy: semantyczne twierdzenia o odrywaniu i generalizacji, twierdzenie stwierdzające, że zbiór formuł prawdziwych jest teorią, semantyczna zasada wyłączonego środka i semantyczna zasada sprzeczności.

15. Pojęcia homomorfizmu i izomorfizmu interpretacji i ich znaczenie.

16. Definicje pojęć tautologii i kontrtautologii KRP.

17. Definicja pojęcia modelu semantycznego. Treść twierdzeń łączących pojęcia modelu semantycznego i niesprzeczności oraz ich znaczenie.

18. Definicja pojęcia konsekwencji semantycznej. Twierdzenie łączące pojęcia konsekwencji semantycznej i konsekwencji logicznej.

19. Treść twierdzenia o pełności KRP i jego znaczenie.

UWAGA: Na ocenę bardzo dobrą wymagane są dowody twierdzeń.

„ ” = rożki Quine'a

Zachowano odmienność notacji dla metajęzyka.

1. Pojęcie języka pierwszego rzędu. Język KRP.

DEFINICJA 1 (1)

Każdy podzbiór zbioru znaków języka rachunku predykatów zawierający w sobie wszystkie stałe logiczne (czyli skończoną liczbę spójników zdaniowych i kwantyfikatory wiążące wyłącznie zmienne nazwowe), wszystkie zmienne przedmiotowe (indywiduowe), przynajmniej jeden predykat, oba nawiasy i ewentualnie jeszcze pewną ilość innych znaków (takich jak nazwy indywidualne, symbole funkcyjne, przecinek) nazywać będziemy językiem pierwszego rzędu. Predykaty, nazwy indywidualne i symbole funkcyjne należące do danego języka to stałe pozalogiczne tego języka.

Język KRP:

Formułami języka J są te ciągi wyrażeń ze słownika języka J, które są schematami poprawnie zbudowanych zdań - jakiegoś języka etnicznego.

Następujące symbole nazywamy znakami języka rachunku predykatów:

∼ ∃ ∧ ∨ → ↔ ∃ ∀ (stałe logiczne)

x₁ x₂ x₃... (zmienne indywiduowe)

P₁¹ P₂¹ P₃¹... (predykaty jednoczłonowe)

P₁² P₂² P₃² (predykaty dwuczłonowe)

P₁ⁿ P₂ⁿ P₃ⁿ (predykaty n-członowe)

a₁ a₂ a₃... (nazwy indywidualne)

F₁¹ F₂¹ F₃¹ (symbole funkcyjne jednoargumentowe)

F₁² F₂² F₃² (symbole funkcyjne dwuargumentowe)

F₁ⁿ F₂ⁿ F₃ⁿ (symbole funkcyjne n-argumentowe)

( ) , (znaki techniczne: nawiasy i przecinek)

Każdy skończony ciąg znaków języka rachunku predykatów nayzwamy wyrażeniem tego języka.

Termy:

1. Wszystkie zmienne indywiduowe x_i oraz wszystkie nazwy indywidualne ai są termami (albo formułami nazwowymi) języka rachunku predykatów.

2. Jeżeli α₁, α₂,...,α_n są dowolnymi termami, to wyrażenie F_kⁿ (α₁,...,α_n) jest również termem.

3. Nie ma innych termów (języka rachunku predykatów) prócz zmiennych indywiduowych i nazw indywidualnych oraz tych termów, które można skonstruować wedle reguły (ii).

Formuła:

Zbiór formuł języka rachunku predykatów jest najmniejszym zbiorem zawierającym formuły atomowe (o postaci P_kⁿ (α₁,...,α_n), gdzie α₁,...,α_n są dowolnymi termami) oraz zamkniętym na ujmowanie formuł w nawiasy, poprzedzanie formuł negacją, łączenie formuł znakami koniunkcji, alternatywy, implikacji, równoważności oraz poprzedzanie formuł kwantyfikatorami wiążącymi zmienne nazwowe.

Zasięg kwantyfikatora:

Wyrażenie A w dowolnej formule zdaniowej o postaci ∀x_i (A) lub o postaci ∃x_i (A) nazywamy zasięgiem odpowiedniego kwantyfikatora.

Zmienna związana:

Zmienna x_i występująca na danym miejscu w formule zdaniowej A jest na tym miejscu związana, jeżeli jest ona podpisana pod którymś z kwantyfikatorów lub też znajduje się w zasięgu jakiegoś kwantyfikatora, pod którym podpisana jest również zmienna x_i.

Zmienna wolna w A na danym miejscu:

Jeżeli zmienna x_i, występująca na danym miejscu w formule zdaniowej A, nie jest na tym miejscu związana, to mówimy, że jest ona na tym miejscu wolna w A.

Zmienna wolna w A:

Mówimy, że xi jest zmienną wolną w A wtedy i tylko wtedy, gdy przynajmniej na jednym miejscu zmienna ta jest wolna w A.

Zdanie:

Formuły zdaniowe nie zawierające żadnych zmiennych wolnych nazywamy zdaniami (języka rachunku predykatów).

Domknięcie formuły:

1. Niech z₁,z₂,...,z_n będą wszystkimi zmiennymi wolnymi formuły A ustawionymi (bez powtórzeń) w porządku rośnięcia ich numerów. Zdanie:∀z₁ ∀z₂ ... ∀z_n (A) będziemy nazywali uniwersalnym domknięciem lub krótko domknięciem formuły A i oznaczali symbolem Ā (Jeżeli A nie zawiera żadnych zmiennych wolnych, to przyjmujemy, że Ā = A ).

2. Symbolem X będziemy oznaczali zbiór domknięć wszystkich formuł należących do zbioru X. Zbiór X będziemy nazywali krótko domknięciem zbioru X.

2. Definicja pojęcia dowodu

DEFINICJA 1(2)

Dowodem formuły zdaniowej A w oparciu o zbiór X formuł zdaniowych nazywamy każdy skończony ciąg formuł D₁,D₂,...,D_n taki, że D_n=A oraz dla każdego wskaźnika k ≤ n spełniony jest przynajmniej jeden z następujących warunków:

1. D_k ∈ X;

2. jeżeli D_k∉X, to istnieją formuły D_i,D_j takie, że i,j<k oraz D_k powstaje z nich przez zastosowanie reguły odrywania, czyli D_i = „D_j → D_k”;

3. jeżeli D_k∉X, to istnieją wskaźnik i oraz formuła D_j takie, że j<k oraz D_k powstaje z D_j przez zastosowanie reguły generalizacji, czyli D_k = ∀x_i (D_j).

3.Definicja pojęcia konsekwencji logicznej i podstawowe jej własności.

DEFINICJA 1(3)

Formuła zdaniowa A jest konsekwencją zbioru X formuł zdaniowych wtedy i tylko wtedy, gdy istnieje przynajmniej jeden dowód formuły A w oparciu o zbiór X. Zbiór wszystkich konsekwencji zbioru X - Cn(X).

DEFINICJA 2(3)

Cn_L(X) = Cn (Arp ∪ X).

Cn_L(X) - zbiór konsekwencji logicznych

Arp - zbiór aksjomatów rachunku predykatów

X - zbiór formuł zdaniowych

Własności konsekwencji logicznej:

TWIERDZENIE 1(3)

1. zwrotność: X ⊆ Cn_L(X); wartość udowodnionych zdań zależy od wartości udowodnionych przesłanek;

2. idempotencja: Cn_L(Cn_L(X)) = Cn_L(X); w uzasadnieniu zdania A opartego na określonym zbiorze przesłanek X można skorzystać z innych zdań, które są Cn_L(X);

3. monotoniczność: Jeżeli X ⊆ Y, to Cn_L(X) ⊆ Cn_L(Y); powiększenie zbioru przesłanek może jedynie zwiększyć zakres naszej wiedzy;

4. finitystyczność: A ∈ Cn_L(X) wtedy i tylko wtedy, gdy istnieje taki skończony zbiór Y, że Y ⊆ X oraz A ∈Cn_L(Y); można udowodnić zdanie A w oparciu o zbiór skończonej liczby przesłanek;

5. Cn_L ( {A,∼A} )=J (J - zbiór wszystkich formuł języka J); wyznacza sens negacji klasycznej; operacja charakterystyczna dla systemu, w którym obowiązują dwa prawa A → (∼A → B ), (A ∧ ∼A) → B;

4. Syntaktyczne twierdzenia o odrywaniu i generalizacji.

TWIERDZENIE 1(4) (syntaktyczne o odrywaniu)

Jeżeli A ∈ Cn_L(X) i „A → B” ∈ Cn_L(X), to B ∈ Cn_L(X).

TWIERDZENIE 2(4) (syntaktyczne o generalizacji)

Jeżeli A ∈ Cn_L(X), to „∀x_i(A)” ∈ Cn_L(X).

5. Treść twierdzenia o dedukcji dla KRP.

TWIERDZENIE 1(5)

Jeżeli A jest zdaniem oraz B ∈ Cn_L(X ∪ {A}), to „A → B” ∈ Cn_L(X).

Dowód

Zakł., że: A jest zdaniem, B ∈ Cn_L(X ∪ {A})

Z 2 założenia i z definicji konsekwencji logicznej wnosimy, że istnieje przynajmniej jeden dowód formuły B w oparciu o Arp ∪ X ∪ {A}.

Niech tym dowodem będzie następujący ciąg formuł: D₁,D₂,...,D_n

Zgodnie z definicją dowodu: D_n=B

Wykażemy, że dla każdego i≤k zachodzi: * „A → D_i”∈Cn_L(X).

W tym celu zastosujemy indukcję względem wskaźnika i:

I i = 1, ponieważ D₁ jest pierwszym elelmentem dowodu, to na pewno D₁∈Arp∪X∪{A}. Rozróżniamy tu trzy przypadki:

1) D₁∈Arp;

D₁∈Cn_L(X) ( gdyż Arp⊆Cn_L(X) )

„D₁→(A→D₁)”∈Arp (prawo poprzednika)

„”D₁→(A→D₁)”∈Cn_L(X)

Korzystamy z syntaktycznego tw. o odrywaniu:

„A→D₁”∈Cn_L(X)

2. D₁∈X:

D₁∈Cn_L(X) (gdyż X⊆Cn_L(X) )

jak wyżej...

3. D₁∈{A}

D₁=A

„A→D₁” = „A→A”

“A→A”∈L

“A→A”∈Cn_L(X) (bo L⊆Cn_L(X) )

„A→D₁”∈Cn_L(X)

II Krok indukcyjny:

Zał. indukcyjne: Tw. o dedukcji zachodzi dla wszystkich wskaźników i<k, gdzie 1<k≤n.

W tej sytuacji wykażemy, że wzór * jest słuszny również dla i=k, czyli wykażemy, że: „A→D_k”∈Cn_L(X).

Musimy rozważyć tu trzy przypadki (z definicji dowodu; w zależności od tego, w jaki sposób formuła dostała się do dowodu):

1) Gdy D_k∈Arp∪X∪{A} rozumowanie, jak w kroku I

2. Gdy D_k jest bezpośrednią konsekwencją (na mocy reguły odrywania) pewnych dwóch fomuł poprzedzających ją w dowodzie od D₁ do D_n. Czyli istnieją takie wskaźniki i,j<k, że D_i=”D_j→D_k”.

Ponieważ i<k, to na mocy założenia ind.:

„A→D_i”∈Cn_L(X)

“A→(D_j→D_k)”∈Cn_L(X)

Z prawa Fregego:

„[A→(D_j→D_k) → [(A→D_j) → (A→D_k)]”∈Arp

„[A→(D_j→D_k) → [(A→D_j) → (A→D_k)]”∈Cn_L(X)

Wykorzystujemy syntaktyczne tw. o odrywaniu:

„[(A→D_j) → (A→D_k)]”∈Cn_L(X)

Wskaźnik j<k - stąd dla wskaźnika j również zachodzi twierdzenie o dedukcji:

„A→D_j”∈Cn_L(X)

Stusując syntaktyczne tw. o odrywaniu otrzymujemy:

„A→D_k”∈Cn_L(X)

3. Gdy formuła D_k jest bezpośrednią konsekwencją (na mocy tw. o generalizacji) pewnej formuły poprzedzającej ją w dowodzie od D₁ do D_n. Czyli istnieją wskaźniki j<k oraz i takie, że:

D_k=”∀x_i(D_j)”

Z zał. ind.: „A→D_j”∈Cn_L(X)

Stosujemy syntaktyczne tw. o generalizacji: „∀x_i(A→D_j)”∈Cn_L(X)

Z drugiej strony: „∀x_i(A→B)→[A→∀x_i(D_j)]”∈Arp (w B nie ma zmiennej wolnej, a A jest zdaniem)

Zatem: „∀x_i(A→B)→[A→∀x_i(D_j)]”∈Cn_L(X)

Stosujemy regułę odrywania: „[A→∀x_i(D_j)]”∈Cn_L(X)

Ponieważ D_k=”∀x_i(D_j)”, to „A→D_k”∈Cn_L(X)

Koniec kroku indukcyjnego.

Wzór * jest słuszny w szczególności, gdzie k=n. To dowodzi, że: „A→D_k”∈Cn_L(X), „A→B”∈Cn_L(X)

6. Definicja pojęcia teorii pierwszego rzędu; pojęcie tezy; przykłady teorii pierwszego rzędu: KRP, KRPI, AR.

DEFINICJA 1(6)

Niech J będzie pewnym językiem. Zbiór X formuł zdaniowych języka J nazywamy systemem dedukcyjnym (albo teorią) w języku J wtedy i tylko wtedy, gdy wszystkie formuły zdaniowe języka J będące konsekwencjami logicznymi zbioru X należą do zbioru X.

Elementy teorii X nazywamy twierdzeniami lub też tezami tej teorii.

Wśród takich teorii można wyróżnić teorie aksjomatyczne, gdzie X jest zbiorem aksjomatów. Na mocy tw. CnL(X)=CnL(X) aksjomaty specyficzne moźemy zapisywać zarówno z jak i bez zmiennych wolnych.

Przykłady teorii pierwszego rzędu:

1. KRP

KRP=Cn_L(∅), Istnieje kilka różnych aksjomatycznych ujęć KRP. Zbiór aksjomatów KRP jest zawsze zbiorem nieskończonym.

Aksjomatyka KRP składa się z dwóch części:

1. zawiera zbiór wszystkich podtawień aksjomatów KRZ formułami języka rachunku predykatów,

2. zawiera aksjomaty właściwe.

Aksjomaty KRP:

A1 A→(B→A)

A2 [A→(B→C)] → [(A→B) → (A→C)]

A3 (∼A→ ∼B) →(B→A)

A4 (A↔B) → (A→B)

A5 (A↔B) → (B→A)

A6 (A→B) → [(B→A) → (A↔B)]

A7 A∧B ↔ ∼ (A→ ∼B)

A8 A∨B ↔ (∼A→B)

A9 ∀X_i(A) → A(X_i/α), o ile α jest podstawialny za x_i do A

A10 ∀X_i(A→B) → [A→∀x_i(B)], o ile xi nie jest wolna w A

A11 A(x_i/α) → ∃x_i(A)

A12 ∀x_i(A→B) → [∃x_i(A) → B], o ile x_i nie jest wolna w B.

Reguły dowodzenia w KRP:

1. reguła odrywania: A→B

A

B

b) reguła generalizacji: A

∀x_i(A)

Na podstawie dwóch lematów:

1. Schematy A1-A8 są schematami pewnej wersji KRZ jak i schematami aksjomatów KRP

2. Jedyną regułą pierwotną owej wersji KRZ jest reguła odrywania, która obowiązuje w KRP. Każdy schemat tezy KRZ jest zarazem schematem tezy KRP.

2. KRPI:

KRPI = CnL(Aid) (zbiór tez). Język KRPI uzyskuje się przez wprowadzenie do języka KRP predykatu dwuczłonowego = i modyfikację formuły atomowej (t=t').

Aksjomaty identyczności:

AI1 t=t

AI2 t=t' → [A(x/t) ↔ A(x/t')]

We wszystkich teoriach z identycznością można zdefiniować kwantyfikatory ilościowe np. istnieje dokładnie jeden taki przedmiot x, że (∃¹)

∃¹xA(x) ↔ ∃xA(x) ∧ ∀x∀y[A(x)∧A(y) → x=y]

∃¹xA(x) ↔ ∃x∀y [A(y) ↔ x=y]

Operator deskrypcyjny i (i-ota operator) to operator nazwotwórczy od 1 argumentu zdaniowego. Zapisana za jego pomocą deskrypcja (ix)A(x) (czyt. jedyny taki x, że A(x)) mówi, że to wyrażenie jest nazwą jednostkową wtedy i tylko wtedy, gdy ∃¹xA(x) jest tezą.

KRP z predykatem = i znakiem deskrypcyjnym otrzymujemy przez dodanie do KRP aksjomatu:

∃¹xA(x) → A(x/(ix)A(x))

lub dołączenie operatora deskrypcyjnego:

∃¹xA(x)

A(x'/(ix)A(x))

3.) Arytmetyka liczb naturalnych (AR, PA)

Zbiór tez AR=Cn_L(Aln)

Język AR: następujące symbole nazywamy znakami języka arytmetyki liczb naturalnych:

∼ ∃ ∧ ∨ → ↔ ∃ ∀ (stałe logiczne)

x₁ x₂ x₃... (zmienne indywiduowe) ZM

= (predykat dwuczłonowy) SR

0 (nazwa indywidualna: zero) SI

S (symbol funkcyjny jednoargumentowy) SF

+ • (symbole funkcyjne dwuargumentowe) SF

( ) (nawiasy)

Def. termu:

Zbiór termów języka arytmetyki (TM_AR) to najmniejszy zbiór, taki że:

1. ZM∪SI⊆TM_AR

2. jeśli t∈TM_AR, to S(t)∈TM_AR

3. jeśli t₁, t₂∈TM_AR, to t₁+t₂, t₁• t₂∈TM_AR

Def. formuły zdaniowej:

FMAR jest to najmnieszy zbiór taki, że:

1. jeżeli t₁, t₂∈TM_AR, to t₁=t₂∈FM_AR

2. jeżeli A,B∈FM_AR i x_i∈ZM, to ∼(A), (A)∧(B), (A)∨(B), (A)→(B), (A)↔(B), ∀x_i(A), ∃x_i(A)∈FM_AR

Zbiór aksjomatów (Aln) zawiera aksjomaty logiczne (Arp∪Aid) i aksjomaty pozalogiczne:

N1 x=y ↔ S(x) = S(y)

N2 ∼(0=S(x))

N3 x+0=x

N4 x+S(y)=S(x+y)

N5 x• 0 = 0

N6 x• S(y) = x• y + x

N7 {A(0)∧∀x[A(x) → A(S(x))]} → ∀A(x); jest to zasada indukcji; głosi ona, że jeżeli 0 posiada jakąś własność I posiada ją następnik jakieś liczby, to wszystkie liczby posiadają tę własność. Arytmetyka bez N7 to tzw. arytmetyka Robinson'a.

7. Definicja pojęcia niesprzeczności. Twierdzenia charakteryzujące pojęcie niesprzeczności. Ogólna metoda dowodów niesprzeczności teorii.

DEFINICJA 1(7)

a) Zbiór formuł zdaniowych X jest niesprzeczny (X∈NSP) wtedy i tylko wtedy, gdy nie istnieje żadna taka formuła A, że A∈Cn_L(X) oraz „∼A” ∈ Cn_L(X).

b) Zbiór formuł X jest sprzeczny (X∈SP) wtedy i tylko wtedy, gdy istnieje co najmniej jedna formuła A taka, że A∈Cn_L(X) i zarazem „∼A”∈Cn_L(X).

DEFINICJA 2(7) POJĘCIA NIESPRZECZNOŚCI W SENSIE ABSOLUTNYM

1. Zbiór formuł X jest niesprzeczny w sensie Posta (nietrywialny) wtedy i tylko wtedy, gdy Cn_L(X)≠J (czyli gdy jest różny od wszystkich formuł języka J).

2. Zbiór formuł X jest sprzeczny w sensie Posta (trywialny) wtedy i tylko wtedy, gdy Cn_L(X)=J.

TWIERDZENIE 1(7)

Zbiór X jest niesprzeczny wtedy i tylko wtedy, gdy zbiór Cn_L(X) jest niesprzeczny.

Dowód:

I. (→)

Zakładamy, że: X∈NSP

Z definicji mamy: nie istnieje formuła A taka, że: A ∈ Cn_L(X) i „∼A” ∈Cn_L(X).

Z twierdzenia: Cn_L(Cn_L(X)) = Cn_L(X) otrzymujemy:

nie istnieje formuła A taka, że: A ∈ Cn_L(Cn_L(X)) i „∼A” ∈ Cn_L(Cn_L(X)).

Wobec definicji niesprzeczności:

Cn_L(X) ∈ NSP.

II. (←)

Zakładamy, że: Cn_L(X) ∈ NSP

Z definicji: nie istnieje formuła A taka, że: A ∈ Cn_L(Cn_L(X)) i „∼A” ∈ Cn_L(Cn_L(X)).

Z twierdzenia: Cn_L(Cn_L(X)) = Cn_L(X) otrzymujemy:

A ∈ Cn_L(X) i „∼A” ∈ Cn_L(X).

Zgodnie z definicją:

X ∈ NSP.

TWIERDZENIE 2(7)

Zbiór X jest niesprzeczny wtedy i tylko wtedy, gdy istnieje co najmniej jedna formuła zdaniowa A taka, że A∉Cn_L(X).

Dowód:

1. (→) Załóżmy, że zbiór X jest niesprzeczny. Weźmy pod uwagę dowolną formułę zdaniową A. Z niesprzeczności X wynika, że dla dowolnej formuły A bądź A ∉ Cn_L(X) bądź „∼A” ∉ Cn_L(X). A więc przynajmniej jedna formuła na pewno nie należy do Cn_L(X).

2. (←) Załóżmy teraz dla dowodu nie wprost, że zbiór X jest sprzeczny. Załóżmy, że istnieje co najmniej jedna formuła A taka, że A ∉ Cn_L(X).

Z def. wnosimy, że: istnieje taka formuła B, że B∈Cn_L(X) i „∼B”∈Cn_L(X)

Z uwagi na prawo Dunsa Szkota, dla dowolnej formuły zdaniowej C mamy, że:

„B → (∼B → C)”∈L

Tym bardziej

„B → (∼B → C)” ∈ Cn_L(X).

Przez dwukrotne zastosowanie syntaktycznego twierdzenia o odrywaniu wnosimy, że C∈Cn_L(X). Wobec dowolności C wnosimy, że każda formuła należy do Cn_L(X). To zaś jest sprzeczne z założeniem.

Jeśli więc istnieje formuła, która nie należy do Cn_L(X), to zbiór X musi być niesprzeczny.

TWIERDZENIE 3(7) (o dziedziczności niesprzeczności przez podzbiory)

Jeżeli X ⊆ Y oraz zbiór Y jest niesprzeczny, to również zbiór X jest niesprzeczny.

Dowód:

Zakładamy, że: X ⊆ Y, Y ∈ NSP

Dla dowodu nie wprost zakładamy, że: X ∈ SP

Na mocy twierdzenia o monotoniczności (jeżeli X⊆Y, to Cn_L(X)⊆Cn_L(Y)):

Cn_L(X) ⊆ Cn_L(Y)

Z założenia dowodu nie wprost i definicji sprzeczności:

istnieje A taka, że A ∈ Cn_L(X) i „∼A” ∈ Cn_L(X).

Więc: istnieje formuła A taka, że: A ∈ Cn_L(Y) i „∼A” ∈ Cn_L(Y),

a to znaczy, że: Y ∈ SP wbrew założeniu dowodu.

TWIERDZENIE 4(7) (syntaktyczne twierdzenie o zwartości)

Zbiór X jest niesprzeczny wtedy i tylko wtedy, gdy każdy skończony podzbiór zbioru X jest niesprzeczny.

Dowód:

1.(→) Zakł., że: X∈NSP

Z tw. o dziedziczności niesprzeczności: każdy podzbiór jest NSP, w szczególności skończony.

2. (←) Zakł., że: każdy skończony podzbiór zbioru X jest niesprzeczny,

Dla dowodu nie wprost zakł., że: XeSP

Z def. wnosimy, że istnieje taka formuła A, że A∈Cn_L(X) i „∼A”∈Cn_L(X)

Z tw. o finitystyczności (A∈Cn_L(X) wtw istnieje zbiór Y⊆X taki, że Y jest zbiorem skończonym i A∈Cn_L(Y)): istnieje zbiór Y₁⊆X i Y₁ jest zbiorem skończonym oraz A∈Cn_L(Y₁), oraz isnieje zbiór Y₂⊆X i Y₂ jest zbiorem skończonym oraz „∼A”∈Cn_L(Y₂).

Czyli: Y₁∪Y₂⊆X i Y₁∪Y₂ to zbiór skończony a A∈Cn_L(Y₁∪Y₂) i „∼A”∈Cn_L(Y₁∪Y₂), co oznacza, że pewien skończonym podzbiór zbioru X jest sprzeczny wbrew założeniu.

TWIERDZENIE 5(7)

Jeżeli A jest zdaniem oraz „∼A” ∉ Cn_L(X), to zbiór X ∪ {A} jest niesprzeczny.

Dowód:

Zakł.,że: A jest zdaniem, „∼A”∉Cn_L(X)

Zakł - dla dowodu nie wprost - że zbiór X ∪ {A} jest sprzeczny.

Z def.: istnieje wówczas taka formuła B, że B∈Cn_L(X ∪ {A}) i równocześnie „∼B” ∈ Cn_L(X ∪ {A}). Ponieważ zaś:

„B → (∼B → B ∧ ∼B)”∈ L, a L⊆Cn_L(X)

więc:

„B → (∼B → B ∧ ∼B)”∈Cn_L(X∪{A})

Po dwukrotnym użyciu reguły odrywania otrzymujemy:

„B ∧ ∼B” ∈ Cn_L(X ∪ {A}).

Stąd - na mocy twierdzenia o dedukcji -

„A → B ∧ ∼B” ∈ Cn_L(X).

Równocześnie

„(A → B ∧ ∼B) → ∼A” ∈L.

„(A → B ∧ ∼B) → ∼A”∈Cn_L(X)

Z syntaktycznego tw. o odrywaniu:

„∼A” ∈ Cn_L(X).

Ten ostatni wniosek przeczy jednak jednemu z założeń twierdzenia.

DEFINICJA 3(7) INDUKCYJNA FUNKCJI H

1. H („P_kⁿ(α₁,...,α_n)”)=”p”

2. H („∼A”) = „∼H(A)”

3. H (“∀x_i(A)”) = H(A)

4. H (“∃x_i(A)”) = H(A)

5. H (“A∧B”) = “H(A)∧H(B)”

6. H (“A∨B”) = “H(A)∨H(B)”

7. H (“A→B”) = “H(A)→H(B)”

8. H (“A↔B”) = “H(A)↔H(B)”

TWIERDZENIE 6(7) (Opisuje podstawową metodę dowodzenia niesprzeczności teorii aksjomatycznych).

Niech X będzie teorią w języku J₁ a Y teorią w języku J₂. Jeżeli H jest funkcją przekształcającą teorię X w teorię Y (H: X → Y), taką, że spełniony jest następujący warunek:

H („∼A”) = „∼H (A)” (czyli funkcja H zachowuje negację)

Dla dowolnego A ∈ J₁, a przy tym teoria Y jest niesprzeczna, to również teoria X jest niesprzeczna.

Dowód:

Zakładamy, że: zbiór X jest teorią - X = Cn_L(X)

zbiór Y jest teorią - Y = Cn_L(Y)

funkcja H(„∼A”) = „∼H(A)” dla dowolnego A ∈ J₁

teoria Y ∈ NSP.

Dla dowodu nie wprost zakł.,że: X ∈ SP.

Z definicji: istnieje formuła A taka, że A ∈ X i „∼A” ∈ X.

Ponieważ funkcja H zachowuje negację, to wśród wartości funkcji H dla argumentów należących do zbioru X znajdują się dwie formuły wzajemnie sprzeczne, a to oznacza, że:

Y ∈ SP, bo H(A) ∈Y i „∼H(A)” ∈ Y

wbrew założeniu twierdzenia, że jest to zbiór niesprzeczny.

LEMAT

Jeżeli A∈L (gdzie L=Cn(Arp)), to H(A)∈Trz.

TWIERDZENIE 7(7) ( o niesprzeczności KRP )

Nie istnieje formuła A taka, że A∈L i „∼A”∈L.

Dowód

Dla dowodu nie wprost zakł., że istnieje formuła A taka, że A∈L i „∼A”∈L.

Czyli: H(A)∈Trz i ∼H(A)∈Trz

Zatem: KRZ∈SP, co nie jest prawdą.

8. Definicja pojęcia niezależności. Treść twierdzeń łączących pojęcia niezależności i niesprzeczności, i ich znaczenie.

DEFINICJA 1(8)

1. Zbiór X jest niezależny (X∈NZL) wtedy i tylko wtedy, gdy dla dowolnej formuły A∈X, A∉Cn_L(X - {A}) - dotyczy niezależności zbioru formuł .

2. Formuła zdaniowa A jest niezależna od zbioru formuł X wtedy i tylko wtedy, gdy A ∉ Cn_L(X). - dotyczy relatywnej niezależności formuły względem określonego zbioru formuł.

TWIERDZENIE 1(8)

Jeżeli zbiór X ∪ {∼Ā} jest niesprzeczny, to formuła A jest niezależna od zbioru X, tzn. A ∉ Cn_L(X).

Dowód:

Zakładamy, że: X∪{∼Ā}∈NSP

Dla dowodu nie wprost zakładamy, że: A∈Cn_L(X)

Wobec tw. o monotoniczności (X⊆X∪{∼A}) i tego, że A∈Cn_L(X): A∈Cn_L(X∪{∼Ā})

Na mocy twierdzenia o generalizacji: Ā∈Cn_L(X∪{∼Ā}).

Dalej, na mocy twierdzenia o zwrotności (X⊆Cn_L(X)): ∼Ā∈Cn_L(X∪{∼Ā}).

Więc: X∪{∼Ā}∈SP, wbrew założeniu twierdzenia, że zbiór ten jest niesprzeczny.

Twierdzenie to pokazuje, że zagadnienie niezależności sprowadza się do zagadnienia niesprzeczności. Jeśli A₁,A₂,...,A_i,... są aksjomatami jakiejś teorii, to dla dowodu, że aksjomat Ai jest niezależny od pozostałych, wystarczy wykazać, że zbiór A₁,A₂,...,A_i-1,B,A_i+1,... gdzie B jest negacją domknięcia aksjomatu A_i, jest niesprzeczny. Do tego celu można stosować metody dowodzenia niesprzeczności.

TWIERDZENIE 2(8)

Jeżeli teoria Y jest niesprzeczna oraz istnieje w niej model dla zbioru X∪{„∼A”}, to formuła A jest niezależna od zbioru X.

Metoda interpretacji, służąca do uzyskiwania dowodów niesprzeczności, może być z powodzeniem wykorzystywana przy dowodzeniu niezależności. Metoda ta ukształtowała się w związku z wielowiekowymi badaniami nad sprawą niezależności piątego postulatu Euklidesa oraz w związku z rozwojem geometrii nieeuklidesowych.

9. Definicja pojęcia zupełności. Twierdzenia charakteryzujące pojęcie zupełności.

DEFINICJA 1(9)

a.) Zbiór formuł zdaniowych X języka J jest zupełny ze względu na język J wtedy i tylko wtedy, gdy dla każdego zdania A języka J bądź A ∈ Cn_L(X) bądź „∼A” ∈ Cn_L(X).

b.) Zbiór X jest niezupełny wtedy i tylko wtedy, gdy istnieje przynajmniej jedno zdanie A takie, że ani A ∉ Cn_L(X) ani „∼A” ∉ Cn_L(X).

DEFINICJA 2(9) (ogólniejsza)

1. Zbiór formuł zdaniowych X jest zupełny w sensie Posta lub maksymalnie niesprzeczny wtedy i tylko wtedy, gdy dla każdego zdania A zachodzi jeśli A∉Cn_L(X), to Cn_L(X∪{A})=J.

2. Zbiór formuł zdaniowych X jest niezupełny w sensie Posta wtedy i tylko wtedy, gdy istnieje co najmniej jedno zdanie A takie, że A∉Cn_L(X) i zarazem Cn_L(X∪{A})≠J.

TWIERDZENIE 1(9)

Zbiór formuł zdaniowych X jest zupełny ze względu na dany język wtedy i tylko wtedy, gdy zbiór Cn_L(X) jest zupełny ze względu na ten sam język.

X∈ZUP wtw, gdy Cn_L(X)∈ZUP.

Dowód:

I.(→)

Zakładamy, że: X∈ZUP

Z definicji dla dowolnego A: albo A∈Cn_L(X) albo „∼A”∈Cn_L(X).

Z twierdzenia o idempotencji ( Cn_L(Cn_L(X))=Cn_L(X) ), dla dowolnego zdania A: albo A∈Cn_L(Cn_L(X)), albo „∼A”∈Cn_L(Cn_L(X)).

Tzn. (na mocy def.), że: Cn_L(X)∈ZUP.

II.(←)

Zakładamy, że: Cn_L(X)∈ZUP

Z definicji wnosimy, że: dla każdego zdania A albo A∈Cn_L(Cn_L(X)) albo „∼A”∈Cn_L(Cn_L(X)).

Z twierdzenia o idempotencji ( Cn_L(Cn_L(X))=Cn_L(X) ) mamy, że: albo A∈Cn_L(X) albo „∼A”∈Cn_L(X).

Tzn. (na mocy def.), że: X∈ZUP.

Twierdzenie to głosi, że mówienie o zupełności aksjomatyki danej teorii jest równoznaczne z mówieniem o zupełności teorii i na odwrót.

TWIERDZENIE 2(9)

Jeżeli zbiór X jest niezupełny, to jest on niesprzeczny. (Jeżeli zbiór X jest sprzeczny, to jest on zupełny).

Dowód:

Zakł.,że: X∈NZUP

Z def.: istnieje zdanie A takie, że A∉Cn_L(X) i „∼A”∉Cn_L(X).

Stąd zaś na mocy twierdzenia: X∈NSP wtw, gdy istnieje co najmniej jedna formuła zdaniowa A taka, że A∉Cn_L(X); wynika niesprzeczność zbioru X.

TWIERDZENIE 3(9)

Niech X będzie zbiorem niesprzecznym. Wtedy X∈ZUP wtedy i tylko wtedy, gdy dla każdej formuły A takiej, że A∉Cn_L(X), zbiór X∪{A} jest sprzeczny.

Dowód:

(→)

Zakładamy, że: X∈NSP, X∈ZUP, A∉Cn_L(X).

Wykażemy: X∪{A}∈SP

Zgodnie z twierdzeniem o generalizacji: Ā∉Cn_L(X)

Ponieważ X∈ZUP, więc wtedy „∼Ā”∈Cn_L(X), to tym bardziej (z tw. o monotoniczności)

„∼Ā”∈Cn_L(X∪{A})

Z tw.X⊆Cn_L(X): A∈Cn_L(X∪{A}),

Z tw. o generalizacji: Ā∈Cn_L(X∪{A}).

Zbiór X∪{A} jest więc sprzeczny, bo „∼Ā” i Ā ∈ Cn_L(X∪{A}).

(←)

Zakładamy: dla każdej formuły A takiej, że A∉Cn_L(X), X∪{A}∈SP

Dla dowodu nie wprost zakładamy: X∉ZUP

Z def.: istnieje zdanie A takie, że A∉Cn_L(X) i „∼A”∉Cn_L(X)

Znaczy to, że X∪{A}∈NSP i zbiór X∪{∼A}∈NSP, a to przeczy założeniu twierdzenia.

TWIERDZENIE 4(9) (Lindenbauma)

Jeżeli X jest niesprzeczna teorią (pierwszego rzędu) sformułowaną w języku J, to istnieje teoria Y sformułowana również w języku J, która jest niesprzecznym i zupełnym rozszerzeniem teorii X. Zbiór Y nazywamy wówczas nadzbiorem Lindenbauma.

Tw. to głosi możliwość dokonania rozszerzenia niesprzecznej teorii pierwszego rzędu do teorii zupełnej.

10. Treść pierwszego i drugiego twierdzenia Gödla o niezupełności arytmetyki i ich znaczenie.

T - dowolna teoria pierwszego rzędu, która jest rekurencyjnie aksjomatyzowalna,

AR-arytmetyka liczb naturalnych Peana,

1 TWIERDZENIE GÖDLA O NIEZUPEŁNOŚĆI AR 1(10)

Jeśli AR jest fragmentem teorii T (AR⊆T) i teoria T∈NSP, to istnieje zdanie A w języku teorii T, że A∉Cn_L(T) i „∼A”∉Cn_L(T), czyli teoria T∉ZUP.

*Niech „Con(T)” skraca zdanie „T jest niesprzeczne” zapisane w języku teorii T.

2 TWIERDZENIE GÖDLA O NIEZUPEŁNOŚCI AR 2(10)

Jeżeli AR⊆T i T∈NSP, to zdanie Con(T)∉Cn_L(T).

(Twierdzenie to głosi, iż dowodu niesprzeczności teorii T mającej AR i będącej niesprzeczną nie można w tej teorii przeprowadzić.)

Znaczenie powyższych twierdzeń:

Z uwagi na to, że każda niesprzeczna teoria formalna zawierająca AR jest niezupełna, okazało się, iż nie można zawrzeć całej matematyki w jednym systemie aksjomatycznym (KRP). Twierdzenie ukazało, że program Hilberta o formalizacji całej matematyki jest niewykonalny.

Twierdzenie wykazało, że w matematyce zawsze istnieją zdania nierozstrzygalne na jakimś zbiorze aksjomatów - musimy więc ująć matematykę jako ciąg teorii, nie jako pojedynczą teorię.

Twierdzenie podważyło tezę uniwersalizmu; ukazało niemożność pełnej realizacji leibnizowskiego języka uniwersalnego (mathesis universalis). Potrzebny byłby język characteristica universalis.

Na gruncie epistemologii (krytyka metodycznego sceptycyzmu Kartezjusza i redukcji ejdetycznej) wskazuje, że niemożliwa jest wiedza niezależna od jakichkolwiek arbitralnych założeń.

Procesów myślenia nie da się wyjaśnić w kategoriach fizykalnych i algorytmicznych.

11. Pojęcie interpretacji semantycznej języka pierwszego rzędu.

DEFINICJA 1(11)

Interpretacją języka KRP jest dowolna para postaci M = <U, Δ>, gdzie U ≠ ∅ jest dowolnym zbiorem zwanym uniwersum interpretacji M, zaś Δ to tak zwana funkcja denotowania, przyporządkowująca wszystkim stałym pozalogicznym języka KRP elementy ze zbioru U lub konstrukcje z tych elementów, przy czym:

1. Każdej literze predykatowej P_iⁿ funkcja denotowania Δ przyporządkowuje n- członową relację zachodzącą między elementami zbioru U ( Δ (P_iⁿ) ⊆ Uⁿ );

2. Każdemu symbolowi funkcyjnemu n- argumentowemu Fin funkcja denotowania Δ przyporządkowuje n- argumentową funkcję o argumentach i wartościach należących do zbioru U ( Δ (f_iⁿ) ∈ U^Un );

3. Każdej stałej nazwowej (nazwie) a_i funkcja denotowania Δ przyporządkowuje pewien wyróżniony element ze zbioru U ( Δ (a_i) ∈ U ).

12. Definicja pojęcia wartościowania termów.

DEFINICJA M-WARTOŚCIOWANIA 1(12)

Nieskończone ciągi elementów uniwersum danej interpretacji M będziemy nazywali m-wartościowaniami lub po prostu wartościowaniami (gdy nie będzie wątpliwości o jaką interpretację chodzi.)

W_M(t, <w_n>) - wartość termu t przy wartościowaniu <w_n> i interpretacji M.

DEFINICJA 2(12)

1. W_M(x_i, <w_n>) = w_i;

2. W_M(a_i, <w_n>) = Δ (a_i);

3. W_M( f_iⁿ (t₁, ..., t_n)”, <w_n>) = Δ (f_iⁿ) (W_M(t₁, <w_n>), ..., W_M(t_n, <w_n>))

13. Definicja pojęcia spełniania formuły przez ciąg przedmiotów.

<w_n> Spł_MA - ciąg <w_n> spełnia przy interpretacji M. formułę A.

DEFINICJA 1(13)

1. <w_n>Spł_M”P_kⁿ(t₁, ..., t_n)” ⇔ Δ (P_kⁿ) (W_M.(t₁, <w_n>), ..., W_M(t_n, <w_n>));

2. <w_n>Spł_M”∼(A)” ⇔ ¬(<w_n>Spł_MA);

3. <w_n>Spł_M”(A) ∧ (B)” ⇔ (<w_n>Spł_M.A) ∧ (<w_n>Spł_MB);

4. <w_n>Spł_M”(A) ∨ (B)” ⇔ (<w_n>Spł_MA) ∨ (<w_n>Spł_MB);

5. <w_n>Spł_M.”(A) → (B)” ⇔ [(<w_n>Spł_M.A) ⇒ (<w_n>Spł_MB)];

6. <w_n>Spł_M.”(A) ≡ (B)” ⇔ [(<w_n>Spł_M.A) ⇔ (<w_n>Spł_M.B)];

7. <w_n>Spł_M.”∀x_i (A)” ⇔ Λu∈U (<w_n> (w_i /u)Spł_MA)

[ gdzie <w_n>(w_i/u) = <w₁,...,w_i-1,u,w_i+1,...>]

8. <w_n>Spł_M.”∃x_i (A)” ⇔ Vu∈U (<w_n> (w_i /u) Spł_MA).

14. Definicja pojęcia prawdy. Twierdzenia charakteryzujące pojęcie prawdy.

DEFINICJA 1(14)

Formuła A jest prawdziwa przy interpretacji M = <U, Δ> wtedy i tylko wtedy, gdy każdy nieskończony, przeliczalny ciąg elementów uniwersum U spełnia formułę A przy interpretacji M. Czyli: A ∈ Vr (M) ⇔ Λ<w_n> (<w_n>∈ U^N ⇒ <w_n>Spł_MA)

[Vr (M) - „zbiór formuł prawdziwych przy interpretacji M”; <w_n>∈U^N: ciąg, którego wyrazami są elementy zbioru U]

TWIERDZENIE 1(14) (semantyczne twierdzenie o odrywaniu)

Jeżeli „A → B”∈Vr(M) i A∈Vr(M), to B∈Vr(M).

Dowód:

(nie wprost)

Zakł., że: „A→B”∈Vr(M), A∈Vr(M)

Zakł. dla dowodu nie wprost: B∉Vr(M)

Z założenia dowodu nie wprost mamy, że: dla pewnego <w_n>, ¬(<w_n>Spł_MB)

Z założenia mamy, że: <w_n>Spł_M”A→B” (bo każde wartościowanie spełnia „A→B” przy M)

Wtedy (z def. wartościowania): <w_n>Spł_MA ⇒ <w_n>Spł_MB

Korzystając z prawa [(A→B)∧∼B]→ ∼A mamy, że: ¬(<w_n>Spł_MA),

czyli formuła A nie jest prawdziwa przy M wbrew założeniu twierdzenia.

TWIERDZENIE 2(14) (semantyczne twierdzenie o generalizacji)

Jeżeli A∈Vr(M), to również „∀x_i (A)”∈Vr(M).

Dowód:

Zakładamy: A∈Vr(M)

Niech <w_n> będzie dowolnym M-wartościowaniem.

Każde wartościowanie spełnia tę formułę, a więc w szczególności:

Λu∈U (<w_n>(w_i /u) Spł_MA)

a to znaczy na mocy definicji spełniania, że: <w_n>Spł_M”∀x_i (A)”,

Wobec dowolności <w_n> mamy, że „∀x_i (A)”∈Vr(M).

TWIERDZENIE 3(14) (odwrotne twierdzenie o generalizacji)

Jeżeli „∀x_i(A)”∈Vr(M), to A∈Vr(M)

Dowód:

Zakł., że: „∀x_i(A)”∈Vr(M)

Niech <w_n> będzie dowolnym M-wartościowaniem.

Z założenia wiemy, źe: <w_n>Spł_M”∀x_i(A)”

Zgodnie z def. spełniania: Λu∈U (<w_n>(w_i /u) Spł_MA)

Ale w_i∈U, stąd: <w_n>Spł_M(A)

Wobec dowolności ciągu <wn>: A∈Vr(M)

TWIERDZENIE 4(14) (silne twierdzenie o generalizacji)

A∈Vr(M) wtedy i tylko wtedy, gdy Ā∈Vr(M).

TWIERDZENIE 5(14)

Zbiór formuł prawdziwych przy interpretacji M jest teorią czyli Cn(Vr(M) = Vr(M).

Dowód:

I. Musimy wykazać, że: Vr(M) ⊆ Cn(Vr(M))

Na mocy twierdzenia: X ⊆ Cn(X) jest to prawdziwe ( za X/ Vr(M) ).

II. Zakładamy: A∈Cn(Vr(M))

Wykażemy, że: dla dowolnej formuły A, jeżeli A∈Cn(Vr(M)), to A∈Vr(M).

Z def. konsekwencji wnosimyu, że: istnieje co najmniej jeden dowód A w oparciu o Vr(M); Niech tym dowodem będzie ciąg formuł D₁,...,D_n; D_n=A.

Wykażemy, że: dla każdego wskaźnika i ≤ n, D_i∈Vr(M). W tym celu zastosujemy indukcję matematyczną względem i.

Krok wyjściowy:

i=1.

Z def. dowodu formuła D₁∈Vr(M)

Krok indukcyjny:

Założenie indukcyjne: dla każdego wskaźnika i<k, gdzie 1<k≤n, D_i∈Vr(M)

Wykażemy, że w tej sytuacji również D_k∈Vr(M).

1. gdy formuła D_k jest jedną z formuł, w oparciu o które przeprowadzamy dowód. Wtedy formuła D_k∈Vr(M).

2. gdy formuła D_k powstaje z pewnych formuł wcześniejszych w dowodzie D₁,...,D_n przez zastosowanie reguły odrywania.

Wtedy istnieją wskaźniki i, j < k takie, że D_i=”D_J→D_k”.

Zgodnie z założeniem indukcyjnym, skoro i<k, to: D_i∈Vr(M), czyli „D_J→D_k”∈Vr(M).

Ponadto zgodnie z tym założeniem, skoro j<k,to: D_J∈Vr(M).

Korzystając z semantycznego twierdzenia o odrywaniu otrzymamy, że D_k∈Vr(M).

3. gdy formuła D_k powstaje z pewnej formuły poprzedzającej ją w dowodzie D₁,...,D_n przez zastosowanie reguły generalizacji.

Wtedy istnieje wskaźnik j<k oraz wskaźnik i takie, że D_k=”∀x_i (D_J)”.

Zgodnie z założeniem indukcyjnym D_J∈Vr(M) (ponieważ j<k).

Korzystając z semantycznego twierdzenia o generalizacji dostajemy, że „∀x_i (D_J)”∈Vr(M), Czyli: D_k∈Vr(M).

W szczególności mamy (ponieważ k ≤ n), że: D_n∈Vr(M),

A ponieważ D_n=A więc A∈Vr(M).

TWIERDZENIE 6(14) (semantyczna zasada wyłączonego środka)

Jeżeli A jest zdaniem, to A∈Vr(M) lub „∼A”∈Vr(M).

Dowód:

Zakł., że: A jest zdaniem

Skorzystamy z prawa: (A∨B)≡(∼A→B)

A∉Vr(M) ⇒ ¬Λ<w_n>(<w_n>Spł_MA) z definicji prawdy

⇒ V<w_n> ¬(<w_n>Spł_MA) z prawa DeMorgana

⇒ V<w_n>(<w_n>Spł_M”∼A”)

⇒ „∼A”∈Vr(M) ( z tego, że „∼A” jest zdaniem oraz na mocy twierdzenia: jeżeli formuła A jest zdaniem, to A∈Vr(M) wtw, gdy istnieje co najmniej jedno M.-wartościowanie <w_n> takie, że <w_n>Spł_MA)

TWIERDZENIE 7(14) (semantyczna zasada sprzeczności / niesprzeczności)

A∉Vr(M) bądź „∼A”∉Vr(M).

Z dwóch formuł wzajemnie sprzecznych jedna jest fałszywa.

Dowód:

Korzystamy w metajęzyku z prawa: (A∨B)≡(∼A→B)

A∈Vr(M) ⇒ Λ<w_n>(<w_n>Spł_MA) z definicji prawdy

⇒ V<w_n>(<w_n>Spł_MA) bo uniwersum jest zbiorem niepustym

⇒ ¬Λ<w_n> ¬(<w_n>Spł_MA) z prawa DeMorgana

⇒ ¬Λ<w_n>(<w_n>Spł_M „∼A”) z definicji spełniania

⇒ „∼A”∈Vr(M) zgodnie z definicją prawdy

15. Pojęcia homomorfizmu i izomorfizmu interpretacji i ich znaczenie.

DEFINICJA 1(15)

Niech M=<U, Δ> i M'=<U', Δ'> będą dwoma różnymi interpretacjami tego samego języka. Mówimy, że funkcja h jest homomorfizmem interpretacji M na interpretację M' wtedy i tylko wtedy, gdy:

1. h jest przekształceniem (funkcją) zbioru U na U', czyli h(U)=U';

2. dla każdego predykatu P_iⁿ (należącego do rozważanego języka) oraz dla dowolnych u₁,...,u_n∈U zachodzi: Δ(P_iⁿ)(u₁,...,u_n) wtedy i tylko wtedy, gdy Δ'(P_iⁿ)(h(u₁),...,h(u_n));

3. dla każdego symbolu funkcyjnego f_iⁿ oraz dla dowolnych u₁,...,u_n∈U zachodzi:

h(Δ(f_iⁿ)(u₁,...,u_n))=Δ'(f_iⁿ)(h(u₁),...,h( u_n));

4. dla dowolnej stałej nazwowej a_i zachodzi: h(Δ(a_i))=Δ'(a_i).

Jeżeli ponadto funkcja h jest różnowartościowa, tzn. dla różnych argumentów przyjmuje różne wartości, to mówimy, że funkcja h jest izomorfizmem interpretacji M na interpretację M'. Natomiast gdy funkcja h jest różnowartościowym odwzorowaniem uniwersum U w uniwersum U', to mówimy, że funkcja h zanurza interpretację M w interpretacji M'.

Znaczenie

• badanie interpretacji homomorficznych lub izomorficznych jest czasem prostsze niż badanie interpretacji właściwych,

• jeśli coś się orzeka o interpretacji M, to to samo można orzec o interpretacji, która jest homomorficzna lub izomorficzna z interpretacją M,

• jeśli dwie interpretacje są izomorficzne, to zbiory uniwersum tych interpretacji są zbiorami równolicznymi

16. Definicja pojęć tautologii i kontrtautologii KRP.

DEFINICJA 1(16)

1. Formuła A jest tautologią KRP wtedy i tylko wtedy, gdy jest ona prawdziwa przy każdej interpretacji języka KRP. A∈Trp wtw, gdy ΛM(A∈Vr(M)).

2. Formuła A jest kontrtautologią KRP wtedy i tylko wtedy, gdy jest ona fałszywa przy każdej interpretacji języka KRP.

A∈Ktrp wtw, gdy ΛM(A∉Vr(M)).

TWIERDZENIE 1(16)

Wszystkie aksjomaty KRP są tautologiami. ( Czyli: Arp⊆Trp).

TWIERDZENIE 2(16)

Wszystkie tezy KRP są tautologiami ( czyli L⊆Trp).

Dowód:

Z tw., że Arp⊆Trp wnosimy, że: Arp⊆Vr(M), dla dowolnej interpretacji M

Z tw. o monotoniczności mamy, że: Cn(Arp)⊆Cn(Vr(M)), dla dowolnej interpretacji M

Z faktu, iż: Cn(Vr(M)) = Vr(M) i z Cn(Arp)=L mamy, że: L⊆Vr(M), dla dowolnej interpretacji M

Ponieważ zaś M jest dowolną interpretacją, to: L⊆Trp.

TWIERDZENIE 3(16)

Zbiór formuł prawdziwych przy interpretacji M jest teorią I-ego rzędu (czyli: Vr(M) = Cn_L(Vr(M)).

TWIERDZENIE 4(16)

Zbiór formuł prawdziwych przy interpretacji M jest systemem dedukcyjnym, niesprzecznym i zupełnym.

17. Definicja pojęcia modelu semantycznego. Treść twierdzeń łączących pojęcia modelu semantycznego i niesprzeczności oraz ich znaczenie.

DEFINICJA 1(17)

Modelem semantycznym zbioru formuł X nazywamy każdą interpretację M. (języka, w którym formuły ze zbioru X są zapisywane) taką, że X⊆Vr(M). Modele zbioru jednoelementowego {A} nazywamy po prostu modelami formuły A.

TWIERDZENIE 1(17)

Jeżeli zbiór formuł X posiada model semantyczny, to jest on niesprzeczny.

[twierdzenie to podaje kryterium niesprzeczności i mówi, że chcąc udowodnić niesprzeczność danej teorii trzeba dla niej zbudować model semantyczny]

TWIERDZENIE 2(17) (twierdzenie Gödla o istnieniu modelu)

Każdy niesprzeczny zbiór formuł posiada model przeliczalny nieskończony.

Znaczenie

Twierdzenie to można uważać za wyrażenie stwierdzenia, że istnienie w matematyce redukuje się do niesprzeczności. Np. aby stwierdzić istnienie przedmiotów i relacji arytmetyki liczb naturalnych trzeba dowieść niesprzeczności tej teorii. Wskazuje ono również na związek pomiędzy niesprzecznością i istnieniem interpretacji.

Z twierdzeń tych otrzymujemy też, że każdy zbiór formuł, który ma model ma też model przeliczalny (nieskończony).

TWIERDZENIE SKALEMA-LOWENHEIMA 3(17)

Zbiór foruł zdaniowych posiada model wtedy i tylko wtedy, gdy posiada on model przeliczalny.

TWIERDZENIE 4(17)

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

[Tw. to głosi, że każda niesprzeczna teoria posiada model w zbiorze liczb naturalnych.]

TWIERDZENIE 5(17) (Semantyczne tw. o zwartości)

Jeżeli każdy skończony podzbiór zbioru formuł X posiada model, to również cały zbiór X posiada model.

Dowód

Jeśli założymy, że każdy podzbiór ma model, to z tw. 2(17) wnosimy, iż podzbiory te są niesprzeczne. Wtedy z tw. o finitystyczności wnosimy, że cały zbiór jest niesprzeczny, a z tw. Godla o istnieniu modelu wnosimy, że ten zbiór ma model.

18. Definicja pojęcia konsekwencji semantycznej. Twierdzenie łączące pojęcia konsekwencji semantycznej i konsekwencji logicznej.

DEFINICJA 1(18)

Formuła A jest konsekwencją semantyczną zbioru formuł X wtedy i tylko wtedy, gdy dla dowolnej interpretacji M języka J zachodzi: jeżeli X⊆Vr(M), to również A∈Vr(M).

X I= A - „formuła A jest konsekwencją semantyczną zbioru formuł X”.

TWIERDZENIE 1(18)

{A₁, A₂,...,A_n} I= B wtedy i tylko wtedy, gdy „A₁→[A₂→...(A_n→B)]” ∈Trp

TWIERDZENIE 2(18)

Jeżeli A∈Trp, to dla dowolnego zbioru X, X I= A.

TWIERDZENIE 3(18) (o pełności - wersja 1)

Formuła A jest konsekwencją semantyczną zbioru formuł X wtedy i tylko wtedy, gdy jest ona konsekwencją logiczną zbioru X.

X I= A ⇔ A∈Cn_L(X).

Dowód:

(→) Nie wprost

Zakł., że: X I=A

Dla dowodu nie wprost zakładamy: A∉Cn_L(X).

Jeśli A∉Cn_L(X), to również Ā∉Cn_L(X).

Korzystając z tw.: jeżeli A jest zdaniem i A∉Cn_L(X), to X∪{∼A}∈NSP, wnosimy, że:

X∪{∼Ā}∈NSP.

Z tw. Gödla o istnieniu modelu: istnieje pewien model dla tego zbioru (bo jest on niesprzeczny) czyli: X∪{∼Ā}⊆Vr(M)

Stąd wnosimy, że: X⊆Vr(M) i ∼Ā∈Vr(M)

Zgodnie z semantyczną zasadą wyłączonego środka ponieważ „∼Ā”∈Vr(M), to:

Ā∉Vr(M)

Również A∉Vr(M) (na mocy twierdzenia o generalizacji)

Zatem (z def. konsekwencji semantycznej): X I≠ A wbrew założeniu twierdzenia.

(←) Wprost

Zakł., że: A∈Cn_L(X), X⊆Vr(M)

Wykażemy, że: A∈Vr(M).

Korzystając z twierdzenia o monotoniczności, mamy, że: Cn_L(X)⊆Cn_L(Vr(M))

Korzystając z twierdzenia Cn_L(Vr(M))=Vr(M), mamy: Cn_L(X)⊆Vr(M)

Skoro A∈Cn_L(X), to A∈Vr(M), czyli X I= A.

[Tw. to pozwala zastąpić pojęcie konsekwencji semantycznej pojęciem konsekwencji syntaktycznej i na odwrót. Płynie stąd wniosek, iż obie te konsekwencje mają te same własności.]

19. Twierdzenie o pełności i jego znaczenie.

TWIERDZENIE POMOCNICZE 1(19)

Jeżeli formuła A∉L (nie jest tezą KRP), to istnieje interpretacja M taka, że „∼A”∈Vr(M).

Dowód

Zakł., że: A∉L, czyli A∉Cn_L(Ø) (gdyż L=Cn_L(Ø)

Na mocy syntaktycznego tw. o generalizacji: Ā∉Cn_L(Ø)

Z tw. o pojęciu niesprzeczności wnosimy, że: Ø∪{∼ Ā}∈NSP

Czyli (gdyż X∪Ø = X): {∼ Ā}∈NSP

Z tw. Godla o istnieniu modelu: istnieje interpretacja M taka, że ∼ Ā∈Vr(M).

TWIERDZENIE O PEŁNOŚCI KRP 2(19)

Formuła A jest tautologią KRP wtedy i tylko wtedy, gdy jest tezą KRP. (A∈Trp ↔ A∈L)

Dowód

(→) Zakł., że: A∈Trp

Dla dowodu nie wprost zakł., że: A∉L, czyli A∉Cn_L(Ø).

Zgodnie z powyższym tw. pomocniczym istnieje interpretacja M taka, że:”∼A”∈Vr(M)

Ponieważ formuła A jest tautologią, to dla każdej interpretacji M: A∈Vr(M).

Z semantycznego tw. o generalizacji: skoro A∈Vr(M), to Ā∈Vr(M).

To oznacza, że dwie formuły wzajemnie sprzeczne (A i ∼A)∈Vr(M), czyli Vr(M)∉NSP (wbrew twierdzeniu, że zbiór formuł prawdziwych przy interpretacji M tworzy system dedukcyjny niesprzeczny i zupełny).

(←) Udowodnione wcześniej: L⊆Trp.

Znaczenie tw. o pełności:

Na każdej udowodnionej tezie można oprzeć regułę dowodową.

Każda niezawodna reguła wnisokowania oparta jest ma jakiejś tautologii.

Tylko tego typu reguły są zrewidencjonowane w logice.

*Od teorii formalnych wymagamy, by były to teorie pełne.

16

---