DWA PARADYGMATY METALOGIKI
JERZY POGONOWSKI
Zakład Logiki Stosowanej UAM
www.logic.amu.edu.pl
Wstęp
Niniejsza notatka zawiera nieco informacji wstępnych związanych z problematyką
wykładów 2 5 Metalogika dla Studium Doktoranckiego Instytutu Filozofii Uniwersy-
tetu Opolskiego. Spis treści wszystkich planowanych wykładów podano w pliku:
http://www.logic.amu.edu.pl/images/9/96/Metalogikaplan.pdf
Niniejszy tekst ma charakter kompilacyjny:
" W części pierwszej podajemy podstawowe definicje oraz informacje o wybra-
nych twierdzeniach dotyczących ogólnych operacji konsekwencji; informacje te
pochodzą z monografii W.A. Pogorzelskiego i P. Wojtylaka Completeness theory
for propositional logics. Birkh�user, Basel Boston Berlin, 2008.
" W części drugiej podajemy dowody I i II twierdzenia Lindstr�ma, w sformuło-
waniach pochodzących z: Ebbinghaus, H.D., Flum, J., Thomas, W. 1996. Ma-
thematical logic. Springer.
" " "
Dwa tytułowe paradygmaty to:
" Paradygmat algebraiczny. Rozważania dotyczące ogólnych operacji konsekwen-
cji (w sensie Tarskiego) oraz logik abstrakcyjnych (w sensie Suszki).
" Paradygmat semantyczny. Rozważania dotyczące soft model theory i logik abs-
trakcyjnych w sensie nadawanym temu terminowi przez: Mostowskiego, Lind-
str�ma, Barwise a i in.
W szczególności, chcielibyśmy zwrócić uwagę na pewną analogię między twier-
dzeniami charakteryzującymi logikę klasyczną w obu paradygmatach:
" twierdzeniami Pogorzelskiego-Wojtylaka (charakteryzującymi logiki progowe w
terminach C-definicji)
" twierdzeniami Lindstr�ma (ukazującymi, iż własność zwartości i własność L�-
wenheima-Skolema charakteryzują klasyczną logikę pierwszego rzędu).
" " "
1
1. Paradygmat algebraiczny
1.1. Operacje konsekwencji
Niech S = (S, F1, . . . , Fn) będzie algebrą ustalonego języka zdaniowego. Przez
regułę wnioskowania w S rozumiemy dowolną relację r ą" !(S) � S. Poprzedniki re-
lacji r nazywamy zbiorami przesłanek reguły r, a jej następniki wnioskami tej reguły.
Ogół reguł wnioskowania w S oznaczamy przez RS. Reguły z pustym zbiorem prze-
słanek nazywamy regułami aksjomatycznymi. Jeśli r jest regułą wnioskowania oraz
(X, ą) " r, to parę (X, ą) nazywamy sekwentem reguły r. Często używamy następu-
jącej notacji dla sekwentów danej reguły:
X
r : .
ą
Najczęściej ograniczamy się do reguł wnioskowania o skończonych zbiorach prze-
słanek. Przypominamy, że F in(X) oznacza rodzinę wszystkich skończonych podzbio-
rów zbioru X, a F in"(X) wszystkich skończonych niepustych podzbiorów zbioru X.
Ponadto, zwykle wszystkie sekwenty danej reguły mają ustaloną budowę składniową;
możemy wtedy regułę zapisywać w postaci schematycznej, jak np. w znanym przy-
padku reguły modus ponens (reguły odrywania), gdy rozważany język zawiera funktor
:
ą �, ą
MP : .
�
Każdą parę (R, X), gdzie R ą" RS, a X ą" S nazywamy systemem logiki zdań
(albo: logiką zdaniową). Jeśli L = (R, X) jest logiką zdaniową, to mówimy, że:
" R jest zbiorem reguł pierwotnych L
" X jest zbiorem aksjomatów L.
Odwzorowanie C : !(S) !(S) jest operacją konsekwencji (nad S) wtedy i
tylko wtedy, gdy dla wszystkich X, Y ą" S:
" X ą" C(X) (zwrotność)
" jeśli X ą" Y , to C(X) ą" C(Y ) (monotoniczność)
" C(C(X)) ą" C(X) (idempotencja).
Zamiast terminu operacja konsekwencji używamy także terminów: operator kon-
sekwencji lub operacja domknięcia (operator domknięcia).
Bezpośrednio z definicji operacji konsekwencji wynika, że każda taka operacja C
spełnia też warunek: C(C(X)) = C(X) dla wszystkich X ą" S.
Mówimy, że operacja domknięcia C jest:
2
" finitystyczna, gdy

C(X) = {C(Y ) : Y " F in(X)}
dla wszystkich X ą" S;
" zwarta, gdy dla każdego Y ą" S istnieje X " F in(Y ) taki, że:
jeśli C(Y ) = S, to C(X) = S;
" niesprzeczna, gdy C(") = S;

" zupełna (w sensie Posta), gdy C({ą}) = S dla każdego ą " C({"}).
/
Przez sprzeczną operację konsekwencji rozumiemy operację C taką, że C(X) = S
dla wszystkich X ą" S.
Ogół wszystkich operacji konsekwencji nad S jest częściowo uporządkowany przez
relację zdefiniowaną następująco:
" C1 C2 wtedy i tylko wtedy, gdy C1(X) ą" C2(X)
dla wszystkich X ą" S.
Następujące warunki są równoważne:
" C1 C2
" C2 ć% C1 = C2
" C1 ć% C2 = C2.
Dla dowolnej rodziny {Ct : t " T } operacji konsekwencji definiujemy operacje

Ct oraz Ct:
t"T t"T

" ( Ct)(X) = {Ct(X) : t " T }
t"T

" ( Ct)(X) = {C(X) : Ct C dla wszystkich t " T }
t"T
dla wszystkich X ą" S.
Wtedy zachodzą następujące fakty dotyczące uporządkowania ogółu konsekwencji
nad S przez relację :

" Ct oraz Ct są operacjami konsekwencji.
t"T t"T

" ( Ct)(X) = {Y : X ą" Y = Ct(Y ) dla wszystkich t " T }.
t"T
3
" Rodzina wszystkich operacji konsekwencji nad S jest kratą zupełną z porząd-
kiem kratowym oraz kresami określonymi wzorami:

inf{Ct : t " T } = Ct, sup{Ct : t " T } = Ct.
t"T t"T
" Elementem największym w tej kracie jest konsekwencja sprzeczna. Elementem
najmniejszym jest operacja Id określona wzorem Id(X) = X dla wszystkich
X ą" S.
" Jeśli wszystkie operacje ze zbioru {Ct : t " T } są finitystyczne, to operacja

Ct też jest finitystyczna.
t"T
1.2. Systemy domknięć
Niech C będzie operacją konsekwencji nad S. Mówimy, że zbiór formuł X ą" S
jest C-domknięty, gdy X = C(X), czyli gdy X jest punktem stałym operacji C.
Rodzina wszystkich zbiorów C-domkniętych jest jest domknięta na iloczyny, tj.:

C( {C(Xt) : t " T }) = {C(Xt) : t " T }.
Rodzina ta nie jest jednak domknięta na sumy. Przy podanych założeniach zachodzi
następujący fakt:
" Jeśli C jest finitystyczna, a {Xt : t " T } jest ą"-łańcuchem zbiorów (formuł),
to:

C( {C(Xt) : t " T }) = {C(Xt) : t " T }.
Rodzina wszystkich zbiorów C-domkniętych jest kratą zupełną (z inkluzją jako po-
rządkiem kratowym), z elementem najmniejszym C(") oraz elementem największym
S. Kresy rodzin {Xt : t " T } zbiorów C-domkniętych wyznaczone są wzorami:

inf{Xt : t " T } = {Xt : t " T },

sup{Xt : t " T } = C( {Xt : t " T }).
Przypominamy, że rodzina zbiorów X jest systemem domknięć, jeśli iloczyn każ-
dej podrodziny rodziny X jest elementem X .
Widzimy więc, że rodzina wszystkich zbiorów C-domkniętych jest systemem do-
mknięć, dla dowolnej operacji konsekwencji C. Zachodzi także implikacja odwrotna:
dowolny system domknięć wyznacza pewną operację konsekwencji. Jeśli mianowicie
X jest systemem domknięć (rodziną podzbiorów zbioru S, domkniętą na iloczyny), to
definiujemy:

C(X) = {Y " X : X ą" Y },
dla dowolnego X ą" S. Można sprawdzić, że tak określona funkcja C jest operacją
konsekwencji.
4
1.3. Zbiory niesprzeczne, maksymalne, aksjomatyzowalne i nieza-
leżne
Powiemy, że zbiór X ą" S jest:
" C-niesprzeczny, gdy C(X) = S;

" C-maksymalny, gdy X jest C-niesprzeczny oraz C(X *" {ą}) = S dla każdego
ą " C(X);
/
" C-aksjomatyzowalny, gdy istnieje skończony zbiór Y taki, że C(X) = C(Y );
" C-niezależny, gdy ą " C(X - {ą}), dla każdego ą " X.
/
Oto niektóre własności tych pojęć:
" Jeśli X jest zbiorem C-maksymalnym, to C(X) jest elementem ą"-maksymalnym
w rodzinie wszystkich zbiorów C-domkniętych i C-niesprzecznych.
" Jeśli C jest finitystyczna, to żaden nieskończony zbiór C-niezależny nie jest C-
aksjomatyzowalny.
" Jeśli istnieje zbiór, który nie jest C-aksjomatyzowalny, to to rodzina wszystkich
C-aksjomatyzowalnych i C-domkniętych zbiorów jest nieskończona.
" Jeśli X jest C-niezależny, to dla dowolnych Y, Z ą" X: Y ą" Z wtedy i tylko
wtedy, gdy C(Y ) ą" C(Z).
Konsekwencją tych własności są m.in. następujące ustalenia dotyczące mocy pew-
nych rodzin zbiorów dla finitystycznej operacji konsekwencji C nad przeliczalnym
językiem S, dla której istnieje nieskończony zbiór C-niezależny:
" Istnieje kontinuum zbiorów o postaci C(X).
" Istnieje przeliczalnie wiele zbiorów o postaci C(X), gdzie X jest zbiorem skoń-
czonym.
" Istnieje kontinuum zbiorów o postaci C(X), gdzie C(X) nie jest C-aksjomaty-
zowalny.
1.4. Operacje konsekwencji wyznaczone przez reguły wnioskowania
Oprócz rozważań dotyczących operacji konsekwencji pojmowanych całkiem ogól-
nie, w myśl podanej uprzednio definicji, interesujące i ważne jest badanie operacji
konsekwencji wyznaczonej przez zespół reguł wnioskowania (oraz, ewentualnie, ze-
staw aksjomatów). W praktyce, gdy mówimy o wnioskach uzyskanych z jakiegoś
zbioru przesłanek, zazwyczaj odwołujemy się do metod, za pomocą których wnioski
te można uzyskać: zazwyczaj są to po prostu stosowne reguły wnioskowania. Ponadto,
5
jak zobaczymy za chwilę, każda operacja konsekwencji może zostać przedstawiona
jako operacja konsekwencji generowana poprzez pewien zestaw reguł wnioskowania
(oraz, ewentualnie, zestaw aksjomatów).
Niech Cld(R, X) oznacza, że zbiór formuł X jest domknięty na wszystkie reguły
ze zbioru R: Cld(R, X) wtedy i tylko wtedy, gdy
("r " R)("P ą" S)("ą " S)(((P, ą) " r '" P ą" X) �! ą " X).
UWAGA. Proszę odróżniać symbol implikacji w KRZ od używanego tu metajęzy-
kowego symbolu �!. Symbolu '" również używamy tu metajęzykowo.
Dla dowolnych: X ą" S oraz R ą" RS niech:

CR(X) = {Y ą" S : X ą" Y oraz Cld(R, Y )}.
Wtedy CR(X) jest ą"-najmniejszym zbiorem zawierającym X i domkniętym na
wszystkie reguły z R. Zachodzą następujące fakty:
" Dla dowolnych: X ą" S oraz R ą" RS: CR(X) = X wtedy i tylko wtedy, gdy
Cld(R, X).
" Załóżmy, że rozważamy jedynie reguły o skończonych zbiorach przesłanek. Wte-
dy: ą " CR(X) wtedy i tylko wtedy, gdy istnieje formalny dowód ą na gruncie
systemu o założeniach X i regułach wnioskowania R, czyli gdy istnieje skoń-
czony ciąg formuł ą1, . . . , ąn taki, że ą jest identyczna z ąn oraz dla wszystkich
i n: albo ąi " X, albo (P, ąi) " r dla pewnych r " R oraz P ą" S.
Każda para o postaci (R, X), gdzie R ą" RS pozwala określić pewną operację
CR,X konsekwencji nad S:
CR,X(Y ) = CR(X *" Y ).
Operacja CR,X jest finitystyczna, jeśli zbiór X jest pusty. Dla X = " będziemy
zamiast CR,X pisali po prostu CR.
Każda finitystyczna operacja konsekwencji może zostać przedstawiona w postaci
CR,X. Zachodzi mianowicie następujący fakt:
" Dla każdej finitystycznej operacji konsekwencji C istnieją: zbiór X ą" S oraz
zbiór R ą" RS takie, że C = CR,X.
Również dowolne operacje konsekwencji (bez zakładania skończoności zbiorów
ich przesłanek) można reprezentować przez reguły:
" Dla każdej operacji konsekwencji C istnieje zbiór R ą" RS taki, że C = CR.
Jeśli C = CR,X, to parę (R, X) nazywamy bazą dla C. Zauważmy, że:
" dana operacja konsekwencji może mieć wiele różnych baz;
" każda para (R, X) jednoznacznie wyznacza operację konsekwencji CR,X.
6
Operacje konsekwencji wyznaczone przez reguły możemy też definiować induk-
cyjnie. Niech R będzie dowolną rodziną reguł wnioskowania w S. Przez operację
konsekwencji w S wyznaczoną przez R rozumiemy każdą funkcję C : 2S 2S,
zdefiniowaną indukcyjnie następującymi warunkami dla dowolnego zbioru formuł X:
0
" (1) CR(X) = X
k+1
k k
" (2) CR (X) = CR(X) *" {ą " S : ("r " R)("P ą" CR(X)) (P, ą) " r}

k
" (3) CR(X) = {CR(X) : k " �}.
Wyrażenie ą " CR(X) czytamy: ą jest wyprowadzalna z X za pomocą reguł
należących do R. Ta notacja jest zgodna z wprowadzoną poprzednio.
1.5. Reguły dopuszczalne i reguły wyprowadzalne
Zbiór Adm(R, X) wszystkich reguł dopuszczalnych ze względu na X i R definiu-
jemy następująco:
r " Adm(R, X) wtedy i tylko wtedy, gdy dla każdego P ą" S oraz każdej ą " S:
jeśli (P, ą) " r i P ą" CR(X), to ą " CR(X).
Zbiór Der(R, X) wszystkich reguł wyprowadzalnych ze względu na X i R defi-
niujemy następująco:
r " Der(R, X) wtedy i tylko wtedy, gdy dla każdego P ą" S oraz każdej ą " S:
jeśli (P, ą) " r, to ą " CR(X *" P ).
Zachodzą następujące fakty, dla każdego R ą" RS oraz X ą" S:
" r " Adm(R, X) wtedy i tylko wtedy, gdy Cld({r}, CR(X));
" r " Der(R, X) wtedy i tylko wtedy, gdy Cld({r}, CR(X *" Y )), dla wszystkich
Y ą" S.
Możemy zatem stwierdzić, że:
" reguła dopuszczalna ze względu na R i X nie wyprowadza poza formuły dowo-
dliwe na podstawie (R, X);
" reguła r jest wyprowadzalna z R oraz X wtedy i tylko wtedy, gdy r jest dopusz-
czalna w każdym nadsystemie systemu (R, X), czyli

Der(R, X) = {Adm(R, X *" Y ) : Y ą" S}.
Stąd, każda reguła wyprowadzalna z (R, X) jest też dopuszczalna dla (R, X).
Inkluzja odwrotna nie zachodzi.
Mówimy, że para (R, X) jest podsystemem (R1, X1) (i piszemy wtedy (R, X)
(R1, X1)) wtedy i tylko wtedy, gdy:
7
" X ą" CR (X1) oraz
1
" R ą" Der(R1, X1).
Jeśli (R, X) (R1, X1), to:
" Der(R, X) ą" Der(R1, X1)
" CR(X) ą" CR (X1).
1
Widzimy zatem, że formuły i reguły wyprowadzalne w podsystemie danego sys-
temu, są również wyprowadzalne w tym systemie. Z faktu, że (R, X) (R1, X1)
nie wynika jednak ani inkluzja Adm(R, X) ą" Adm(R1, X1), ani inkluzja do niej od-
wrotna.
Jeśli X oraz X1 są niepuste, to: (R, X) (R1, X1) wtedy i tylko wtedy, gdy
Der(R, X) ą" Der(R1, X1).
Relacja jest zwrotna i przechodnia. Wyznacza zatem relację równoważności
H"= )"( )-1. Jeśli (R, X) H" (R1, X1), to:
" Der(R, X) = Der(R1, X1);
" CR(X) = CR (X1);
1
" Adm(R, X) = Adm(R1, X1).
Jeśli X oraz X1 są niepuste, to (R, X) H" (R1, X1) wtedy i tylko wtedy, gdy
Der(R, X) = Der(R1, X1).
Zachodzą następujące fakty:
" (R, X) H" (Der(R, X), X)
" (Der(R, X), X) H" (R, CR(X))
" (R, CR(X)) H" (Der(R, X), CR(X))
" (Der(R, X), CR(X)) (Adm(R, X), X)
" (Adm(R, X), X) H" (Adm(R, X), CX(X)).
Będziemy używać symbolu z" dla -( )-1.
Zachodzą następujące fakty, dla dowolnych X, X1 ą" S oraz R, R1 ą" RS:
" (R, X) (R1, X1) wtedy i tylko wtedy, gdy CR,X CR ,X1;
1
" (R, X) H" (R1, X1) wtedy i tylko wtedy, gdy CR,X = CR ,X1.
1
W świetle powyższego (oraz pamiętając o tym, że każda operacja konsekwencji
może zostać przedstawiona w postaci operacji konsekwencji wyznaczonej przez reguły
wnioskowania), porządek kratowy w kracie wszystkich operacji konsekwencji może
być uważany za generowany poprzez porządek .
Pojęcia: reguły wyprowadzalnej i reguły dopuszczalnej (sformułowane dla syste-
mów o postaci (R, X)) mogą też (również na mocy powyższego) zostać wyrażone w
terminach operacji konsekwencji:
8
" r " DER(C) wtedy i tylko wtedy, gdy ą " C(P ), dla wszystkich (P, ą) " r;
" r " ADM(C) wtedy i tylko wtedy, gdy: jeśli P ą" C("), to ą " C("), dla
wszystkich (P, ą) " r.
Wśród wszystkich systemów, generujących daną operację konsekwencji rolę wy-
różnioną pełni system (DER(C), C(")), nazywany systemem domkniętym logiki zda-
niowej.
Dla porządku kratowego definiujemy kresy rodzin {(Rt, Xt) : t " T }:

" (Rt, Xt) = ( Der(Rt, Xt), CR (Xt));
t
t"T t"T t"T

" (Rt, Xt) = ( Rt, Xt).
t"T t"T t"T

Wtedy (Rt, Xt) jest systemem domkniętym, czyli:
t"T

" Der( (Rt, Xt)) = Der(Rt, Xt);
t"T t"T

" C( (Rt, Xt)) = CR (Xt).
t
t"T t"T
1.6. Reguły strukturalne
Jak pamiętamy z elementarnego kursu logiki, reguła podstawiania (formuł za zmien-
ne zdaniowe w KRZ) ma bardzo szczególny charakter: odwołujemy się w niej do pew-
nej (algebraicznej) operacji, inaczej niż w przypadku reguł w rodzaju np. modus po-
nens, gdzie odwołujemy się jedynie do własności syntaktycznych (kształtu przesłanek
oraz wniosku). Obecnie poznamy pewną własność reguł wnioskowania, związaną z
podstawieniami.
Przypominamy, że At oznacza zbiór formuł atomowych (zmiennych zdaniowych)
rozważanego języka. Pamiętamy, że każde podstawienie, czyli odwzorowanie e : At
S może w sposób jednoznaczny zostać rozszerzone do endomorfizmu he : S S. Z
tego powodu, wynik (jednoczesnego) podstawienia w formule ą wyznaczonego przez
wartości e(pi) = łi, dla wszystkich zmiennych zdaniowych p1, . . . , pn występujących
w ą może być poprawnie oznaczany przez ą[p1/ł1, . . . , pn/łn]. Rozumie się przez
to, że he(ą) = ą[p1/ł1, . . . , pn/łn].
Możemy teraz podać precyzyjną definicję reguły podstawiania r" w S:
" ({ą}, �) " r" wtedy i tylko wtedy, gdy � = he(ą), dla pewnego podstawienia
e : At S.
Reguła r" określona może także być poprzez schemat:
ą
" r" : , dla wszystkich ą " S oraz wszystkich e : At S.
he(ą)
9
Operacja konsekwencji wyznaczona przez regułę podstawiania jest oznaczana przez
Sb. Tak więc, dla każdego X ą" S:
Sb(X) = C{r }(X) = {ą : ą " he(X) dla pewnego e : At S}.
"
Powiemy, że reguła r " RS jest strukturalna, co zapisujemy r " Struct, wtedy i
tylko wtedy, gdy:
" jeśli (P, ą) " r, to (he(P ), he(ą)) " r, dla wszystkich e : At S.
Zwykle rozważane reguły KRZ są strukturalne, oprócz reguły podstawiania.
Precyzyjna definicja reguł strukturalnych jest prosta, jak widzieliśmy. Trudniej od-
dać w języku potocznym tzw. intuicje związane z tymi regułami. W.A. Pogorzelski w
Elementarnym słowniku logiki formalnej (s. 416) pisze:
Bardzo ogólnikowo można przedstawić strukturalność reguł jako stoso-
walność do wszelkich przesłanek o ustalonej strukturze wyznaczonej na
ogół ich funktorem głównym.
Powiemy, że system (R, X) (gdzie R ą" RS, X ą" S) jest niezmienniczy (co
zapisujemy: (R, X) " Inv), jeśli:
" R ą" Struct oraz X = Sb(X).
Jeśli R ą" Struct, to (R *" {r"}, X) nazywamy systemem podstawieniowym.
Powiemy, że sekwent (P, ą) jest sekwentem bazowym reguły r wtedy i tylko wtedy,
gdy:
r = {(he(P ), he(ą)) : dla wszystkich podstawień e}.
Reguły, które posiadają sekwent bazowy, nazywane są regułami standardowymi.
Każda reguła standardowa r może zostać przedstawiona w postaci:

r = {r : r ą" r oraz r jest standardowa}.
Każda reguła standardowa jest strukturalna (lecz nie na odwrót). Przykładem reguły
strukturalnej, która nie jest standardowa jest reguła rX, dla każdego X ą" S:
" (P, ą) " rX wtedy i tylko wtedy, gdy: jeśli he(P ) ą" X, to he(ą) " X, dla
wszystkich podstawień e.
Z wielu względów warto rozważać pojęcie strukturalności zrelatywizowane do
pewnego zbioru � ą" S. Definiujemy:
ą
" r"|� : , dla wszystkich ą " S oraz e : At �.
he(ą)
Dalej, definiujemy: Sb�(X) = C{r }|�(X). Zachodzą następujące fakty:
"
" r"|S = r"
" SbS = Sb
10
" r"|" = "
" Sb"(X) = X, dla wszystkich X ą" S
" Sb�(X *" Y ) = Sb�(X) *" Sb�(Y ), dla wszystkich X, Y ą" S.
Mówimy, że reguła r jest �-strukturalna (co zapisujemy: r " Struct(�)), gdy:
" jeśli (P, ą) " r, to (he(P ), he(ą)) " r, dla wszystkich e : At �.
Mówimy, że system (R, X) jest �-niezmienniczy ((R, X) " Inv(�)) wtedy i tylko
wtedy, gdy:
" R ą" Struct oraz X = Sb�(X).
Zachodzą następujące fakty:
" (R, X) " Struct wtedy i tylko wtedy, gdy (R, X) " Struct(S).
" (R, X) " Inv wtedy i tylko wtedy, gdy (R, X) " Inv(S).
" Wszystkie reguły (nad S) są "-strukturalne.
" (R, X) " Inv(") dla wszystkich R ą" RS oraz X ą" S.
" Dla każdych �1, �2: jeśli �1 ą" �2, to Struct(�2) ą" Struct(�1).
" Dla każdych �1, �2: jeśli �1 ą" �2, to Inv(�2) ą" Inv(�1).
" Dla każdego � ą" S: Struct ą" Struct(�) ą" RS.
" Dla każdego � ą" S: Inv ą" Inv(�) ą" Inv(").
" Jeśli R ą" Struct(�) oraz X ą" S, to he(CR(X)) ą" CR(he(X)), dla wszystkich
e : At �.
" Jeśli R ą" Struct(�) oraz X, Y ą" S, to
he(CR(Sb�(X) *" Y )) ą" CR(Sb�(X) *" he(Y )), dla wszystkich e : At �.
Ostatni z powyższych faktów można wykorzystać dla redukcji reguły podstawiania
do zbioru aksjomatów:
" Jeśli R ą" Struct(�) oraz X ą" S, to:
CR*"{r |�}(X) = CR(Sb�(X)).
"
Dowód tego twierdzenia podaje monografia Pogorzelskiego i Wojtylaka (s. 29).
Niektóre konsekwencje tego twierdzenia to:
" Dla każdych R ą" Struct(�) oraz X ą" S:
Sb�(CR(X)) ą" CR(Sb�(X)).
11
" Jeśli (R, X) jest �-niezmienniczy, to jest domknięty na regułę r"|�.
" r"|� " Adm(R, Sb�(X)).
" Jeśli R ą" Struct(�), r " RS oraz X ą" S, to: r " Der(R *" {r"|�}, X) wtedy i
tylko wtedy, gdy r " Adm(R, Sb�(X) *" Sb�(Y )), dla wszystkich Y ą" S.
Zachodzi następujący fakt dotyczący reguły podstawiania:
" Dla wszystkich R ą" Struct oraz X ą" S:
1) r" " Adm(R, Sb(X))
2) r" " Der(R, Sb(X)), jeśli " = CR(X) = S.
/
Jeśli system (R, X) jest niezmienniczy, to dodanie reguły podstawiania do zbioru
R nie zmienia zbioru formuł wyprowadzalnych w (R, X). Systemy (R, X) oraz (R *"
{r"}, X) nie są jednak równoważne. Systemy logiczne przedstawiać możemy w dwóch,
nierównoważnych wersjach:
" niezmienniczej (R, Sb(X)), gdzie R ą" Struct
" podstawieniowej (R *" {r"}, X).
Pojęcia: �-strukturalności oraz �-niezmienniczości mogą zostać odniesione do ope-
racji konsekwencji:
" C jest �-strukturalna (symbolicznie: C " STRUCT(�)), jeśli
he(C(X)) ą" C(he(X)), dla wszystkich X ą" S oraz e : At �
" C jest strukturalna (symbolicznie: C " STRUCT), jeśli
he(C(X)) ą" C(he(X)), dla wszystkich X ą" S oraz e : At S.
Każdy �-niezmienniczy system (R, X) wyznacza �-strukturalną operację konse-
kwencji CR,X. Ponadto, każda �-strukturalna operacja konsekwencji jest generowana
przez pewien system �-niezmienniczy.
Rodzina wszystkich strukturalnych (�-strukturalnych) operacji konsekwencji two-
rzy podkratę zupełną kraty wszystkich operacji konsekwencji nad S, gdzie kresami
dowolnej rodziny {Ct : t " T } strukturalnych (�-strukturalnych) operacji konsekwen-

cji są: Ct oraz Ct.
t"T t"T
1.7. Operacje konsekwencji a relacje konsekwencji
Ogólna (finitystyczna) relacja konsekwencji ą" 2S � S w S określona jest dla
dowolnych X, Y ą" S oraz ą " S przez warunki:
" ( 1) X ą dla każdego ą " X
" ( 2) jeśli X ą i X ą" Y , to Y ą
12
" ( 3) jeśli dla każdej � " Y X � oraz Y ą, to X ą
" ( 4) jeśli X ą, to istnieje Y taki, że: Y " F in(X) oraz Y ą.
Operacje i relacje konsekwencji są wzajemnie przez siebie definiowalne:
( ) X C ą wtedy i tylko wtedy, gdy ą " C (X)
(tj. dla każdej istnieje C taka, że ( ), a także dla każdej C istnieje C taka, że
( )).
Powyższa zależność ( ) może być zapisana także w takiej postaci:
" Jeśli C jest operacją konsekwencji, to definiujemy relację konsekwencji C:
X C ą wtedy i tylko wtedy, gdy ą " C(X);
" Jeśli jest relacją konsekwencji, to definiujemy operację konsekwencji C :
ą " C (X) wtedy i tylko wtedy, gdy X ą.
Twierdzenia dotyczące operacji konsekwencji przekładają się zatem na twierdzenia
dotyczące relacji konsekwencji i na odwrót.
1.8. Kilka ważnych przykładów
Zwykle w charakterze ważnych przykładów logik zdaniowych rozważa się logiki
następujące:
" logikę intuicjonistyczną
" logikę klasyczną
" logiki modalne
" logiki wielowartościowe (A
ukasiewicza).
Zobaczmy zatem, jak powyższe systemy logiczne opisywane są w terminach ope-
racji konsekwencji.
LOGIKA INTUICJONISTYCZNA.
Językiem tej logiki jest standardowy język S2 = (S2, , (", '", Ź). Niech Aint
będzie następującym zbiorem aksjomatów:
" (1) p (q p)
" (2) (p (p q)) (p q)
" (3) (p q) ((q s) (p s))
" (4) p (p (" q)
13
" (5) q (p (" q)
" (6) (p s) ((q s) ((p (" q) s))
" (7) (p '" q) p
" (8) (p '" q) q
" (9) (p q) ((p r) (p (q '" r)))
" (10) p (Źp p)
" (11) (p Źp) Źp.
oraz niech R0" = {r0, r"}, gdzie r0 jest regułą modus ponens, a r" regułą podstawiania
w S2. Wtedy (R0", Aint) jest systemem intuicjonistycznej logiki zdaniowej. W wersji
niezmienniczej logika intuicjonistyczna jest systemem (R0, Sb(Aint)), gdzie R0 =
{r0}. Jak pamiętamy, na podstawie własności operacji Sb oraz reguły podstawiania:
CR (Aint) = CR (Sb(Aint)).
0" 0
Niech Cint będzie operacją konsekwencji generowaną przez system (R0, Sb(Aint)).
Mamy zatem dla każdego X ą" S2:
Cint(X) = CR (Sb(Aint) *" X).
0
W systemie tym zachodzi twierdzenie o dedukcji:
" Dla dowolnych X ą" S2 oraz ą, � " S2:
� " Cint(X *" {ą}) wtedy i tylko wtedy, gdy (ą �) " Cint(X).
Twierdzenie o dedukcji charakteryzuje implikację. Pozostałe funktory logiki in-
tuicjonistycznej są charakteryzowane następująco (formuła ą a" � jest skrótem dla
formuły (ą �) '" (� ą)):
" Cint(X *" {ą '" �}) = Cint(X *" {ą, �})
" Cint(X *" {ą (" �}) = Cint(X *" {ą}) )" Cint(X *" {�})
" (ą a" �) " Cint(X) wtedy i tylko wtedy, gdy Cint(X *"{ą}) = Cint(X *"{�})
" Źą " Cint(X) wtedy i tylko wtedy, gdy Cint(X *" {ą}) = S2.
Otrzymujemy stąd, że w logice intuicjonistycznej wyprowadzalna jest reguła do-
dawania koniunkcji ra:
ą,�
ra : , dla wszystkich ą, � " S2.
ą'"�
Zachodzą także następujące fakty:
" ą � " Cint(X) wtedy i tylko wtedy, gdy Cint(X *" {�}) ą" Cint(X *" {ą}).
" ą (" � " Cint(X) wtedy i tylko wtedy, gdy Cint(X *" {ą}) )" Cint(X *" {�}) ą"
Cint(X).
14
" ą '" � " Cint(X) wtedy i tylko wtedy, gdy Cint(X *" {ą}) *" Cint(X *" {�}) ą"
Cint(X).
" Źą " Cint(X) wtedy i tylko wtedy, gdy S2 ą" Cint(X *" {ą}).
Nadto, Cint jest najmniejszą operacją konsekwencji nad S2, która spełnia powyż-
sze cztery warunki.
Będziemy odwoływać się też (ale nie w tej notce) do pewnych fragmentów logiki
intuicjonistycznej (logiki pozytywnej Hilberta, czysto implikacyjnej logiki Hilberta).
LOGIKA KLASYCZNA.
Niech A2 będzie zbiorem aksjomatów logiki intuicjonistycznej powiększonym o
aksjomat ŹŹp p. Przez klasyczną logikę zdaniową rozumiemy system (R0, Sb(A2))
(lub: (R0", A2)). Definiujemy operację konsekwencji Cn2:
Cn2(X) = CR (Sb(A2) *" X).
0
Wprost z definicji zbiorów aksjomatów dla logiki intuicjonistycznej i logiki kla-
sycznej (oraz z monotoniczności operacji konsekwencji) widać, że CR (Aint) ą"
0"
CR (A2).
0"
Zachodzą następujące fakty:
" (ą �) " Cn2(X) wtedy i tylko wtedy, gdy � " Cn2(X *" {ą}).
" Cn2(X *" {ą '" �}) = Cn2(X *" {ą, �}.
" Cn2(X *" {ą (" �}) = Cn2(X *" {ą} )" Cn2(X *" {�}.
" Źą " Cn2(X) wtedy i tylko wtedy, gdy Cn2(X *" {ą}) = S2.
" ą " Cn2(X) wtedy i tylko wtedy, gdy Cn2(X *" {Źą}) = S2.
Ponieważ, jak można wykazać:
" operacja konsekwencji wyznaczona przez (R0, Sb(A2)) jest największą struk-
turalną oraz niesprzeczną operacją konsekwencji spełniającą powyższe pięć wa-
runków;
" (R0, Sb(A2)) jest najmniejszym systemem spełniającym powyższe pięć warun-
ków,
więc warunki te jednoznacznie określają klasyczną logikę zdaniową, czyli następujące
warunki są równoważne:
" Niesprzeczny niezmienniczy system (R, A) spełnia powyższe pięć warunków.
" (R, A) H" (R0, Sb(A2)).
LOGIKA MODALNA S5.
Niech AS5 będzie następującym systemem aksjomatów:
15
" (1) (p (q s)) ((p q) (p s))
" (2) (s t) (q (s t))
" (3) (p '" q) p
" (4) (p '" q) p
" (5) (p q) ((p s) (p (q '" s)))
" (6) p (p (" q)
" (7) q (p (" q)
" (8) (p q) ((q s) ((p (" q) s))
" (9) Ź(s t) ((s t) q)
" (10) (p '" Źp) q
" (11) (p Źp) Źp
" (12) (p '" Ź(p '" q)) Źq
" (13) (p ŹŹp) '" (ŹŹp p).
System modalny S5 jest wyznaczone przez te aksjomaty oraz reguły:
" r0 modus ponens
" r" podstawiania
" ra dodawania koniunkcji.
Oznaczamy: R0a" = {r0, ra, r"} oraz R0a = {r0, ra}.
Twierdzenie o dedukcji dla systemu S5 może zastać zapisane w następujących po-
staciach:
" Jeśli X ą" {� � : �, � " S2}, to dla wszystkich ą, � " S2:
Jeśli � " CR (Sb(AS5) *" X *" {ą}), to (ą �) " CR (Sb(AS5) *" X).
0a 0a
" Dla każdego X ą" S2 oraz ą " S2: ą " CR (Sb(AS5) *" X) wtedy i tylko
0a
wtedy, gdy ((�1 '" �2 '" . . . '" �k) ą) " CR (Sb(AS5)) dla pewnych
0a
�1, �2, . . . , �k " X.
Zachodzą następujące fakty, charakteryzujące funktory logiki S5 w terminach ope-
racji konsekwencji tej logiki:
" Źą " CR (Sb(AS5) *" X) wtedy i tylko wtedy, gdy CR (Sb(AS5) *" X *"
0a 0a
{ą}) = S2.
" ą " CR (Sb(AS5) *" X) wtedy i tylko wtedy, gdy CR (Sb(AS5) *" X *"
0a 0a
{Źą}) = S2.
16
" CR (Sb(AS5) *" X *" {ą '" �}) = CR (Sb(AS5) *" X *" {ą, �}).
0a 0a
" CR (Sb(AS5)*"X *"{ą("�}) = CR (Sb(AS5)*"X *"{ą}))"CR (Sb(AS5)*"
0a 0a 0a
X *" {�}).
Wprowadzamy oznaczenie: ą dla (ą ą) ą. Wtedy ( ą a" (� �)
ą) " CR (AS5), dla wszystkich ą, � " S2.
0a"
Zachodzą następujące fakty:
" p p
" (p q) (p q)
" Ź p Ź p
" ( p (" q) (p (" q)
" ( p '" q) (p '" q).
Definiujemy zbiór formuł -domkniętych S : ą " S wtedy i tylko wtedy, gdy
ą ą " CR (AS5). Wtedy: ą " S wtedy i tylko wtedy, gdy ą a" ą "
0a"
CR (AS5). Zachodzą także następujące fakty:
0a"
" (ą �) " S .
" Jeśli ą " S , to Źą " S .
" Jeśli ą, � " S , to ą '" �, ą (" � " S .
" CR (AS5) ą" S .
0a"
Wreszcie, zachodzą także następujące fakty:
" Dla wszystkich X ą" S oraz ą, � " S2:
� " CR (Sb(AS5) *" X *" {ą}) wtedy i tylko wtedy, gdy
0a
(ą �) " CR (Sb(AS5) *" X).
0a
" ą " CR (AS5 *" {ą}) dla wszystkich ą " S2.
0a"
Ponieważ � " S dla dowolnej formuły atomowej �, więc S2 -S = ". Tak więc,
/
reguła:
ą
r : ,
ą
gdzie ą " S2, nie jest wyprowadzalna w (R0a, Sb(AS5)). Jest ona jednak dopusz-
czalna w (R0a, Sb(AS5)), czyli:
" jeśli ą " CR (Sb(AS5)), to ą " CR (Sb(AS5))
0a 0a
17
Jak widzieliśmy, reguła r jest wyprowadzalna w (R0a", AS5).
Powyższe przedstawienie systemu modalnego S5 pochodzi od Pogorzelskiego i
Wojtylaka. Pod nazwą S5 występują także inne systemy modalne.
LOGIKI WIELOWARTOŚCIOWE A
UKASIEWICZA.
Systemem aksjomatów (nieskończenie) wielowartościowej logiki A
ukasiewicza jest
zbiór A
" następujących formuł:
" (1) (p q) ((q s) (p s))
" (2) p (q p)
" (3) (p (p q)) (p q)
" (4) (p '" q) p
" (5) (p '" q) q
" (6) (p q) ((p r) (p (q '" r)))
" (7) p (p (" q)
" (8) q (p (" q)
" (9) (p s) ((q s) ((p (" q) s))
" (10) (Źp Źq) (q p)
Przez "-wartościową logikę A
ukasiewicza rozumiemy system (R0", A
") lub, w
wersji niezmienniczej: (R0, Sb(A
")).
Wprowadz
my oznaczenia:
" p 0 q dla q,
" p k+1 q dla p (p k q).
Skończenie wielowartościowe logiki A
ukasiewicza to systemy (R0", A
n), dla n
2, gdzie zbiór A
n zawiera powyższe aksjomaty oraz dwa aksjomaty następującej po-
staci:
" (11) (p n q) (p n-1 q)
" (12) (p a" (p k Źp)) n-1 q
dla każdej k n takiej, że k + 2 nie dzieli bez reszty n - 1.
Zachodzi następujący fakt:

CR (A
") = {CR (A
n) : n 2}.
0" 0"
Zachodzi następująca wersja twierdzenia o dedukcji:
18
" � " CR (Sb(A
n) *" X *" {ą}) wtedy i tylko wtedy, gdy
0
ą n-1 � " CR (Sb(A
n) *" X)
0
" � " CR (Sb(A
") *" X *" {ą}) wtedy i tylko wtedy, gdy istnieje n taka, że
0
ą n � " CR (Sb(A
") *" X).
0
W konsekwencji, dla dowolnych X ą" S2 oraz ą " S2:
" CR (Sb(A
n) *" X *" {ą}) = S2 wtedy i tylko wtedy, gdy
0
ą n-2 Źą " CR (Sb(A
n) *" X)
0
" CR (Sb(A
") *" X *" {ą}) = S2 wtedy i tylko wtedy, gdy istnieje n taka, że
0
ą n Źą " CR (Sb(A
") *" X).
0
1.9. Matryce logiczne
Określimy teraz semantykę dla rachunków zdaniowych. Pojęciem podstawowym
będzie pojęcie matrycy logicznej. Wszystkie pojęcia algebraiczne potrzebne do okre-
ślenia zarówno tego pojęcia, jak i podstawowych własności matryc logicznych podane
zostały w Preliminariach matematycznych.
1.9.1. Algebry prauporządkowane
Algebrą prauporządkowaną (w skrócie: prp-algebrą) nazywamy każdy układ o
postaci (A, ), gdzie A jest algebrą, a praporządkiem (relacją zwrotną i przechod-
nią) w A, czyli w uniwersum algebry A. Jeśli operacje samej algebry A wyznaczają
jakiś porządek w A (np. porządek kratowy), to nie musi on być ani tożsamy, ani jak-
kolwiek związany z praporządkiem .
Niech S będzie algebrą języka zdaniowego z nieskończonym zbiorem At zmien-
nych zdaniowych oraz zbiorem wszystkich formuł S i niech (A, ) będzie prp-algebrą
podobną do S. Definiujemy operację konsekwencji wyznaczoną przez A = (A, ),
-

czyli funkcję A : !(S) !(S):
-

" ą " A (X) wtedy i tylko wtedy, gdy hv(ą) " F(hv(X)), dla każdego podsta-
wienia v : At A.
-

Zatem ą " A (X) wtedy i tylko wtedy, gdy hv(ą) należy do filtru wyznaczonego
(generowanego) przez hv(X), dla każdego podstawienia v : At A.
UWAGA. Posługujemy się tu (i dalej) pojęciem filtru w prp-algebrach. Przypominamy
też, że F(X) jest najmniejszym filtrem zawierającym zbiór X.
Bezpośrednio z tej definicji wynika, że:
-

" ą " A (X) wtedy i tylko wtedy, gdy hv(ą) " F , dla każdego filtru w prp-
algebrze A = (A, ) oraz każdego podstawienia v : At A.
19
-

Operacja A istotnie jest operacją konsekwencji, mamy bowiem dla wszystkich
X ą" S:
-

" X ą" A (X).
- -

" Jeśli X ą" Y , to A (X) ą" A (Y ).
- - -

" A ( A (X)) ą" A (X).
- -

" he( A (X)) ą" A (he(X)) dla wszystkich e : At A.
-

Ostatni z powyższych warunków implikuje, że A jest strukturalną operacją konse-
-

kwencji. A nie musi jednak być finitystyczna.
Przypominamy, że dla dowolnego praporządku (A, ), X ą" A oraz a " A:
" a " Bu(X) wtedy i tylko wtedy, gdy y a dla wszystkich y " X
" a " Bl(X) wtedy i tylko wtedy, gdy a y dla wszystkich y " X
" Great(X) = X )" Bu(X)
" Least(X) = X )" Bl(X)
" Sup(X) = Least(Bu(X))
" Inf(X) = Great(Bl(X)).
Dla dowolnej prp-algebry A = (A, ) definiujemy:
" ą " E(A) wtedy i tylko wtedy, gdy hv(ą) " Great(A), dla każdego podsta-
wienia v : At A.
-

Ponieważ Great(A) = F("), więc mamy: E(A) = A (").
Dwie prp-algebry nazywamy izomorficznymi, gdy istnieje ich izomorfizm, zacho-
<"
wujący porządek. Jeśli A i B są izomorficzne, to piszemy A B.
=
Algebra B = (B, 1) jest podstrukturą algebry A = (A, 2) (piszemy wtedy:
B ą" A), gdy B jest podalgebrą A oraz 1 jest obcięciem porządku 2 do B.
Zachodzą następujące fakty:
- -

<"
" Jeśli A B, to A = B.
=
- -

" Jeśli B ą" A, to A B.
20
1.9.2. Reguły A-niezawodne i A-normalne
Dla dowolnych X ą" S, r " RS oraz prp-algebry A niech:
" r " V (A, X) wtedy i tylko wtedy, gdy dla każdego (P, ą) " r:
- -

jeśli P ą" A (X), to ą " A (X).
" r " N(A, X) wtedy i tylko wtedy, gdy dla każdego (P, ą) " r:
-

ą " A (X *" P ).
Jeśli X = ", to piszemy V (A) oraz N(A), odpowiednio. Wtedy:
" Reguły z V (A) nazywamy regułami A-niezawodnymi.
" Reguły z N(A) nazywamy regułami A-normalnymi.
Zachodzą następujące fakty:

" N(A, X) = {V (A, Y ) : X ą" Y }

" N(A) = {V (A, X) : X ą" S}
-

" N(A) = Der( A ) = Der(N(A), E(A))
-

" V (A) = Adm( A ) = Adm(N(A), E(A))
" r" " V (A)
" N(A) ą" V (A) (odwrotna inkluzja nie zachodzi).
1.9.3. Matryce logiczne
Każdą parę M = (A, A"), gdzie A jest algebrą, a A" jest podzbiorem uniwer-
sum algebry A (czyli A" ą" A) nazywamy matrycą logiczną. Zbiór A" jest zbiorem
elementów wyróżnionych matrycy M.
Zbiór E(M) wszystkich formuł M-prawdziwych (M-tautologii) jest zdefiniowany
następująco:
" ą " E(M) wtedy i tylko wtedy, gdy hv(ą) " A", dla każdego v : At A.
Zbiór E(M) nazywany jest także zawartością matrycy M.
-

Z kolei, operacja konsekwencji matrycowej M ma następującą definicję:
-

" ą " M(X) wtedy i tylko wtedy, gdy dla każdego v : At A
jeśli hv(X) ą" A", to hv(ą) " A".
21
-

Mamy oczywiście E(M) = M(").
Podamy teraz związki między konsekwencją matrycową a wprowadzoną wcześniej
operacją konsekwencji w prp-algebrach.
Niech A będzie algebrą o uniwersum A, podobną do algebry (ustalonego) języka
zdaniowego S. Gdy wyróżnimy jakiś podzbiór A" w uniwersum A, otrzymujemy ma-
trycę logiczną M = (A, A"). Rozważymy dwa przypadki:
" A" jest pusty lub identyczny z uniwersum A;
" " = A" A.

Matryca M = (A, A) generuje sprzeczną operację konsekwencji, czyli w tym
-

przypadku M(X) = S dla wszystkich X ą" S. Z kolei, matryca M = (A, ") generuje
następującą operację konsekwencji:
-

" M(X) = ", gdy X = "
-

" M(X) = S, gdy X = ".

Rozważmy teraz przypadek drugi, czyli matrycę M = (A, A"), gdzie " = A"

A.
W zbiorze A definiujemy relację praporządku :
" x y wtedy i tylko wtedy, gdy x " A" lub y " A".
/
Wtedy A" jest jedynym filtrem właściwym w zbiorze prauporządkowanym (A, ),
ponieważ:
" Great(A) = A"
" Least(A) = A - A"
" F(X) = A", gdy X ą" A"
" F(X) = A", gdy X A".
- -

Mamy zatem w tym przypadku: M(X) = A (X), gdzie A = (A, ) jest prp-
algebrą wyznaczoną w podany wyżej sposób przez zbiór A". I to właśnie jest podsta-
wowy związek między konsekwencjami matrycowymi a konsekwencjami wyznaczo-
nymi przez prp-algebry.
Podobnie jak dla prp-algebr, określamy reguły niezawodne oraz reguły normalne
w matrycy M:
" r " V (M) wtedy i tylko wtedy, gdy dla każdego (P, ą) " r:
jeśli P ą" E(M), to ą " (M);
-

" r " N(M) wtedy i tylko wtedy, gdy dla każdego (P, ą) " r: ą " M(P ).
Zachodzą wtedy następujące fakty:
22
-

" N(M) = Der(M)
-

" V (M) = Adm(M)
" r" " V (M) - N(M), jeśli " A" A.
Z olbrzymiej mnogości faktów dotyczących matryc logicznych wybieramy, na po-
trzeby tej notatki, jedynie niektóre ustalenia.
-

Jeśli M jest matrycą skończoną, to M jest finitystyczną operacją konsekwencji.
Mówimy, że zbiór X ą" S jest spełnialny w matrycy M = (A, A"), gdy istnieje
wartościowanie v : At A takie, że: hv(X) ą" A". Jeśli X jest spełnialny w M, to
piszemy X " Sat(M).
Jeśli M jest matrycą skończoną, to:
" X " Sat(M) wtedy i tylko wtedy, gdy Y " Sat(M) dla wszystkich Y "
F in(X).
Niech M = (A, A") oraz N = (B, B") będą matrycami podobnymi. Mówimy, że:
" M jest podmatrycą N, gdy A jest podalgebrą B oraz A" = A )" B". Jeśli M jest
podmatrycą N, to piszemy M ą" N.
" M jest izomorficzna z N, gdy istnieje izomorfizm h algebry A na algebrę B
taki, że dla wszystkich x " A: x " A" wtedy i tylko wtedy, gdy h(x) " B".
<"
Jeśli M jest izomorficzna z N, to piszemy M N.
=
Zachodzą następujące fakty:
-
-
<"
" Jeśli M N, to M = N.
=
-
-
" Jeśli N ą" M, to M N.

-

" M(Sb(X)) = {E(N) : N ą" M '" X ą" E(N)}.
Relacja R jest kongruencją matrycy M = (A, A"), gdy R jest kongruencją alge-
bry A oraz dla wszystkich x, y " A:
" jeśli xRy i x " A", to y " A".
Każda kongruencja R matrycy M = (A, A") wyznacza matrycę ilorazową M/R =
(A/R, A"/R), gdzie A/R jest algebrą ilorazową oraz A" = {[a]R : a " A"}.
Jeśli R jest kongruencją matrycy M, to konsekwencja matrycowa wyznaczona
przez M jest identyczna z konsekwencją matrycową wyznaczoną przez matrycę ilo-
- -
--
razową: M = M/R.
Produktem rodziny matryc podobnych {Mt}t"T , gdzie Mt = (At, A") nazy-
t

wamy matrycę Mt = ( At, A").
t
t"T t"T t"T
Zachodzą następujące fakty:
23

" E( Mt) = {E(Mt) : t " T }.
t"T
- -
--
-

" Dla każdego X ą" S: Mt(X) = {Mt(X) : t " T }, o ile X " Sat(Mt); w
t"T
-
--
-
przeciwnym przypadku Mt(X) = S.
t"T
Szczególną rolę pełnią tzw. matryce Lindenbauma. Dla dowolnych R ą" RS oraz
X ą" S matrycę:
MR,X = (S, CR(X))
nazywamy matrycą Lindenbauma dla systemu (R, X).
Zachodzą następujące fakty:
" E(MR,X) = {ą : Sb(ą) ą" CR(X)}.
" Jeśli r" " Adm(R, X), to E(MR,X) = CR(X).
Matrycy Lindenbauma nie należy mylić z algebrą Lindenbauma-Tarskiego. Jeśli
(R, X) jest logiką zdaniową nad standardowym językiem S2 = (S2, , (", '", Ź), to
definiujemy relację: ą <"R,X � wtedy i tylko wtedy, gdy ą �, � ą " CR(X).
Przy odpowiednich założeniach o (R, X) relacja <"R,X jest kongruencją matrycy Lin-
denbauma MR,X. Wtedy algebrę ilorazową S2/ <"R,X= (S2/ <"R,X, , *", )", -) na-
zywamy algebrą Lindenbauma-Tarskiego systemu (R, X). Operacje tej algebry są
zdefiniowane wzorami:
" [ą]<" *" [�]<" = [ą (" �]<"
R,X R,X R,X
" [ą]<" )" [�]<" = [ą '" �]<"
R,X R,X R,X
" [ą]<" [�]<" = [ą �]<"
R,X R,X R,X
" -[ą]<" = [Źą]<" .
R,X R,X
W kracie (S2/ <"R,X, *", )") mamy porządek kratowy: [ą]<" [�]<" wtedy i
R,X R,X
tylko wtedy, gdy ą � " CR(X). Przy stosownych założeniach, krata ta ma zero i
jedynkę.
1.9.4. Adekwatność
Niech (R, X) będzie systemem logiki zdaniowej, a M matrycą logiczną podobną
do algebry języka tego systemu. Jeżeli E(M) = CR(X) = CR,X("), to mówimy, że
matryca M jest (słabo) adekwatna dla (R, X).
Zachodzi następujący fakt:
" Dla każdej logiki zdaniowej (R, X) takiej, że r" " Adm(R, X) oraz R-{r"} ą"
Struct istnieje matryca M taka, że: CR(X) = E(M) oraz R - {r"} ą" N(M).
24
Mogłoby się wydawać, że fakt powyższy czyni pytanie o istnienie semantyki dla
dowolnych rachunków zdaniowych całkiem trywialnym: dla każdego rachunku (R, X)
takiego, że r" " Adm(R, X) oraz R - {r"} ą" Struct zachodzi CR(X) = E(MR,X),
gdzie MR,X jest matrycą Lindenbauma dla (R, X). Tak jednak nie jest: poszukujemy
nie całkiem dowolnych semantyk dla rachunków zdaniowych, lecz raczej semantyk,
spełniających pewne określone warunki. Dla przykładu, wiemy, iż:
" M2 jest minimalną matrycą adekwatną dla logiki klasycznej.
" Logika modalna (R0a", AS5) nie ma żadnej skończonej matrycy adekwatnej.
Istnieje jednak dla niej nieskończona matryca adekwatna (matryca Wajsberga).
" Istnieją matryce skończone, które nie są skończenie aksjomatyzowalne (wyniki
Wojtylaka i Pałasińskiej).
" Skończenie wartościowe wielowartościowe logiki A
ukasiewicza mają skończone
matryce słabo adekwatne.
" Nieskończenie wartościowa logika A
ukasiewicza ma nieskończoną matrycę słabo
adekwatną.
Jeśli CR(X) = E(M), to:
" Adm(R, X) = V (M)
" Der(R, X) ą" V (M)
" N(M) ą" Adm(R, X).
Mówimy, że matryca M jest silnie adekwatna dla logiki (R, X) (lub dla operacji
konsekwencji CR,X), gdy dla wszystkich Y ą" S:
-

CR(X *" Y ) = M(Y ).
Wprost z definicji wynika, że M jest silnie adekwatna dla logiki (R, X) wtedy i
tylko wtedy, gdy N(M) = Der(R, X).
Niech X0 będzie zbiorem następujących formuł:
" p p
" (p q) ((q s) (p s))
" (q s) ((p q) (p s))
" ((p p) (p p)) (p p)
" (p '" q) p
" (p '" q) q
" (p q) ((p s) (p (q '" s)))
25
" p (p (" q)
" q (p (" q)
" (p s) ((q s) ((p (" q) s)).
Zachodzi wtedy następujący fakt (S1 to zbiór formuł czysto implikacyjnych):
" Jeśli (R, X) jest systemem niezmienniczym nad S1 takim, że r0 " Der(R, X)
oraz X0 ą" CR(X), to istnieje matryca M silnie adekwatna dla (R, X).
O matrycach silnie adekwatnych dla różnych systemów logicznych wiadomo np.,
że:
" Nie istnieją matryce silnie adekwatne dla systemów modalnych S1 S3 Lewisa.
" Matryca M2 jest silnie adekwatna dla logiki klasycznej.
" Istnieje matryca silnie adekwatna dla systemu modalnego (R0a, Sb(AS5)) (różna
od wspomnianej wcześniej matrycy Wajsberga).
Dla celów tej notatki nie jest potrzebne podawanie innych jeszcze rodzajów ade-
kwatności, rozważanych w literaturze przedmiotu.
1.9.5. Filtr-konsekwencja
Zdefiniujmy następujące dwie operacje konsekwencji:
" Zbiór F Ci(X), dla X ą" S2 niech będzie zbiorem tych wszystkich formuł
ą " S2, które w każdej algebrze Heytinga A spełniają następujący warunek
dla wszystkich v : At A:
hv(ą) " F(hv(X)).
" Zbiór F C2(X), dla X ą" S2 niech będzie zbiorem tych wszystkich formuł
ą " S2, które w każdej algebrze Boole a A spełniają następujący warunek dla
wszystkich v : At A:
hv(ą) " F(hv(X)).
Dla F C równego F Ci lub F C2 zachodzą wtedy następujące fakty:
" X ą" F C(X).
" Jeśli X ą" Y , to F C(X) ą" F C(Y ).
" F C(F C(X)) ą" F C(X).
" he(F C(X)) ą" F C(he(X)) dla wszystkich e : At S.

" F C(X) ą" {F C(Y ) : Y " F in(X)}.
26
" Jeśli � " F C(X), to (ą �) " F C(X).
" � " F C(X *" {ą}) wtedy i tylko wtedy, gdy (ą �) " F C(X).
" Jeśli ą, ą � " F C(X), to � " F C(X).
" Sb(F C(")) ą" F C(").
Przy pomocy operacji F Ci oraz F C2 udowodnić można twierdzenia o zupełności
dla, odpowiednio, logiki intuicjonistycznej oraz logiki klasycznej.
Niech (R0, Sb(Aint)) będzie logiką intuicjonistyczną. Przypominamy, że filtr-kon-
sekwencja F Ci zdefiniowana jest warunkiem:
-

" ą " F Ci(X) wtedy i tylko wtedy, gdy ą " A(X), dla każdej algebry Heytinga
A.
Zachodzą następujące fakty:
" Aint ą" F Ci(").
" CR (Sb(Aint) *" X) = F Ci(X) dla wszystkich X ą" S2.
0
" Dla dowolnych ą " S2 oraz X ą" S2: ą " CR (Aint *" X) wtedy i tylko wtedy,
0"
gdy dla każdej algebry Heytinga A, X ą" E(A) implikuje ą " E(A).
" Dla dowolnej ą " S2: ą " CR (Aint) wtedy i tylko wtedy, gdy dla każdej
0"
skończonej algebry Heytinga A, ą " E(A).

" CR (Aint) = {E(Jn) : n 1}, gdzie Jn są algebrami Jaśkowskiego.
0"
-

" Dla każdego skończonego X ą" S2: CR (Sb(A) *" X) = {Jn : n 1}.
0
Z kolei, zajmijmy się systemem logiki klasycznej (R0, Sb(A2)) i filtr-konsekwencją
F C2. Zachodzą następujące fakty:
" Zbiór F C2(") wszystkich tautologii Boolowskich jest zbiorem tych wszystkich
formuł ą " S2, które w każdej algebrze Boole a B i dla każdego wartościowania
v : At B spełniają warunek:
hv(ą) = 1B.
" A2 ą" F C2(").
" CR (Sb(A2) *" X) = F C2(X) dla wszystkich X ą" S2.
0
-

" CR (Sb(A2) *" X) = B2(X) dla wszystkich X ą" S2.
0
27
1.10. Różne pojęcia zupełności rachunków zdaniowych
Podane wyżej przykładowe twierdzenia o pełności logik zdaniowych (tu: intuicjo-
nistycznej oraz klasycznej) nie wyczerpują całości problematyki związanej z zupełno-
ścią systemów logiki zdaniowej. Wiele dalszych problemów dotyczy np.: uogólnionej
zupełności, zupełności w sensie Posta, strukturalnej zupełności, itd. Bardzo wyryw-
kowo podamy kilka znanych rezultatów w tej dziedzinie.
1.10.1. Uogólniona zupełność
Niech S = (S, F1, . . . , Fm) będzie algebrą języka zdaniowego z przeliczalnym
zbiorem zmiennych. Niech � ą" S. Dla dowolnych A ą" S oraz R ą" RS definiujemy:
" (R, A) " �-Cpl wtedy i tylko wtedy, gdy Adm(R, A) )" Struct(�) ą" Der(R, A).
Jeśli (R, A) " �-Cpl, to mówimy, że (R, A) jest �-zupełny.
" (R, A) " �-Max wtedy i tylko wtedy, gdy (R, A) " Inv(�) oraz nie istnieje
system (R1, A1) " Inv(�) taki, że (R, A) z" (R1, A1). Jeśli (R, A) " �-Max,
to mówimy, że (R, A) jest �-maksymalny.
Powyższe pojęcia wyrazić można również w terminach operacji konsekwencji:
" C " �-CPL wtedy i tylko wtedy, gdy ADM(C) )" Struct(�) ą" DER(C).
" C " �-MAX wtedy i tylko wtedy, gdy C(") = S lub C jest elementem maksy-
malnym w rodzinie wszystkich niesprzecznych �-strukturalnych operacji konse-
kwencji nad S.
Zachodzą następujące fakty:
" �-Max ą" �-Cpl )" Inv(�)
" Jeśli (R, A) " Inv(�), to:
1. (R, A) " �-Max wtedy i tylko wtedy, gdy (R*"{r}, A) " Cns, dla wszyst-
/
kich r " Struct(�) - Der(R, A).
2. (R, A) " �-Cpl wtedy i tylko wtedy, gdy (R *" {r}, A) " Cns, dla wszyst-
/
kich r " Struct(�) )" Adm(R, A) - Der(R, A).
" Jeśli r"|� " Adm(R, A) oraz " = CR(A) = S, to następujące warunki są

równoważne:
1. Der(R, A) )" Struct(�) = V (M) )" Struct(�).
2. (R, A) " �-Cpl oraz E(M) = CR(A).
" Jeśli E(M) = CR(A), to następujące warunki są równoważne:
28
1. Der(R, A) )" Struct(�) = V (M) )" Struct(�).
2. (R, A) " �-Cpl.
Dla każdego X ą" S niech:
n 1
" (P, ą) " � - rX wtedy i tylko wtedy, gdy: jeśli (he ć% . . . ć% he )(P ) ą" X), to
n 1
(he ć% . . . ć% he )(ą) " X, dla n 0 oraz e1, . . . , en : At �.
Wtedy następujące warunki sa równoważne:
" (R, A) " �-Cpl.
" � - rC (A) " Der(R, A).
R
Zachodzą następujące fakty:
" Jeśli (R, A) " Inv(�), to następujące warunki są równoważne:
1. (R, A) " �-Cpl.
2. Jeśli CR(A) = CR (A1), to (R1, A1) (R, A), dla wszystkich (R1, A1) "
1
Inv(�).
" Następujące warunki są równoważne:
1. (R, A) " �-Cpl.
2. Jeśli CR(A) = CR (A1), to (R1, A1) (R, A), dla wszystkich A1 ą" S
1
oraz R1 ą" Struct(�).
" Niech (R, A) " Inv(�). Wtedy:
1. (R, A) " �-Max wtedy i tylko wtedy, gdy: jeśli (R *" {r}, A) " Cns, to
Adm(R *" {r}, A) )" Struct(�) ą" Der(R, A) dla wszystkich r " RS.
2. Jeśli (R, A) " �-Max, to CR(Sb�({ą}) *" A) = S dla każdej ą " CR(A).
/
" Następujące warunki są równoważne:
1. (R, A) " �-Max.
2. (R, A) " �-Cpl )" Inv(�) oraz (R *" {r"|�}, A) " "-Cpl.
" Jeśli C " STRUCT(�), to:
1. C " �-MAX wtedy i tylko wtedy, gdy dla wszystkich r " Struct(�): jeśli
r " DER(C), to C *" Cr " CNS. [Tutaj stosujemy oznaczenie: Cr(X) =
/ /
C{r}(X).]
2. C " �-MAX wtedy i tylko wtedy, gdy dla wszystkich r " Struct(�): jeśli
r " ADM(C) - DER(C), to C *" Cr " CNS.
/
29
" Dla każdego (R, A) " Cns istnieje (R1, A1) " �-Cpl taki, że (R, A) (R1, A1) "
Cns.
" Jeśli (R, A) " Inv(�))"Cns oraz (R*"{r"|�}, A) " Comp, to istnieje (R1, A1) "
�-Max taki, że (R, A) (R1, A1) " Cns.
Z dwóch ostatnich z powyższych twierdzeń widzimy zatem, że:
" Dowolny niesprzeczny system (R, A) można rozszerzyć do systemu �-zupełnego.
Wystarczy bowiem wziąć: R1 = Adm(R, A) oraz A1 = A.
" Dowolny zwarty system (R, A) można rozszerzyć do systemu �-maksymalnego.
Przypominamy, że (R, A) " Comp, gdy dla każdego Y ą" S istnieje X "
F in(Y ) taki, że jeśli CR(A *" Y ) = S, to CR(A *" X) = S.
Ponadto, system (R1, A1), o którym mowa w przedostatnim z powyższych twier-
dzeń ma następujące własności:
" CR(A) = CR (A1).
1
" Jeśli (R, A) " �-Cpl, to (R1, A1) H" (R, A).
" Jeśli (R, A) " Inv(�), to (R1, A1) " Inv(�)
" Jeśli (R, A) " Inv(�) oraz (R *" {r"|�}, A) " "-Cpl, to (R1, A1) " �-Max.
" (R1, A1) " �-Max dla pewnego (R, A) " Inv(�) i pewnego � ą" S.
/
1.10.2. Zupełność w sensie Posta
Przypomnijmy:
" (R, A) " Cpl wtedy i tylko wtedy, gdy CR(A *" {ą}) = S dla wszystkich
ą " CR(A)
/
" (R, A) " "-Cpl wtedy i tylko wtedy, gdy Adm(R, A) ą" Der(R, A)
" (R, A) " Max wtedy i tylko wtedy, gdy dla wszystkich (R1, A1) " Cns, nie
zachodzi (R, A) z" (R1, A1).
Zachodzą następujące fakty:
" "-Cpl = Cpl = Max.
" (R, A) " Cpl wtedy i tylko wtedy, gdy (R *" {r}, A) " Cns, dla wszystkich
/
r " Der(R, A).
/
" Jeśli M jest matrycą logiczną oraz " = CR(A) = S, to:

1. Der(R, A) = V (M) wtedy i tylko wtedy, gdy E(M) = CR(A) oraz
(R, A) " Cpl.
30
2. Jeśli E(M) = CR(A), to (R, A) " Cpl wtedy i tylko wtedy, gdy
Der(R, A) = V (M).
" Jeśli r" " Adm(R, A), to Der(R, A) = V (MR,A) wtedy i tylko wtedy, gdy
(R, A) " Cpl.
" Dla każdego (R, A) " Cns istnieje (R1, A1) " Cns )" Cpl taki, że (R, A) z"
(R1, A1). Tak więc, każdy niesprzeczny system logiczny (R, A) może zostać
rozszerzony do systemu niesprzecznego i Post-zupełnego. Przy tym, rozszerze-
nie (R1, A1) ma następujące własności:
1. CR(A) = CR (A1).
1
2. Jeśli (R, A) " Cpl, to (R, A) H" (R1, A1).
" Jeśli (R, A) " Comp oraz CR(A *" X) = S, to istnieje Y ą" S taki, że:

1. CR(A *" X) ą" CR(A *" Y ) = S

2. CR(A *" Y ) = Y
3. CR(A *" Y *" {ą}) = S dla wszystkich ą " Y .
/
Dla dowolnego (R, X) definiujemy rodzinę L(R, X) nadzbiorów Lindenbauma
dla CR(X):
" L(R, X) = {Y : X ą" Y = CR(Y ) = S '" ("ą " Y ) CR(Y *" {ą}) = S}.
/
Dla każdego Y " L(R, X) system (R, Y ) jest wyznaczony jednoznacznie. Wtedy
oczywiście (R, Y ) " Cns )" Cpl. System (R, Y ) nazywamy w takim przypadku nad-
systemem Lindenbauma dla systemu (R, X).
Wprowadzimy pewne miary stopnia niezupełności oraz stopnia maksymalności
systemów logicznych.
" Przez (globalny) stopień niezupełności systemu (R, A) rozumiemy moc rodziny:
{Der(R *" R , A *" A ) : A ą" S '" R ą" RS}.
" Jeśli w definicji powyższej ograniczymy się do systemów (R , A ) " Inv, to
otrzymujemy stopień maksymalności systemu (R, A) " Inv.
" Dla strukturalnych operacji konsekwencji C, przez stopień maksymalności C
rozumiemy moc rodziny {C " Struct : C C }.
" Stopniem zupełności systemu (R, A) nazywamy liczbę kardynalną dc(R, A)
równą mocy rodziny:
{CR(A *" X) : X ą" S}.
Zachodzą następujące fakty:
-

" Jeśli M jest matrycą skończoną, to dc(M ć% Sb) < 5!0.
31
- -

" Jeśli M jest matrycą funkcyjnie zupełną, to Mć%Sb " CPL, czyli dc(Mć%Sb) 2.
Dla logik finitystycznych (które niekoniecznie są zwarte) zachodzi następujące
twierdzenie A
osia-Lindenbauma-Assera:
" Jeśli CRA jest finitystyczna oraz ą " CR(A *" X), to istnieje Y ą" S taki, że:
/
1. CR(A *" X) ą" Y = CR(A *" Y ) oraz ą " Y
/
2. ą " CR(A *" Y *" {�}) dla wszystkich � " CR(A *" Y ).
/
Dla dowolnej ą " S niech:
" Lą(R, A) = {Y : X ą" CR(Y ) = Y '" ą " Y '" ("� " Y ) ą " CR(Y *" {�})}.
/ /
Każdy element rodziny Lą(R, A) nazywamy ą-relatywnym nadzbiorem Linden-
bauma dla systemu (R, A).
Twierdzenie A
osia-Lindenbauma-Assera przyjmuje zatem następującą postać (gdy
rozważamy jedynie reguły wnioskowania o skończonych zbiorach przesłanek):
" Dla każdej ą " CR(A): Lą(R, A) = ".
/
Ustalmy własności logiki klasycznej, jeśli chodzi o wprowadzone wyżej pojęcia.
Przypomnijmy, że Cn2 jest operacją konsekwencji wyznaczoną przez niezmienniczą
wersję logiki klasycznej R0, Sb(A2), czyli:
Cn2(X) = CR (Sb(A2) *" X).
0
Zachodzą (jak wiadomo z elementarnego kursu logiki) następujące fakty, dla każ-
dego X ą" S2 oraz ą, � " S2:
" ą " Cn2(X *" {�}) wtedy i tylko wtedy, gdy (� ą) " Cn2(X).
" Cn2(X *" {Źą}) = S2 wtedy i tylko wtedy, gdy ą " Cn2(X).
/
" Cn2(X *" {ą}) = S2 wtedy i tylko wtedy, gdy Źą " Cn2(X).
/
Z pomocą powyższych faktów dokonać można szeregu dalszych ustaleń, np.:
" (R0, Sb(A2) *" X) " Cns wtedy i tylko wtedy, gdy istnieje ą " S2 taka, że nie
zachodzi: ą, Źą " Cn2(X).
" (R0, Sb(A2) *" X) " Cpl wtedy i tylko wtedy, gdy dla każdej ą " S2: albo
ą " Cn2(X), albo Źą " Cn2(X).
" Lą(R0, Sb(A2)) ą" L(R0, Sb(A2)).
" Jeśli ą " Cn2(X), to istnieje zbiór Y ą" S2 taki, że:
/
1. Cn2(X) ą" Y = Cn2(Y ) oraz ą " Cn2(Y )
/
2. Cn2(Y ) *" {�} = S2 dla wszystkich � " Y .
/
32
" Dla wszystkich X ą" S2 oraz ą " S2:
1. Jeśli ą " Cn2(X), to istnieje Y " L(R0, Sb(A2)) taki, że X ą" Y oraz
/
ą " Y .
/

2. Cn2(X) = {Y ą" S2 : X ą" Y " L(R0, Sb(A2))}.
" Dla każdego Y " L(R0, Sb(A2)):
1. ą � " Y wtedy i tylko wtedy, gdy: jeśli ą " Y , to � " Y .
2. ą (" � " Y wtedy i tylko wtedy, gdy: ą " Y lub � " Y .
3. ą '" � " Y wtedy i tylko wtedy, gdy ą " Y oraz � " Y .
4. Źą " Y wtedy i tylko wtedy, gdy ą " Y .
/
" A2 ą" E(M2) oraz r0 " N(M2).
" Cn2(X) = S2 wtedy i tylko wtedy, gdy X " Sat(M2), dla wszystkich X ą" S2.

" Dla wszystkich X ą" S2: X " Sat(M2) wtedy i tylko wtedy, gdy Y " Sat(M2),
dla każdego Y " F in(X).
" CR (Sb(A2)) = CR (A2) = E(M2).
0 0"
" Der(R0, Sb(A2)) = N(M2).
" Der(R0", A2) = Adm(R0, Sb(A2)) = Adm(R0", A2).
-

" CR (Sb(A2) *" X) = M2(X), dla wszystkich X ą" S2.
0
" (R0", A2) " Cpl.
" dc(R0, Sb(A2)) = c. W konsekwencji, stopień zupełności dowolnej logiki słab-
szej od (R0, Sb(A2)) także jest równy kontinuum.
1.10.3. Jednoznaczność rozszerzeń Lindenbauma
Interesują nas systemy logiczne (R, A) takie, dla których rodzina L(R, X) zawiera
dokładnie jeden element. Zdefiniujmy:
" (R, X) " T (M) wtedy i tylko wtedy, gdy L(R, X) = {M}, dla M ą" S.
Jeśli (R, X) " T dla pewnego M = S, to mówimy, że (R, X) ma własność

Tarskiego.
Podamy pewne informacje dotyczące rozszerzeń Lindenbauma w przypadku:
" logiki intuicjinistycznej
" logik wielowartościowych A
ukasiewicza.
33
Wprowadz
my oznaczenie: Z2 = CR (A2).
0"
Przypominamy, że Cint jest operacją konsekwencji generowaną przez niezmienni-
czą wersję logiki intuicjonistycznej (R0, Sb(Aint)). Mamy wtedy:
" (ą �) " Cint(X) wtedy i tylko wtedy, gdy Ci(X *" {�}) ą" Cint(X *" {ą}).
" Cint(X *" {ą}) = S2 wtedy i tylko wtedy, gdy Źą " Cint(X).
/
Dla logiki intuicjonistycznej zachodzą następujące fakty:
" (R0, Sb(Aint) *" X) " Cns wtedy i tylko wtedy, gdy istnieje ą " S2 taka, że nie
zachodzi: ą, Źą " Cint(X).
" (R0, Sb(Aint) *" X) " Cpl wtedy i tylko wtedy, gdy dla każdej ą " S2: albo
ą " Cnint(X), albo Źą " Cint(X).
" L(R0, Sb(Aint)) = L(R0, Sb(A2)).
" L(R0", A2) = L(R0", Aint) = {Z2}.
" Jeśli Y " L�(R0", Aint), to następujące warunki są równoważne:
1. (R0, Y ) " Cpl
/
2. ((� ą) �) " Y , dla pewnej ą " S2.
" Jeśli p0 p0 " X oraz ą " CR (Sb(X)), to zbiór Lą(R0, Sb(X)) ma moc
/
0
kontinuum.
" dc(R0", Aint) = c.
Z kolei, dla wielowartościowych logik A
ukasiewicza zachodzą następujące fakty:
" L(R0", A
") = L(R0", A
m) = L(R0", A2) = {Z2}.
" dc(R0", A
m) 2k-1 + 1, gdzie k jest liczbą podzielników m - 1.
Można w pełnej ogólności rozstrzygnąć problem istnienia R0"-systemów, mają-
cych własność Tarskiego. Pomijamy w niniejszej notatce odnośne twierdzenia.
1.10.4. Strukturalna zupełność
Strukturalna zupełność jest pewnym szczególnym przypadkiem �-zupełności, a
mianowicie takim, dla którego � = S. Zdefiniujmy:
" (R, A) " SCpl wtedy i tylko wtedy, gdy Adm(R, A))"Struct ą" Der(R, A). Jeśli
(R, A) " SCpl, to mówimy, że system (R, A) jest strukturalnie zupełny.
Zachodzą następujące fakty:
34
" (R, A) " SCpl wtedy i tylko wtedy, gdy dla wszystkich R1 ą" Struct oraz
wszystkich A1 ą" S: jeśli CR(A) = CR (A1), to (R1, A1) (R, A).
1
" Jeśli (R, A) " Inv, to: (R, A) " SCpl wtedy i tylko wtedy, gdy dla wszystkich
(R1, A1) " Inv: jeśli CR(A) = CR (A1), to (R1, A1) (R, A).
1
" Jeśli C " STRUCT, to C " SCPL wtedy i tylko wtedy, gdy dla wszystkich
C1 " STRUCT: jeśli C(") = C1("), to C1 C.
" Jeśli r" " Adm(R, A) oraz " = CR(A) = S, to następujące warunki są równo-

ważne:
1. Der(R, A) )" Struct = V (M) )" Struct
2. CR(A) = E(M) oraz (R, A) " SCpl.
" Jeśli CR(A) = E(M), to następujące warunki są równoważne:
1. (R, A) " SCpl
2. V (M) )" Struct ą" Der(R, A).
" Każdy system niesprzeczny (R, A) można niesprzecznie rozszerzyć do pewnego
systemu strukturalnie zupełnego (R1, A1).
" Niech (R, A) " Inv oraz CR(A *" Z2) ą" Z2. Wtedy: jeśli (R *" {r"}, A) " SCpl,
to (R *" {r"}, A) " T (Z2).
" (R, A) " SCpl wtedy i tylko wtedy, gdy rC (A) " Der(R, A).
R
" (R, A) " SCpl wtedy i tylko wtedy, gdy N(MR,A) ą" Der(R, A).
-
--
" (R, A) " SCpl wtedy i tylko wtedy, gdy MR,A(X) ą" CR,A(X), dla wszystkich
X ą" S.
" Jeśli (R, A) " Inv, to:
1. (R, A) " SCpl wtedy i tylko wtedy, gdy N(MR,A) = Der(R, A).
2. (R, A) " SCpl wtedy i tylko wtedy, gdy dla wszystkich X ą" S:
-
--
MR,A(X) = CR(A *" X).
3. (Przy założeniu, że wszystkie reguły mają tylko skończone zbiory prze-
słanek.) (R, A) " SCpl wtedy i tylko wtedy, gdy dla wszystkich X "
-
--
F in(S): MR,A(X) = CR(A *" X).
" Niech (R, A) będzie systemem niezmienniczym takim, że CR,A jest finitystyczna.
Wtedy następujące warunki są równoważne:
1. (R, A) " SCpl
2. Dla każdej � " S oraz każdego Y " L�(R, A) istnieje endomorfizm
h : S S taki, że Y = h-1(CR(A)).
35
" Niech (R, A) będzie systemem niezmienniczym. Jeśli (R, A) " SCpl, to dla
każdego Y " L(R, A) istnieje odwzorowanie e : At : S takie, że Y =
-1
he (CR(A)).
Dla systemów: logiki klasycznej, logiki intuicjonistycznej, logik wielowartościo-
wych A
ukasiewicza oraz logik modalnych zachodzą następujące fakty dotyczące wła-
sności strukturalnej zupełności:
" (R0, Sb(A2)) " SCpl.
" (R0", Aint) " SCpl.
/
" Niektóre fragmenty logiki intuicjonistycznej są jednak strukturalnie zupełne: np.
fragment (R0, Sb(A,'",Ź)).
int
" (R0, Sb(A
n)) " SCpl, dla każdej n > 2.
" (R0", A
n) " SCpl, dla każdej n 2.
" (R0"a, AS5) " SCpl.
" (R0a, Sb(AS5)) " SCpl.
/
1.11. C-definiowalność
Wiadomo, że Cn2 jest najmniejszą operacją konsekwencji C spełniającą następu-
jące warunki:
" (T0) Jeśli X ą" C(X), to Y *" C(X) ą" C(Y )
" (T1) C({ą, Źą}) = S2 oraz C({ą}) )" C({Źą}) = C(")
" (T2) ą � " C(X) wtedy i tylko wtedy, gdy � " C(X *" {ą})
" (T3) C(X *" {ą (" �}) = C(X *" {ą}) )" C(X *" {�})
" (T4) C(X *" {ą '" �}) = C(X *" {ą, �}).
Wiadomo też, że Cn2 jest jedyną niesprzeczną oraz strukturalną operacją konse-
kwencji spełniającą te warunki.
Powyższa charakterystyka nie jest jednakże zadowalająca: poszczególne warunki
nie są jednorodne. Chcielibyśmy mieć (oprócz (T0), który ustala, że C jest operacją
konsekwencji) zestaw warunków o postaci:
" ąż� " C(X) wtedy i tylko wtedy, gdy . . .
gdzie ż " {Ź, , (", '"}, a po prawej stronie równoważności występuje warunek, cha-
rakteryzujący poszczególny spójnik przez operację konsekwencji.
Okazuje się, że dla pewnych logik możliwe jest podanie tego typu jednorodnych
warunków. Nie jest tak jednak w przypadku logiki klasycznej Cn2.
Dla przykładu, wiadomo, że operacja konsekwencji intuicjonistycznej Cnint jest
najmniejszą operacją konsekwencji spełniającą następujące warunki (H):
36
" (H1) Źą " C(X) wtedy i tylko wtedy, gdy S2 ą" C(X *" {ą})
" (H2) ą � " C(X) wtedy i tylko wtedy, gdy C(X *" {�}) ą" C(X *" {ą})
" (H3) ą("� " C(X) wtedy i tylko wtedy, gdy C(X*"{ą}))"C(X*"{�}) ą" C(X)
" (H4) ą'"� " C(X) wtedy i tylko wtedy, gdy C(X*"{ą})*"C(X*"{�}) ą" C(X).
Rozważmy następujący zbiór warunków (D):
" (D1) Źą " C(X) wtedy i tylko wtedy, gdy C(X *" {ą}) = S2
" (D2) ą � " C(X) wtedy i tylko wtedy, gdy C(X *" {ą, Ź�}) = S2
" (D3) ą (" � " C(X) wtedy i tylko wtedy, gdy C(X *" {Źą, Ź�}) = S2
" (D4) ą'"� " C(X) wtedy i tylko wtedy, gdy C(X*"{Źą}))"C(X*"{Ź�}) = S2.
Klasyczna konsekwencja Cn2 oczywiście spełnia te warunki. Zauważmy jednak,
że:
" Jeśli C spełnia (D), to każde aksjomatyczne rozszerzenie C także spełnia (D). A
zatem (D) nie wyznaczają C jednoznacznie.
" Jednak najmniejsza operacja C spełniająca warunki (D) (czyli przekrój wszyst-
kich operacji C, spełniających (D)) jest wyznaczona jednoznacznie i jest: struk-
turalna oraz finitystyczna.
" Jeśli C spełnia (D), to Sb(A2) ą" C(").
Najmniejsza operacja spełniająca (D) (oznaczana przez CD) jest wyznaczona przez
aksjomaty Sb(A2) oraz następujące reguły wnioskowania:
ą, ą Ź�
r01 :
Ź�
ą, ą (� ł)
r02 :
� ł
ą, ą (� (" ł)
r03 :
� (" ł
ą, ą (� '" ł)
r04 :
� '" ł
ą, Źą
r1 : .
�
Ponieważ reguły CD są niezawodne klasycznie, więc CD(X) ą" Cn2(X) dla
wszystkich X. Ponadto, dla wszystkich X ą" S2:
" CD(X) = S2 wtedy i tylko wtedy, gdy Cn2(X) = S2.
37
" ą " CD(X) wtedy i tylko wtedy, gdy ą " Cn2(X), dla ą " At.
/
" ą " CD(X) wtedy i tylko wtedy, gdy ą " X, dla ą " At oraz Cn2(X) = S2.

Mamy zatem CD Cn2, lecz nierówność odwrotna nie zachodzi. Mamy jedynie:
CD(") = CR (A2).
0"
Tak więc, logika CD jest słabsza od logiki klasycznej. Jej spójniki nie są spójni-
kami klasycznymi, co widać z następującego faktu.
Rozważmy matrycę logiczną MD zbudowaną na zbiorze {1, 2, 3} z 3 jako jedynym
elementem wyróżnionym oraz następującą interpretacją spójników:
1 2 3 (" 1 2 3 '" 1 2 3 Ź
1 3 3 3 1 1 3 3 1 1 1 1 1 3
2 1 3 3 2 3 3 3 2 1 3 3 2 1
3 1 3 3 3 3 3 3 3 1 3 3 3 1
-
-
Wtedy konsekwencja CD jest dokładnie konsekwencją matrycową MD.
Logika CD jest tzw. logiką progową. Zachodzi mianowicie następujący fakt:
" Jeśli C jest niesprzeczną strukturalną operacją konsekwencji oraz CD < C, to
C = Cn2.
Tak więc, klasyczna operacja konsekwencji Cn2 jest jedynym właściwym nie-
sprzecznym i strukturalnym rozszerzeniem CD.
Można wykazać, że same reguły r0i (wraz z A2), bez reguły r1, nie aksjomaty-
zują CD. Niech mianowicie M1 będzie matrycą na zbiorze {1, 3}, z 3 jako jedynym
elementem wyróżnionym i niech:
" Źx = 3
" f(x, y) = 3 dla f " {, (", '"}.
Wtedy: wszystkie aksjomaty Sb(A2) są prawdziwe w M1 oraz reguły r0i są nieza-
wodne w M1, ale r1 nie jest niezawodna w M1. Ponadto, konsekwencja wyznaczona
przez te reguły (oraz Sb(A2)) pokrywa się z przekrojem konsekwencji matrycowych
- -

M1 )" M2, gdzie M2 jest matrycą klasyczną. Zależności między omawianymi konse-
kwencjami są następujące (tu Cinc jest konsekwencją sprzeczną):
- -

" M1 )" M2 < CD < Cn2 < Cinc
- - -

" M1 )" M2 < M1 < Cinc
-

" konsekwencja M1 jest -nieporównywalna ani z CD, ani z Cn2.
Wreszcie, MD jest podmatrycą M1 � M2 oraz zachodzi:
- -
- -----
" MD = M1 � M2.
Istnieje wiele wariantów systemu (D). Żaden z nich jednak nie daje poszukiwanej
C-definicji logiki klasycznej, o ile operacje konsekwencji rozumiemy w sensie nada-
nym im przez Tarskiego. Definicje takie są możliwe, gdy zmienimy to rozumienie.
38
2. Paradygmat semantyczny
2.1. Logiki abstrakcyjne
Dla naszych celów wystarczająca będzie następująca definicja logiki abstrakcyjnej
(albo: systemu logicznego, w sensie uogólnionym).
Przez logikę abstrakcyjną rozumiemy każdą parę uporządkowaną L = (L, |=L),
spełniającą następujące warunki:
" L przyporządkowuje każdej sygnaturze � zbiór L(�), zwany zbiorem �-zdań lo-
giki L. [Uwaga: w niektórych przypadkach trzeba rozważać klasy zamiast zbio-
rów.]
" Jeśli � ą" �, to L(�) ą" L(�).
" Jeśli A |=L �, to dla pewnego � mamy: A " Str� oraz � " L(�).
<"
" WARUNEK IZOMORFIZMU. Jeśli A |=L � oraz A B, to B |=L �.
=
" WARUNEK REDUKTU. Jeśli � ą" �, � " L(�) oraz A " Str�, to A |=L � wtedy
i tylko wtedy, gdy A � |=L �
Przypominamy, że A � jest �-reduktem struktury A, czyli strukturą powstającą
z A poprzez uwzględnienie tylko interpretacji wszystkich symboli z � (a więc, gdy
A " Str� oraz � ą" �, to w A � uwzględniamy tylko interpretacje symboli z �,
pomijając interpretacje symboli z � - �).
Dla dowolnej logiki abstrakcyjnej L oraz � " L(�) miech:
Mod� (�) = {A : A " Str� '" A |=L �}
L
(jeśli � będzie jasne z kontekstu, będziemy pisać ModL(�)).
Niech L�� oznacza logikę pierwszego rzędu. W tym przypadku funkcja L przy-
porządkowuje każdej sygnaturze � zbiór wszystkich zdań pierwszego rzędu w których
występują symbole z �. Dla logiki L�� będziemy używali relacji |=, bez indeksu, po-
krywającej się z relacją spełniania znaną z wykładu Semantyka KRP.
 Moc wyrażania poszczególnych logik abstrakcyjnych definiowana jest w termi-
nach semantycznych:
" Piszemy L1 L2 wtedy i tylko wtedy, gdy dla każdej sygnatury � oraz każdego
� " L1(�) istnieje � " L2(�) taka, że: Mod� (�) = Mod� (�). Mówimy
L1 L2
wtedy, że L1 ma moc wyrażania nie większą niż L2.
" Gdy zachodzi L1 L2, ale nie zachodzi L2 L1, to piszemy L1 < L2 i
mówimy, że L2 ma moc wyrażania większą niż L1.
" Gdy zachodzi L1 L2 oraz zachodzi L2 L1, to piszemy L1 <" L2 i mówimy,
że L1 i L1 mają taką samą moc wyrażania.
39
Spośród wszystkich logik abstrakcyjnych wyróżnimy klasę logik regularnych, speł-
niających pewne naturalne warunki.
Powiemy, że logika L ma własność spójników Boolowskich, gdy:
" Dla każdej � oraz � " L(�) istnieje � " L(�) taka, że dla każdej A " Str�:
A |=L � wtedy i tylko wtedy, gdy nie zachodzi A |=L �.
" Dla każdej � oraz każdych �, � " L(�) istnieje � " L(�) taka, że dla każdej
A " Str�:
A |=L � wtedy i tylko wtedy, gdy A |=L � lub A |=L �.
Jeśli L ma własność spójników Boolowskich, to będziemy używać oznaczeń, od-
powiednio, Ź� oraz � (" � dla formuły �, o której mowa powyżej. W podobny sposób
określamy też pozostałe spójniki Boolowskie logiki L. Jest to oczywiście uproszczenie
notacyjne: dla pełnej poprawności trzeba byłoby używać np. symboli ŹL, ("L, itd.
Powiemy, że logika L ma własność relatywizacji, gdy dla każdej � oraz � " L(�)
oraz każdego jednoargumentowego predykatu U istnieje � " L(� *" {U}) takie, że:
(A, UA) |=L � wtedy i tylko wtedy, gdy [UA]A |=L �, dla wszystkich A " Str� oraz
wszystkich �-domkniętych podzbiorów UA ą" A = dom(A). Tutaj [UA]A jest pod-
strukturą A o uniwersum UA. Jeśli L ma własność relatywizacji, to niech �U oznacza
formułę �, o której mowa w powyższej definicji.
" " "
Przed sformułowaniem następnej własności logik abstrakcyjnych potrzebne będzie
przypomnienie pewnych faktów z semantyki KRP.
Przypomnijmy, że dla dowolnej �, dowolnego zbioru zdań Ś z L�� oraz symboli:
n-argumentowego predykatu P , n-argumentowego symbolu funkcyjnego F oraz stałej
indywidualnej c takich, że P " �, F " � oraz c " � mówimy, że:
/ / /
" formuła "v0 . . . "vn-1(P (v0, . . . , vn-1) a" �(v0, . . . , vn-1)) jest �-definicją P
w Ś;
" formuła "v0 . . . "vn-1"vn(F (v0, . . . , vn-1) = vn a" �(v0, . . . , vn-1, vn)) jest
�-definicją F w Ś, gdy Ś |= "!vn�(v0, . . . , vn-1, vn);
" formuła "v0(c = v0 a" �(v0)) jest �-definicją c w Ś, gdy Ś |= "!v0�(v0).
Jeśli " jest zbiorem �-definicji dla predykatów P " � - �, symboli funkcyjnych
F " � - � oraz stałych indywidualnych c " � - �, to dla każdej A " Str� takiej, że
A |= Ś istnieje dokładnie jedna struktura A" " Str�-� taka, że A" � = A oraz
A" |= ".
Rozważamy teraz sygnatury �" takie, że � ą" �" oraz " jest zbiorem �-definicji
symboli z �" - �.
Niech Ś będzie zbiorem zdań sygnatury �. Wtedy każdej formule � o n zmiennych
wolnych można przyporządkować formułę �" taką, że:
40
" Jeśli A " Str�, A |= Ś oraz a0, . . . , an-1 " dom(A), to: A" |= �[a0, . . . , an-1]
wtedy i tylko wtedy, gdy A |= �"[a0, . . . , an-1].
" Ś *" " |= � a" �".
W konsekwencji, jeśli A a" B, to A" a" B".
Powyższe fakty pozwalają na przejście od dowolnych sygnatur do sygnatur czysto
relacyjnych, tj. takich, które zawierają jedynie predykaty. Inaczej mówiąc, możemy
każdy n-argumentowy symbol funkcyjny f zamienić na n + 1-argumentowy symbol
relacyjny (predykat) F oraz każdą stałą indywidualną c zastąpić jednoargumentowym
predykatem C. Niech �r oznacza sygnaturę w ten sposób utworzoną z sygnatury �.
Każdej strukturze A " Str� przyporządkowujemy wtedy strukturę Ar określoną w
sposób następujący:
" Ar = dom(Ar) = A = dom(A);
" dla predykatów P " � niech: interpretacja P w Ar będzie identyczna z interpre-
tacją P w A;
Ar
" dla n-argumentowego symbolu funkcyjnego f " � niech F będzie wykresem
Ar
funkcji fA, czyli F (a0, . . . , an-1, an) wtedy i tylko wtedy, gdy
fA(a0, . . . , an-1) = an;
r
" dla stałej indywidualnej c " �, niech CA (a) wtedy i tylko wtedy, gdy cA = a.
Dla każdej formuły � o n zmiennych wolnych w języku o sygnaturze � istnieje
wtedy formuła �r w języku o sygnaturze �r taka, że dla wszystkich A oraz wszyst-
kich a0, . . . , an-1 " dom(A): A |= �[a0, . . . , an-1] wtedy i tylko wtedy, gdy Ar |=
�r[a0, . . . , an-1].
W konsekwencji, dla dowolnych A, B " Str�: A a" B wtedy i tylko wtedy, gdy
Ar a" Br.
Te wiadomości wystarczają do sformułowania następnej własności logik abstrak-
cyjnych.
" " "
Powiemy, że logika L dopuszcza zastąpienie symboli funkcyjnych oraz stałych
indywidualnych poprzez symbole relacyjne, gdy dla dowolnej �:
" dla każdej � " L(�) istnieje � " L(�r) taka, że dla wszystkich A " Str�:
A |=L � wtedy i tylko wtedy, gdy Ar |=L �.
Jeśli logika L ma powyższą własność, to formułę � istniejącą na mocy definicji
wyżej będziemy oznaczać przez �r.
Powiemy, że logika L jest regularna, gdy:
" L ma własność spójników Boolowskich;
" L ma własność relatywizacji;
41
" L dopuszcza zastąpienie symboli funkcyjnych oraz stałych indywidualnych po-
przez symbole relacyjne.
Następujące pojęcia przenosimy z KRP na wypadek logik abstrakcyjnych:
" zdanie � " L(�) nazywamy spełnialnym w logice L, gdy Mod� = ";

L

" zbiór Ś ą" L(�) nazywamy spełnialnym w logice L, gdy Mod� = ";

L
�"Ś
" zdanie � " L(�) nazywamy prawdziwym w logice L, gdy Mod� = Str�;
L
" piszemy Ś |=L �, gdy każdy L-model wszystkich zdań z Ś jest także L-mode-

lem � (czyli gdy Mod(Ś) = {Mod(�) : � " Ś} ą" Mod(�)).
Mówimy, że logika L ma własność:
" L�wenheima-Skolema, gdy każde zdanie L-spełnialne ma model przeliczalny.
" zwartości, gdy dla dowolnego Ś ą" L(�), jeśli każdy skończony podzbiór zbioru
Ś jest L-spełnialny, to Ś jest L-spełnialny.
2.2. Algebraiczna charakteryzacja elementarnej równoważności
Jest rzeczą ważną (oraz interesującą), że pojęcia semantyczne możemy charakte-
ryzować w terminach matematycznych. W szczególności, okazuje się, że podstawowe
pojęcia semantyczne mogą zostać scharakteryzowane w (prostych) terminach algebra-
icznych.
Niech A, B " Str�. Mówimy, że f jest częściowym izomorfizmem A w B, gdy:
" f jest injekcją o dziedzinie dom(f) zawartej w dom(A) oraz zbiorze wartości
rng(f) zawartym w dom(B)
" dla dowolnego n-argumentowego predykatu P " � oraz dowolnych elementów
A
a0, . . . , an-1 " dom(f): P (a0, . . . , an-1) wtedy i tylko wtedy, gdy
B
P (f(a0), . . . , f(an-1));
" dla dowolnego n-argumentowego symbolu funkcyjnego F " � oraz dowol-
A
nych a0, . . . , an-1 " dom(f): F (a0, . . . , an-1) = a wtedy i tylko wtedy,
B
gdy F (f(a0), . . . , f(an-1)) = f(a);
" dla dowolnej stałej indywidualnej c " � oraz a " dom(f): cA = a wtedy i tylko
wtedy, gdy cB = f(a).
Przez P art(A, B) będziemy oznaczać rodzinę wszystkich częściowych izomorfi-
zmów z A w B.
Gdy � jest czysto relacyjna oraz a0, . . . , an-1 " dom(A), b0, . . . , bn-1 " dom(B),
oraz f " P art(A, B) jest taki, że f(ai) = bi dla wszystkich i < n, to dla każdej for-
muły atomowej � o n zmiennych wolnych zachodzi: A |= �[a0, . . . , an-1] wtedy i
tylko wtedy, gdy B |= �[b0, . . . , bn-1].
42
Pojedyncze częściowe izomorfizmy nie zachowują jednak (w powyższym sensie)
dowolnych formuł. Jak się okaże, dopiero pewne rodziny częściowych izomorfizmów
pozwalają o takim zachowywaniu dowolnych formuł przesądzać, a tym samym rodziny
takie pozwalają scharakteryzować elementarną równoważność struktur relacyjnych.
Będziemy identyfikować odwzorowania z ich (teorio-mnogościowymi) wykresami,
czyli odwzorowanie f identyfikujemy z wykresem {(x, f(x)) : x " dom(f)}.
Powiemy, że A oraz B są skończenie izomorficzne, gdy istnieje ciąg (In)n"� o
następujących własnościach:
" Każdy In jest niepustym zbiorem częściowych izomorfizmów z A w B.
" Jeśli f " In+1 oraz a " dom(A), to istnieje g " In taki, że f ą" g oraz
a " dom(g).
" Jeśli f " In+1 oraz b " dom(B), to istnieje g " In taki, że f ą" g oraz
b " rng(g).
<"
Jeśli rodzina (In)n"� ma powyższe własności, to piszemy: (In)n"� : A B.
=
e
<"
Jeśli A oraz B są skończenie izomorficzne, to piszemy A B.
=
e
Powiemy, że A oraz B są częściowo izomorficzne, gdy istnieje zbiór I taki, że:
" I jest niepustym zbiorem częściowych izomorfizmów z A w B.
" Jeśli f " I oraz a " dom(A), to istnieje g " I taki, że f ą" g oraz a " dom(g).
" Jeśli f " I oraz b " dom(A), to istnieje g " I taki, że f ą" g oraz b " rng(g).
<"
Jeśli rodzina I ma powyższe własności, to piszemy: I : A B. Jeśli A oraz B są
=
p
<"
skończenie izomorficzne, to piszemy A B.
=
p
Zachodzą następujące fakty:
<" <"
" Jeśli A B, to A B.
= =
p
<" <"
" Jeśli A B, to A B.
= =
p e
<" <"
" Jeśli A B oraz A jest skończona, to A B.
= =
e
<" <"
" Jeśli A B oraz A i B są co najwyżej przeliczalne, to A B.
= =
p
Charakterystykę elementarnej równoważności, która nie odwołuje się do własności
języka podaje TWIERDZENIE FRA�SS� GO:
" Dla dowolnej skończonej � oraz A, B " Str�: A a" B wtedy i tylko wtedy, gdy
<"
A B.
=
e
Przypomnijmy pojęcie kwantyfikatorowego rzędu formuły:
" qr(�) = 0, gdy � jest atomowa;
" qr(Ź�) = qr(�)
43
" qr(� (" �) = max{qr(�), qr(�)} (podobnie dla innych funktorów dwuargu-
mentowych);
" qr("x�) = qr(�) + 1.
Powiemy, że struktury A oraz B są m-izomorficzne, gdy istnieje ciąg I0, . . . , Im
niepustych zbiorów częściowych izomorfizmów z A w B taki, że:
" Jeśli n + 1 m, f " In+1 oraz a " dom(A), to istnieje g " In taki, że f ą" g
oraz a " dom(g).
" Jeśli n + 1 m, f " In+1 oraz b " dom(B), to istnieje g " In taki, że f ą" g
oraz b " rng(g).
Jeśli I0, . . . , Im jest ciągiem o powyższych własnościach, to piszemy (In)n m :
<" <"
A B. Jeśli A oraz B są m-izomorficzne, to piszemy A B.
= =
m m
W dowodzie twierdzenia Fra�ss� go wykorzystujemy następujące fakty:
<"
" Niech (In)n"� : A B. Wtedy dla każdej formuły � o k zmiennych wolnych:
=
e
jeśli qr(�) n, f " In oraz a0, . . . ak-1 " dom(f):
A |= �[a0, . . . ak-1] wtedy i tylko wtedy, gdy B |= �[f(a0), . . . f(ak-1)].
<"
" Jeśli A B, to A oraz B spełniają te same zdania o rzędzie kwantyfikatoro-
=
m
wym m.
" Dla każdych n i r istnieje tylko skończenie wiele klas równoważności względem
relacji równoważności logicznej w zbiorze wszystkich formuł o r zmiennych
wolnych i o rzędzie kwantyfikatorowym n.
<"
" Jeśli A a" B, to A B.
=
e
" Jeśli A i B spełniają te same zdania o rzędzie kwantyfikatorowym m, to
<"
A B.
=
m
" Niech � będzie skończona i czysto relacyjna. Wtedy dla każdych struktur A, B "
Str� następujące warunki są równoważne:
<"
1. A B
=
m
2. A i B spełniają te same zdania o rzędzie kwantyfikatorowym m.
2.3. Twierdzenia Lindstr�ma
W tym punkcie rozważamy logiki regularne L takie, że L�� L. Pokażemy m.in.,
że L�� jest -maksymalną logiką o wybranych naturalnych własnościach.
Jeśli � jest zdaniem L�� sygnatury �, to przez �" będziemy oznaczać zdanie z L
o tych samych modelach, co �, czyli takie, że Mod� = Mod� (�"). Dla zbioru Ś
L�� L
zdań języka L�� (ustalonej sygnatury �) niech Ś" = {�" : � " Ś}.
44
I Twierdzenie Lindstr�ma
Zanim przejdziemy do dowodu twierdzenia Lindstr�ma udowodnimy kilka lema-
tów potrzebnych w tym dowodzie. Dowód twierdzenia Lindstr�ma nie jest całkiem
prosty  można go rozłożyć na części i śledzić uważnie każdą z tych części, a potem
uświadomić sobie, jak składają się one w całość.
LEMAT 1.
Jeśli L jest zwarta oraz Ś *" {�} jest zbiorem zdań logiki L sygnatury � takim, że
Ś |=L �, to istnieje skończony zbiór Ś0 ą" Ś taki, że Ś0 |=L �.
DOWÓD.
Niech L będzie zwarta. Ponieważ L ma własność spójników Boolowskich, istnieje
formuła Ź�. Dokładniej, powinniśmy pisać np.: ŹL�, ale ponieważ istotne dalej będą
jedynie własności semantyczne logiki, upraszczamy ten pedantyczny zapis.
Skoro Ś |=L �, to zbiór Ś *" {Ź�} nie jest spełnialny. Na mocy zwartości L,
istnieje skończony podzbiór Ś0 ą" taki, że Ś0 *"{Ź�} nie jest spełnialny. Wtedy jednak
Ś0 |=L �, co kończy dowód lematu 1.
LEMAT 2.
Niech L będzie zwarta oraz � " L(�). Wtedy istnieje skończony zbiór �0 ą" �
taki, że dla wszystkich A, B " Str�: jeśli A �0 <" B �0, to A |=L � wtedy i tylko
=
wtedy, gdy B |=L �.
DOWÓD.
Ograniczymy się do przypadku, gdy � jest czysto relacyjna (tylko taki przypadek
będzie nam póz
niej potrzebny).
Wybierzmy nowe symbole jednoargumentowe (predykaty): U, V oraz jednoar-
gumentowy symbol funkcyjny f. Zbudujemy teraz zbiór Ś zdań w sygnaturze � *"
{U, V, f},  mówiących , że f jest izomorfizmem podstruktury generowanej przez U
w podstrukturę generowaną przez V . Elementami Ś są:
" "x U(x)
" "x V (x)
" "x (U(x) V (f(x)))
" "y (V (y) "x (U(x) '" f(x) = y))
" "x"y ((U(x) '" V (y) '" f(x) = f(y)) x = y)
" "x1 . . . "xn ((U(x1)'". . .'"U(xn)) (R(x1, . . . , xn) a" R(f(x1), . . . , f(xn)))
(ostatni z warunków zapisujemy dla każdego n-argumentowego predykatu R " �).
Używamy tu symbolu = dla predykatu identyczności; nie należy go oczywiście mylić
z symbolem = używanym dla relacji identyczności w metajęzyku.
Wtedy zachodzi:
45
(1) Ś" |=L (�U a" �V ).
A
Udowodnimy (1). Jeśli A " Str� jest taka, że (A, UA, V , fA) |=L Ś" (czyli
A A
(A, UA, V , fA) |= Ś), to: UA oraz V są niepuste, a fA UA jest izomorfizmem
A
[UA]A na [V ]A. Przypominamy, że stosujemy następujące konwencje notacyjne:
" A oznacza dom(A)
" UA oznacza interpretację predykatu U w A
" [UA]A oznacza podstrukturę struktury A, której uniwersum jest zbiór UA i której
relacje otrzymujemy z relacji w A, ograniczając je do UA.
Na mocy własności izomorfizmu (zobacz: definicja logik abstrakcyjnych) mamy:
A
[UA]A |=L � wtedy i tylko wtedy, gdy [V ]A |=L �. Ponieważ L ma własność rela-
tywizacji (zobacz: definicja logik regularnych), więc: (A, UA) |=L �U wtedy i tylko
A
wtedy, gdy (A, V ) |=L �V . Ponieważ L ma własność spójników Boolowskich (zo-
bacz: definicja logik regularnych) oraz własność reduktów (zobacz: definicja logik abs-
A
trakcyjnych), więc: (A, UA, V , fA) |=L �U a" �V . To kończy dowód warunku (1).
Na mocy zwartości L otrzymujemy skończony zbiór Ś0 ą" Ś taki, że:
(2) Ś" |=L (�U a" �V ).
0
Ponieważ Ś składa się ze zdań pierwszego rzędu, możemy wybrać skończony zbiór
�0 ą" � taki, że Ś0 składa się z �0-zdań (czyli zdań z języka o sygnaturze �0). Poka-
żemy, że �0 spełnia tezę lematu 2.
Niech A, B " Str� i niech Ą : A �0 <" B �0. Możemy założyć, że dziedziny
=
tych struktur, czyli A i B są rozłączne: A )" B = ". Gdyby tak nie było, to wzięli-
byśmy izomorficzną kopię B o uniwersum rozłącznym zA, korzystając z własności
izomorfizmu (zobacz: definicja logik abstrakcyjnych).
C
Zdefiniujemy strukturę (C, UC, V , fC) " Str�*"{U,V,f}. Uniwersum tej struktury
to C = A *" B. Jej relacje (i jedną funkcję) definiujemy następująco:
" RC = RA *" RB dla R " � [uwaga: � jest czysto relacyjna]
" UC = A
C
" V = B
" fC definiujemy tak, aby fC UC = Ą.
C
Wtedy (C, UC, V , fC) jest modelem Ś0, a więc mamy także:
C
(C, UC, V , fC) |=L Ś".
0
C
Na mocy (2) dostajemy: (C, UC, V , fC) |=L (�U a" �V ).
C
Ponieważ [UC]C = A oraz [V ]C = B, więc (skoro L ma własność spójników
Boolowskich oraz relatywizacji): A |=L � wtedy i tylko wtedy, gdy B |=L �. To
kończy dowód lematu 2.
Niech A, B " Str�. Powiemy, że A jest L-równoważna z B, gdy dla każdego
�-zdania � z L: A |=L � wtedy i tylko wtedy, gdy B |=L �. Jeśli A i B są L-
równoważne, to piszemy A a"L B. Relacja elementarnej równoważności pokrywa się
z relacją L��-równoważności i będzie, jak dotychczas oznaczana przez a".
46
LEMAT 3.
Niech L będzie zwarta. Jeśli każde dwie elementarnie równoważne struktury są
także L-równoważne, to L <" L��.
DOWÓD.
Ponieważ L�� L (co zakładaliśmy na początku rozważań w całym tym punkcie),
więc musimy pokazać, że L L��, czyli że dla każdego � oraz każdego zdania
� " L(�) istnieje �-zdanie pierwszego rzędu � takie, że ModL (�) = ModL(�).
��
Niech � będzie zdaniem spełnialnym. W przeciwnym przypadku możemy wziąć
za � np. zdanie "x Źx = x i teza lematu będzie trywialnie spełniona.
Twierdzimy, że:
(1) Dla każdej A " ModL(�) istnieje �-zdanie �A " L(�) takie, że A |= �A
oraz �" |= �.
A
Dowód (1) przeprowadzimy metodą wprost. Niech A " ModL(�). Wtedy zacho-
dzi: T h(A)" |=L �. Jest tak, ponieważ jeśli B |=L T h(A)", czyli B |= T h(A), to
A a" B. Z założenia mamy A a"L B, a więc B |=L �.
Na mocy zwartości L istnieje liczba r oraz zdania �0, . . . , �r " T h(A) takie, że
{�", . . . , �"} |=L �. Niech �A będzie koniunkcją �0 '" . . . '" �r. Wtedy �A " T h(A),
0 r
czyli A |= �A oraz �" |=L �. To kończy dowód (1).
A
Na mocy (1) otrzymujemy teraz:

(2) ModL(�) = ModL(�" ).
A
A"ModL(�)
Pokażemy, że istnieją A0, . . . , An " ModL(�) takie, iż:
(3) ModL(�) = ModL(�" ) *" . . . *" ModL(�" ).
A0 A0
W przeciwnym przypadku (tj. gdyby (3) miało nie zachodzić), dla każdej skończo-
nej liczby modeli A0, . . . , An " ModL(�) mielibyśmy:
ModL(�" ) *" . . . *" ModL(�" ) ModL(�).
A0 A0
Wtedy każdy skończony podzbiór zbioru {Ź�} *" {Ź�" : A " ModL(�)} byłby
A
spełnialny, a więc na mocy zwartości L cały ten zbiór byłby spełnialny, co daje sprzecz-
ność z (2).
Na mocy (3) otrzymujemy:
ModL(�) = ModL (�A )*". . .*"ModL (�A ) = ModL (�A (". . .("�A ).
�� 0 �� n �� 0 n
Dla � o postaci �A (". . .("�A zachodzi zatem ModL = ModL(�). To kończy
0 n ��
dowód lematu 3.
I TWIERDZENIE LINDSTR�MA.
Niech L będzie regularna i L�� L. Jeśli L jest zwarta i ma własność L�wenheima-
Skolema, to L <" L��.
DOWÓD.
Wystarczy pokazać, że L L��.
Ponadto, na mocy lematu 3 wystarczy pokazać, że dla wszystkich �:
( ) Dla wszystkich A, B " Str�, jeśli A a" B, to A a"L B.
Możemy przy tym ograniczyć się do sygnatur relacyjnych �, z następującego po-
wodu. Jeśli ( ) zachodzi dla sygnatur relacyjnych �, to gdy A a" B przechodzimy
47
do �r, Ar oraz Br i otrzymujemy Ar a" Br. Teraz ( ) zachodzi dla sygnatur rela-
cyjnych �r i mamy: Ar a"L Br. Na mocy własności zamiany symboli funkcyjnych i
stałych indywidualnych na predykaty (zobacz: definicja logiki regularnej), dla dowol-
nego � " L(�) następujące warunki są równoważne:
" A |=L �
" Ar |=L �r
" Br |=L �r (ponieważ Ar a"L Br)
" B |=L �,
a zatem zachodzi A a"L B.
Dowód ( ) dla sygnatur relacyjnych � poprowadzimy nie wprost. Przypuśćmy, że
dla pewnych A, B " Str� oraz pewnej � " L(�):
(1) A a" B, A |=L � oraz B |=L Ź�
(jak pamiętamy, powinniśmy właściwie pisać np. ŹL; korzystamy z tego, że L ma
własność spójników Boolowskich).
Wybieramy � spełniającą (1) oraz (na mocy lematu 2) skończoną sygnaturę �0 ą"
�. Wtedy  znaczenie � zależy tylko od skończenie wielu symboli .
Skoro A a" B, to oczywiście także A �0 a" B �0, więc na mocy twierdzenia
Fra�ss� go struktury A �0 oraz B �0 są skończenie izomorficzne. Otrzymujemy
zatem, dla odpowiedniego (In)n"�:
(2) (In)n"� : A �0 <" B �0, A |=L �, B |=L Ź�.
=
e
Istota dowodu zasadza się w tym, aby otrzymać teraz (na mocy własności zwartości
oraz własności L�wenheima-Skolema) struktury przeliczalne A oraz B takie, że:
(3) A �0 <" B �0, A |=L �, B |=L Ź�.
=
p
Gdy otrzymamy (3), to twierdzenie będzie udowodnione: ponieważ przeliczalne
częściowo izomorficzne struktury A �0 oraz B �0 są izomorficzne, a zatem,
na mocy wyboru �0 mamy: A |=L � wtedy i tylko wtedy, gdy B |=L �, a to jest
sprzeczność z (3). Trzeba zatem odrzucić przypuszczenie dowodu nie wprost warunku
( ) i twierdzenie zachodzi.
Trzeba więc jedynie udowodnić (3). Dowód może sprawiać wrażenie nieco zawi-
łego. Będziemy, intuicyjnie mówiąc, podawać  opis warunku (2) w logice L.
Możemy założyć, że A i B, czyli dziedziny struktur A i, odpowiednio, B, są roz-
łączne. Pamiętajmy także, że sygnatura � jest czysto relacyjna.
Tworzymy sygnaturę �+ dodając do � nowe symbole:
" jednoargumentowy symbol funkcyjny f
" jednoargumentowe predykaty P, U, V
" dwuargumentowe predykaty <, I
" trójargumentowy predykat G.
48
Zbudujemy strukturę C " Str�+, której uniwersum C będzie zawierało uniwersa
struktur A oraz B, a także (jako elementy) wszystkie częściowe izomorfizmy In. W
ten sposób L  opisze skończoną izomorficzność (In)n"� : A �0 <" B �0.
=
e
Niech zatem:

" (a) C = A *" B *" � *" In
n"�
0
" (b) UC = A oraz [UC]C � = A
C C
0
" (c) V = B oraz [V ]C � = B
" (d) czyli fC(n + 1) = n, a fC(0) = 0

C
" (e) P = In
n"�
" (f) IC(n, p) wtedy i tylko wtedy, gdy n " � oraz p " In
C
" (g) GC(p, a, b) wtedy i tylko wtedy, gdy P (p), a " dom(p) oraz p(a) = b.
Teraz zbudujemy koniunkcję � skończenie wielu poniższych zdań (i) (viii) z L(�+),
dla której C będzie modelem.
" (i) "p (P (p) "x"y (G(p, x, y) (U(x) '" V (y))))
" (ii) "p (P (p) "x"y"u"v ((G(p, x, y) '" G(p, u, v)) (x = u '" y = v)))
" (iii) "p (P (p) "x1 . . . xn"y1 . . . yn ((G(p, x1, y1) '" . . . '" G(p, xn, yn))
(R(x1, . . . , xn) a" R(y1, . . . yn))))
dla każdego n-argumentowego predykatu R " �0
" (iv) aksjomaty częściowego porządku dla < oraz fakt,że pole < jest uporządko-
wane przez < wraz z funkcją poprzednika f:
"x ("y (y < x) (f(x) < x '" Ź"z (f(x) < z '" z < x)))
" (v) "x ("y (x < y (" y < x) "p (P (p) '" I(x, p)))
(czyli: jeśli x jest w polu <, to Ix = {p : P (p) '" I(x, p)} = ")

" (vi) "x"p"u ((f(x) < x '" I(x, p) '" U(u)) "q"v (I(f(x), q) '" G(q, u, v) '"
"x "y (G(p, x , y ) G(q, x , y ))))
(to jest, jak widać, własność rozszerzania częściowych izomorfizmów  w przód )
" (vii) "x"p"v ((f(x) < x '" I(x, p) '" V (v)) "q"u (I(f(x), q) '" G(q, u, v) '"
"x "y (G(p, x , y ) G(q, x , y ))))
(to jest, jak widać, własność rozszerzania częściowych izomorfizmów  w tył )
" (viii) "x U(x) '" "y V (y) '" �U '" (Ź�)V
C
(pamiętamy, że UC = A, V = B oraz A |=L � i B |=L Ź�).
49
Uwaga: tu (i wcześniej) używamy predykatu identyczności =, którego nie należy
mylić z (metajezykowym) symbolem relacji identyczności =.
Na mocy (i) (iii), G opisuje wykres częściowego izomorfizmu z �0-podstruktury
generowanej przez U w �0-podstrukturę generowaną przez V .
Wybieramy nową stałą indywidualną c. Termy c, f(c), f(f(c)), . . . będziemy ozna-
czać f0c, f1c, f2c, . . .. Niech � = {�} *" {fn+1c < fn; n " �}. Każdy skończony

podzbiór zbioru � ma model, a mianowicie model C = (C, cC ), gdzie cC jest wystar-
czająco dużą liczbą naturalną. Na mocy zwartości logiki L istnieje model (D, cD) dla
całego zbioru �. Zbiór D zawiera nieskończony ciąg . . . (f2c)D Nie możemy jednak skorzystać bezpośrednio z własności L�wenheima-Skolema, bo
dotyczy ona tylko pojedynczych zdań, a zbiór � jest nieskończonym zbiorem zdań.
Rozszerzamy teraz sygnaturę �+ *" {c} o nowy jednoargumentowy predykat Q.
Niech Ń będzie (�+ *" {c, Q})-zdaniem:
Q(c) '" "x (Q(x) (f(x) < x '" Q(f(x))))
(widać, że Q jest podzbiorem pola <: Q zawiera c i każdy element Q ma bezpośredni
poprzednik, który także należy do Q).
Niech QD = {(fnc)D : n " �}. Wtedy (D, cD, QD) |=L � '" Ń.
Ponieważ � '" Ń jest spełnialna, więc na mocy własności L�wenheima-Skolema
istnieje (co najwyżej) przeliczalny model (E, cE, QE) dla � '" Ń.
E
Skoro w E zachodzi (viii), to UE = " oraz V = ". Ponieważ � jest relacyjna,

E
więc UE oraz V są uniwersami podstruktur. Niech:
" A = [UE]E �
E
" B = [V ]E �.
Pokażemy, że (co najwyżej) przeliczalne struktury A oraz B spełniają (3).
Na mocy (viii) mamy: E |=L �U oraz E |=L (Ź�)V , a stąd otrzymujemy (na mocy
własności relatywizacji):
(4) A |=L �, B |=L Ź�.
E
Z warunków (i) (iii) wiemy, że każdy p " P odpowiada częściowemu izomor-
fizmowi z A �0 w B �0 (będziemy każdy taki częściowy izomorfizm oznaczać
przez p).
Ponieważ (E, cE, QE) |= Ń, więc dla każdego n " � element en = (fnc)E należy
do QE oraz elementy en tworzą ciąg zstępujący:
. . . e3 Niech I = {p : istnieje n taka, że IE(en, p)}. Na mocy (v) otrzymujemy, że
I = ". Na mocy (vi) oraz (vii) otrzymujemy, że I ma własność rozszerzania w przód i

w tył.
Dostajemy zatem:
(5) I : A �0 <" B �0.
=
p
Teraz (4) i (5) dają łącznie (3). Tym samym, dowód I twierdzenia Lindstr�ma jest
zakończony.
50
Udowodnimy jeszcze dwa lematy, który będą potrzebne w dowodzie II twierdzenia
Lindstr�ma.
LEMAT 4.
Niech L będzie logiką regularną, L�� L. Niech L będzie zwarta i niech ma
własność L�wenheima-Skolema. Niech wreszcie �0 będzie skończoną sygnaturą czy-
sto relacyjną, c stałą indywidualną spoza �0 oraz � niech będzie �0-zdaniem logiki L.
Niech dla każdego m " � istnieją struktury Am, Bm takie, że:
( ) Am <" Bm, Am |=L �, Bm |=L Ź�.
=
m
Wtedy istnieje �1-zdanie �1, gdzie �0 *" {<, c} ą" �1 oraz �1 jest skończona, takie,
że:
" (a) Jeśli A |=L �1, to (A, o skończonej liczbie " (b) Dla każdego m " � istnieje A taka, że A |= �1 oraz cA ma co najmniej m
DOWÓD.
W oznaczeniach poprzedniego dowodu, niech � = �0, �1 = �+ *" {c} oraz �1
niech będzie koniunkcją � i zdania stwierdzającego, że c leży w polu <.
Najpierw udowodnimy (b). Niech dla danego m " � struktury Am, Bm spełniają
( ) oraz niech (In)n m : Am <" Bm.
=
Definiujemy C tak, jak w dowodzie I twierdzenia Lindstr�ma, z następującymi mo-
dyfikacjami:
" (i)
C
" (ii) P = In.
n m
Niech cC = m. Wtedy (C, cC) spełnia (b).
Dla dowodu (nie wprost) (a), przypuśćmy, że istnieje model (D, cD) dla �1, w któ-
rym cD ma nieskończenie wiele Lindstr�ma, z (D, cD) otrzymujemy dwie izomorficzne struktury A i B takie, że:
A |=L � oraz B |=L Ź�. To daje sprzeczność (izomorficzne modele muszą spełniać
dokładnie te same zdania), a więc przypuszczenie dowodu nie wprost trzeba odrzucić.
Tym samym dowód (a) oraz całego lematu jest zakończony.
LEMAT 5.
Niech L będzie logiką regularną, L�� L. Niech � będzie skończoną sygnaturą
czysto relacyjną. Jeśli dla � " L(�) nie istnieje zdanie pierwszego rzędu o tych samych
modelach, co �, to dla każdego m " � istnieją struktury Am, Bm " Str� takie, że:
( ) Am <" Bm, Am |=L � oraz Bm |=L Ź�.
=
m
DOWÓD.
51
Załóżmy, że � jest spełnialna. W przeciwnym przypadku, teza lematu spełniona
jest trywialnie: ModL(�) = ModL ("v Źv = v).
��
Przeprowadzimy dowód nie wprost. Przypuśćmy, że dla pewnego m " � oraz
wszystkich struktur A, B " Str�:
<"
(1) jeśli A B, to A |=L � wtedy i tylko wtedy, gdy B |=L �.
=
m
Niech �0, . . . , �k będą wszystkimi nierównoważnymi logicznie zdaniami pierw-
szego rzędu o rzędzie kwantyfikatorowym m. Pamiętamy, że jeśli � będzie skoń-
czoną sygnaturą czysto relacyjną, to istnieje tylko skończenie wiele takich nierówno-
ważnych logicznie formuł (dowodzimy tego faktu w KRP, przez indukcję po złożoności
formuł). Wtedy:
<"
(2) A B wtedy i tylko wtedy, gdy dla wszystkich 0 i k mamy:
=
m
A |= �i wtedy i tylko wtedy, gdy B |= �i.
Dla A " Str� niech �A będzie koniunkcją wszystkich zdań ze zbioru:
{�i : 0 i k '" A |= �i} *" {Ź�i : 0 i k '" A |= Ź�i}.
Na mocy (2) mamy wtedy, dla dowolnej B:
<"
(3) A B wtedy i tylko wtedy, gdy B |= �A.
=
m
Niech � będzie alternatywą (skończenie wielu!) zdań �A, dla których zachodzi
A |= �, czyli � jest zdaniem:

(4) {�A : A " Str� '" A |= �}.
Pokażemy, że:
(5) ModL(�) = ModL (�)
��
i uzyskamy sprzeczność z przypuszczeniem dowodu nie wprost.
Jeśli B jest modelem �, to �B należy do alternatywy (4) (jest jednym z jej czło-
nów). Ponieważ B |= �B, więc B |= �.
Jeśli, z drugiej strony, B |= �, to (na mocy (4)) istnieje A taka, że A |=L � oraz
<"
B |= �A. Na mocy (3) mamy wtedy A B, a na mocy (1) mamy B |=L �.
=
m
Mamy stąd sprzeczność, gdyż równoważność: B |=L � wtedy i tylko wtedy, gdy
B |= � oznacza, że ModL(�) = ModL (varphi). Tak więc, przypuszczenie do-
��
wodu nie wprost musimy odrzucić, co kończy dowód lematu 5.
II Twierdzenie Lindstr�ma
Przed sformułowaniem II twierdzenia Lindstr�ma trzeba wprowadzić kilka pojęć,
których twierdzenie to dotyczy. Zakładamy, że czytelnik ma podstawowe wiadomości
dotyczące elementarnej teorii rekursji, a więc że zna np. pojęcie zbioru rekurencyjnego,
zbioru rekurencyjnie przeliczalnego, funkcji rekurencyjnej, itp.
Powiemy, że logika L jest efektywna, gdy dla każdej rekurencyjnej sygnatury �
zbiór L(�) jest rekurencyjny oraz dla każdego zdania � " L(�) istnieje skończona
�0 ą" � taka, że � " L(�0).
Niech logiki L i L będą efektywne. Piszemy:
" (a) L eff L wtedy i tylko wtedy, gdy istnieje funkcja rekurencyjna F taka, że
dla każdego � " L(�) mamy: F (�) " L (�) oraz Mod� (�) = Mod� (F (�)).
L L
52
" (b) L <"eff L wtedy i tylko wtedy, gdy L eff L oraz L eff L. Jeśli
L <"eff L , to mówimy, że L i L są efektywnie równoważne.
Dla przykładu:
" L��, logika drugiego rzędu L2, słaba logika drugiego rzędu Lw2, logika L(Q1)
(czyli logika z kwantyfikatorem  istnieje nieprzeliczalnie wiele ) są efektywne
" L� � nie jest efektywna
1
" L�� eff Lw2
" Lw2 eff L2.
Mówimy, że logika L jest efektywnie regularna, gdy L jest efektywna oraz dla
każdej rekurencyjnej sygnatury � zachodzą następujące warunki:
" (i) istnieją funkcje rekurencyjne � Ź� oraz (�, �) � (" � (i podobnie dla
pozostałych spójników)
" (ii) dla każdego jednoargumentowego predykatu U istnieje funkcja rekurencyjna
� �U
" (iii) istnieje funkcja rekurencyjna � �r (przy tym sygnatura �r musi być
rekurencyjna).
Niech logika L będzie efektywna. Mówimy, że zbiór zdań prawdziwych logiki
L jest rekurencyjnie przeliczalny, gdy dla każdej rekurencyjnej sygnatury � zbiór
{� " L(�) : " |=L �} jest rekurencyjnie przeliczalny. Mówiąc, że ten ostatni zbiór
jest rekurencyjnie przeliczalny mamy oczywiście na myśli to, że zbiór kodów jego
elementów (uzyskanych przez jakąś funkcję rekurencyjną, czyli np. przez numerację
G�dlowską) jest rekurencyjnie przeliczalny.
II TWIERDZENIE LINDSTR�MA
Niech L będzie efektywnie regularna i L�� eff L. Jeśli L ma własność L�wen-
heima-Skolema oraz zbiór zdań prawdziwych logiki L jest rekurencyjnie przeliczalny,
to L�� <"eff L.
DOWÓD.
Niech L spełnia założenia twierdzenia. Pokażemy, że L eff L�� w dwóch kro-
kach:
" (") Najpierw pokażemy, że spełniony jest następujący warunek:
( ) Dla każdej rekurencyjnej sygnatury � oraz każdego � " L(�) istnieje
� " L��(�) takie, że ModL(�) = Mod(�).
" ("") Potem pokażemy, że przejście od � do Ć jest efektywne.
53
Ponieważ L jest efektywna, więc wystarczy rozważać skończone sygnatury re-
kurencyjne. Ponieważ dla L istnieje efektywny odpowiednik własności zastępowania
symboli funkcyjnych i stałych indywidualnych przez predykaty, możemy ograniczyć
się do sygnatur � czysto relacyjnych.
Niech zatem � będzie: rekurencyjna, skończona i relacyjna.
Poprowadzimy dowód kroku (") metodą nie wprost, korzystając z lematów 4 i 5
oraz z Twierdzenia Traktenbrota.
Przypuszczamy zatem, że ( ) nie zachodzi, czyli że � " L(�) oraz że żadne
zdanie pierwszego rzędu nie ma dokładnie tych samych modeli co �.
Na mocy lematu 5, dla każdej m istnieją Am, Bm " Str� takie, że:
" Am <" Bm
=
m
" Am |=L �
" Bm |=L Ź�.
Spełnione są więc założenia lematu 4. Istnieją zatem: sygnatura �1 oraz zdanie �1
z tezy tego lematu.
Rozszerzamy �1 przez dodanie jednoargumentowego predykatu W i rozważamy
zdanie Ń " L(�1 *" {W }) o następującej postaci:
�1 '" "x W (x) '" "x (W (x) x < c).
Na mocy własności zdania �1 mamy wtedy:
A
" (a) Jeśli A " Str� *"{W } oraz A |=L Ń, to zbiór W jest niepusty i skończony.
1
A
" (b) Dla każdej m 1 istnieje A taka, że A |= Ń oraz W ma dokładnie m
elementów.
A
Tak więc, jeśli A przebiega wszystkie modele Ń, to W przebiega wszystkie (nie-
puste) zbiory skończone (pamiętajmy, że wszystkie rozważane logiki mają własność
izomorfizmu).
Z powyższych warunków (a) i (b) otrzymamy sprzeczność z przypuszczeniem do-
wodu nie wprost.
Na mocy twierdzenia Traktenbrota istnieje rekurencyjna i skończona sygnatura �2
taka, że zbiór wszystkich �2-zdań prawdziwych we wszystkich strukturach skończo-
nych (tej sygnatury) nie jest zbiorem rekurencyjnie przeliczalnym.
Możemy założyć, że �2 jest czysto relacyjna i rozłączna z �1 *" {W }.
Niech F będzie odwzorowaniem rekurencyjnym � F (�), ze zbioru L(�2) w
L(�2) taką, że Mod(�) = Mod(F (�)). Wtedy dla wszystkich zdań � " L(�2):
" ( ) � jest prawdziwe we wszystkich strukturach skończonych (sygnatury
�2) wtedy i tylko wtedy, gdy |=L Ń (F (�))W .
Aby udowodnić równoważność ( ), trzeba dowieść implikacji prostej oraz odwrot-
nej.
54
�! Niech � będzie prawdziwe we wszystkich strukturach skończonych oraz A "
A
Str� *"{W }*"�2 będzie taka, że A |=L Ń. Na mocy (a), W jest niepusty i skończony, a
1
A A
2 2
więc [W ]A � |=L �, a stąd [W ]A � |=L F (�). Wtedy A �2 |=L (F (�))W .
A
�! Na mocy (b), dla każdej m 1 istnieje A taka, że A |= Ń i W ma dokładnie
2
m elementów. Stąd A |=L (F (�))W , czyli A |=L �W . W konsekwencji, [A]A � |= �.
To kończy dowód ( ), a tym samym dowód kroku (").
�
Przechodzimy do dowodu kroku (""). Niech gL będzie funkcją rekurencyjną, przy-
pisującą numery (np. numery G�dlowskie) zdaniom logiki L, czyli zdaniom ustalonej
sygnatury rekurencyjnej �. Na mocy faktu, że zbiór zdań prawdziwych logiki L jest
rekurencyjnie przeliczalny, dla każdej rekurencyjnej sygnatury � istnieje dwuargumen-
towa relacja rekurencyjna, powiedzmy R, taka, że dla wszystkich zdań � " L(�):
�
" |=L � wtedy i tylko wtedy, gdy "m R(m, gL(�)).
Ustalmy wyliczenie �n : n " � wszystkich �-zdań logiki L�� takie, że przypo-
�
rządkowanie n gL (�n) jest rekurencyjne. Niech G będzie funkcją rekurencyjną
��
taką, że dla �-zdań logiki L:
� �
" G(gL(�)) = ((� m, n )R(m, gL(� a"L (�n)L)))1
(tu jest np. pierwotnie rekurencyjną funkcją kodującą (pary) Cantora, a ()1 jest pier-
wotnie rekurencyjną funkcją rzutu, na pierwszy argument pary; � x [. . .] jest efektyw-
nym �-operatorem, czytanym:  najmniejsze x takie, że [. . .] ). Powyżej zaznaczyliśmy
wyraz
nie, że bierzemy spójnik równoważności z logiki L oraz, że rozważamy  prze-
kład formuły �n na stosowne zdanie logiki L.
�
Niech �" będzie formułą �G(g (�)). Wtedy rekurencyjne odwzorowanie � �"
L
poświadcza, że L eff L��.
Dowód II twierdzenia Lindstr�ma został tym samym zakończony.
Przypomnijmy jeszcze sformułowanie twierdzenia Traktenbrota, na które powołu-
jemy się w powyższym dowodzie (jego dowód podajemy w Preliminariach matema-
tycznych, w dziale dotyczącym matematycznych modeli obliczalności).
TWIERDZENIE TRAKTENBROTA. Istnieje skończona sygnatura � taka,
że zbiór wszystkich zdań (języka KRP o sygnaturze �) prawdziwych we
wszystkich strukturach skończonych należących do Str� nie jest rekuren-
cyjnie przeliczalny.
Oprócz powyższych twierdzeń Lindstr�ma, znaleziono cały szereg innych jeszcze
twierdzeń, charakteryzujących logiki abstrakcyjne maksymalne jeśli chodzi o wybrane
zestawy własności. Twierdzenia te dotyczą zarówno logik z uogólnionymi kwantyfika-
torami, jak i logik infinitarnych. Także logiki wyższych rzędów mogą być oczywiście
traktowane jako logiki abstrakcyjne w omówionym wyżej sensie.
55
2.4. Kilka przykładów
Wspominaliśmy już na Seminarium Zakładu Logiki Stosowanej UAM o logikach
z uogólnionymi kwantyfikatorami. Dla przypomnienia, podajmy garstkę informacji o
niektórych takich logikach.
Mostowski rozważał tzw. kwantyfikatory numeryczne Qą, gdzie ą jest liczbą po-
rządkową. Znaczenie formuły Qąx�(x) określa się następująco:
" M |= Qąx�(x) wtedy i tylko wtedy, gdy zbiór {a " dom(M) : M |= �(x)[a]}
ma moc nie mniejszą od 5!ą.
W szczególności, Q0 jest kwantyfikatorem, za pomocą którego wyrazić można po-
jęcia: nieskończenie wiele oraz skończenie wiele, ponieważ formuła Q0x�(x) jest speł-
niona w strukturze M wtedy i tylko wtedy, gdy w dom(M) istnieje co najmniej 5!0
obiektów, spełniających formułę �(x). Jak pamiętamy z elementarnego kursu logiki,
pojęć tych nie można wyrazić w klasycznej logice pierwszego rzędu.
Mostowski formułuje pewne warunki, które muszą być spełnione, aby tak wprowa-
dzone pojęcie miało porządną (i zamierzoną) semantykę. Do warunków takich należy
to, że jeśli M |= Qąx�(x) oraz struktury M i N są izomorficzne, to zachodzi również
N |= Qąx�(x). Odpowiada to intuicjom związanym z kwantyfikatorem (numerycz-
nym): ma on charakteryzować jedynie liczbę obiektów, nie przesądzając niczego o ich
jakości.
Kwantyfikatory numeryczne Mostowskiego rozumieć można w sposób relacyjny:
kwantyfikatorem (jednoargumentowym) jest rodzina Q par zbiorów (U, X), gdzie X ą"
U oraz jeśli (U, X) " Q i |X| = |Y |, |U - X| = |V - Y |, to (V, Y ) " Q. Symbol |X|
oznacza, przypomnijmy, moc zbioru X. Dla przykładu:
Q0 = {(U, X) : |X| 5!0}.
Kwantyfikatory tak rozumiane mogą być traktowane jako operacje Q spełniające
następujące warunki:
- -
) ).
" Jeśli �(x, y jest formułą, to formułą jest również Qx�(x, y
- -
)[b, ]
" M |= Qx�(x, y a wtedy i tylko wtedy, gdy:
- -
)[b, ]})
(dom(M), {b : M |= �(x, y a " Q.
Jeśli L�� oznacza klasyczną logikę pierwszego rzędu, to niech L��(Q) oznacza
jej rozszerzenie otrzymane przez dodanie tak rozumianego kwantyfikatora Q.
Mostowski udowodnił, że L��(Q0) nie jest (efektywnie) aksjomatyzowalna. Niech
� będzie zdaniem:
"xŹQ0y (y < x)
języka L��(Q0) i niech  będzie aksjomatyką arytmetyki Peana (w języku L��), a
N0 modelem standardowym tej arytmetyki. Wtedy dla każdego zdania Ć języka L��
mamy:
56
" N0 |= Ć wtedy i tylko wtedy, gdy dla każdego M, jeśli M |= , to
M |= (� Ć).
Ponieważ, jak wiadomo, nie ma efektywnej procedury arytmetycznej dla rozstrzy-
gania lewej strony tej równoważności, więc nie istnieje pełna metoda dowodowa dla
L��(Q0).
Postawiony przez Mostowskiego problem, czy L��(Q1) jest aksjomatyzowalna
został rozwiązany przez Keislera.
Mostowski podał także teorio-modelową charakterystykę kwantyfikatorów pierw-
szego rzędu: dowolne rozszerzenie logiki pierwszego rzędu otrzymane przez dodanie
jednoargumentowego kwantyfikatora, które spełnia warunek:
" każde zdanie, które ma model nieskończony, ma też model każdej mocy nieskoń-
czonej
jest równoważne z logiką pierwwszego rzędu.
Ujęcie Mostowskiego doczekało się wkrótce uogólnienia, w pracach Lindstr�ma
(1969), gdzie rozważa się nie tylko kwantyfikatory jednoargumentowe, lecz również
wieloargumentowe. Takimi są, dla przykładu:
" KWANTYFIKATOR H�RTIGA. I = {(U, X, Y ) : |X| = |Y |}
" KWANTYFIKATOR RESCHERA. R = {(U, X, Y ) : |X| |Y |}.
Te kwantyfikatory nie mogą zostać wyrażone w formalizmie Mostowskiego. Defi-
nicja Lindstr�ma ma, w uproszczeniu, postać następującą:
(Lokalnym) kwantyfikatorem uogólnionym na M typu k1, . . . , kn nazywamy do-
1 n
wolną n-arną relację pomiędzy podzbiorami Mk , . . . , Mk .
Uogólnionym kwantyfikatorom poświęciliśmy osobny wykład. W większości przy-
padków była mowa o tzw. kwantyfikatorach uogólnionych monadycznych binarnych,
czyli typu 1, 1 .
Kwantyfikatory rozważane przez Mostowskiego były typu 1 , kwantyfikatory H�r-
tiga i Reschera są typu 1, 1 .
W 1959 roku Henkin rozważał inne rodzaje kwantyfikatorów, różne od kwantyfi-
katorów numerycznych Mostowskiego.
Pamiętamy, że przy tworzeniu prefiksowej postaci normalnej formuły języka ra-
chunku predykatów wszystkie kwantyfikatory poprzedzają matrycę formuły. Przy sko-
lemizacji takiej formuły eliminujemy kwantyfikatory egzystencjalne, wprowadzając
nowe symbole funkcyjne (dla funkcji Skolema).
Symbol funkcyjny f wprowadzony przez eliminację kwantyfikatora " z prefiksu
kwantyfikatorowego Q1Q2 . . . Qn (gdzie Qi są kwantyfikatorami klasycznymi: " oraz
") ma tyle argumentów, ile kwantyfikatorów ogólnych poprzedza ów eliminowany
kwantyfikator " w prefiksie Q1Q2 . . . Qn. Powstaje problem, czy ta procedura dobrze
opisuje sytuacje, w których dokonujemy wyborów niezależnych. Henkin wprowadził
uogólnienie tej procedury, dopuszczając prefiksy częściowo uporządkowane lub ina-
czej prefiksy rozgałęzione, za pomocą których można wyrazić zależności, których nie
można przedstawić w sposób liniowy. Kwantyfikator Henkina ma postać następującą:
57

"x  "y


Ć(x, y, u, v)

"u  "v
Częściowy porządek prefiksu ma oddawać sytuację, gdy dokonujemy wyborów
niezależnych. Semantykę dla tego kwantyfikatora ustala się następująco:
Kwantyfikator Henkina to kwantyfikator typu 4 taki, że:
H = {R ą" M4 : istnieją funkcje f, g na M takie,że
dla dowolnych a, b " M (a, f(a), b, f(b)) " R}.
Język z kwantyfikatorem Henkina ma moc wyrażania istotnie większą niż język
klasycznego rachunku predykatów. Można pokazać, że kwantyfikator Q0 Mostow-
skiego jest definiowalny przez kwantyfikator Henkina. Pojęcie  mocy wyrażania ję-
zyka było objaśnione wcześniej
Dalszych uogólnień dokonał w latach siedemdziesiatych XX wieku Barwise. Roz-
ważał m.in. rozgałęzione prefiksy, w których występowały uogólnione kwantyfikatory
(w sensie Lindstr�ma).
Oto jeszcze kilka dalszych kwantyfikatorów uogólnionych:
"M = {M},
"M = {X ą" M : X = "},

("e"n)M = {X ą" M : |X| e" n},
(Qą)M = {X ą" M : |X| e" 5!ą},
(QR)M = {X ą" M : |X| > |M - X|}, (Kwantyfikator Reschera),
(QR)M = {X ą" M : |X| = |M|}, (Kwantyfikator Changa).
Widać zatem, że również  zwykłe kwantyfikatory można uważać za kwantyfika-
tory uogólnione (co jest dość oczywiste  dobre uogólnienie powinno uwzględniać
przypadki wyjściowe).
Przez LQ oznaczać teraz będziemy język KRP z kwantyfikatorem Q. Interpretacje
LQ wyznaczone będą przez semantyczną charakterystykę Q. Dla języka LQ z ustaloną
interpretacją semantyczną Q będziemy też używać terminu  logika LQ . Niech 5!ą bę-
dzie ą-tą mocą nieskończoną (gdzie ą jest liczbą porządkową). Zamiast 5!0 piszemy
czasem �. Jeśli �,  są nieskończonymi liczbami kardynalnymi, to przez L� rozu-
miemy język w którym dopuszczalne są koniunkcje i alternatywy długości mniejszej
niż � oraz prefiksy kwantyfikatorowe długości mniejszej niż . Tak więc, L�� to ję-
zyk KRP, klasycznej logiki pierwszego rzędu. Przez L" rozumiemy język, w którym
dopuszczalne są koniunkcje i alternatywy dowolnej długości oraz prefiksy kwantyfika-
torowe długości mniejszej niż .
KWANTYFIKATOR  ISTNIEJE NIESKOC
CZENIE WIELE
Wyrażenie Q0x ą(x) czytamy: istnieje nieskończenie wiele x takich, że ą(x).
Semantyka Q0 wyznaczona jest przez warunek:
A |= Q0x ą(x) wtedy i tylko wtedy, gdy zbiór {a " dom(A) : A |= ą[a]} jest
nieskończony.
Oto niektóre własności LQ :
0
58
" Standardowy model arytmetyki PA można scharakteryzować w LQ z dokładno-
0
ścią do izomorfizmu.
Wystarczy do aksjomatów dyskretnego liniowego porządku < dodać aksjomat:
"xŹQ0y y < x.
" W LQ nie zachodzi górne twierdzenie L�wenheima-Skolema.
0
" LQ nie jest aksjomatyzowalna.
0
" W LQ nie zachodzi twierdzenie o zwartości.
0
" W LQ zachodzi dolne twierdzenie L�wenheima-Skolema.
0
" Pełność (systemu dowodowego z nieskończonymi dowodami) dla LQ można
0
otrzymać przez dodanie reguły infinitarnej:
" 1x ą(x), " 2x ą(x), . . .
.
Q0x ą(x)
" Dowolna przeliczalna 5!0-kategoryczna teoria w LQ bez modeli skończonych
0
jest zupełna.
" Teoria gęstych liniowych porządków jest zupełna w LQ .
0
" LQ jest fragmentem L� �, co widać z równoważności:
0 1

Q0x ą(x) a" " nx ą(x).
n<�
KWANTYFIKATOR  ISTNIEJE NIEPRZELICZALNIE WIELE
Wyrażenie Q1x ą(x) czytamy: istnieje nieprzeliczalnie wiele x takich, że ą(x).
Semantyka Q1 wyznaczona jest przez warunek:
A |= Q1x ą(x) wtedy i tylko wtedy, gdy zbiór {a " dom(A) : A |= ą[a]} jest
nieprzeliczalny.
Ograniczamy się do interpretacji nieprzeliczalnych.
Tak jak w LQ definiowalne jest pojęcie skończoności, tak w LQ definiowalne jest
0 1
pojęcie przeliczalności.
Oto niektóre własności LQ :
1
" Teoria gęstych liniowych porządków nie jest zupełna w LQ .
1
" Górne twierdzenie L�wenheima-Skolema nie zachodzi w LQ . Dolne twierdze-
1
nie LS zachodzi w następującej wersji: jeśli teoria w LQ (mocy co najwyżej 5!1)
1
ma model, to ma model mocy 5!1.
" Każda 5!1-kategoryczna teoria w LQ (mocy co najwyżej 5!1) jest zupełna.
1
" Teoria ciał algebraicznie domkniętych charakterystyki zero jest zupełna w LQ .
1
59
" LQ jest (!) aksjomatyzowalna.
1
KWANTYFIKATOR CHANGA
Wyrażenie Qcx ą(x) czytamy: istnieje tyle x takich, że ą(x) ile jest obiektów w
całym uniwersum.
Semantyka Qc wyznaczona jest przez warunek:
A |= Qcx ą(x) wtedy i tylko wtedy, gdy zbiór {a " dom(A) : A |= ą[a]} ma taką
samą moc, jak zbiór dom(A).
Oto niektóre własności LQ :
c
" W modelach mocy 5!1 kwantyfikator Qc ma taką samą interpretację, jak kwan-
tyfikator Q1.
" Teoria gęstych porządków liniowych nie jest zupełna w LQ .
c
" Teoria ciał algebraicznie domkniętych charakterystyki zero jest zupełna w LQ .
c
[Teoria ta dopuszcza eliminację kwantyfikatorów " i Qc.]
" Jeśli przeliczalna teoria w LQ ma model, którego moc jest liczbą kardynalną
c
następnikową, to ma model mocy 5!1.
" Jeśli przeliczalna teoria w LQ ma model mocy 5!0, to ma modele każdej mocy
c
nieskończonej.
" Niech V al1 będzie zbiorem wszystkich zdań LQ prawdziwych w modelach
c
mocy 5!1 i niech V al� będzie zbiorem wszystkich zdań LQ prawdziwych w
c
modelach mocy 5!�. Wtedy (przy założeniu uogólnionej hipotezy kontinuum):
1. V al1 oraz V al� są rekurencyjnie przeliczalne.
2. V al1 )" V al� jest zbiorem wszystkich LQ -tautologii.
c
KWANTYFIKATOR  JEST WI
CEJ A NIŻ B
Wyrażenie QM x ą(x)�(x) czytamy: jest więcej x takich, że ą(x) niż x takich, że
�(x).
Semantyka QM wyznaczona jest przez warunek:
A |= QM x ą(x)�(x) wtedy i tylko wtedy, gdy moc zbioru {a " dom(A) : A |=
ą[a]} jest większa od mocy zbioru {a " dom(A) : A |= �[a]}.
Oto niektóre własności LQ :
M
" Standardowy model arytmetyki PA można scharakteryzować w LQ z dokład-
M
nością do izomorfizmu.
" LQ nie jest aksjomatyzowalna.
M
" W LQ nie zachodzi: ani dolne ani górne twierdzenie L�wenheima-Skolema,
M
ani twierdzenie o zwartości.
" Q0 oraz Qc są definiowalne w LQ .
M
60
" LQ jest logiką o znacznej  mocy wyrażania : można w niej sformułować np.
M
zdanie, które ma model wtedy i tylko wtedy, gdy fałszywa jest uogólniona hipo-
teza kontinuum.
KWANTYFIKATOR HENKINA
Wyrażenie QH(x, y, u, v)ą(x, y, u, v) jest skrótem dla formuły z następującym
częściowo uporządkowanym prefiksem kwantyfikatorowym:

"x  "y


ą(x, y, u, v)

"u  "v
Semantyka dla tego kwantyfikatora wyznaczona jest przez warunek:
A |= QHxyuv ą(x, y, u, v) wtedy i tylko wtedy, gdy istnieją funkcje f oraz g
(określone na dom(A) i o wartościach w dom(A)) takie, że A |= ą(x, f(x), u, g(u)).
Oto niektóre własności LQ :
H
" Kwantyfikatory Q0, Qc oraz QM są definiowalne w LQ .
H
" LQ nie jest aksjomatyzowalna.
H
" W LQ nie zachodzi twierdzenie o zwartości.
H
" W LQ nie zachodzi ani dolne, ani górne twierdzenie L�wenheima-Skolema.
H
Widzimy więc, że również LQ ma znaczną  moc wyrażania .
H
" " "
Niektóre z wymienionych wyżej logik (z uogólnionymi kwantyfikatorami) są upo-
rządkowane następująco pod względem mocy wyrażania (strzałka oznacza zachodze-
nie relacji z"):
LQ LI
0

L�� LQ LH
M

LQ LQ
R w
(tu I jest kwantyfikatorem H�rtiga, a Qw jest kwantyfikatorem większości most:
Qwxą(x)�(x) ma semantykę odpowiadającą warunkowi, że większość obiektów, które
spełniają ą(x), spełnia �(x)).
" " "
Na początku drugiej połowy XX wieku rozpoczęto również intensywne badania
logik infinitarnych. Wspominaliśmy już, że pewne pojęcia są niewyrażalne w L��,
czyli w klasycznej logice pierwszego rzędu. Są one natomiast wyrażalne w Lą�, dla
stosownie dobranych ą oraz �. Przypomnijmy parę przykładów:
61
" w L� � scharakteryzować można model standardowy arytmetyki Peana;
1
" w L� � scharakteryzować można klasę wszystkich zbiorów skończonych;
1
" teoria uporządkowanych ciał archimedesowych jest w L� � skończenie aksjo-
1
matyzowalna;
" predykat prawdziwości formuł języka o przeliczalnej liczbie symboli jest defi-
niowalny w L� �;
1
" pojęcie dobrego porządku nie jest definiowalne w L� �, jest natomiast definio-
1
walne (pojedynczą formułą) w L� �1.
1
Jak wiadomo, logiki infinitarne, w których dopuszcza się nieskończone prefiksy
kwantyfikatorowe są bliższe logice drugiego rzędu, z wszelkimi tego faktu konsekwen-
cjami, a więc, w szczególności, brakiem pełności. Dla L� �1 zachodzi twierdzenie
1
Scotta o niedefiniowalności predykatu prawdziwości w tymże języku; definiowalność
jest tu rozumiana w odpowiedni sposób, z wykorzystaniem kodowań w klasie wszyst-
kich zbiorów dziedzicznie przeliczalnych. Wśród logik infinitarnych o skończonych
prefiksach kwantyfikatorowych szczególne miejsce zajmuje L� �. Zachodzi w niej
1
twierdzenie o pełności, gdy na obecną w niej infinitarną regułę wnioskowania pozwa-

lającą wywnioskować koniunkcję Ś ze zbioru przesłanek Ś narzucimy warunek,
aby Ś był przeliczalny. Warunek ten jest istotny: istnieje nieprzeliczalny zbiór zdań
języka L� �, który nie ma modelu, a którego każdy przeliczalny podzbiór ma model.
1
Przykład ten pokazuje jednocześnie, że ani w L� �, ani w żadnej z logik Lą�, gdzie
1
ą �1, nie zachodzi twierdzenie o zwartości. Rozważano jednak stosowne modyfika-
cje tego twierdzenia i wykazano, iż zachodzenie tych uogólnionych wersji twierdzenia
o zwartości powiązane jest z istnieniem dużych liczb kardynalnych.
W L� � dowolną przeliczalną strukturę z przeliczalną liczbą relacji można scha-
1
rakteryzować z dokładnością do izomorfizmu, jak wiadomo ze słynnego twierdzenia
Scotta o izomorfizmie. Własności semantyczne modeli dla logik Lą� i L"� (np. ele-
mentarną równoważność) można charakteryzować metodami algebraicznymi (twier-
dzenie Karp o częściowych izomorfizmach).
Pierwsze zastosowania infinitarnych reguł inferencji znalez
ć można (w mniej lub
bardziej świadomej formie) m.in. w pracach Poincar�go, L�wenheima, Carnapa (zob.
też np. podręcznik Ajdukiewicza z 1928 roku). Wraz z wyborem finitystycznego para-
dygmatu logiki pierwszego rzędu reguły takie usunięte zostają z tego paradygmatu.
Dołączenie do aparatury inferencyjnej �-reguły pozwala, jak wiadomo, przeprowa-
dzić w przypadku pewnych teorii dowody ich zupełności. W przypadku pewnych teorii
jednak nawet tak silne środki dowodowe nie wystarczają: porównajmy w tym kon-
tekście uwagi Mostowskiego (Mostowski 1967, s. 110; w pierwszym akapicie autor
odnosi się do  z góry skazanych na niepowodzenie  prób uzyskania jakiejś charak-
terystyki teorii mnogości przy użyciu infinitarnych metod dowodowych, w drugim 
do prób mocniejszego ugruntowania teorii mnogości np. w logice drugiego rzędu):
Wszystkie te wyniki pokazują, że teoria mnogości oparta na aksjomatyce Zermelo-
Fraenkla jest niezupełna i to w bardzo silnym stopniu. Oczywiście nikt nie oczeki-
wał, że okaże się ona zupełna, ale też nikt zapewne nie spodziewał się, że okaże się
62
ona tak słaba. Dowody niezależności przeprowadzone metodą Cohena pokazują,
że  w odróżnieniu od arytmetyki liczb naturalnych  nie usuniemy niezupeł-
ności wzmacniając reguły wnioskowania np. przez przyjęcie tzw. reguły �. Niezu-
pełność aksjomatycznej teorii mnogości porównać można raczej do niezupełności
teorii grup lub ciał lub podobnych teorii algebraicznych. Nikt nie dziwi się, że
te teorie są niezupełne. Ich aksjomatyki były od początku sformułowane tak, by
istniały dla nich różnorodne modele. W przypadku aksjomatów teorii mnogości
intencja była odmienna, ale wyniki są niemal takie same.
Istnieją próby oparcia teorii mnogości (i wielu innych teorii matematycznych) na
logice drugiego rzędu. Wydaje mi się, że próby te jakkolwiek mogą przynieść cie-
kawe rezultaty formalne, nie doprowadzą do wyjaśnienia podstaw teorii mnogości.
W logice drugiego rzędu występuje bowiem pojęcie dowolnej własności. Reguły
wnioskowania i aksjomaty logiki drugiego rzędu mają charakteryzować to poję-
cie. Otóż jest jasne, że pojęcie to w równym stopniu domaga się sprecyzowania,
jak pojęcie zbioru. Ponieważ matematycy z zasady dopuszczają tylko własności
ekstensjonalne, więc nie ma żadnej różnicy między pojęciem zbioru a pojęciem
własności rozpatrywanym w logice drugiego rzędu. W ten sposób opierając teorię
mnogości na logice drugiego rzędu nie wyjaśniamy pojęcia zbioru, lecz sprowa-
dzamy je do innego, w zasadzie mu równoważnego pojęcia.
Formuły logiki pierwszego rzędu L�� kodować można liczbami naturalnymi lub,
co na jedno wychodzi, zbiorami dziedzicznie skończonymi, tj. elementami zbioru H(�).
Z kolei, formuły logiki L� � kodować można elementami zbioru H(�1), tj. zbio-
1
rami dziedzicznie przeliczalnymi. Także dowody w L� � kodować można elementami
1
H(�1).
Dowody w logice L� � mają długość przeliczalną. Można jednak podać przykład
1
zbioru zdań � oraz zdania � z tego języka takich, że � |= �, ale nie istnieje dowód � z
� w L� �. Zbiór � można dobrać w ten sposób, aby był on Ł1 na H(�1).
1
Zbiór H(�1) jest domknięty na tworzenie przeliczalnych podzbiorów oraz ciągów.
Jednak fakt wspomniany w poprzednim akapicie wskazuje iż, mówiąc w uproszczeniu,
H(�1) nie jest domknięty ze względu na operację odpowiadającą kodowaniu dowodów
z dowolnych Ł1 na H(�1) zbiorów formuł. Naturalne jest w tej sytuacji poszukiwanie
takich zbiorów A zastępujących H(�1), które byłyby domknięte na operacje odpowia-
dające kodowaniom dowodów w A oraz rozważanie tylko takich formuł, które mają
kody w A. Była to jedna z motywacji do rozpatrywania tzw. dopuszczalnych fragmen-
tów LA logiki L� �.
1
Barwise odkrył, że istnieją przeliczalne zbiory (admissible sets) A ą" H(�1), które
spełniają powyższe warunki. Są to więc takie uogólnienia zbiorów dziedzicznie skoń-
czonych, na których (jako na zbiorach kodów formuł) możliwe i sensowne jest upra-
wianie (uogólnionej) teorii rekursji oraz teorii dowodu. Udowodnił także swoje zna-
mienite twierdzenie o zwartości: jeśli A jest przeliczalnym zbiorem dopuszczalnym, to
każdy zbiór formuł języka LA będący Ł1 na A, którego każdy podzbiór (będący jedno-
cześnie elementem A) ma model, sam również ma model. Twierdzenie Barwise a ma
mnogie zastosowania, m.in. pozwala np. udowodnić, że każdy przeliczalny przechodni
model dla ZFC ma właściwe rozszerzenie końcowe. Prace Barwise a to swego rodzaju
unifikacja rozważań w teorii modeli, teorii rekursji oraz teorii mnogości.
63
Szczególnie przydatna dla badań zbiorów dopuszczalnych okazała się wersja teorii
mnogości KP zaproponowana przez Kripke go i Platka w połowie lat sześćdziesią-
tych XX wieku. Jest ona teorią elementarną, ze stałą pozalogiczną ", będącą pew-
nym osłabieniem teorii mnogości Zermelo-Fraenkla. Nie ma w niej aksjomatu zbioru
potęgowego, a szczególną rolę pełnią schematy aksjomatów "0-separation oraz "0-
collection (odpowiedniki schematów aksjomatów wyróżniania i zastępowania), w któ-
rych występują formuły klasy "0. Zbiory przechodnie A takie, że (A, ") jest modelem
KP nazywane są zbiorami dopuszczalnymi (admissible sets). Rozważa się także teorię
KPU, czyli teorię KP z atomami.
Uwagi końcowe
Powyższe notatki mają charakter kompilacyjny. Przygotowano je także z myślą
o pracownikach Zakładu Logiki Stosowanej UAM, dla ułatwienia im wykonywania
posługi dydaktycznej w zakresie logiki. Korzystaliśmy m.in. z następujących z
ródeł:
" Barwise, J. Feferman, S. (eds.) 1985. Model-theoretic logics. Springer-Verlag,
New York Berlin Heidelberg Tokyo.
" Czelakowski, J. 2001. Protoalgebraic logics. Kluwer Academic Publishers, Do-
rdrecht Boston London.
" Ebbinghaus, H.D., Flum, J., Thomas, W. 1996. Mathematical logic. Springer.
" Mostowski, A. 1967. O niektórych nowych wynikach matematycznych dotyczą-
cych teorii mnogości. Studia Logica 20, 99 116.
" Pogorzelski, W.A. 1975. Klasyczny rachunek zdań. Zarys teorii. Państwowe Wy-
dawnictwo Naukowe, Warszawa.
" Pogorzelski, W.A. 1981. Klasyczny rachunek kwantyfikatorów. Zarys teorii. Pań-
stwowe Wydawnictwo Naukowe, Warszawa.
" Pogorzelski, W.A., Wojtylak, P. 2008. Completeness theory for propositional
logics. Birkh�user, Basel Boston Berlin. [Prawie wszystkie ustalenia z punktu
pierwszego pochodzą z tej pracy.]
" Rasiowa, H., Sikorski, R. 1963. The mathematics of metamathematics. Państwowe
Wydawnictwo Naukowe, Warszawa.
" Stegm�ller, W., Varga von Kib�d, M. 1984. Probleme und Resultate der Wissen-
schaftstheorie und Analytischen Philosophie, Band III: Strukturtypen der Logik.
Teil C. Springer-Verlag, Berlin Heidelberg New York Tokyo.
" V��n�nen, J. 2004. Barwise: abstract model theory and generalized quantifiers.
The Bulletin of Symbolic Logic Volume 10, Number 1, 37 53.
64
" Westerst�hl, D. 1989. Quantifiers in formal and natural languages. Handbook of
Philosophical Logic. Vol. IV, 1 131.
" Wójcicki, R. 1984. Lectures on propositional calculi. Ossolineum, Wrocław.
Dowody wszystkich przytoczonych twierdzeń znalez
ć można w wymienionych
wyżej pracach. Na razie nie ma monografii w języku polskim, która przedstawiałaby
w sposób systematyczny którykolwiek ze wspomnianych wyżej paradygmatów meta-
logiki (algebraiczny i semantyczny).
" " "
Postawmy na zakończenie tych notatek kilka przykładowych pytań, na które ma
próbować odpowiedzieć przygotowywana monografia:
1. Czy możliwa jest unifikacja obu wspomnianych paradygmatów?
2. Jakie ewentualne korzyści mogłaby przynieść?
3. Jakie są związki między matematycznymi podstawami metalogiki a czynionymi
w metalogice założeniami filozoficznymi?
4. Jakie są inspiracje/motywacje dla tworzenia nowych pojęć metalogicznych?
5. Jaki jest status takich pojęć, jak np.: stała logiczna w obu paradygmatach?
Nie podamy w tych notatkach odpowiedzi na powyższe pytania. Ograniczymy się
jedynie do kilku wskazówek. Nie są to przy tym uwagi podane w jakikolwiek systema-
tyczny sposób, mają one na razie charakter zebranych ad hoc konstatacji.
1. Paradygmat algebraiczny jest rozwinięty w przypadku rachunków zdaniowych.
Z kolei, paradygmat nazwany tu semantycznym, za punkt wyjścia bierze języki
pierwszego rzędu. Oczywiście, paradygmat algebraiczny może być stosowany
także w przypadku języków pierwszego rzędu, jak pokazuje np. prezentacja tej
problematyki w The mathematics of metamathematics. Dla właściwego algebra-
icznego ujęcia systemów logicznych z kwantyfikatorami potrzebujemy jednak
algebr (np. algebr Boole a) z nieskończonymi operacjami. Wykorzystywane są
w takich ujęciach np. algebry cylindryczne lub algebry kwantyfikatorowe.
Można się zastanawiać, jakie operacje algebraiczne wyznaczane są poprzez po-
rządek w klasie logik abstrakcyjnych (w rozumieniu punktu drugiego tych nota-
tek).
2. W paradygmacie algebraicznym wychodzimy od operacji konsekwencji, w usta-
lonym języku. Reprezentacje semantyczne (semantyka matrycowa) wyznaczone
są w dużym stopniu przez algebrę tego języka. Z kolei, w paradygmacie nazy-
wanym tu semantycznym punktem wyjścia jest (aksjomatycznie charakteryzo-
wana) relacja spełniania. Status formuł (i zdań) jest tu inny niż w paradygmacie
algebraicznym: zdaniom logik abstrakcyjnych odpowiadają klasy struktur rela-
cyjnych (modeli).
65
Mówiąc Humanistycznie, głęboko mętnie, unifikacja obu paradygmatów mia-
łaby na celu wykrycie (oraz wykorzystanie) ewentualnych warunków zgodności
między: przejściem od operacji konsekwencji do semantyki (w paradygmacie
algebraicznym), a przejściem od relacji spełniania do operacji konsekwencji (w
paradygmacie semantycznym).
3. To bardzo trudne pytanie. Zwykle w charakterze przykładu związków między
czynionymi w logice (oraz metalogice) założeniami filozoficznymi a wykorzy-
stywaną na tym obszarze matematyczną aparaturą pojęciową podaje się zależno-
ści łączące intuicjonizm (oraz różne wersje konstruktywizmu) z wybranymi dla
intuicjonizmu strukturami matematycznymi (algebraicznymi, topologicznymi,
itd.), w odróżnieniu od stosownej reprezentacji matematycznej dla logiki kla-
sycznej.
Już sama matematyczna kodyfikacja metalogiki (w każdym z omówionych wy-
żej paradygmatów) implikuje przyjęcie określonego stanowiska filozoficznego.
Dla przykładu, trudno sobie wyobrazić, aby istniały rozumne powody dla upra-
wiania parakonsystentnej metalogiki (choć systemy logiki parakonsystentnej mo-
gą mieć ważkie aplikacje).
Osobnym problemem jest np. dopuszczanie (lub nie) możliwości stosowania w
metalogice rozumowań nieefektywnych, np. używanie aksjomatu wyboru, le-
matu K�niga, różnych form aksjomatu wyróżniania.
4. Na Seminarium Zakładu Logiki Stosowanej UAM mówiliśmy już o problema-
tyce dotyczącej wyłaniania się pojęć metalogicznych, takich jak np.: pełność,
różne rodzaje zupełności, kategoryczność, zwartość. Wspominaliśmy np. o roz-
dzieleniu (początkowo utożsamianych) pojęć odpowiadających, w dzisiejszej
terminologii, kategoryczności oraz zupełności. W tym kontekście warto rów-
nież zwrócić uwagę np. na rolę niektórych twierdzeń czysto matematycznych
dla ustalania paradygmatu logiki (np. twierdzenie Stone a o reprezentacji algebr
Boole a).
5. Twierdzenia Pogorzelskiego-Wojtylaka przytoczone w punkcie 1.11. dostarczają
przykładu pokazującego, że nie istnieje charakterystyka stałych logicznych lo-
giki klasycznej, spełniająca pewne naturalne wymogi. Jak widzieliśmy, dla lo-
giki intuicjonistycznej taka charakterystyka istnieje. W tym kontekście ważne są
też uwagi Pogorzelskiego i Wojtylaka dotyczące możliwości uzyskania pożąda-
nych charakterystyk stałych logicznych logiki klasycznej za cenę rozszerzenia
rozumienia pojęcia operacji konsekwencji.
Wnioskiem z twierdzeń Lindstr�ma jest m.in. to, że klasyczna logika pierwszego
rzędu jest maksymalną logiką (regularną!), która nie odróżnia mocy nieskończo-
nych i która jest zwarta. Czy z tego mamy także jakiekolwiek wnioski na temat
stałych logicznych (logiki pierwszego rzędu)?
66


Wyszukiwarka

Podobne podstrony:
Materiały pomocnicze do wykładów
Gibas M Chemia makroczasteczek Materiały pomocnicze do wykładu
Ekologia materialy pomocnicze do wykladow
MATERIA Y POMOCNICZE do warsztatu asertywno ci 1 1
Materiały pomocnicze do ćwiczenia nr 3 co powinien wiedzieć wnioskodawca (1)
Elektrotechnika (materiały pomocnicze do ćwiczeń)
Materiały pomocnicze do przedmiotu mikromaszyny
Materiał pomocniczy do listy 3
form Fizyka w Mechatronice materialy pomocnicze do zajec
Koncepcje zarz Materialy pomocnicze do studiowania
TM1 Materiały pomocnicze do ćwiczeń(1)
TM1 Materiały pomocnicze do ćwiczeń(1)

więcej podobnych podstron