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

1

x

2

x

3

...

(zmienne indywiduowe)

P

1

1

P

2

1

P

3

1

...

(predykaty jednoczłonowe)

P

1

2

P

2

2

P

3

2

(predykaty dwuczłonowe)

P

1

n

P

2

n

P

3

n

(predykaty n-członowe)

a

1

a

2

a

3

...

(nazwy indywidualne)

F

1

1

F

2

1

F

3

1

(symbole funkcyjne jednoargumentowe)

F

1

2

F

2

2

F

3

2

(symbole funkcyjne dwuargumentowe)

F

1

n

F

2

n

F

3

n

(symbole funkcyjne n-argumentowe)

( ) ,

(znaki techniczne: nawiasy i przecinek)

1

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

Termy:

i)

Wszystkie zmienne indywiduowe x

i

oraz wszystkie nazwy indywidualne ai są termami (albo

formułami nazwowymi) języka rachunku predykatów.

ii)

Jeżeli



1

,



2

,...,



n

są dowolnymi termami, to wyrażenie F

k

n

(



1

,...,



n

) jest również termem.

iii)

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

(



1

,...,



n

), gdzie



1

,...,



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

1

,z

2

,...,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

1



z

2

...



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

1

,D

2

,...,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:

(i)

D

k



X;

(ii)

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

”;

(iii)

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)

2

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)

(i)

zwrotność: X



Cn

L

(X); wartość udowodnionych zdań zależy od wartości udowodnionych

przesłanek;

(ii)

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);

(iii)

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;

(iv)

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;

(v)

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

1

,D

2

,...,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

1

jest pierwszym elelmentem dowodu, to na pewno D

1

ArpX{A}. Rozróżniamy tu

trzy przypadki:
1) D

1

Arp;

D

1

Cn

L

(X) ( gdyż Arp

Cn

L

(X) )

„D

1

(AD

1

)”

Arp

(prawo poprzednika)

„”D

1

(AD

1

)”

Cn

L

(X)

Korzystamy z syntaktycznego tw. o odrywaniu:
„A

D

1

”

Cn

L

(X)

2)

D

1

X:

D

1

Cn

L

(X)

(gdyż X

Cn

L

(X) )

3

jak wyżej...

3)

D

1

{A}

D

1

=A

„A

D

1

” = „A

A”

“A

A”L

“A

A”Cn

L

(X)

(bo L

Cn

L

(X) )

„A

D

1

”

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

1

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

1

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:

4

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:

a)

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 (



1

)



1

xA(x)





xA(x)





x



y[A(x)



A(y)



x=y]



1

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



1

xA(x) jest tezą.

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



1

xA(x)



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

lub dołączenie operatora deskrypcyjnego:



1

xA(x)

A(x’/(ix)A(x))

5

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

1

x

2

x

3

...

(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

1

, t

2



TM

AR

, to t

1

+t

2

, t

1



t

2



TM

AR

Def. formuły zdaniowej:
FMAR jest to najmnieszy zbiór taki, że:

1.

jeżeli t

1

, t

2



TM

AR

, to t

1

=t

2



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

a)

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).

b)

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:

6

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

1



X i Y

1

jest zbiorem skończonym oraz A



Cn

L

(Y

1

),

oraz isnieje zbiór Y

2



X i Y

2

jest zbiorem skończonym oraz „



A”



Cn

L

(Y

2

).

Czyli: Y

1



Y

2



X i Y

1



Y

2

to zbiór skończony a A



Cn

L

(Y

1



Y

2

) i „



A”



Cn

L

(Y

1



Y

2

), 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.

7

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

(



1

,...,



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

1

a Y teorią w języku J

2

. 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

1

, 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

1

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.

8

DEFINICJA 1(8)

(i)

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ł .

(ii)

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

1

,A

2

,...,A

i

,... są aksjomatami jakiejś teorii, to dla dowodu, że aksjomat Ai jest niezależny od

pozostałych, wystarczy wykazać, że zbiór A

1

,A

2

,...,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)

a.)

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.

b.)

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).

9

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.

10

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

n

funkcja denotowania



przyporządkowuje n- członową relację

zachodzącą między elementami zbioru U (



(P

i

n

)



U

n

);

(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

n

)



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

n

(t

1

, ..., t

n

)”, <w

n

>) =

 (f

i

n

) (W

M

(t

1

, <w

n

>), ..., W

M

(t

n

, <w

n

>))

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

<w

n

> Spł

M

A – ciąg <w

n

> spełnia przy interpretacji M. formułę A.

DEFINICJA 1(13)

(1)

<w

n

>Spł

M

”P

k

n

(t

1

, ..., t

n

)”





(P

k

n

) (W

M.

(t

1

, <w

n

>), ..., W

M

(t

n

, <w

n

>));

(2)

<w

n

>Spł

M

”



(A)”





(<w

n

>Spł

M

A);

(3)

<w

n

>Spł

M

”(A)



(B)”



(<w

n

>Spł

M.

A)



(<w

n

>Spł

M

B);

(4)

<w

n

>Spł

M

”(A)



(B)”



(<w

n

>Spł

M

A)



(<w

n

>Spł

M

B);

(5)

<w

n

>Spł

M.

”(A)



(B)”



[(<w

n

>Spł

M.

A)



(<w

n

>Spł

M

B)];

(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ł

M

A)

[ gdzie <w

n

>(w

i

/u) = <w

1

,...,w

i-1

,u,w

i+1

,...>]

11

(8)

<w

n

>Spł

M.

”



x

i

(A)”



Vu



U (<w

n

> (w

i

/u) Spł

M

A).

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ł

M

A)

[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ł

M

B)

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ł

M

A

 <w

n

>Spł

M

B

Korzystając z prawa [(A

B)B] A mamy, że: (<w

n

>Spł

M

A),

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ł

M

A)

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ł

M

A)

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

1

,...,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:

12

i=1.
Z def. dowodu formuła D

1

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

1

,...,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

1

,...,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ł

M

A)

z definicji prawdy

 V<w

n

>

(<w

n

>Spł

M

A)

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ł

M

A)

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ł

M

A)

z definicji prawdy

 V<w

n

>(<w

n

>Spł

M

A)

bo uniwersum jest zbiorem niepustym

 <w

n

>

(<w

n

>Spł

M

A) 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

n

(należącego do rozważanego języka) oraz dla dowolnych u

1

,...,u

n



U

zachodzi:



(P

i

n

)(u

1

,...,u

n

) wtedy i tylko wtedy, gdy



’(P

i

n

)(h(u

1

),...,h(u

n

));

(3)

dla każdego symbolu funkcyjnego f

i

n

oraz dla dowolnych u

1

,...,u

n



U zachodzi:

h(



(f

i

n

)(u

1

,...,u

n

))=



’(f

i

n

)(h(u

1

),...,h( u

n

));

(4)

dla dowolnej stałej nazwowej a

i

zachodzi: h(



(a

i

))=



’(a

i

).

13

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

1

6. Definicja pojęć tautologii i kontrtautologii KRP.

DEFINICJA 1(16)

(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(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

14

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

1

, A

2

,...,A

n

} I= B wtedy i tylko wtedy, gdy „A

1



[A

2



...(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

15

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