Pytania egzaminacyjne – Semantyka logiczna
1. Definicja pojęcia niesprzeczności. Twierdzenia charakteryzujące pojęcie niesprzeczności. Ogólna metoda dowodów niesprzeczności teori .
2. Definicja pojęcia niezależności. Treść twierdzeń łączących pojęcia niezależności i niesprzeczności, i ich znaczenie.
3. 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).
4. Treść pierwszego i drugiego twierdzenia Gödla o niezupełności arytmetyki i ich znaczenie.
5. Pojęcie interpretacji semantycznej języka pierwszego rzędu.
6. Definicja pojęcia wartościowania termów.
7. Definicja pojęcia spełniania formuły przez ciąg przedmiotów.
8. 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. Twierdzenie Tarskiego o niedefiniowalności prawdy.
9. Pojęcia homomorfizmu i izomorfizmu interpretacji i ich znaczenie.
10. Definicje pojęć tautologi i kontrtautologi KRP.
11. Definicja pojęcia modelu semantycznego. Treść twierdzeń łączących pojęcia modelu semantycznego i niesprzeczności oraz ich znaczenie.
12. Definicja pojęcia konsekwencji semantycznej.
13. Treść twierdzenia o pełności KRP i jego znaczenie.
„ ” = rożki Quine’a
/Zachowano odmienność notacji dla metajęzyka/.
1
I. Definicja pojęcia niesprzeczności. Twierdzenia charakteryzujące pojęcie niesprzeczności. Ogólna metoda dow
odów niesprzeczności teorii .
1) DEFINICJA pojęcia niesprzeczności:
a) Zbiór formuł zdaniowych X jest niesprzeczny (X∈ NSP) wtedy i tylko wtedy, gdy nie istnieje żadna taka formuła A, że A∈ CnL(X) oraz „∼ A” ∈ CnL(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∈ CnL(X) i zarazem „∼ A” ∈ CnL(X).
2) Twierdzenia charakteryzujące pojęcie niesprzeczności:
TWIERDZENIE 1(7)
Zbiór X jest niesprzeczny wtedy i tylko wtedy, gdy zbiór CnL(X) jest niesprzeczny.
Dowód:
I. (→)
Zakładamy, że: X∈NSP
Z definicji mamy: nie istnieje formuła A taka, że: A ∈ CnL(X) i „∼A” ∈CnL(X).
Z twierdzenia: CnL(CnL(X)) = CnL(X) otrzymujemy:
nie istnieje formuła A taka, że: A ∈ CnL(CnL(X)) i „∼A” ∈ CnL(CnL(X)).
Wobec definicji niesprzeczności:
CnL(X) ∈ NSP.
II. (←)
Zakładamy, że: CnL(X) ∈ NSP
Z definicji: nie istnieje formuła A taka, że: A ∈ CnL(CnL(X)) i „∼A” ∈ CnL(CnL(X)).
Z twierdzenia: CnL(CnL(X)) = CnL(X) otrzymujemy:
A ∈ CnL(X) i „∼A” ∈ CnL(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∉ CnL(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 ∉ CnL(X) bądź „∼A” ∉ CnL(X). A więc przynajmniej jedna formuła na pewno nie należy do CnL(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 ∉ CnL(X).
Z def. wnosimy, że: istnieje taka formuła B, że B∈CnL(X) i „∼B”∈CnL(X)
Z uwagi na prawo Dunsa Szkota, dla dowolnej formuły zdaniowej C mamy, że:
„B → (∼B → C)”∈L
2
„B → (∼B → C)” ∈ CnL(X).
Przez dwukrotne zastosowanie syntaktycznego twierdzenia o odrywaniu wnosimy, że C∈CnL(X). Wobec dowolności C wnosimy, że każda formuła należy do CnL(X). To zaś jest sprzeczne z założeniem.
Jeśli więc istnieje formuła, która nie należy do CnL(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 CnL(X)⊆CnL(Y)):
CnL(X) ⊆ CnL(Y)
Z założenia dowodu nie wprost i definicji sprzeczności:
istnieje A taka, że A ∈ CnL(X) i „∼A” ∈ CnL(X).
Więc: istnieje formuła A taka, że: A ∈ CnL(Y) i „∼A” ∈ CnL(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∈ CnL(X) i „∼ A” ∈ CnL(X) Z tw. o finitystyczności (A∈ CnL(X) wtw istnieje zbiór Y⊆ X taki, że Y jest zbiorem skończonym i A∈ CnL(Y)): istnieje zbiór Y1⊆ X i Y1 jest zbiorem skończonym oraz A∈ CnL(Y1), oraz isnieje zbiór Y2⊆ X
i Y2 jest zbiorem skończonym oraz „∼ A” ∈ CnL(Y2).
Czyli: Y1∪ Y2⊆ X i Y1∪ Y2 to zbiór skończony a A∈ CnL(Y1∪ Y2) i „∼ A” ∈ CnL(Y1∪ Y2), 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” ∉ CnL(X), to zbiór X ∪ {A} jest niesprzeczny.
Dowód:
Zakł.,że: A jest zdaniem, „∼A”∉CnL(X)
Zakł – dla dowodu nie wprost – że zbiór X ∪ {A} jest sprzeczny.
Z def.: istnieje wówczas taka formuła B, że B∈CnL(X ∪ {A}) i równocześnie „∼B” ∈ CnL(X ∪ {A}). Ponieważ zaś:
„B → (∼B → B ∧ ∼B)”∈ L, a L⊆CnL(X)
więc:
„B → (∼B → B ∧ ∼B)”∈CnL(X∪{A})
3
Po dwukrotnym użyciu reguły odrywania otrzymujemy:
„B ∧ ∼B” ∈ CnL(X ∪ {A}).
Stąd – na mocy twierdzenia o dedukcji –
„A → B ∧ ∼B” ∈ CnL(X).
Równocześnie
„(A → B ∧ ∼B) → ∼A” ∈L.
„(A → B ∧ ∼B) → ∼A”∈CnL(X)
Z syntaktycznego tw. o odrywaniu:
„∼A” ∈ CnL(X).
Ten ostatni wniosek przeczy jednak jednemu z założeń twierdzenia.
3) Ogólna metoda dowodów niesprzeczności teorii:
LEMAT
Jeżeli A∈ L (gdzie L=Cn(Arp)), to H(A)∈ Trz.
DEFINICJA 3(7) INDUKCYJNA FUNKCJI H
1.) H („P n
k (α1,...,αn)”)=”p”
2.) H („∼A”) = „∼H(A)”
3.) H (“∀xi(A)”) = H(A)
4.) H (“∃xi(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)”
Funkcja H przyporządkowuje językowi KRP język KRZ.
TWIERDZENIE 6(7) (Opisuje podstawową metodę dowodzenia niesprzeczności teorii aksjomatycznych).
Niech X będzie teorią w języku J 1 a Y teorią w języku J2. 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 ∈ J1, 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 = CnL(X)
zbiór Y jest teorią – Y = CnL(Y)
funkcja H(„∼A”) = „∼H(A)” dla dowolnego A ∈ J1
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:
4
Y ∈ SP, bo H(A) ∈Y i „∼H(A)” ∈ Y
wbrew założeniu twierdzenia, że jest to zbiór niesprzeczny.
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ą.
II. Definicja pojęcia niezależności. Treść twierdzeń łączących pojęcia niezależności i niesprzeczności, i ich znaczenie.
1) DEFINICJA pojęcia niezależności:
(i)
Zbiór X jest niezależny (X∈ NZL) wtedy i tylko wtedy, gdy dla dowolnej formuły A∈ X, A∉ CnL(X – {A})
– dotyczy niezależności zbioru formuł .
(ii)
Formuła zdaniowa A jest niezależna od zbioru formuł X wtedy i tylko wtedy, gdy A ∉ CnL(X). –
dotyczy relatywnej niezależności formuły względem określonego zbioru formuł.
2) Treść twierdzeń łączących pojęcia niezależności i niesprzeczności, i ich znaczenie:
TWIERDZENIE 1(1)
Jeżeli zbiór X ∪ {∼ Ā} jest niesprzeczny, to formuła A jest niezależna od zbioru X, tzn. A ∉ CnL(X).
Dowód:
Zakładamy, że: X∪{∼Ā}∈NSP
Dla dowodu nie wprost zakładamy, że: A∈CnL(X)
Wobec tw. o monotoniczności (X⊆X∪{∼A}) i tego, że A∈CnL(X): A∈CnL(X∪{∼Ā})
Na mocy twierdzenia o generalizacji: Ā∈CnL(X∪{∼Ā}).
Dalej, na mocy twierdzenia o zwrotności (X⊆CnL(X)): ∼Ā∈CnL(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 A1,A2,...,Ai,... są aksjomatami jakiejś teori , to dla dowodu, że aksjomat Ai jest niezależny od pozostałych, wystarczy wykazać, że zbiór A1,A2,...,Ai-1,B,Ai+1,... gdzie B jest negacją domknięcia aksjomatu Ai, jest niesprzeczny. Do tego celu można stosować metody dowodzenia niesprzeczności.
5
efinicja pojęcia zupełności. Twierdzenia charakteryzujące pojęcie zupełności.
1) DEFINICJA pojęcia zupełności:
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 ∈ CnL(X) bądź „∼ A” ∈ CnL(X).
b.) Zbiór X jest niezupełny wtedy i tylko wtedy, gdy istnieje przynajmniej jedno zdanie A takie, że ani A ∉ CnL(X) ani
„∼ A” ∉ CnL(X).
2) Twierdzenia charakteryzujące pojęcie zupełności:
TWIERDZENIE 1(4)
Zbiór formuł zdaniowych X jest zupełny ze względu na dany język wtedy i tylko wtedy, gdy zbiór CnL(X) jest zupełny ze względu na ten sam język.
X∈ ZUP wtw, gdy CnL(X)∈ ZUP.
Dowód:
I.(→)
Zakładamy, że: X∈ZUP
Z definicji dla dowolnego A: albo A∈CnL(X) albo „∼A”∈CnL(X).
Z twierdzenia o idempotencji ( CnL(CnL(X))=CnL(X) ), dla dowolnego zdania A: albo A∈CnL(CnL(X)), albo
„∼A”∈CnL(CnL(X)).
Tzn. (na mocy def.), że: CnL(X)∈ZUP.
II.(←)
Zakładamy, że: CnL(X)∈ZUP
Z definicji wnosimy, że: dla każdego zdania A albo A∈CnL(CnL(X)) albo „∼A”∈CnL(CnL(X)).
Z twierdzenia o idempotencji ( CnL(CnL(X))=CnL(X) ) mamy, że: albo A∈CnL(X) albo „∼A”∈CnL(X).
Tzn. (na mocy def.), że: X∈ZUP.
Twierdzenie to głosi, że mówienie o zupełności aksjomatyki danej teori jest równoznaczne z mówieniem o zupełności teori i na odwrót.
TWIERDZENIE 2(4)
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∉CnL(X) i „∼A”∉CnL(X).
Stąd zaś na mocy twierdzenia: X∈NSP wtw, gdy istnieje co najmniej jedna formuła zdaniowa A taka, że A∉CnL(X); wynika niesprzeczność zbioru X.
TWIERDZENIE 3(4)
Niech X będzie zbiorem niesprzecznym. Wtedy X∈ ZUP wtedy i tylko wtedy, gdy dla każdej formuły A takiej, że A∉ CnL(X), zbiór X∪ {A} jest sprzeczny.
6
(→)
Zakładamy, że: X∈NSP, X∈ZUP, A∉CnL(X).
Wykażemy: X∪{A}∈SP
Zgodnie z twierdzeniem o generalizacji: Ā∉CnL(X)
Ponieważ X∈ZUP, więc wtedy „∼Ā”∈CnL(X), to tym bardziej (z tw. o monotoniczności)
„∼Ā”∈CnL(X∪{A})
Z tw.X⊆CnL(X): A∈CnL(X∪{A}),
Z tw. o generalizacji: Ā∈CnL(X∪{A}).
Zbiór X∪{A} jest więc sprzeczny, bo „∼Ā” i Ā ∈ CnL(X∪{A}).
(←)
Zakładamy: dla każdej formuły A takiej, że A∉CnL(X), X∪{A}∈SP
Dla dowodu nie wprost zakładamy: X∉ZUP
Z def.: istnieje zdanie A takie, że A∉CnL(X) i „∼A”∉CnL(X)
Znaczy to, że X∪{A}∈NSP i zbiór X∪{∼A}∈NSP, a to przeczy założeniu twierdzenia.
TWIERDZENIE 4(4) (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 teori X. Zbiór Y nazywamy wówczas nadzbiorem Lindenbauma.
Tw. to głosi możliwość dokonania rozszerzenia niesprzecznej teori pierwszego rzędu do teori zupełnej.
IV. 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,
PA – arytmetyka liczb naturalnych Peana,
1 TWIERDZENIE GÖDLA O NIEZUPEŁNOŚĆI AR 1(2)
Jeśli PA jest fragmentem teori T (PA⊆ T) i teoria T∈ NSP, to istnieje zdanie A w języku teori T, że A∉ CnL(T) i
„∼ A” ∉ CnL(T), czyli teoria T∉ ZUP.
*Niech „Con(T)” skraca zdanie „T jest niesprzeczne” zapisane w języku teori T.
2 TWIERDZENIE GÖDLA O NIEZUPEŁNOŚCI AR 2(2)
Jeżeli PA⊆ T i T∈ NSP, to zdanie Con(T)∉ CnL(T).
(Twierdzenie to głosi, iż dowodu niesprzeczności teori T mającej PA i będącej niesprzeczną nie można w tej teori przeprowadzić.)
Znaczenie powyższych twierdzeń:
Z uwagi na to, że każda niesprzeczna teoria formalna zawierająca PA 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.
7
Twierdzenie wykazało, że w matematyce zawsze istnieją zdania nierozstrzygalne na jakimś zbiorze aksjomatów –
musimy więc ująć matematykę jako ciąg teori , 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 epistemologi (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.
V. Pojęcie interpretacji semantycznej języka pierwszego rzędu.
1) DEFINICJA pojęcia interpretacji semantycznej języka pierwszego rzędu:
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 ni funkcja denotowania ∆ przyporządkowuje n- członową relację zachodzącą między elementami zbioru U ( ∆ (P ni) ⊆ Un );
(2) Każdemu symbolowi funkcyjnemu n- argumentowemu F ni funkcja denotowania ∆ przyporządkowuje n-argumentową funkcję o argumentach i wartościach należących do zbioru U ( ∆ (f ni) ∈ UUn ); (3) Każdej stałej nazwowej (nazwie) ai funkcja denotowania ∆ przyporządkowuje pewien wyróżniony element ze zbioru U ( ∆ (ai) ∈ U ).
VI. Definicja pojęcia wartościowania termów.
1) DEFINICJA M-Wartościowania:
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.)
WM(t, <wn>) – wartość termu t przy wartościowaniu <wn> i interpretacji M.
2) DEFINICJA funkcji wartościowania:
(1) WM(xi, <wn>) = wi;
(2) WM(ai, <wn>) = ∆ (ai);
(3) W
n
n
M( fi (t1, ..., tn)”, <wn>) = ∆ (fi ) (WM(t1, <wn>), ..., WM(tn, <wn>))
8
VII. Definicja pojęcia spełniania formuły przez ciąg przedmiotów.
<wn> SpłMA – ciąg <wn> spełnia przy interpretacji M. formułę A.
(1) <w
n
n
n>SpłM”Pk (t1, ..., tn)” ⇔ ∆ (Pk ) (WM.(t1, <wn>), ..., WM(tn, <wn>)); (2) <wn>SpłM” ∼ (A)” ⇔ ¬ (<wn>SpłMA);
(3) <wn>SpłM”(A) ∧ (B)” ⇔ (<wn>SpłM.A) ∧ (<wn>SpłMB); (4) <wn>SpłM”(A) ∨ (B)” ⇔ (<wn>SpłMA) ∨ (<wn>SpłMB); (5) <wn>SpłM.”(A) → (B)” ⇔ [(<wn>SpłM.A) ⇒ (<wn>SpłMB)]; (6) <wn>SpłM.”(A) ≡ (B)” ⇔ [(<wn>SpłM.A) ⇔ (<wn>SpłM.B)]; (7) <wn>SpłM.” ∀ xi (A)” ⇔ ∀ u∈ U (<wn> (wi /u)SpłMA)
[ gdzie <wn>(wi/u) = <w1,...,wi-1,u,wi+1,...>]
(8) <wn>SpłM.” ∃ xi (A)” ⇔ ∃ u∈ U (<wn> (wi /u) SpłMA).
VIII. Definicja pojęcia prawdy. Twierdzenia charakteryzujące pojęcie prawdy.
1) DEFINICJA pojęcia prawdy:
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) ⇔ Λ <wn> (<wn> ∈
UN ⇒ <wn>SpłMA)
[Vr (M) – „zbiór formuł prawdziwych przy interpretacji M”; <wn>∈UN: ciąg, którego wyrazami są elementy zbioru U]
2) Twierdzenia charakteryzujące pojęcie prawdy:
TWIERDZENIE 1(8) (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 <wn>, ¬(<wn>SpłMB)
Z założenia mamy, że: <wn>SpłM”A→B” (bo każde wartościowanie spełnia „A→B” przy M)
Wtedy (z def. wartościowania): <wn>SpłMA ⇒ <wn>SpłMB
Korzystając z prawa [(A→B)∧∼B]→ ∼A mamy, że: ¬(<wn>SpłMA),
czyli formuła A nie jest prawdziwa przy M wbrew założeniu twierdzenia.
TWIERDZENIE 2(8) (semantyczne twierdzenie o generalizacji)
Jeżeli A∈ Vr(M), to również „∀ xi (A)” ∈ Vr(M).
Dowód:
Zakładamy: A∈Vr(M)
Niech <wn> będzie dowolnym M-wartościowaniem.
Każde wartościowanie spełnia tę formułę, a więc w szczególności:
9
a to znaczy na mocy definicji spełniania, że: <wn>SpłM”∀xi (A)”,
Wobec dowolności <wn> mamy, że „∀xi (A)”∈Vr(M).
TWIERDZENIE 3(8) (odwrotne twierdzenie o generalizacji)
Jeżeli „∀xi(A)”∈Vr(M), to A∈Vr(M)
Dowód:
Zakł., że: „∀xi(A)”∈Vr(M)
Niech <wn> będzie dowolnym M-wartościowaniem.
Z założenia wiemy, źe: <wn>SpłM”∀xi(A)”
Zgodnie z def. spełniania: Λu∈U (<wn>(wi /u) SpłMA)
Ale wi∈U, stąd: <wn>SpłM(A)
Wobec dowolności ciągu <wn>: A∈Vr(M)
TWIERDZENIE 4(8) (silne twierdzenie o generalizacji)
A∈ Vr(M) wtedy i tylko wtedy, gdy Ā∈ Vr(M).
TWIERDZENIE 5(8) (twierdzenie stwierdzające, że zbiór formuł prawdziwych jest teorią)
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ł D1,...,Dn; Dn=A.
Wykażemy, że: dla każdego wskaźnika i ≤ n, Di∈Vr(M). W tym celu zastosujemy indukcję matematyczną względem i.
Krok wyjściowy:
i=1.
Z def. dowodu formuła D1∈Vr(M)
Krok indukcyjny:
Założenie indukcyjne: dla każdego wskaźnika i<k, gdzie 1<k≤n, Di∈Vr(M)
Wykażemy, że w tej sytuacji również Dk∈Vr(M).
1. gdy formuła Dk jest jedną z formuł, w oparciu o które przeprowadzamy dowód. Wtedy formuła Dk∈Vr(M).
2. gdy formuła Dk powstaje z pewnych formuł wcześniejszych w dowodzie D1,...,Dn przez zastosowanie reguły odrywania.
Wtedy istnieją wskaźniki i, j < k takie, że Di=”DJ→Dk”.
Zgodnie z założeniem indukcyjnym, skoro i<k, to: Di∈Vr(M), czyli „DJ→Dk”∈Vr(M).
Ponadto zgodnie z tym założeniem, skoro j<k,to: DJ∈Vr(M).
Korzystając z semantycznego twierdzenia o odrywaniu otrzymamy, że Dk∈Vr(M).
1
3. gdy formuła Dk powstaje z pewnej formuły poprzedzającej ją w dowodzie D1,...,Dn przez zastosowanie reguły generalizacji.
Wtedy istnieje wskaźnik j<k oraz wskaźnik i takie, że Dk=”∀xi (DJ)”.
Zgodnie z założeniem indukcyjnym DJ∈Vr(M) (ponieważ j<k).
Korzystając z semantycznego twierdzenia o generalizacji dostajemy, że „∀xi (DJ)”∈Vr(M), Czyli: Dk∈Vr(M).
W szczególności mamy (ponieważ k ≤ n), że: Dn∈Vr(M),
A ponieważ Dn=A więc A∈Vr(M).
TWIERDZENIE 6(8) (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) ⇒ ¬Λ<wn>(<wn>SpłMA)
z definicji prawdy
⇒ V<wn> ¬(<wn>SpłMA)
z prawa DeMorgana
⇒ V<wn>(<wn>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 <wn> takie, że <wn>SpłMA) TWIERDZENIE 7(8) (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) ⇒ Λ<wn>(<wn>SpłMA)
z definicji prawdy
⇒ V<wn>(<wn>SpłMA)
bo uniwersum jest zbiorem niepustym
⇒ ¬Λ<wn> ¬(<wn>SpłMA)
z prawa DeMorgana
⇒ ¬Λ<wn>(<wn>SpłM „∼A”)
z definicji spełniania
⇒ „∼A”∈Vr(M)
zgodnie z definicją prawdy
TWIERDZENIE 8(8) (Tarskiego o niedefiniowalności pojęcia prawdy)
Nie istnieje formuła Tr(X) języka JT definiująca zbiór zdań
prawdziwych teori T, tzn. taka, że dla dowolnego zdania A języka JT,
T |- A ↔ Tr(”A”).
1
IX. Pojęcia homomorfizmu i izomorfizmu interpretacji i ich znaczenie.
1) Definicja homomorfizmu i izomorfizmu interpretacji:
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 n
n
i (należącego do rozważanego języka) oraz dla dowolnych u1,...,un∈ U zachodzi: ∆ (Pi ) (u
n
1,...,un) wtedy i tylko wtedy, gdy ∆ ’(Pi )(h(u1),...,h(un));
(3) dla każdego symbolu funkcyjnego f ni oraz dla dowolnych u1,...,un∈ U zachodzi: h(∆ (f n
n
i )(u1,...,un))=∆ ’(fi )(h(u1),...,h( un));
(4) dla dowolnej stałej nazwowej ai zachodzi: h(∆ (ai))=∆ ’(ai).
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 X. Definicja pojęć tautologii i kontrtautologii KRP.
1)
1) DEFINICJA pojęć tautologii i kontrtautologii:
(a) 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)).
(b) 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(4)
Wszystkie aksjomaty KRP są tautologiami. ( Czyli: Arp⊆ Trp).
TWIERDZENIE 2(4)
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.
1
Zbiór formuł prawdziwych przy interpretacji M jest teorią I-ego rzędu (czyli: Vr(M) = CnL(Vr(M)).
TWIERDZENIE 4(4)
Zbiór formuł prawdziwych przy interpretacji M jest systemem dedukcyjnym, niesprzecznym i zupełnym.
XI. Definicja pojęcia modelu semantycznego. Treść twierdzeń łączących pojęcia modelu semantycznego i niesprzeczności.
1) DEFINICJA pojęcia modelu semantycznego:
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.
2) Twierdzenia łączące pojęcia modelu semantycznego i niesprzeczności:
TWIERDZENIE 1(5)
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 teori trzeba dla niej zbudować model semantyczny]
TWIERDZENIE 2(5) (twierdzenie Gödla o istnieniu modelu)
Każdy niesprzeczny zbiór formuł posiada model przeliczalny nieskończony.
TWIERDZENIE SKALEMA-LOWENHEIMA 3(5)
Zbiór formuł zdaniowych posiada model wtedy i tylko wtedy, gdy posiada on model przeliczalny.
TWIERDZENIE 4(5)
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(5) (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.
1
XII. Definicja pojęcia konsekwencji semantycznej. Twierdzenie łączące pojęcia konsekwencji semantycznej i konsekwencji logicznej.
1) DEFINICJA pojęcia konsekwencji semantycznej:
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”.
X
III . Twierdzenie o pełności KRP i jego znaczenie.
TWIERDZENIE POMOCNICZE 1(3)
Jeżeli formuła A∉ L (nie jest tezą KRP; Lemat: L = CnL(Arp)), to istnieje interpretacja M taka, że „∼ A” ∈ Vr(M).
Dowód
Zakł., że: A∉L, czyli A∉CnL(Ø) (gdyż L=CnL(Ø)
Na mocy syntaktycznego tw. o generalizacji: Ā∉CnL(Ø)
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 (Silne) 2(3)
Formuła A jest konsekwencją semantyczną zbioru formuł X wtedy i tylko wtedy, gdy jest ona konsekwencją logiczną zbioru X.
X I= A ⇔ A∈ CnL(X).
Dowód:
(→) Nie wprost
Zakł., że: X I= A
Dla dowodu nie wprost zakładamy: A∉CnL(X).
Jeśli A∉CnL(X), to również Ā∉CnL(X).
Korzystając z tw.: jeżeli A jest zdaniem i A∉CnL(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∈CnL(X), X⊆Vr(M)
Wykażemy, że: A∈Vr(M).
1
Korzystając z twierdzenia o monotoniczności, mamy, że: CnL(X)⊆CnL(Vr(M))
Korzystając z twierdzenia CnL(Vr(M))=Vr(M), mamy: CnL(X)⊆Vr(M)
Skoro A∈CnL(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.]
TWIERDZENIE O PEŁNOŚCI KRP (Słabe) 3(3)
Formuła A jest tautologią KRP wtedy i tylko wtedy, gdy A jest tezą KRP. (A∈ Trp ↔ A∈ L) Dowód
(→)
Zakł., że: A∈Trp
Dla dowodu nie wprost zakł., że: A∉L, czyli A∉CnL(Ø).
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ś tautologi .
Tylko tego typu reguły są zrewidencjonowane w logice.
*Od teori formalnych wymagamy, by były to teorie pełne.
1