Jerzy Pogonowski Dwa paradygmaty metalogiki Materiały pomocnicze do wykładów 2 5

ARADYGMATY

ETALOGIKI

ERZY

OGONOWSKI

Zakład Logiki Stosowanej UAM

www.logic.amu.edu.pl

Wst˛ep

Niniejsza notatka zawiera nieco informacji wst˛epnych zwi ˛

azanych z problematyk ˛

wykładów 2–5 Metalogika dla Studium Doktoranckiego Instytutu Filozofii Uniwersy-
tetu Opolskiego. Spis tre´sci 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˛e´sci pierwszej podajemy podstawowe definicje oraz informacje o wybra-

nych twierdzeniach dotycz ˛

acych ogólnych operacji konsekwencji; informacje te

pochodz ˛

a z monografii W.A. Pogorzelskiego i P. Wojtylaka Completeness theory

for propositional logics.

Birkhäuser, Basel Boston Berlin, 2008.

• W cz˛e´sci drugiej podajemy dowody I i II twierdzenia Lindströma, w sformuło-

waniach pochodz ˛

acych z: Ebbinghaus, H.D., Flum, J., Thomas, W. 1996. Ma-

thematical logic.

Springer.

∗ ∗ ∗

Dwa tytułowe paradygmaty to:

• Paradygmat algebraiczny. Rozwa˙zania dotycz ˛

ace ogólnych operacji konsekwen-

cji (w sensie Tarskiego) oraz logik abstrakcyjnych (w sensie Suszki).

• Paradygmat semantyczny. Rozwa˙zania dotycz ˛

ace soft model theory i logik abs-

trakcyjnych w sensie nadawanym temu terminowi przez: Mostowskiego, Lind-
ströma, Barwise’a i in.

W szczególno´sci, chcieliby´smy zwróci´c uwag˛e na pewn ˛

a analogi˛e mi˛edzy twier-

dzeniami charakteryzuj ˛

acymi logik˛e klasyczn ˛

a w obu paradygmatach:

• twierdzeniami Pogorzelskiego-Wojtylaka (charakteryzuj ˛

acymi logiki progowe w

terminach C-definicji)

• twierdzeniami Lindströma (ukazuj ˛

acymi, i˙z własno´s´c zwarto´sci i własno´s´c Lö-

wenheima-Skolema charakteryzuj ˛

a klasyczn ˛

a logik˛e pierwszego rz˛edu).

∗ ∗ ∗

1. Paradygmat algebraiczny

1.1. Operacje konsekwencji

Niech S = (S, F

, . . . , F

) b˛edzie algebr ˛

a ustalonego j˛ezyka zdaniowego. Przez

reguł˛e wnioskowania w S rozumiemy dowoln ˛

a relacj˛e r ⊆ ℘(S) × S. Poprzedniki re-

lacji r nazywamy zbiorami przesłanek reguły r, a jej nast˛epniki wnioskami tej reguły.
Ogół reguł wnioskowania w S oznaczamy przez R

. Reguły z pustym zbiorem prze-

słanek nazywamy regułami aksjomatycznymi. Je´sli r jest reguł ˛

a wnioskowania oraz

(X, α) ∈ r, to par˛e (X, α) nazywamy sekwentem reguły r. Cz˛esto u˙zywamy nast˛epu-
j ˛

acej notacji dla sekwentów danej reguły:

r :

Najcz˛e´sciej ograniczamy si˛e do reguł wnioskowania o sko ´nczonych zbiorach prze-

słanek. Przypominamy, ˙ze F in(X) oznacza rodzin˛e wszystkich sko´nczonych podzbio-
rów zbioru X, a F in

∗

(X) wszystkich sko´nczonych niepustych podzbiorów zbioru X.

Ponadto, zwykle wszystkie sekwenty danej reguły maj ˛

a ustalon ˛

a budow˛e składniow ˛

mo˙zemy wtedy reguł˛e zapisywa´c w postaci schematycznej, jak np. w znanym przy-
padku reguły modus ponens (reguły odrywania), gdy rozwa˙zany j˛ezyk zawiera funktor
→:

M P :

α → β, α

Ka˙zd ˛

a par˛e (R, X), gdzie R ⊆ R

, a X ⊆ S nazywamy systemem logiki zda ´n

(albo: logik ˛

a zdaniow ˛

a). Je´sli L = (R, X) jest logik ˛

a zdaniow ˛

a, to mówimy, ˙ze:

• R jest zbiorem reguł pierwotnych L

• X jest zbiorem aksjomatów L.

Odwzorowanie C : ℘(S) → ℘(S) jest operacj ˛

a konsekwencji (nad S) wtedy i

tylko wtedy, gdy dla wszystkich X, Y ⊆ S:

• X ⊆ C(X)

(zwrotno´s´c)

• je´sli X ⊆ Y , to C(X) ⊆ C(Y )

(monotoniczno´s´c)

• C(C(X)) ⊆ C(X)

(idempotencja).

Zamiast terminu operacja konsekwencji u˙zywamy tak˙ze terminów: operator kon-

sekwencji lub operacja domkni˛ecia (operator domkni˛ecia).

Bezpo´srednio z definicji operacji konsekwencji wynika, ˙ze ka˙zda taka operacja C

spełnia te˙z warunek: C(C(X)) = C(X) dla wszystkich X ⊆ S.

Mówimy, ˙ze operacja domkni˛ecia C jest:

• finitystyczna, gdy

C(X) =

[

{C(Y ) : Y ∈ F in(X)}

dla wszystkich X ⊆ S;

• zwarta, gdy dla ka˙zdego Y ⊆ S istnieje X ∈ F in(Y ) taki, ˙ze:

je´sli C(Y ) = S, to C(X) = S;

• niesprzeczna, gdy C(∅) 6= S;

• zupełna (w sensie Posta), gdy C({α}) = S dla ka˙zdego α /

∈ C({∅}).

Przez sprzeczn ˛

a operacj˛e konsekwencji rozumiemy operacj˛e C tak ˛

a, ˙ze C(X) = S

dla wszystkich X ⊆ S.

Ogół wszystkich operacji konsekwencji nad S jest cz˛e´sciowo uporz ˛

adkowany przez

relacj˛e

6 zdefiniowan ˛

a nast˛epuj ˛

aco:

• C

6 C

wtedy i tylko wtedy, gdy C

(X) ⊆ C

(X)

dla wszystkich X ⊆ S.

Nast˛epuj ˛

ace warunki s ˛

a równowa˙zne:

• C

6 C

• C

◦ C

= C

• C

◦ C

= C

Dla dowolnej rodziny {C

: t ∈ T } operacji konsekwencji definiujemy operacje

t∈T

oraz

t∈T

• (

t∈T

)(X) =

T{C

(X) : t ∈ T }

• (

t∈T

)(X) =

T{C(X) : C

6 C dla wszystkich t ∈ T }

dla wszystkich X ⊆ S.

Wtedy zachodz ˛

a nast˛epuj ˛

ace fakty dotycz ˛

ace uporz ˛

adkowania ogółu konsekwencji

nad S przez relacj˛e

•

t∈T

oraz

t∈T

s ˛

a operacjami konsekwencji.

• (

t∈T

)(X) =

T{Y : X ⊆ Y = C

(Y ) dla wszystkich t ∈ T }.

• Rodzina wszystkich operacji konsekwencji nad S jest krat ˛

a zupełn ˛

a z porz ˛

ad-

kiem kratowym

6 oraz kresami okre´slonymi wzorami:

inf{C

: t ∈ T } =

t∈T

sup{C

: t ∈ T } =

t∈T

• Elementem najwi˛ekszym w tej kracie jest konsekwencja sprzeczna. Elementem

najmniejszym jest operacja Id okre´slona wzorem Id(X) = X dla wszystkich
X ⊆ S.

• Je´sli wszystkie operacje ze zbioru {C

: t ∈ T } s ˛

a finitystyczne, to operacja

t∈T

te˙z jest finitystyczna.

1.2. Systemy domkni˛e´c

Niech C b˛edzie operacj ˛

a konsekwencji nad S. Mówimy, ˙ze zbiór formuł X ⊆ S

jest C-domkni˛ety, gdy X = C(X), czyli gdy X jest punktem stałym operacji C.
Rodzina wszystkich zbiorów C-domkni˛etych jest jest domkni˛eta na iloczyny, tj.:

{C(X

) : t ∈ T }) =

{C(X

) : t ∈ T }.

Rodzina ta nie jest jednak domkni˛eta na sumy. Przy podanych zało˙zeniach zachodzi

nast˛epuj ˛

acy fakt:

• Je´sli C jest finitystyczna, a {X

: t ∈ T } jest ⊆-ła´ncuchem zbiorów (formuł),

to:

[

{C(X

) : t ∈ T }) =

[

{C(X

) : t ∈ T }.

Rodzina wszystkich zbiorów C-domkni˛etych jest krat ˛

a zupełn ˛

a (z inkluzj ˛

a jako po-

rz ˛

adkiem kratowym), z elementem najmniejszym C(∅) oraz elementem najwi˛ekszym

S. Kresy rodzin {X

: t ∈ T } zbiorów C-domkni˛etych wyznaczone s ˛

a wzorami:

inf{X

: t ∈ T } =

: t ∈ T },

sup{X

: t ∈ T } = C(

[

: t ∈ T }).

Przypominamy, ˙ze rodzina zbiorów X jest systemem domkni˛e´c, je´sli iloczyn ka˙z-

dej podrodziny rodziny X jest elementem X .

Widzimy wi˛ec, ˙ze rodzina wszystkich zbiorów C-domkni˛etych jest systemem do-

mkni˛e´c, dla dowolnej operacji konsekwencji C. Zachodzi tak˙ze implikacja odwrotna:
dowolny system domkni˛e´c wyznacza pewn ˛

a operacj˛e konsekwencji. Je´sli mianowicie

X jest systemem domkni˛e´c (rodzin ˛

a podzbiorów zbioru S, domkni˛et ˛

a na iloczyny), to

definiujemy:

C(X) =

{Y ∈ X : X ⊆ Y },

dla dowolnego X ⊆ S. Mo˙zna sprawdzi´c, ˙ze tak okre´slona funkcja C jest operacj ˛

konsekwencji.

1.3. Zbiory niesprzeczne, maksymalne, aksjomatyzowalne i nieza-
le˙zne

Powiemy, ˙ze zbiór X ⊆ S jest:

• C-niesprzeczny, gdy C(X) 6= S;

• C-maksymalny, gdy X jest C-niesprzeczny oraz C(X ∪ {α}) = S dla ka˙zdego

α /

∈ C(X);

• C-aksjomatyzowalny, gdy istnieje sko´nczony zbiór Y taki, ˙ze C(X) = C(Y );

• C-niezale˙zny, gdy α /

∈ C(X − {α}), dla ka˙zdego α ∈ X.

Oto niektóre własno´sci tych poj˛e´c:

• Je´sli X jest zbiorem C-maksymalnym, to C(X) jest elementem ⊆-maksymalnym

w rodzinie wszystkich zbiorów C-domkni˛etych i C-niesprzecznych.

• Je´sli C jest finitystyczna, to ˙zaden niesko´nczony zbiór C-niezale˙zny nie jest C-

aksjomatyzowalny.

• Je´sli istnieje zbiór, który nie jest C-aksjomatyzowalny, to to rodzina wszystkich

C-aksjomatyzowalnych i C-domkni˛etych zbiorów jest niesko´nczona.

• Je´sli X jest C-niezale˙zny, to dla dowolnych Y, Z ⊆ X: Y ⊆ Z wtedy i tylko

wtedy, gdy C(Y ) ⊆ C(Z).

Konsekwencj ˛

a tych własno´sci s ˛

a m.in. nast˛epuj ˛

ace ustalenia dotycz ˛

ace mocy pew-

nych rodzin zbiorów dla finitystycznej operacji konsekwencji C nad przeliczalnym
j˛ezykiem S, dla której istnieje niesko´nczony zbiór C-niezale˙zny:

• Istnieje kontinuum zbiorów o postaci C(X).

• Istnieje przeliczalnie wiele zbiorów o postaci C(X), gdzie X jest zbiorem sko´n-

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˙za´n dotycz ˛

acych operacji konsekwencji pojmowanych całkiem ogól-

nie, w my´sl podanej uprzednio definicji, interesuj ˛

ace i wa˙zne 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´s
zbioru przesłanek, zazwyczaj odwołujemy si˛e do metod, za pomoc ˛

a których wnioski

te mo˙zna uzyska´c: zazwyczaj s ˛

a to po prostu stosowne reguły wnioskowania. Ponadto,

jak zobaczymy za chwil˛e, ka˙zda operacja konsekwencji mo˙ze zosta´c przedstawiona
jako operacja konsekwencji generowana poprzez pewien zestaw reguł wnioskowania
(oraz, ewentualnie, zestaw aksjomatów).

Niech Cld(R, X) oznacza, ˙ze zbiór formuł X jest domkni˛ety 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).

WAGA

. Prosz˛e odró˙znia´c symbol implikacji → w KRZ od u˙zywanego tu metaj˛ezy-

kowego symbolu ⇒. Symbolu ∧ równie˙z u˙zywamy tu metaj˛ezykowo.

Dla dowolnych: X ⊆ S oraz R ⊆ R

niech:

(X) =

{Y ⊆ S : X ⊆ Y oraz Cld(R, Y )}.

Wtedy C

(X) jest ⊆-najmniejszym zbiorem zawieraj ˛

acym X i domkni˛etym na

wszystkie reguły z R. Zachodz ˛

a nast˛epuj ˛

ace fakty:

• Dla dowolnych: X ⊆ S oraz R ⊆ R

: C

(X) = X wtedy i tylko wtedy, gdy

Cld(R, X).

• Załó˙zmy, ˙ze rozwa˙zamy jedynie reguły o sko´nczonych zbiorach przesłanek. Wte-

dy: α ∈ C

(X) wtedy i tylko wtedy, gdy istnieje formalny dowód α na gruncie

systemu o zało˙zeniach X i regułach wnioskowania R, czyli gdy istnieje sko´n-
czony ci ˛

ag formuł α

, . . . , α

taki, ˙ze α jest identyczna z α

oraz dla wszystkich

i 6 n: albo α

∈ X, albo (P, α

) ∈ r dla pewnych r ∈ R oraz P ⊆ S.

Ka˙zda para o postaci (R, X), gdzie R ⊆ R

pozwala okre´sli´c pewn ˛

a operacj˛e

R,X

konsekwencji nad S:

R,X

(Y ) = C

(X ∪ Y ).

Operacja C

R,X

jest finitystyczna, je´sli zbiór X jest pusty. Dla X = ∅ b˛edziemy

zamiast C

R,X

pisali po prostu C

Ka˙zda finitystyczna operacja konsekwencji mo˙ze zosta´c przedstawiona w postaci

R,X

. Zachodzi mianowicie nast˛epuj ˛

acy fakt:

• Dla ka˙zdej finitystycznej operacji konsekwencji C istniej ˛

a: zbiór X ⊆ S oraz

zbiór R ⊆ R

takie, ˙ze C = C

R,X

Równie˙z dowolne operacje konsekwencji (bez zakładania sko´nczono´sci zbiorów

ich przesłanek) mo˙zna reprezentowa´c przez reguły:

• Dla ka˙zdej operacji konsekwencji C istnieje zbiór R ⊆ R

taki, ˙ze C = C

Je´sli C = C

R,X

, to par˛e (R, X) nazywamy baz ˛

a dla C. Zauwa˙zmy, ˙ze:

• dana operacja konsekwencji mo˙ze mie´c wiele ró˙znych baz;

• ka˙zda para (R, X) jednoznacznie wyznacza operacj˛e konsekwencji C

R,X

Operacje konsekwencji wyznaczone przez reguły mo˙zemy te˙z definiowa´c induk-

cyjnie. Niech R b˛edzie dowoln ˛

a rodzin ˛

a reguł wnioskowania w S. Przez operacj˛e

konsekwencji w S wyznaczon ˛

a przez R rozumiemy ka˙zd ˛

a funkcj˛e C : 2

→ 2

zdefiniowan ˛

a indukcyjnie nast˛epuj ˛

acymi warunkami dla dowolnego zbioru formuł X:

• (1) C

(X) = X

• (2) C

k+1

(X) = C

(X) ∪ {α ∈ S : (∃r ∈ R)(∃P ⊆ C

(X)) (P, α) ∈ r}

• (3) C

(X) =

S{C

(X) : k ∈ ω}.

Wyra˙zenie α ∈ C

(X) czytamy: α jest wyprowadzalna z X za pomoc ˛

a reguł

nale˙z ˛

acych do R. Ta notacja jest zgodna z wprowadzon ˛

a poprzednio.

1.5. Reguły dopuszczalne i reguły wyprowadzalne

Zbiór Adm(R, X) wszystkich reguł dopuszczalnych ze wzgl˛edu na X i R definiu-

jemy nast˛epuj ˛

aco:

r ∈ Adm(R, X) wtedy i tylko wtedy, gdy dla ka˙zdego P ⊆ S oraz ka˙zdej α ∈ S:

je´sli (P, α) ∈ r i P ⊆ C

(X), to α ∈ C

(X).

Zbiór Der(R, X) wszystkich reguł wyprowadzalnych ze wzgl˛edu na X i R defi-

niujemy nast˛epuj ˛

aco:

r ∈ Der(R, X) wtedy i tylko wtedy, gdy dla ka˙zdego P ⊆ S oraz ka˙zdej α ∈ S:

je´sli (P, α) ∈ r, to α ∈ C

(X ∪ P ).

Zachodz ˛

a nast˛epuj ˛

ace fakty, dla ka˙zdego R ⊆ R

oraz X ⊆ S:

• r ∈ Adm(R, X) wtedy i tylko wtedy, gdy Cld({r}, C

(X));

• r ∈ Der(R, X) wtedy i tylko wtedy, gdy Cld({r}, C

(X ∪ Y )), dla wszystkich

Y ⊆ S.

Mo˙zemy zatem stwierdzi´c, ˙ze:

• reguła dopuszczalna ze wzgl˛edu 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˙zdym nadsystemie systemu (R, X), czyli

Der(R, X) =

{Adm(R, X ∪ Y ) : Y ⊆ S}.

St ˛

ad, ka˙zda reguła wyprowadzalna z (R, X) jest te˙z dopuszczalna dla (R, X).

Inkluzja odwrotna nie zachodzi.

Mówimy, ˙ze para (R, X) jest podsystemem (R

, X

) (i piszemy wtedy (R, X) 4

, X

)) wtedy i tylko wtedy, gdy:

• X ⊆ C

) oraz

• R ⊆ Der(R

, X

Je´sli (R, X)

4 (R

, X

), to:

• Der(R, X) ⊆ Der(R

, X

)

• C

(X) ⊆ C

Widzimy zatem, ˙ze formuły i reguły wyprowadzalne w podsystemie danego sys-

temu, s ˛

a równie˙z wyprowadzalne w tym systemie. Z faktu, ˙ze (R, X)

4 (R

, X

)

nie wynika jednak ani inkluzja Adm(R, X) ⊆ Adm(R

, X

), ani inkluzja do niej od-

wrotna.

Je´sli X oraz X

s ˛

a niepuste, to: (R, X)

4 (R

, X

) wtedy i tylko wtedy, gdy

Der(R, X) ⊆ Der(R

, X

Relacja

4 jest zwrotna i przechodnia. Wyznacza zatem relacj˛e równowa˙zno´sci

≈=4 ∩(4)

−1

. Je´sli (R, X) ≈ (R

, X

), to:

• Der(R, X) = Der(R

, X

);

• C

(X) = C

);

• Adm(R, X) = Adm(R

, X

Je´sli X oraz X

s ˛

a niepuste, to (R, X) ≈ (R

, X

) wtedy i tylko wtedy, gdy

Der(R, X) = Der(R

, X

Zachodz ˛

a nast˛epuj ˛

ace fakty:

• (R, X) ≈ (Der(R, X), X)

• (Der(R, X), X) ≈ (R, C

(X))

• (R, C

(X)) ≈ (Der(R, X), C

(X))

• (Der(R, X), C

(X)) 4 (Adm(R, X), X)

• (Adm(R, X), X) ≈ (Adm(R, X), C

(X)).

B˛edziemy u˙zywa´c symbolu ≺ dla

4 −(4)

−1

Zachodz ˛

a nast˛epuj ˛

ace fakty, dla dowolnych X, X

⊆ S oraz R, R

⊆ R

• (R, X) 4 (R

, X

) wtedy i tylko wtedy, gdy C

R,X

6 C

;

• (R, X) ≈ (R

, X

) wtedy i tylko wtedy, gdy C

R,X

= C

W ´swietle powy˙zszego (oraz pami˛etaj ˛

ac o tym, ˙ze ka˙zda operacja konsekwencji

mo˙ze zosta´c przedstawiona w postaci operacji konsekwencji wyznaczonej przez reguły
wnioskowania), porz ˛

adek kratowy

6 w kracie wszystkich operacji konsekwencji mo˙ze

by´c uwa˙zany za generowany poprzez porz ˛

adek

Poj˛ecia: reguły wyprowadzalnej i reguły dopuszczalnej (sformułowane dla syste-

mów o postaci (R, X)) mog ˛

a te˙z (równie˙z na mocy powy˙zszego) zosta´c wyra˙zone w

terminach operacji konsekwencji:

• r ∈ DER(C) wtedy i tylko wtedy, gdy α ∈ C(P ), dla wszystkich (P, α) ∈ r;

• r ∈ ADM(C) wtedy i tylko wtedy, gdy: je´sli P ⊆ C(∅), to α ∈ C(∅), dla

wszystkich (P, α) ∈ r.

W´sród wszystkich systemów, generuj ˛

acych dan ˛

a operacj˛e konsekwencji rol˛e wy-

ró˙znion ˛

a pełni system (DER(C), C(∅)), nazywany systemem domkni˛etym logiki zda-

niowej.

Dla porz ˛

adku kratowego

4 definiujemy kresy rodzin {(R

, X

) : t ∈ T }:

•

t∈T

, X

) = (

t∈T

Der(R

, X

t∈T

));

•

t∈T

, X

) = (

t∈T

Wtedy

t∈T

, X

) jest systemem domkni˛etym, czyli:

• Der(

t∈T

, X

)) =

t∈T

Der(R

, X

);

• C(

t∈T

, X

)) =

t∈T

1.6. Reguły strukturalne

Jak pami˛etamy z elementarnego kursu logiki, reguła podstawiania (formuł za zmien-

ne zdaniowe w KRZ) ma bardzo szczególny charakter: odwołujemy si˛e w niej do pew-
nej (algebraicznej) operacji, inaczej ni˙z w przypadku reguł w rodzaju np. modus po-
nens

, gdzie odwołujemy si˛e jedynie do własno´sci syntaktycznych (kształtu przesłanek

oraz wniosku). Obecnie poznamy pewn ˛

a własno´s´c reguł wnioskowania, zwi ˛

azan ˛

a z

podstawieniami.

Przypominamy, ˙ze At oznacza zbiór formuł atomowych (zmiennych zdaniowych)

rozwa˙zanego j˛ezyka. Pami˛etamy, ˙ze ka˙zde podstawienie, czyli odwzorowanie e : At →
S mo˙ze w sposób jednoznaczny zosta´c rozszerzone do endomorfizmu h

: S → S. Z

tego powodu, wynik (jednoczesnego) podstawienia w formule α wyznaczonego przez
warto´sci e(p

) = γ

, dla wszystkich zmiennych zdaniowych p

, . . . , p

wyst˛epuj ˛

acych

w α mo˙ze by´c poprawnie oznaczany przez α[p

/γ

, . . . , p

/γ

]. Rozumie si˛e przez

to, ˙ze h

(α) = α[p

/γ

, . . . , p

/γ

Mo˙zemy teraz poda´c precyzyjn ˛

a definicj˛e reguły podstawiania r

∗

w S:

• ({α}, β) ∈ r

∗

wtedy i tylko wtedy, gdy β = h

(α), dla pewnego podstawienia

e : At → S.

Reguła r

∗

okre´slona mo˙ze tak˙ze by´c poprzez schemat:

• r

∗

(α)

, dla wszystkich α ∈ S oraz wszystkich e : At → S.

Operacja konsekwencji wyznaczona przez reguł˛e podstawiania jest oznaczana przez

Sb. Tak wi˛ec, dla ka˙zdego X ⊆ S:

Sb(X) = C

∗

}

(X) = {α : α ∈ h

(X) dla pewnego e : At → S}.

Powiemy, ˙ze reguła r ∈ R

jest strukturalna, co zapisujemy r ∈ Struct, wtedy i

tylko wtedy, gdy:

• je´sli (P, α) ∈ r, to (h

(P ), h

(α)) ∈ r, dla wszystkich e : At → S.

Zwykle rozwa˙zane reguły KRZ s ˛

a strukturalne, oprócz reguły podstawiania.

Precyzyjna definicja reguł strukturalnych jest prosta, jak widzieli´smy. Trudniej od-

da´c w j˛ezyku potocznym tzw. intuicje zwi ˛

azane z tymi regułami. W.A. Pogorzelski w

Elementarnym słowniku logiki formalnej

(s. 416) pisze:

Bardzo ogólnikowo mo˙zna przedstawi´c strukturalno´s´c reguł jako stoso-
walno´s´c do wszelkich przesłanek o ustalonej strukturze wyznaczonej na
ogół ich funktorem głównym.

Powiemy, ˙ze system (R, X) (gdzie R ⊆ R

, X ⊆ S) jest niezmienniczy (co

zapisujemy: (R, X) ∈ Inv), je´sli:

• R ⊆ Struct oraz X = Sb(X).

Je´sli R ⊆ Struct, to (R ∪ {r

∗

}, X) nazywamy systemem podstawieniowym.

Powiemy, ˙ze sekwent (P, α) jest sekwentem bazowym reguły r wtedy i tylko wtedy,

gdy:

r = {(h

(P ), h

(α)) : dla wszystkich podstawie´n e}.

Reguły, które posiadaj ˛

a sekwent bazowy, nazywane s ˛

a regułami standardowymi.

Ka˙zda reguła standardowa r mo˙ze zosta´c przedstawiona w postaci:

r =

[

: r

⊆ r oraz r

jest standardowa}.

Ka˙zda reguła standardowa jest strukturalna (lecz nie na odwrót). Przykładem reguły

strukturalnej, która nie jest standardowa jest reguła r

, dla ka˙zdego X ⊆ S:

• (P, α) ∈ r

wtedy i tylko wtedy, gdy: je´sli h

(P ) ⊆ X, to h

(α) ∈ X, dla

wszystkich podstawie´n e.

Z wielu wzgl˛edów warto rozwa˙za´c poj˛ecie strukturalno´sci zrelatywizowane do

pewnego zbioru Γ ⊆ S. Definiujemy:

• r

∗

|Γ :

(α)

dla wszystkich α ∈ S oraz e : At → Γ.

Dalej, definiujemy: Sb

(X) = C

∗

}|Γ

(X). Zachodz ˛

a nast˛epuj ˛

ace fakty:

• r

∗

|S = r

∗

• Sb

= Sb

• r

∗

|∅ = ∅

• Sb

∅

(X) = X, dla wszystkich X ⊆ S

• Sb

(X ∪ Y ) = Sb

(X) ∪ Sb

(Y ), dla wszystkich X, Y ⊆ S.

Mówimy, ˙ze reguła r jest Γ-strukturalna (co zapisujemy: r ∈ Struct(Γ)), gdy:

• je´sli (P, α) ∈ r, to (h

(P ), h

(α)) ∈ r, dla wszystkich e : At → Γ.

Mówimy, ˙ze system (R, X) jest Γ-niezmienniczy ((R, X) ∈ Inv(Γ)) wtedy i tylko

wtedy, gdy:

• R ⊆ Struct oraz X = Sb

(X).

Zachodz ˛

a nast˛epuj ˛

ace 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 ˛

a ∅-strukturalne.

• (R, X) ∈ Inv(∅) dla wszystkich R ⊆ R

oraz X ⊆ S.

• Dla ka˙zdych Γ

, Γ

: je´sli Γ

⊆ Γ

, to Struct(Γ

) ⊆ Struct(Γ

• Dla ka˙zdych Γ

, Γ

: je´sli Γ

⊆ Γ

, to Inv(Γ

) ⊆ Inv(Γ

• Dla ka˙zdego Γ ⊆ S: Struct ⊆ Struct(Γ) ⊆ R

• Dla ka˙zdego Γ ⊆ S: Inv ⊆ Inv(Γ) ⊆ Inv(∅).

• Je´sli R ⊆ Struct(Γ) oraz X ⊆ S, to h

(X)) ⊆ C

(X)), dla wszystkich

e : At → Γ.

• Je´sli R ⊆ Struct(Γ) oraz X, Y ⊆ S, to

(Sb

(X) ∪ Y )) ⊆ C

(Sb

(X) ∪ h

(Y )), dla wszystkich e : At → Γ.

Ostatni z powy˙zszych faktów mo˙zna wykorzysta´c dla redukcji reguły podstawiania

do zbioru aksjomatów:

• Je´sli R ⊆ Struct(Γ) oraz X ⊆ S, to:

R∪{r

∗

|Γ}

(X) = C

(Sb

(X)).

Dowód tego twierdzenia podaje monografia Pogorzelskiego i Wojtylaka (s. 29).
Niektóre konsekwencje tego twierdzenia to:

• Dla ka˙zdych R ⊆ Struct(Γ) oraz X ⊆ S:

(X)) ⊆ C

(Sb

(X)).

• Je´sli (R, X) jest Γ-niezmienniczy, to jest domkni˛ety na reguł˛e r

∗

|Γ.

• r

∗

|Γ ∈ Adm(R, Sb

(X)).

• Je´sli R ⊆ Struct(Γ), r ∈ R

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˛epuj ˛

acy fakt dotycz ˛

acy reguły podstawiania:

• Dla wszystkich R ⊆ Struct oraz X ⊆ S:

1) r

∗

∈ Adm(R, Sb(X))

2) r

∗

∈ Der(R, Sb(X)), je´sli ∅ 6= C

(X) 6= S.

Je´sli 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 ˛

a jednak równowa˙zne. Systemy logiczne przedstawia´c mo˙zemy w dwóch,

nierównowa˙znych wersjach:

• niezmienniczej (R, Sb(X)), gdzie R ⊆ Struct

• podstawieniowej (R ∪ {r

∗

}, X).

Poj˛ecia: Γ-strukturalno´sci oraz Γ-niezmienniczo´sci mog ˛

a zosta´c odniesione do ope-

racji konsekwencji:

• C jest Γ-strukturalna (symbolicznie: C ∈ STRUCT(Γ)), je´sli

(C(X)) ⊆ C(h

(X)), dla wszystkich X ⊆ S oraz e : At → Γ

• C jest strukturalna (symbolicznie: C ∈ STRUCT), je´sli

(C(X)) ⊆ C(h

(X)), dla wszystkich X ⊆ S oraz e : At → S.

Ka˙zdy Γ-niezmienniczy system (R, X) wyznacza Γ-strukturaln ˛

a operacj˛e konse-

kwencji C

R,X

. Ponadto, ka˙zda Γ-strukturalna operacja konsekwencji jest generowana

przez pewien system Γ-niezmienniczy.

Rodzina wszystkich strukturalnych (Γ-strukturalnych) operacji konsekwencji two-

rzy podkrat˛e zupełn ˛

a kraty wszystkich operacji konsekwencji nad S, gdzie kresami

dowolnej rodziny {C

: t ∈ T } strukturalnych (Γ-strukturalnych) operacji konsekwen-

cji s ˛

t∈T

oraz

t∈T

1.7. Operacje konsekwencji a relacje konsekwencji

Ogólna (finitystyczna) relacja konsekwencji `⊆ 2

× S w S okre´slona jest dla

dowolnych X, Y ⊆ S oraz α ∈ S przez warunki:

• (` 1) X ` α dla ka˙zdego α ∈ X

• (` 2) je´sli X ` α i X ⊆ Y , to Y ` α

• (` 3) je´sli dla ka˙zdej β ∈ Y X ` β oraz Y ` α, to X ` α

• (` 4) je´sli X ` α, to istnieje Y taki, ˙ze: Y ∈ F in(X) oraz Y ` α.

Operacje i relacje konsekwencji s ˛

a wzajemnie przez siebie definiowalne:

(F)

X `

α wtedy i tylko wtedy, gdy α ∈ C

(X)

(tj. dla ka˙zdej ` istnieje C

taka, ˙ze (

F), a tak˙ze dla ka˙zdej C istnieje `

taka, ˙ze

(

F)).

Powy˙zsza zale˙zno´s´c (

F) mo˙ze by´c zapisana tak˙ze w takiej postaci:

• Je´sli C jest operacj ˛

a konsekwencji, to definiujemy relacj˛e konsekwencji `

X `

α wtedy i tylko wtedy, gdy α ∈ C(X);

• Je´sli ` jest relacj ˛

a konsekwencji, to definiujemy operacj˛e konsekwencji C

α ∈ C

(X) wtedy i tylko wtedy, gdy X ` α.

Twierdzenia dotycz ˛

ace operacji konsekwencji przekładaj ˛

a si˛e zatem na twierdzenia

dotycz ˛

ace relacji konsekwencji i na odwrót.

1.8. Kilka wa˙znych przykładów

Zwykle w charakterze wa˙znych przykładów logik zdaniowych rozwa˙za si˛e logiki

nast˛epuj ˛

ace:

• logik˛e intuicjonistyczn ˛

• logik˛e klasyczn ˛

• logiki modalne

• logiki wielowarto´sciowe (Łukasiewicza).

Zobaczmy zatem, jak powy˙zsze systemy logiczne opisywane s ˛

a w terminach ope-

racji konsekwencji.

OGIKA

NTUICJONISTYCZNA

J˛ezykiem tej logiki jest standardowy j˛ezyk S

= (S

, →, ∨, ∧, ¬). Niech A

int

b˛edzie nast˛epuj ˛

acym zbiorem aksjomatów:

• (1) p → (q → p)

• (2) (p → (p → q)) → (p → q)

• (3) (p → q) → ((q → s) → (p → s))

• (4) p → (p ∨ q)

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

0∗

= {r

, r

∗

}, gdzie r

jest reguł ˛

a modus ponens, a r

∗

reguł ˛

a podstawiania

w S

. Wtedy (R

0∗

, A

int

) jest systemem intuicjonistycznej logiki zdaniowej. W wersji

niezmienniczej logika intuicjonistyczna jest systemem (R

, Sb(A

int

)), gdzie R

}. Jak pami˛etamy, na podstawie własno´sci operacji Sb oraz reguły podstawiania:

0∗

int

) = C

(Sb(A

int

)).

Niech C

int

b˛edzie operacj ˛

a konsekwencji generowan ˛

a przez system (R

, Sb(A

int

)).

Mamy zatem dla ka˙zdego X ⊆ S

int

(X) = C

(Sb(A

int

) ∪ X).

W systemie tym zachodzi twierdzenie o dedukcji:

• Dla dowolnych X ⊆ S

oraz α, β ∈ S

β ∈ C

int

(X ∪ {α}) wtedy i tylko wtedy, gdy (α → β) ∈ C

int

(X).

Twierdzenie o dedukcji charakteryzuje implikacj˛e. Pozostałe funktory logiki in-

tuicjonistycznej s ˛

a charakteryzowane nast˛epuj ˛

aco (formuła α ≡ β jest skrótem dla

formuły (α → β) ∧ (β → α)):

• C

int

(X ∪ {α ∧ β}) = C

int

(X ∪ {α, β})

• C

int

(X ∪ {α ∨ β}) = C

int

(X ∪ {α}) ∩ C

int

(X ∪ {β})

• (α ≡ β) ∈ C

int

(X) wtedy i tylko wtedy, gdy C

int

(X ∪ {α}) = C

int

(X ∪ {β})

• ¬α ∈ C

int

(X) wtedy i tylko wtedy, gdy C

int

(X ∪ {α}) = S

Otrzymujemy st ˛

ad, ˙ze w logice intuicjonistycznej wyprowadzalna jest reguła do-

dawania koniunkcji r

α,β

α∧β

, dla wszystkich α, β ∈ S

Zachodz ˛

a tak˙ze nast˛epuj ˛

ace fakty:

• α → β ∈ C

int

(X) wtedy i tylko wtedy, gdy C

int

(X ∪ {β}) ⊆ C

int

(X ∪ {α}).

• α ∨ β ∈ C

int

(X) wtedy i tylko wtedy, gdy C

int

(X ∪ {α}) ∩ C

int

(X ∪ {β}) ⊆

int

(X).

• α ∧ β ∈ C

int

(X) wtedy i tylko wtedy, gdy C

int

(X ∪ {α}) ∪ C

int

(X ∪ {β}) ⊆

int

(X).

• ¬α ∈ C

int

(X) wtedy i tylko wtedy, gdy S

⊆ C

int

(X ∪ {α}).

Nadto, C

int

jest najmniejsz ˛

a operacj ˛

a konsekwencji nad S

, która spełnia powy˙z-

sze cztery warunki.

B˛edziemy odwoływa´c si˛e te˙z (ale nie w tej notce) do pewnych fragmentów logiki

intuicjonistycznej (logiki pozytywnej Hilberta, czysto implikacyjnej logiki Hilberta).

OGIKA

LASYCZNA

Niech A

b˛edzie zbiorem aksjomatów logiki intuicjonistycznej powi˛ekszonym o

aksjomat ¬¬p → p. Przez klasyczn ˛

a logik˛e zdaniow ˛

a rozumiemy system (R

, Sb(A

))

(lub: (R

0∗

, A

)). Definiujemy operacj˛e konsekwencji Cn

(X) = C

(Sb(A

) ∪ X).

Wprost z definicji zbiorów aksjomatów dla logiki intuicjonistycznej i logiki kla-

sycznej (oraz z monotoniczno´sci operacji konsekwencji) wida´c, ˙ze C

0∗

int

) ⊆

0∗

Zachodz ˛

a nast˛epuj ˛

ace fakty:

• (α → β) ∈ Cn

(X) wtedy i tylko wtedy, gdy β ∈ Cn

(X ∪ {α}).

• Cn

(X ∪ {α ∧ β}) = Cn

(X ∪ {α, β}.

• Cn

(X ∪ {α ∨ β}) = Cn

(X ∪ {α} ∩ Cn

(X ∪ {β}.

• ¬α ∈ Cn

(X) wtedy i tylko wtedy, gdy Cn

(X ∪ {α}) = S

• α ∈ Cn

(X) wtedy i tylko wtedy, gdy Cn

(X ∪ {¬α}) = S

Poniewa˙z, jak mo˙zna wykaza´c:

• operacja konsekwencji wyznaczona przez (R

, Sb(A

)) jest najwi˛eksz ˛

a struk-

turaln ˛

a oraz niesprzeczn ˛

a operacj ˛

a konsekwencji spełniaj ˛

ac ˛

a powy˙zsze pi˛e´c wa-

runków;

• (R

, Sb(A

)) jest najmniejszym systemem spełniaj ˛

acym powy˙zsze pi˛e´c warun-

ków,

wi˛ec warunki te jednoznacznie okre´slaj ˛

a klasyczn ˛

a logik˛e zdaniow ˛

a, czyli nast˛epuj ˛

ace

warunki s ˛

a równowa˙zne:

• Niesprzeczny niezmienniczy system (R, A) spełnia powy˙zsze pi˛e´c warunków.

• (R, A) ≈ (R

, Sb(A

)).

OGIKA

ODALNA

S5.

Niech A

b˛edzie nast˛epuj ˛

acym systemem aksjomatów:

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

• r

modus ponens

• r

∗

podstawiania

• r

dodawania koniunkcji.

Oznaczamy: R

0a∗

= {r

, r

∗

} oraz R

= {r

, r

Twierdzenie o dedukcji dla systemu S5 mo˙ze zasta´c zapisane w nast˛epuj ˛

acych po-

staciach:

• Je´sli X ⊆ {ϕ → ψ : ϕ, ψ ∈ S

}, to dla wszystkich α, β ∈ S

Je´sli β ∈ C

(Sb(A

) ∪ X ∪ {α}), to (α → β) ∈ C

(Sb(A

) ∪ X).

• Dla ka˙zdego X ⊆ S

oraz α ∈ S

: α ∈ C

(Sb(A

) ∪ X) wtedy i tylko

wtedy, gdy ((β

∧ β

∧ . . . ∧ β

) → α) ∈ C

(Sb(A

)) dla pewnych

, β

, . . . , β

∈ X.

Zachodz ˛

a nast˛epuj ˛

ace fakty, charakteryzuj ˛

ace funktory logiki S5 w terminach ope-

racji konsekwencji tej logiki:

• ¬α ∈ C

(Sb(A

) ∪ X) wtedy i tylko wtedy, gdy C

(Sb(A

) ∪ X ∪

{α}) = S

• α ∈ C

(Sb(A

) ∪ X) wtedy i tylko wtedy, gdy C

(Sb(A

) ∪ X ∪

{¬α}) = S

• C

(Sb(A

) ∪ X ∪ {α ∧ β}) = C

(Sb(A

) ∪ X ∪ {α, β}).

• C

(Sb(A

)∪X ∪{α∨β}) = C

(Sb(A

)∪X ∪{α})∩C

(Sb(A

)∪

X ∪ {β}).

Wprowadzamy oznaczenie:

α dla (α → α) → α. Wtedy (α ≡ (β → β) →

α) ∈ C

0a∗

), dla wszystkich α, β ∈ S

Zachodz ˛

a nast˛epuj ˛

ace fakty:

• p → p

• (p → q) → (p → q)

• ¬p → ¬p

• (p ∨ q) → (p ∨ q)

• (p ∧ q) → (p ∧ q).

Definiujemy zbiór formuł

-domkni˛etych S

: α ∈ S

wtedy i tylko wtedy, gdy

α → α ∈ C

0a∗

). Wtedy: α ∈ S

wtedy i tylko wtedy, gdy α ≡

α ∈

0a∗

). Zachodz ˛

a tak˙ze nast˛epuj ˛

ace fakty:

• (α → β) ∈ S

• Je´sli α ∈ S

, to ¬α ∈ S

• Je´sli α, β ∈ S

, to α ∧ β, α ∨ β ∈ S

• C

0a∗

) ⊆ S

Wreszcie, zachodz ˛

a tak˙ze nast˛epuj ˛

ace fakty:

• Dla wszystkich X ⊆ S

oraz α, β ∈ S

β ∈ C

(Sb(A

) ∪ X ∪ {α}) wtedy i tylko wtedy, gdy

(α → β) ∈ C

(Sb(A

) ∪ X).

• α ∈ C

0a∗

∪ {α}) dla wszystkich α ∈ S

Poniewa˙z β /

∈ S

dla dowolnej formuły atomowej β, wi˛ec S

− S

6= ∅. Tak wi˛ec,

reguła:

gdzie α ∈ S

, nie jest wyprowadzalna w (R

, Sb(A

)). Jest ona jednak dopusz-

czalna w (R

, Sb(A

)), czyli:

• je´sli α ∈ C

(Sb(A

)), to α ∈ C

(Sb(A

))

Jak widzieli´smy, reguła r

jest wyprowadzalna w (R

0a∗

, A

Powy˙zsze przedstawienie systemu modalnego S5 pochodzi od Pogorzelskiego i

Wojtylaka. Pod nazw ˛

a S5 wyst˛epuj ˛

a tak˙ze inne systemy modalne.

OGIKI

IELOWARTO ´SCIOWE

UKASIEWICZA

Systemem aksjomatów (niesko´nczenie) wielowarto´sciowej logiki Łukasiewicza jest

zbiór Ł

∞

nast˛epuj ˛

acych 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´sciow ˛

a logik˛e Łukasiewicza rozumiemy system (R

0∗

, Ł

∞

) lub, w

wersji niezmienniczej: (R

, Sb(Ł

∞

)).

Wprowad´zmy oznaczenia:

• p →

q dla q,

• p →

k+1

q dla p → (p →

q).

Sko´nczenie wielowarto´sciowe logiki Łukasiewicza to systemy (R

0∗

, Ł

), dla n >

2, gdzie zbiór Ł

zawiera powy˙zsze aksjomaty oraz dwa aksjomaty nast˛epuj ˛

acej po-

staci:

• (11) (p →

q) → (p →

n−1

• (12) (p ≡ (p →

¬p)) →

n−1

dla ka˙zdej k

6 n takiej, ˙ze k + 2 nie dzieli bez reszty n − 1.

Zachodzi nast˛epuj ˛

acy fakt:

0∗

(Ł

∞

) =

0∗

(Ł

) : n > 2}.

Zachodzi nast˛epuj ˛

aca wersja twierdzenia o dedukcji:

• β ∈ C

(Sb(Ł

) ∪ X ∪ {α}) wtedy i tylko wtedy, gdy

α →

n−1

β ∈ C

(Sb(Ł

) ∪ X)

• β ∈ C

(Sb(Ł

∞

) ∪ X ∪ {α}) wtedy i tylko wtedy, gdy istnieje n taka, ˙ze

α →

β ∈ C

(Sb(Ł

∞

) ∪ X).

W konsekwencji, dla dowolnych X ⊆ S

oraz α ∈ S

• C

(Sb(Ł

) ∪ X ∪ {α}) = S

wtedy i tylko wtedy, gdy

α →

n−2

¬α ∈ C

(Sb(Ł

) ∪ X)

• C

(Sb(Ł

∞

) ∪ X ∪ {α}) = S

wtedy i tylko wtedy, gdy istnieje n taka, ˙ze

α →

¬α ∈ C

(Sb(Ł

∞

) ∪ X).

1.9. Matryce logiczne

Okre´slimy teraz semantyk˛e dla rachunków zdaniowych. Poj˛eciem podstawowym

b˛edzie poj˛ecie matrycy logicznej. Wszystkie poj˛ecia algebraiczne potrzebne do okre-

´slenia zarówno tego poj˛ecia, jak i podstawowych własno´sci matryc logicznych podane

zostały w Preliminariach matematycznych.

1.9.1. Algebry prauporz ˛

adkowane

Algebr ˛

a prauporz ˛

adkowan ˛

a (w skrócie: prp-algebr ˛

a) nazywamy ka˙zdy układ o

postaci (A,

6), gdzie A jest algebr ˛

a, a

6 praporz ˛

adkiem (relacj ˛

a zwrotn ˛

a i przechod-

ni ˛

a) w A, czyli w uniwersum algebry A. Je´sli operacje samej algebry A wyznaczaj ˛

jaki´s porz ˛

adek w A (np. porz ˛

adek kratowy), to nie musi on by´c ani to˙zsamy, ani jak-

kolwiek zwi ˛

azany z praporz ˛

adkiem

Niech S b˛edzie algebr ˛

a j˛ezyka zdaniowego z niesko´nczonym zbiorem At zmien-

nych zdaniowych oraz zbiorem wszystkich formuł S i niech (A,

6) b˛edzie prp-algebr ˛

podobn ˛

a do S. Definiujemy operacj˛e konsekwencji wyznaczon ˛

a przez A = (A,

6),

czyli funkcj˛e

−

→

: ℘(S) → ℘(S):

• α ∈

−

→

(X) wtedy i tylko wtedy, gdy h

(α) ∈ F(h

(X)), dla ka˙zdego podsta-

wienia v : At → A.

Zatem α ∈

−

→

(X) wtedy i tylko wtedy, gdy h

(α) nale˙zy do filtru wyznaczonego

(generowanego) przez h

(X), dla ka˙zdego podstawienia v : At → A.

WAGA

. Posługujemy si˛e tu (i dalej) poj˛eciem filtru w prp-algebrach. Przypominamy

te˙z, ˙ze F(X) jest najmniejszym filtrem zawieraj ˛

acym zbiór X.

Bezpo´srednio z tej definicji wynika, ˙ze:

• α ∈

−

→

(X) wtedy i tylko wtedy, gdy h

(α) ∈ F , dla ka˙zdego filtru w prp-

algebrze A = (A,

6) oraz ka˙zdego podstawienia v : At → A.

Operacja

−

→

A istotnie jest operacj ˛

a konsekwencji, mamy bowiem dla wszystkich

X ⊆ S:

• X ⊆

−

→

(X).

• Je´sli X ⊆ Y , to

−

→

(X) ⊆

−

→

(Y ).

•

−

→

(

−

→

(X)) ⊆

−

→

(X).

• h

(

−

→

(X)) ⊆

−

→

(X)) dla wszystkich e : At → A.

Ostatni z powy˙zszych warunków implikuje, ˙ze

−

→

A jest strukturaln ˛

a operacj ˛

a konse-

kwencji.

−

→

A nie musi jednak by´c finitystyczna.

Przypominamy, ˙ze dla dowolnego praporz ˛

adku (A,

6), X ⊆ A oraz a ∈ A:

• a ∈ B

(X) wtedy i tylko wtedy, gdy y 6 a dla wszystkich y ∈ X

• a ∈ B

(X) wtedy i tylko wtedy, gdy a 6 y dla wszystkich y ∈ X

• Great(X) = X ∩ B

(X)

• Least(X) = X ∩ B

(X)

• Sup(X) = Least(B

(X))

• Inf (X) = Great(B

(X)).

Dla dowolnej prp-algebry A = (A,

6) definiujemy:

• α ∈ E(A) wtedy i tylko wtedy, gdy h

(α) ∈ Great(A), dla ka˙zdego podsta-

wienia v : At → A.

Poniewa˙z Great(A) = F(∅), wi˛ec mamy: E(A) =

−

→

(∅).

Dwie prp-algebry nazywamy izomorficznymi, gdy istnieje ich izomorfizm, zacho-

wuj ˛

acy porz ˛

adek. Je´sli A i B s ˛

a izomorficzne, to piszemy A ∼

= B.

Algebra B = (B,

) jest podstruktur ˛

a algebry A = (A,

) (piszemy wtedy:

⊆ A), gdy B jest podalgebr ˛

a A oraz

jest obci˛eciem porz ˛

adku

do B.

Zachodz ˛

a nast˛epuj ˛

ace fakty:

• Je´sli A ∼

= B, to

−

→

−

→

• Je´sli B ⊆ A, to

−

→

−

→

1.9.2. Reguły A-niezawodne i A-normalne

Dla dowolnych X ⊆ S, r ∈ R

oraz prp-algebry A niech:

• r ∈ V (A, X) wtedy i tylko wtedy, gdy dla ka˙zdego (P, α) ∈ r:

je´sli P ⊆

−

→

(X), to α ∈

−

→

(X).

• r ∈ N (A, X) wtedy i tylko wtedy, gdy dla ka˙zdego (P, α) ∈ r:

α ∈

−

→

(X ∪ P ).

Je´sli 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 ˛

a nast˛epuj ˛

ace fakty:

• N (A, X) =

T{V (A, Y ) : X ⊆ Y }

• N (A) =

T{V (A, X) : X ⊆ S}

• N (A) = Der(

−

→

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

• V (A) = Adm(

−

→

) = Adm(N (A), E(A))

• r

∗

∈ V (A)

• N (A) ⊆ V (A) (odwrotna inkluzja nie zachodzi).

1.9.3. Matryce logiczne

Ka˙zd ˛

a par˛e M = (A, A

∗

), gdzie A jest algebr ˛

a, a A

∗

jest podzbiorem uniwer-

sum algebry A (czyli A

∗

⊆ A) nazywamy matryc ˛

a logiczn ˛

a. Zbiór A

∗

jest zbiorem

elementów wyró˙znionych matrycy M.

Zbiór E(M) wszystkich formuł M-prawdziwych (M-tautologii) jest zdefiniowany

nast˛epuj ˛

aco:

• α ∈ E(M) wtedy i tylko wtedy, gdy h

(α) ∈ A

∗

, dla ka˙zdego v : At → A.

Zbiór E(M) nazywany jest tak˙ze zawarto´sci ˛

a matrycy M.

Z kolei, operacja konsekwencji matrycowej

−

→

M ma nast˛epuj ˛

ac ˛

a definicj˛e:

• α ∈

−

→

(X) wtedy i tylko wtedy, gdy dla ka˙zdego v : At → A

je´sli h

(X) ⊆ A

∗

, to h

(α) ∈ A

∗

Mamy oczywi´scie E(M) =

−

→

(∅).

Podamy teraz zwi ˛

azki mi˛edzy konsekwencj ˛

a matrycow ˛

a a wprowadzon ˛

a wcze´sniej

operacj ˛

a konsekwencji w prp-algebrach.

Niech A b˛edzie algebr ˛

a o uniwersum A, podobn ˛

a do algebry (ustalonego) j˛ezyka

zdaniowego S. Gdy wyró˙znimy jaki´s podzbiór A

∗

w uniwersum A, otrzymujemy ma-

tryc˛e logiczn ˛

a M = (A, A

∗

). Rozwa˙zymy dwa przypadki:

• A

∗

jest pusty lub identyczny z uniwersum A;

• ∅ 6= A

∗

Matryca M = (A, A) generuje sprzeczn ˛

a operacj˛e konsekwencji, czyli w tym

przypadku

−

→

(X) = S dla wszystkich X ⊆ S. Z kolei, matryca M = (A, ∅) generuje

nast˛epuj ˛

ac ˛

a operacj˛e konsekwencji:

•

−

→

(X) = ∅, gdy X = ∅

•

−

→

(X) = S, gdy X 6= ∅.

Rozwa˙zmy teraz przypadek drugi, czyli matryc˛e M = (A, A

∗

), gdzie ∅ 6= A

∗

W zbiorze A definiujemy relacj˛e praporz ˛

adku

• x 6 y wtedy i tylko wtedy, gdy x /

∈ A

∗

lub y ∈ A

∗

Wtedy A

∗

jest jedynym filtrem wła´sciwym w zbiorze prauporz ˛

adkowanym (A,

6),

poniewa˙z:

• Great(A) = A

∗

• Least(A) = A − A

∗

• F(X) = A

∗

, gdy X ⊆ A

∗

• F(X) = A

∗

, gdy X A

∗

Mamy zatem w tym przypadku:

−

→

(X) =

−

→

(X), gdzie A = (A, 6) jest prp-

algebr ˛

a wyznaczon ˛

a w podany wy˙zej sposób przez zbiór A

∗

. I to wła´snie jest podsta-

wowy zwi ˛

azek mi˛edzy konsekwencjami matrycowymi a konsekwencjami wyznaczo-

nymi przez prp-algebry.

Podobnie jak dla prp-algebr, okre´slamy reguły niezawodne oraz reguły normalne

w matrycy M:

• r ∈ V (M) wtedy i tylko wtedy, gdy dla ka˙zdego (P, α) ∈ r:

je´sli P ⊆ E(M), to α ∈ (M);

• r ∈ N (M) wtedy i tylko wtedy, gdy dla ka˙zdego (P, α) ∈ r: α ∈

−

→

(P ).

Zachodz ˛

a wtedy nast˛epuj ˛

ace fakty:

• N (M) = Der(

−

→

)

• V (M) = Adm(

−

→

)

• r

∗

∈ V (M) − N (M), je´sli ∅ A

∗

Z olbrzymiej mnogo´sci faktów dotycz ˛

acych matryc logicznych wybieramy, na po-

trzeby tej notatki, jedynie niektóre ustalenia.

Je´sli M jest matryc ˛

a sko´nczon ˛

a, to

−

→

M jest finitystyczn ˛

a operacj ˛

a konsekwencji.

Mówimy, ˙ze zbiór X ⊆ S jest spełnialny w matrycy M = (A, A

∗

), gdy istnieje

warto´sciowanie v : At → A takie, ˙ze: h

(X) ⊆ A

∗

. Je´sli X jest spełnialny w M, to

piszemy X ∈ Sat(M).

Je´sli M jest matryc ˛

a sko´nczon ˛

a, 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˛ed ˛

a matrycami podobnymi. Mówimy, ˙ze:

• M jest podmatryc ˛

a N, gdy A jest podalgebr ˛

a B oraz A

∗

= A ∩ B

∗

. Je´sli M jest

podmatryc ˛

a N, to piszemy M ⊆ N.

• M jest izomorficzna z N, gdy istnieje izomorfizm h algebry A na algebr˛e B

taki, ˙ze dla wszystkich x ∈ A: x ∈ A

∗

wtedy i tylko wtedy, gdy h(x) ∈ B

∗

Je´sli M jest izomorficzna z N, to piszemy M ∼

= N.

Zachodz ˛

a nast˛epuj ˛

ace fakty:

• Je´sli M ∼

= N, to

−

→

−

→

• Je´sli N ⊆ M, to

−

→

−

→

•

−

→

(Sb(X)) =

T{E(N) : N ⊆ M ∧ X ⊆ E(N)}.

Relacja R jest kongruencj ˛

a matrycy M = (A, A

∗

), gdy R jest kongruencj ˛

a alge-

bry A oraz dla wszystkich x, y ∈ A:

• je´sli xRy i x ∈ A

∗

, to y ∈ A

∗

Ka˙zda kongruencja R matrycy M = (A, A

∗

) wyznacza matryc˛e ilorazow ˛

a M/R =

(A/R, A

∗

/R), gdzie A/R jest algebr ˛

a ilorazow ˛

a oraz A

∗

= {[a]

: a ∈ A

∗

Je´sli R jest kongruencj ˛

a matrycy M, to konsekwencja matrycowa wyznaczona

przez M jest identyczna z konsekwencj ˛

a matrycow ˛

a wyznaczon ˛

a przez matryc˛e ilo-

razow ˛

−

→

−−−→

/R.

Produktem rodziny matryc podobnych {M

}

t∈T

, gdzie M

= (A

, A

∗

) nazy-

wamy matryc˛e

t∈T

= (

t∈T

∗

Zachodz ˛

a nast˛epuj ˛

ace fakty:

• E(

t∈T

) =

T{E(M

) : t ∈ T }.

• Dla ka˙zdego X ⊆ S:

−−−−→

t∈T

(X) =

−→

(X) : t ∈ T }, o ile X ∈ Sat(M

); w

przeciwnym przypadku

−−−−→

t∈T

(X) = S.

Szczególn ˛

a rol˛e pełni ˛

a tzw. matryce Lindenbauma. Dla dowolnych R ⊆ R

oraz

X ⊆ S matryc˛e:

R,X

= (S, C

(X))

nazywamy matryc ˛

a Lindenbauma dla systemu (R, X).

Zachodz ˛

a nast˛epuj ˛

ace fakty:

• E(M

R,X

) = {α : Sb(α) ⊆ C

(X)}.

• Je´sli r

∗

∈ Adm(R, X), to E(M

R,X

) = C

(X).

Matrycy Lindenbauma nie nale˙zy myli´c z algebr ˛

a Lindenbauma-Tarskiego. Je´sli

(R, X) jest logik ˛

a zdaniow ˛

a nad standardowym j˛ezykiem S

= (S

, →, ∨, ∧, ¬), to

definiujemy relacj˛e: α ∼

R,X

β wtedy i tylko wtedy, gdy α → β, β → α ∈ C

(X).

Przy odpowiednich zało˙zeniach o (R, X) relacja ∼

R,X

jest kongruencj ˛

a matrycy Lin-

denbauma M

R,X

. Wtedy algebr˛e ilorazow ˛

a S

/ ∼

R,X

= (S

/ ∼

R,X

, a, ∪, ∩, −) na-

zywamy algebr ˛

a 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

a [β]

∼

R,X

= [α → β]

∼

R,X

• −[α]

∼

R,X

= [¬α]

∼

R,X

W kracie (S

/ ∼

R,X

, ∪, ∩) mamy porz ˛

adek kratowy: [α]

∼

R,X

6 [β]

∼

R,X

wtedy i

tylko wtedy, gdy α → β ∈ C

(X). Przy stosownych zało˙zeniach, krata ta ma zero i

jedynk˛e.

1.9.4. Adekwatno´s´c

Niech (R, X) b˛edzie systemem logiki zdaniowej, a M matryc ˛

a logiczn ˛

a podobn ˛

do algebry j˛ezyka tego systemu. Je˙zeli E(M) = C

(X) = C

R,X

(∅), to mówimy, ˙ze

matryca M jest (słabo) adekwatna dla (R, X).

Zachodzi nast˛epuj ˛

acy fakt:

• Dla ka˙zdej logiki zdaniowej (R, X) takiej, ˙ze r

∗

∈ Adm(R, X) oraz R−{r

∗

} ⊆

Struct istnieje matryca M taka, ˙ze: C

(X) = E(M) oraz R − {r

∗

} ⊆ N (M).

Mogłoby si˛e wydawa´c, ˙ze fakt powy˙zszy czyni pytanie o istnienie semantyki dla

dowolnych rachunków zdaniowych całkiem trywialnym: dla ka˙zdego rachunku (R, X)
takiego, ˙ze r

∗

∈ Adm(R, X) oraz R − {r

∗

} ⊆ Struct zachodzi C

(X) = E(M

R,X

gdzie M

R,X

jest matryc ˛

a Lindenbauma dla (R, X). Tak jednak nie jest: poszukujemy

nie całkiem dowolnych semantyk dla rachunków zdaniowych, lecz raczej semantyk,
spełniaj ˛

acych pewne okre´slone warunki. Dla przykładu, wiemy, i˙z:

• M

jest minimaln ˛

a matryc ˛

a adekwatn ˛

a dla logiki klasycznej.

• Logika modalna (R

0a∗

, A

) nie ma ˙zadnej sko´nczonej matrycy adekwatnej.

Istnieje jednak dla niej niesko´nczona matryca adekwatna (matryca Wajsberga).

• Istniej ˛

a matryce sko´nczone, które nie s ˛

a sko´nczenie aksjomatyzowalne (wyniki

Wojtylaka i Pałasi´nskiej).

• Sko´nczenie warto´sciowe wielowarto´sciowe logiki Łukasiewicza maj ˛

a sko´nczone

matryce słabo adekwatne.

• Niesko´nczenie warto´sciowa logika Łukasiewicza ma niesko´nczon ˛

a matryc˛e słabo

adekwatn ˛

Je´sli C

(X) = E(M), to:

• Adm(R, X) = V (M)

• Der(R, X) ⊆ V (M)

• N (M) ⊆ Adm(R, X).

Mówimy, ˙ze matryca M jest silnie adekwatna dla logiki (R, X) (lub dla operacji

konsekwencji C

R,X

), gdy dla wszystkich Y ⊆ S:

(X ∪ Y ) =

−

→

(Y ).

Wprost z definicji wynika, ˙ze M jest silnie adekwatna dla logiki (R, X) wtedy i

tylko wtedy, gdy N (M) = Der(R, X).

Niech X

b˛edzie zbiorem nast˛epuj ˛

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

• p → (p ∨ q)

• q → (p ∨ q)

• (p → s) → ((q → s) → ((p ∨ q) → s)).

Zachodzi wtedy nast˛epuj ˛

acy fakt (S

to zbiór formuł czysto implikacyjnych):

• Je´sli (R, X) jest systemem niezmienniczym nad S

takim, ˙ze r

∈ Der(R, X)

oraz X

⊆ C

(X), to istnieje matryca M silnie adekwatna dla (R, X).

O matrycach silnie adekwatnych dla ró˙znych systemów logicznych wiadomo np.,

˙ze:

• Nie istniej ˛

a matryce silnie adekwatne dla systemów modalnych S1–S3 Lewisa.

• Matryca M

jest silnie adekwatna dla logiki klasycznej.

• Istnieje matryca silnie adekwatna dla systemu modalnego (R

, Sb(A

)) (ró˙zna

od wspomnianej wcze´sniej matrycy Wajsberga).

Dla celów tej notatki nie jest potrzebne podawanie innych jeszcze rodzajów ade-

kwatno´sci, rozwa˙zanych w literaturze przedmiotu.

1.9.5. Filtr-konsekwencja

Zdefiniujmy nast˛epuj ˛

ace dwie operacje konsekwencji:

• Zbiór F C

(X), dla X ⊆ S

niech b˛edzie zbiorem tych wszystkich formuł

α ∈ S

, które w ka˙zdej algebrze Heytinga A spełniaj ˛

a nast˛epuj ˛

acy warunek

dla wszystkich v : At → A:

(α) ∈ F(h

(X)).

• Zbiór F C

(X), dla X ⊆ S

niech b˛edzie zbiorem tych wszystkich formuł

α ∈ S

, które w ka˙zdej algebrze Boole’a A spełniaj ˛

a nast˛epuj ˛

acy warunek dla

wszystkich v : At → A:

(α) ∈ F(h

(X)).

Dla F C równego F C

lub F C

zachodz ˛

a wtedy nast˛epuj ˛

ace fakty:

• X ⊆ F C(X).

• Je´sli X ⊆ Y , to F C(X) ⊆ F C(Y ).

• F C(F C(X)) ⊆ F C(X).

• h

(F C(X)) ⊆ F C(h

(X)) dla wszystkich e : At → S.

• F C(X) ⊆

S{F C(Y ) : Y ∈ F in(X)}.

• Je´sli β ∈ F C(X), to (α → β) ∈ F C(X).

• β ∈ F C(X ∪ {α}) wtedy i tylko wtedy, gdy (α → β) ∈ F C(X).

• Je´sli α, α → β ∈ F C(X), to β ∈ F C(X).

• Sb(F C(∅)) ⊆ F C(∅).

Przy pomocy operacji F C

oraz F C

udowodni´c mo˙zna twierdzenia o zupełno´sci

dla, odpowiednio, logiki intuicjonistycznej oraz logiki klasycznej.

Niech (R

, Sb(A

int

)) b˛edzie logik ˛

a intuicjonistyczn ˛

a. Przypominamy, ˙ze filtr-kon-

sekwencja F C

zdefiniowana jest warunkiem:

• α ∈ F C

(X) wtedy i tylko wtedy, gdy α ∈

−

→

A(X), dla ka˙zdej algebry Heytinga

Zachodz ˛

a nast˛epuj ˛

ace fakty:

• A

int

⊆ F C

(∅).

• C

(Sb(A

int

) ∪ X) = F C

(X) dla wszystkich X ⊆ S

• Dla dowolnych α ∈ S

oraz X ⊆ S

: α ∈ C

0∗

int

∪ X) wtedy i tylko wtedy,

gdy dla ka˙zdej algebry Heytinga A, X ⊆ E(A) implikuje α ∈ E(A).

• Dla dowolnej α ∈ S

: α ∈ C

0∗

int

) wtedy i tylko wtedy, gdy dla ka˙zdej

sko´nczonej algebry Heytinga A, α ∈ E(A).

• C

0∗

int

) =

T{E(J

) : n > 1}, gdzie J

s ˛

a algebrami Ja´skowskiego.

• Dla ka˙zdego sko´nczonego X ⊆ S

: C

(Sb(A) ∪ X) =

−

→

: n > 1}.

Z kolei, zajmijmy si˛e systemem logiki klasycznej (R

, Sb(A

)) i filtr-konsekwencj ˛

F C

. Zachodz ˛

a nast˛epuj ˛

ace fakty:

• Zbiór F C

(∅) wszystkich tautologii Boolowskich jest zbiorem tych wszystkich

formuł α ∈ S

, które w ka˙zdej algebrze Boole’a B i dla ka˙zdego warto´sciowania

v : At → B spełniaj ˛

a warunek:

(α) = 1

• A

⊆ F C

(∅).

• C

(Sb(A

) ∪ X) = F C

(X) dla wszystkich X ⊆ S

• C

(Sb(A

) ∪ X) =

−

→

(X) dla wszystkich X ⊆ S

1.10. Ró˙zne poj˛ecia zupełno´sci rachunków zdaniowych

Podane wy˙zej przykładowe twierdzenia o pełno´sci logik zdaniowych (tu: intuicjo-

nistycznej oraz klasycznej) nie wyczerpuj ˛

a cało´sci problematyki zwi ˛

azanej z zupełno-

´sci ˛

a systemów logiki zdaniowej. Wiele dalszych problemów dotyczy np.: uogólnionej

zupełno´sci, zupełno´sci w sensie Posta, strukturalnej zupełno´sci, itd. Bardzo wyryw-
kowo podamy kilka znanych rezultatów w tej dziedzinie.

1.10.1. Uogólniona zupełno´s´c

Niech S = (S, F

, . . . , F

) b˛edzie algebr ˛

a j˛ezyka zdaniowego z przeliczalnym

zbiorem zmiennych. Niech Γ ⊆ S. Dla dowolnych A ⊆ S oraz R ⊆ R

definiujemy:

• (R, A) ∈ Γ-Cpl wtedy i tylko wtedy, gdy Adm(R, A) ∩ Struct(Γ) ⊆ Der(R, A).

Je´sli (R, A) ∈ Γ-Cpl, to mówimy, ˙ze (R, A) jest Γ-zupełny.

• (R, A) ∈ Γ-Max wtedy i tylko wtedy, gdy (R, A) ∈ Inv(Γ) oraz nie istnieje

system (R

, A

) ∈ Inv(Γ) taki, ˙ze (R, A) ≺ (R

, A

). Je´sli (R, A) ∈ Γ-Max,

to mówimy, ˙ze (R, A) jest Γ-maksymalny.

Powy˙zsze poj˛ecia wyrazi´c mo˙zna równie˙z 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 ˛

a nast˛epuj ˛

ace fakty:

• Γ-Max ⊆ Γ-Cpl ∩ Inv(Γ)

• Je´sli (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´sli r

∗

|Γ ∈ Adm(R, A) oraz ∅ 6= C

(A) 6= S, to nast˛epuj ˛

ace warunki s ˛

równowa˙zne:

1. Der(R, A) ∩ Struct(Γ) = V (M) ∩ Struct(Γ).

2. (R, A) ∈ Γ-Cpl oraz E(M) = C

(A).

• Je´sli E(M) = C

(A), to nast˛epuj ˛

ace warunki s ˛

a równowa˙zne:

1. Der(R, A) ∩ Struct(Γ) = V (M) ∩ Struct(Γ).

2. (R, A) ∈ Γ-Cpl.

Dla ka˙zdego X ⊆ S niech:

• (P, α) ∈ Γ − r

wtedy i tylko wtedy, gdy: je´sli (h

◦ . . . ◦ h

)(P ) ⊆ X), to

◦ . . . ◦ h

)(α) ∈ X, dla n > 0 oraz e

, . . . , e

: At → Γ.

Wtedy nast˛epuj ˛

ace warunki sa równowa˙zne:

• (R, A) ∈ Γ-Cpl.

• Γ − r

(A)

∈ Der(R, A).

Zachodz ˛

a nast˛epuj ˛

ace fakty:

• Je´sli (R, A) ∈ Inv(Γ), to nast˛epuj ˛

ace warunki s ˛

a równowa˙zne:

1. (R, A) ∈ Γ-Cpl.

2. Je´sli C

(A) = C

), to (R

, A

) (R, A), dla wszystkich (R

, A

) ∈

Inv(Γ).

• Nast˛epuj ˛

ace warunki s ˛

a równowa˙zne:

1. (R, A) ∈ Γ-Cpl.

2. Je´sli C

(A) = C

), to (R

, A

) (R, A), dla wszystkich A

⊆ S

oraz R

⊆ Struct(Γ).

• Niech (R, A) ∈ Inv(Γ). Wtedy:

1. (R, A) ∈ Γ-Max wtedy i tylko wtedy, gdy: je´sli (R ∪ {r}, A) ∈ Cns, to

Adm(R ∪ {r}, A) ∩ Struct(Γ) ⊆ Der(R, A) dla wszystkich r ∈ R

2. Je´sli (R, A) ∈ Γ-Max, to C

(Sb

({α}) ∪ A) = S dla ka˙zdej α /

∈ C

(A).

• Nast˛epuj ˛

ace warunki s ˛

a równowa˙zne:

1. (R, A) ∈ Γ-Max.

2. (R, A) ∈ Γ-Cpl ∩ Inv(Γ) oraz (R ∪ {r

∗

|Γ}, A) ∈ ∅-Cpl.

• Je´sli C ∈ STRUCT(Γ), to:

1. C ∈ Γ-MAX wtedy i tylko wtedy, gdy dla wszystkich r ∈ Struct(Γ): je´sli

r /

∈ DER(C), to C ∪ C

∈ CNS. [Tutaj stosujemy oznaczenie: C

(X) =

{r}

(X).]

2. C ∈ Γ-MAX wtedy i tylko wtedy, gdy dla wszystkich r ∈ Struct(Γ): je´sli

r ∈ ADM(C) − DER(C), to C ∪ C

∈ CNS.

• Dla ka˙zdego (R, A) ∈ Cns istnieje (R

, A

) ∈ Γ-Cpl taki, ˙ze (R, A) (R

, A

) ∈

Cns.

• Je´sli (R, A) ∈ Inv(Γ)∩Cns oraz (R∪{r

∗

|Γ}, A) ∈ Comp, to istnieje (R

, A

) ∈

Γ-Max taki, ˙ze (R, A) (R

, A

) ∈ Cns.

Z dwóch ostatnich z powy˙zszych twierdze´n widzimy zatem, ˙ze:

• Dowolny niesprzeczny system (R, A) mo˙zna rozszerzy´c do systemu Γ-zupełnego.

Wystarczy bowiem wzi ˛

a´c: R

= Adm(R, A) oraz A

= A.

• Dowolny zwarty system (R, A) mo˙zna rozszerzy´c do systemu Γ-maksymalnego.

Przypominamy, ˙ze (R, A) ∈ Comp, gdy dla ka˙zdego Y ⊆ S istnieje X ∈
F in(Y ) taki, ˙ze je´sli C

(A ∪ Y ) = S, to C

(A ∪ X) = S.

Ponadto, system (R

, A

), o którym mowa w przedostatnim z powy˙zszych twier-

dze´n ma nast˛epuj ˛

ace własno´sci:

• C

(A) = C

• Je´sli (R, A) ∈ Γ-Cpl, to (R

, A

) ≈ (R, A).

• Je´sli (R, A) ∈ Inv(Γ), to (R

, A

) ∈ Inv(Γ)

• Je´sli (R, A) ∈ Inv(Γ) oraz (R ∪ {r

∗

|Γ}, A) ∈ ∅-Cpl, to (R

, A

) ∈ Γ-Max.

• (R

, A

) /

∈ Γ-Max dla pewnego (R, A) ∈ Inv(Γ) i pewnego Γ ⊆ S.

1.10.2. Zupełno´s´c w sensie Posta

Przypomnijmy:

• (R, A) ∈ Cpl wtedy i tylko wtedy, gdy C

(A ∪ {α}) = S dla wszystkich

α /

∈ C

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

, A

) ∈ Cns, nie

zachodzi (R, A) ≺ (R

, A

Zachodz ˛

a nast˛epuj ˛

ace fakty:

• ∅-Cpl = Cpl = Max.

• (R, A) ∈ Cpl wtedy i tylko wtedy, gdy (R ∪ {r}, A) /

∈ Cns, dla wszystkich

r /

∈ Der(R, A).

• Je´sli M jest matryc ˛

a logiczn ˛

a oraz ∅ 6= C

(A) 6= S, to:

1. Der(R, A) = V (M) wtedy i tylko wtedy, gdy E(M) = C

(A) oraz

(R, A) ∈ Cpl.

2. Je´sli E(M) = C

(A), to (R, A) ∈ Cpl wtedy i tylko wtedy, gdy

Der(R, A) = V (M).

• Je´sli r

∗

∈ Adm(R, A), to Der(R, A) = V (M

R,A

) wtedy i tylko wtedy, gdy

(R, A) ∈ Cpl.

• Dla ka˙zdego (R, A) ∈ Cns istnieje (R

, A

) ∈ Cns ∩ Cpl taki, ˙ze (R, A) ≺

, A

). Tak wi˛ec, ka˙zdy niesprzeczny system logiczny (R, A) mo˙ze zosta´c

rozszerzony do systemu niesprzecznego i Post-zupełnego. Przy tym, rozszerze-
nie (R

, A

) ma nast˛epuj ˛

ace własno´sci:

1. C

(A) = C

2. Je´sli (R, A) ∈ Cpl, to (R, A) ≈ (R

, A

• Je´sli (R, A) ∈ Comp oraz C

(A ∪ X) 6= S, to istnieje Y ⊆ S taki, ˙ze:

1. C

(A ∪ X) ⊆ C

(A ∪ Y ) 6= S

2. C

(A ∪ Y ) = Y

3. C

(A ∪ Y ∪ {α}) = S dla wszystkich α /

∈ Y .

Dla dowolnego (R, X) definiujemy rodzin˛e L(R, X) nadzbiorów Lindenbauma

dla C

(X):

• L(R, X) = {Y : X ⊆ Y = C

(Y ) 6= S ∧ (∀α /

∈ Y ) C

(Y ∪ {α}) = S}.

Dla ka˙zdego Y ∈ L(R, X) system (R, Y ) jest wyznaczony jednoznacznie. Wtedy

oczywi´scie (R, Y ) ∈ Cns ∩ Cpl. System (R, Y ) nazywamy w takim przypadku nad-
systemem Lindenbauma dla systemu (R, X).

Wprowadzimy pewne miary stopnia niezupełno´sci oraz stopnia maksymalno´sci

systemów logicznych.

• Przez (globalny) stopie ´n niezupełno´sci systemu (R, A) rozumiemy moc rodziny:

{Der(R ∪ R

, A ∪ A

) : A

⊆ S ∧ R

⊆ R

• Je´sli w definicji powy˙zszej ograniczymy si˛e do systemów (R

, A

) ∈ Inv, to

otrzymujemy stopie ´n maksymalno´sci systemu (R, A) ∈ Inv.

• Dla strukturalnych operacji konsekwencji C, przez stopie ´n maksymalno´sci C

rozumiemy moc rodziny {C

∈ Struct : C 6 C

• Stopniem zupełno´sci systemu (R, A) nazywamy liczb˛e kardynaln ˛

a dc(R, A)

równ ˛

a mocy rodziny:

(A ∪ X) : X ⊆ S}.

Zachodz ˛

a nast˛epuj ˛

ace fakty:

• Je´sli M jest matryc ˛

a sko´nczon ˛

a, to dc(

−

→

◦ Sb) < ℵ

• Je´sli M jest matryc ˛

a funkcyjnie zupełn ˛

a, to

−

→

◦Sb ∈ CPL, czyli dc(

−

→

◦Sb) 6 2.

Dla logik finitystycznych (które niekoniecznie s ˛

a zwarte) zachodzi nast˛epuj ˛

ace

twierdzenie Łosia-Lindenbauma-Assera:

• Je´sli C

jest finitystyczna oraz α /

∈ C

(A ∪ X), to istnieje Y ⊆ S taki, ˙ze:

1. C

(A ∪ X) ⊆ Y = C

(A ∪ Y ) oraz α /

∈ Y

2. α ∈ C

(A ∪ Y ∪ {β}) dla wszystkich β /

∈ C

(A ∪ Y ).

Dla dowolnej α ∈ S niech:

• L

(R, A) = {Y : X ⊆ C

(Y ) = Y ∧ α /

∈ Y ∧ (∀β /

∈ Y ) α ∈ C

(Y ∪ {β})}.

Ka˙zdy element rodziny L

(R, A) nazywamy α-relatywnym nadzbiorem Linden-

bauma dla systemu (R, A).

Twierdzenie Łosia-Lindenbauma-Assera przyjmuje zatem nast˛epuj ˛

ac ˛

a posta´c (gdy

rozwa˙zamy jedynie reguły wnioskowania o sko´nczonych zbiorach przesłanek):

• Dla ka˙zdej α /

∈ C

(A): L

(R, A) 6= ∅.

Ustalmy własno´sci logiki klasycznej, je´sli chodzi o wprowadzone wy˙zej poj˛ecia.

Przypomnijmy, ˙ze Cn

jest operacj ˛

a konsekwencji wyznaczon ˛

a przez niezmiennicz ˛

wersj˛e logiki klasycznej R

, Sb(A

), czyli:

(X) = C

(Sb(A

) ∪ X).

Zachodz ˛

a (jak wiadomo z elementarnego kursu logiki) nast˛epuj ˛

ace fakty, dla ka˙z-

dego X ⊆ S

oraz α, β ∈ S

• α ∈ Cn

(X ∪ {β}) wtedy i tylko wtedy, gdy (β → α) ∈ Cn

(X).

• Cn

(X ∪ {¬α}) 6= S

wtedy i tylko wtedy, gdy α /

∈ Cn

(X).

• Cn

(X ∪ {α}) 6= S

wtedy i tylko wtedy, gdy ¬α /

∈ Cn

(X).

Z pomoc ˛

a powy˙zszych faktów dokona´c mo˙zna szeregu dalszych ustale´n, np.:

• (R

, Sb(A

) ∪ X) ∈ Cns wtedy i tylko wtedy, gdy istnieje α ∈ S

taka, ˙ze nie

zachodzi: α, ¬α ∈ Cn

(X).

• (R

, Sb(A

) ∪ X) ∈ Cpl wtedy i tylko wtedy, gdy dla ka˙zdej α ∈ S

: albo

α ∈ Cn

(X), albo ¬α ∈ Cn

(X).

• L

, Sb(A

)) ⊆ L(R

, Sb(A

)).

• Je´sli α /

∈ Cn

(X), to istnieje zbiór Y ⊆ S

taki, ˙ze:

1. Cn

(X) ⊆ Y = Cn

(Y ) oraz α /

∈ Cn

(Y )

2. Cn

(Y ) ∪ {β} = S

dla wszystkich β /

∈ Y .

• Dla wszystkich X ⊆ S

oraz α ∈ S

1. Je´sli α /

∈ Cn

(X), to istnieje Y ∈ L(R

, Sb(A

)) taki, ˙ze X ⊆ Y oraz

α /

∈ Y .

2. Cn

(X) =

T{Y ⊆ S

: X ⊆ Y ∈ L(R

, Sb(A

))}.

• Dla ka˙zdego Y ∈ L(R

, Sb(A

)):

1. α → β ∈ Y wtedy i tylko wtedy, gdy: je´sli α ∈ 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 .

• A

⊆ E(M

) oraz r

∈ N (M

• Cn

(X) 6= S

wtedy i tylko wtedy, gdy X ∈ Sat(M

), dla wszystkich X ⊆ S

• Dla wszystkich X ⊆ S

: X ∈ Sat(M

) wtedy i tylko wtedy, gdy Y ∈ Sat(M

dla ka˙zdego Y ∈ F in(X).

• C

(Sb(A

)) = C

0∗

) = E(M

• Der(R

, Sb(A

)) = N (M

• Der(R

0∗

, A

) = Adm(R

, Sb(A

)) = Adm(R

0∗

, A

• C

(Sb(A

) ∪ X) =

−→

(X), dla wszystkich X ⊆ S

• (R

0∗

, A

) ∈ Cpl.

• dc(R

, Sb(A

)) = c. W konsekwencji, stopie´n zupełno´sci dowolnej logiki słab-

szej od (R

, Sb(A

)) tak˙ze jest równy kontinuum.

1.10.3. Jednoznaczno´s´c rozszerze ´n Lindenbauma

Interesuj ˛

a 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´sli (R, X) ∈ T dla pewnego M 6= S, to mówimy, ˙ze (R, X) ma własno´s´c

Tarskiego.

Podamy pewne informacje dotycz ˛

ace rozszerze´n Lindenbauma w przypadku:

• logiki intuicjinistycznej

• logik wielowarto´sciowych Łukasiewicza.

Wprowad´zmy oznaczenie: Z

= C

0∗

Przypominamy, ˙ze C

int

jest operacj ˛

a konsekwencji generowan ˛

a przez niezmienni-

cz ˛

a wersj˛e logiki intuicjonistycznej (R

, Sb(A

int

)). Mamy wtedy:

• (α → β) ∈ C

int

(X) wtedy i tylko wtedy, gdy C

(X ∪ {β}) ⊆ C

int

(X ∪ {α}).

• C

int

(X ∪ {α}) 6= S

wtedy i tylko wtedy, gdy ¬α /

∈ C

int

(X).

Dla logiki intuicjonistycznej zachodz ˛

a nast˛epuj ˛

ace fakty:

• (R

, Sb(A

int

) ∪ X) ∈ Cns wtedy i tylko wtedy, gdy istnieje α ∈ S

taka, ˙ze nie

zachodzi: α, ¬α ∈ C

int

(X).

• (R

, Sb(A

int

) ∪ X) ∈ Cpl wtedy i tylko wtedy, gdy dla ka˙zdej α ∈ S

: albo

α ∈ Cn

int

(X), albo ¬α ∈ C

int

(X).

• L(R

, Sb(A

int

)) = L(R

, Sb(A

)).

• L(R

0∗

, A

) = L(R

0∗

, A

int

) = {Z

• Je´sli Y ∈ L

0∗

, A

int

), to nast˛epuj ˛

ace warunki s ˛

a równowa˙zne:

1. (R

, Y ) /

∈ Cpl

2. ((β → α) → β) ∈ Y , dla pewnej α ∈ S

• Je´sli p

→ p

∈ X oraz α /

∈ C

(Sb(X)), to zbiór L

, Sb(X)) ma moc

kontinuum.

• dc(R

0∗

, A

int

) = c.

Z kolei, dla wielowarto´sciowych logik Łukasiewicza zachodz ˛

a nast˛epuj ˛

ace fakty:

• L(R

0∗

, Ł

∞

) = L(R

0∗

, Ł

) = L(R

0∗

, A

) = {Z

• dc(R

0∗

, Ł

) 6 2

k−1

+ 1, gdzie k jest liczb ˛

a podzielników m − 1.

Mo˙zna w pełnej ogólno´sci rozstrzygn ˛

a´c problem istnienia R

0∗

-systemów, maj ˛

cych własno´s´c Tarskiego. Pomijamy w niniejszej notatce odno´sne twierdzenia.

1.10.4. Strukturalna zupełno´s´c

Strukturalna zupełno´s´c jest pewnym szczególnym przypadkiem Γ-zupełno´sci, a

mianowicie takim, dla którego Γ = S. Zdefiniujmy:

• (R, A) ∈ SCpl wtedy i tylko wtedy, gdy Adm(R, A) ∩ Struct ⊆ Der(R, A). Je´sli

(R, A) ∈ SCpl, to mówimy, ˙ze system (R, A) jest strukturalnie zupełny.

Zachodz ˛

a nast˛epuj ˛

ace fakty:

• (R, A) ∈ SCpl wtedy i tylko wtedy, gdy dla wszystkich R

⊆ Struct oraz

wszystkich A

⊆ S: je´sli C

(A) = C

), to (R

, A

) (R, A).

• Je´sli (R, A) ∈ Inv, to: (R, A) ∈ SCpl wtedy i tylko wtedy, gdy dla wszystkich

, A

) ∈ Inv: je´sli C

(A) = C

), to (R

, A

) (R, A).

• Je´sli C ∈ STRUCT, to C ∈ SCPL wtedy i tylko wtedy, gdy dla wszystkich

∈ STRUCT: je´sli C(∅) = C

(∅), to C

6 C.

• Je´sli r

∗

∈ Adm(R, A) oraz ∅ 6= C

(A) 6= S, to nast˛epuj ˛

ace warunki s ˛

a równo-

wa˙zne:

1. Der(R, A) ∩ Struct = V (M) ∩ Struct

2. C

(A) = E(M) oraz (R, A) ∈ SCpl.

• Je´sli C

(A) = E(M), to nast˛epuj ˛

ace warunki s ˛

a równowa˙zne:

1. (R, A) ∈ SCpl

2. V (M) ∩ Struct ⊆ Der(R, A).

• Ka˙zdy system niesprzeczny (R, A) mo˙zna niesprzecznie rozszerzy´c do pewnego

systemu strukturalnie zupełnego (R

, A

• Niech (R, A) ∈ Inv oraz C

(A ∪ Z

) ⊆ Z

. Wtedy: je´sli (R ∪ {r

∗

}, A) ∈ SCpl,

to (R ∪ {r

∗

}, A) ∈ T (Z

• (R, A) ∈ SCpl wtedy i tylko wtedy, gdy r

(A)

∈ Der(R, A).

• (R, A) ∈ SCpl wtedy i tylko wtedy, gdy N (M

R,A

) ⊆ Der(R, A).

• (R, A) ∈ SCpl wtedy i tylko wtedy, gdy

−−−→

R,A

(X) ⊆ C

R,A

(X), dla wszystkich

X ⊆ S.

• Je´sli (R, A) ∈ Inv, to:

1. (R, A) ∈ SCpl wtedy i tylko wtedy, gdy N (M

R,A

) = Der(R, A).

2. (R, A) ∈ SCpl wtedy i tylko wtedy, gdy dla wszystkich X ⊆ S:

−−−→

R,A

(X) = C

(A ∪ X).

3. (Przy zało˙zeniu, ˙ze wszystkie reguły maj ˛

a tylko sko´nczone zbiory prze-

słanek.) (R, A) ∈ SCpl wtedy i tylko wtedy, gdy dla wszystkich X ∈

F in(S):

−−−→

R,A

(X) = C

(A ∪ X).

• Niech (R, A) b˛edzie systemem niezmienniczym takim, ˙ze C

R,A

jest finitystyczna.

Wtedy nast˛epuj ˛

ace warunki s ˛

a równowa˙zne:

1. (R, A) ∈ SCpl

2. Dla ka˙zdej ψ ∈ S oraz ka˙zdego Y ∈ L

(R, A) istnieje endomorfizm

h : S → S taki, ˙ze Y = h

−1

(A)).

• Niech (R, A) b˛edzie systemem niezmienniczym. Je´sli (R, A) ∈ SCpl, to dla

ka˙zdego Y ∈ L(R, A) istnieje odwzorowanie e : At :→ S takie, ˙ze Y =
h

−1

(A)).

Dla systemów: logiki klasycznej, logiki intuicjonistycznej, logik wielowarto´scio-

wych Łukasiewicza oraz logik modalnych zachodz ˛

a nast˛epuj ˛

ace fakty dotycz ˛

ace wła-

sno´sci strukturalnej zupełno´sci:

• (R

, Sb(A

)) ∈ SCpl.

• (R

0∗

, A

int

) /

∈ SCpl.

• Niektóre fragmenty logiki intuicjonistycznej s ˛

a jednak strukturalnie zupełne: np.

fragment (R

, Sb(A

→,∧,¬
int

)).

• (R

, Sb(Ł

)) ∈ SCpl, dla ka˙zdej n > 2.

• (R

0∗

, Ł

) ∈ SCpl, dla ka˙zdej n > 2.

• (R

0∗a

, A

) ∈ SCpl.

• (R

, Sb(A

)) /

∈ SCpl.

1.11. C-definiowalno´s´c

Wiadomo, ˙ze Cn

jest najmniejsz ˛

a operacj ˛

a konsekwencji C spełniaj ˛

ac ˛

a nast˛epu-

j ˛

ace warunki:

• (T0) Je´sli X ⊆ C(X), to Y ∪ C(X) ⊆ C(Y )

• (T1) C({α, ¬α}) = S

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˙z, ˙ze Cn

jest jedyn ˛

a niesprzeczn ˛

a oraz strukturaln ˛

a operacj ˛

a konse-

kwencji spełniaj ˛

ac ˛

a te warunki.

Powy˙zsza charakterystyka nie jest jednak˙ze zadowalaj ˛

aca: poszczególne warunki

nie s ˛

a jednorodne. Chcieliby´smy mie´c (oprócz (T0), który ustala, ˙ze C jest operacj ˛

konsekwencji) zestaw warunków o postaci:

• α§β ∈ C(X) wtedy i tylko wtedy, gdy . . .

gdzie § ∈ {¬, →, ∨, ∧}, a po prawej stronie równowa˙zno´sci wyst˛epuje warunek, cha-
rakteryzuj ˛

acy poszczególny spójnik przez operacj˛e konsekwencji.

Okazuje si˛e, ˙ze dla pewnych logik mo˙zliwe jest podanie tego typu jednorodnych

warunków. Nie jest tak jednak w przypadku logiki klasycznej Cn

Dla przykładu, wiadomo, ˙ze operacja konsekwencji intuicjonistycznej Cn

int

jest

najmniejsz ˛

a operacj ˛

a konsekwencji spełniaj ˛

ac ˛

a nast˛epuj ˛

ace warunki (H):

• (H1) ¬α ∈ C(X) wtedy i tylko wtedy, gdy S

⊆ 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˙zmy nast˛epuj ˛

acy zbiór warunków (D):

• (D1) ¬α ∈ C(X) wtedy i tylko wtedy, gdy C(X ∪ {α}) = S

• (D2) α → β ∈ C(X) wtedy i tylko wtedy, gdy C(X ∪ {α, ¬β}) = S

• (D3) α ∨ β ∈ C(X) wtedy i tylko wtedy, gdy C(X ∪ {¬α, ¬β}) = S

• (D4) α∧β ∈ C(X) wtedy i tylko wtedy, gdy C(X∪{¬α})∩C(X∪{¬β}) = S

Klasyczna konsekwencja Cn

oczywi´scie spełnia te warunki. Zauwa˙zmy jednak,

˙ze:

• Je´sli C spełnia (D), to ka˙zde aksjomatyczne rozszerzenie C tak˙ze spełnia (D). A

zatem (D) nie wyznaczaj ˛

a C jednoznacznie.

• Jednak najmniejsza operacja C spełniaj ˛

aca warunki (D) (czyli przekrój wszyst-

kich operacji C, spełniaj ˛

acych (D)) jest wyznaczona jednoznacznie i jest: struk-

turalna oraz finitystyczna.

• Je´sli C spełnia (D), to Sb(A

) ⊆ C(∅).

Najmniejsza operacja spełniaj ˛

aca (D) (oznaczana przez C

) jest wyznaczona przez

aksjomaty Sb(A

) oraz nast˛epuj ˛

ace reguły wnioskowania:

α, α → ¬β

¬β

α, α → (β → γ)

β → γ

α, α → (β ∨ γ)

β ∨ γ

α, α → (β ∧ γ)

β ∧ γ

α, ¬α

Poniewa˙z reguły C

s ˛

a niezawodne klasycznie, wi˛ec C

(X) ⊆ Cn

(X) dla

wszystkich X. Ponadto, dla wszystkich X ⊆ S

• C

(X) = S

wtedy i tylko wtedy, gdy Cn

(X) = S

• α ∈ C

(X) wtedy i tylko wtedy, gdy α ∈ Cn

(X), dla α /

∈ At.

• α ∈ C

(X) wtedy i tylko wtedy, gdy α ∈ X, dla α ∈ At oraz Cn

(X) 6= S

Mamy zatem C

6 Cn

, lecz nierówno´s´c odwrotna nie zachodzi. Mamy jedynie:

(∅) = C

0∗

Tak wi˛ec, logika C

jest słabsza od logiki klasycznej. Jej spójniki nie s ˛

a spójni-

kami klasycznymi, co wida´c z nast˛epuj ˛

acego faktu.

Rozwa˙zmy matryc˛e logiczn ˛

a M

zbudowan ˛

a na zbiorze {1, 2, 3} z 3 jako jedynym

elementem wyró˙znionym oraz nast˛epuj ˛

ac ˛

a interpretacj ˛

a spójników:

→

∨

∧

Wtedy konsekwencja C

jest dokładnie konsekwencj ˛

a matrycow ˛

−−→

Logika C

jest tzw. logik ˛

a progow ˛

a. Zachodzi mianowicie nast˛epuj ˛

acy fakt:

• Je´sli C jest niesprzeczn ˛

a strukturaln ˛

a operacj ˛

a konsekwencji oraz C

< C, to

C = Cn

Tak wi˛ec, klasyczna operacja konsekwencji Cn

jest jedynym wła´sciwym nie-

sprzecznym i strukturalnym rozszerzeniem C

Mo˙zna wykaza´c, ˙ze same reguły r

(wraz z A

), bez reguły r

, nie aksjomaty-

zuj ˛

a C

. Niech mianowicie M

b˛edzie matryc ˛

a na zbiorze {1, 3}, z 3 jako jedynym

elementem wyró˙znionym i niech:

• ¬x = 3

• f (x, y) = 3 dla f ∈ {→, ∨, ∧}.

Wtedy: wszystkie aksjomaty Sb(A

) s ˛

a prawdziwe w M

oraz reguły r

s ˛

a nieza-

wodne w M

, ale r

nie jest niezawodna w M

. Ponadto, konsekwencja wyznaczona

przez te reguły (oraz Sb(A

)) pokrywa si˛e z przekrojem konsekwencji matrycowych

−→

∩

−→

, gdzie M

jest matryc ˛

a klasyczn ˛

a. Zale˙zno´sci mi˛edzy omawianymi konse-

kwencjami s ˛

a nast˛epuj ˛

ace (tu C

inc

jest konsekwencj ˛

a sprzeczn ˛

a):

•

−→

∩

−→

< C

< Cn

< C

inc

•

−→

∩

−→

< C

inc

• konsekwencja

−→

jest

6-nieporównywalna ani z C

, ani z Cn

Wreszcie, M

jest podmatryc ˛

a M

× M

oraz zachodzi:

•

−−→

−−−−−−→

× M

Istnieje wiele wariantów systemu (D). ˙

Zaden 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 ˛

a mo˙zliwe, gdy zmienimy to rozumienie.

2. Paradygmat semantyczny

2.1. Logiki abstrakcyjne

Dla naszych celów wystarczaj ˛

aca b˛edzie nast˛epuj ˛

aca definicja logiki abstrakcyjnej

(albo: systemu logicznego, w sensie uogólnionym).

Przez logik˛e abstrakcyjn ˛

a rozumiemy ka˙zd ˛

a par˛e uporz ˛

adkowan ˛

a L = (L, |=

spełniaj ˛

ac ˛

a nast˛epuj ˛

ace warunki:

• L przyporz ˛

adkowuje ka˙zdej sygnaturze σ zbiór L(σ), zwany zbiorem σ-zda ´n lo-

giki L. [Uwaga: w niektórych przypadkach trzeba rozwa˙za´c klasy zamiast zbio-
rów.]

• Je´sli σ ⊆ τ , to L(σ) ⊆ L(τ ).

• Je´sli A |=

ϕ, to dla pewnego σ mamy: A ∈ Str

oraz ϕ ∈ L(σ).

• W

ARUNEK IZOMORFIZMU

. Je´sli A |=

ϕ oraz A ∼

= B, to B |=

ϕ.

• W

ARUNEK REDUKTU

. Je´sli τ ⊆ σ, ϕ ∈ L(σ) oraz A ∈ Str

, to A |=

ϕ wtedy

i tylko wtedy, gdy A

τ |=

Przypominamy, ˙ze A

τ jest τ -reduktem struktury A, czyli struktur ˛

a powstaj ˛

ac ˛

z A poprzez uwzgl˛ednienie tylko interpretacji wszystkich symboli z τ (a wi˛ec, gdy
A

∈ Str

oraz τ ⊆ σ, to w A

τ uwzgl˛edniamy tylko interpretacje symboli z τ ,

pomijaj ˛

ac interpretacje symboli z σ − τ ).

Dla dowolnej logiki abstrakcyjnej L oraz ϕ ∈ L(σ) miech:

M od

(ϕ) = {A : A ∈ Str

∧ A |=

ϕ}

(je´sli σ b˛edzie jasne z kontekstu, b˛edziemy pisa´c M od

(ϕ)).

Niech L

ωω

oznacza logik˛e pierwszego rz˛edu. W tym przypadku funkcja L przy-

porz ˛

adkowuje ka˙zdej sygnaturze σ zbiór wszystkich zda´n pierwszego rz˛edu w których

wyst˛epuj ˛

a symbole z σ. Dla logiki L

ωω

b˛edziemy u˙zywali relacji |=, bez indeksu, po-

krywaj ˛

acej si˛e z relacj ˛

a spełniania znan ˛

a z wykładu Semantyka KRP.

„Moc wyra˙zania” poszczególnych logik abstrakcyjnych definiowana jest w termi-

nach semantycznych:

• Piszemy L

6 L

wtedy i tylko wtedy, gdy dla ka˙zdej sygnatury σ oraz ka˙zdego

ϕ ∈ L

(σ) istnieje ψ ∈ L

(σ) taka, ˙ze: M od

(ϕ) = M od

(ψ). Mówimy

wtedy, ˙ze L

ma moc wyra˙zania nie wi˛eksz ˛

a ni˙z L

• Gdy zachodzi L

6 L

, ale nie zachodzi L

6 L

, to piszemy L

< L

mówimy, ˙ze L

ma moc wyra˙zania wi˛eksz ˛

a ni˙z L

• Gdy zachodzi L

6 L

oraz zachodzi L

6 L

, to piszemy L

∼ L

i mówimy,

˙ze L

i L

maj ˛

a tak ˛

a sam ˛

a moc wyra˙zania.

Spo´sród wszystkich logik abstrakcyjnych wyró˙znimy klas˛e logik regularnych, speł-

niaj ˛

acych pewne naturalne warunki.
Powiemy, ˙ze logika L ma własno´s´c spójników Boolowskich, gdy:

• Dla ka˙zdej σ oraz ϕ ∈ L(σ) istnieje χ ∈ L(σ) taka, ˙ze dla ka˙zdej A ∈ Str

χ wtedy i tylko wtedy, gdy nie zachodzi A |=

ϕ.

• Dla ka˙zdej σ oraz ka˙zdych ϕ, ψ ∈ L(σ) istnieje χ ∈ L(σ) taka, ˙ze dla ka˙zdej

∈ Str

χ wtedy i tylko wtedy, gdy A |=

ϕ lub A |=

ψ.

Je´sli L ma własno´s´c spójników Boolowskich, to b˛edziemy u˙zywa´c oznacze´n, od-

powiednio, ¬ϕ oraz ϕ ∨ ψ dla formuły χ, o której mowa powy˙zej. W podobny sposób
okre´slamy te˙z pozostałe spójniki Boolowskie logiki L. Jest to oczywi´scie uproszczenie
notacyjne: dla pełnej poprawno´sci trzeba byłoby u˙zywa´c np. symboli ¬

, ∨

, itd.

Powiemy, ˙ze logika L ma własno´s´c relatywizacji, gdy dla ka˙zdej σ oraz ϕ ∈ L(σ)

oraz ka˙zdego jednoargumentowego predykatu U istnieje ψ ∈ L(σ ∪ {U }) takie, ˙ze:
(A, U

) |=

ψ wtedy i tylko wtedy, gdy [U

]

ϕ, dla wszystkich A ∈ Str

oraz

wszystkich σ-domkni˛etych podzbiorów U

⊆ A = dom(A). Tutaj [U

]

jest pod-

struktur ˛

a A o uniwersum U

. Je´sli L ma własno´s´c relatywizacji, to niech ϕ

oznacza

formuł˛e ψ, o której mowa w powy˙zszej definicji.

∗ ∗ ∗

Przed sformułowaniem nast˛epnej własno´sci logik abstrakcyjnych potrzebne b˛edzie

przypomnienie pewnych faktów z semantyki KRP.

Przypomnijmy, ˙ze dla dowolnej σ, dowolnego zbioru zda´n Φ z L

ωω

oraz symboli:

n-argumentowego predykatu P , n-argumentowego symbolu funkcyjnego F oraz stałej
indywidualnej c takich, ˙ze P /

∈ σ, F /

∈ σ oraz c /

∈ σ mówimy, ˙ze:

• formuła ∀v

. . . ∀v

n−1

(P (v

, . . . , v

n−1

) ≡ ϕ(v

, . . . , v

n−1

)) jest σ-definicj ˛

a P

w Φ;

• formuła ∀v

. . . ∀v

n−1

∀v

(F (v

, . . . , v

n−1

) = v

≡ ϕ(v

, . . . , v

n−1

, v

)) jest

σ-definicj ˛

a F w Φ, gdy Φ |= ∃!v

ϕ(v

, . . . , v

n−1

, v

);

• formuła ∀v

(c = v

≡ ϕ(v

)) jest σ-definicj ˛

a c w Φ, gdy Φ |= ∃!v

ϕ(v

Je´sli ∆ jest zbiorem σ-definicji dla predykatów P ∈ τ − σ, symboli funkcyjnych

F ∈ τ − σ oraz stałych indywidualnych c ∈ τ − σ, to dla ka˙zdej A ∈ Str

takiej, ˙ze

|= Φ istnieje dokładnie jedna struktura A

∆

∈ Str

τ −σ

taka, ˙ze A

∆

σ = A oraz

∆

|= ∆.

Rozwa˙zamy teraz sygnatury σ

∆

takie, ˙ze σ ⊆ σ

∆

oraz ∆ jest zbiorem σ-definicji

symboli z σ

∆

− σ.

Niech Φ b˛edzie zbiorem zda´n sygnatury σ. Wtedy ka˙zdej formule ψ o n zmiennych

wolnych mo˙zna przyporz ˛

adkowa´c formuł˛e ψ

∆

tak ˛

a, ˙ze:

• Je´sli A ∈ Str

, A |= Φ oraz a

, . . . , a

n−1

∈ dom(A), to: A

∆

|= ψ[a

, . . . , a

n−1

]

wtedy i tylko wtedy, gdy A |= ψ

∆

, . . . , a

n−1

• Φ ∪ ∆ |= ψ ≡ ψ

∆

W konsekwencji, je´sli A ≡ B, to A

∆

≡ B

∆

Powy˙zsze fakty pozwalaj ˛

a na przej´scie od dowolnych sygnatur do sygnatur czysto

relacyjnych, tj. takich, które zawieraj ˛

a jedynie predykaty. Inaczej mówi ˛

ac, mo˙zemy

ka˙zdy n-argumentowy symbol funkcyjny f zamieni´c na n + 1-argumentowy symbol
relacyjny (predykat) F oraz ka˙zd ˛

a stał ˛

a indywidualn ˛

a c zast ˛

api´c jednoargumentowym

predykatem C. Niech σ

oznacza sygnatur˛e w ten sposób utworzon ˛

a z sygnatury σ.

Ka˙zdej strukturze A ∈ Str

przyporz ˛

adkowujemy wtedy struktur˛e A

okre´slon ˛

a w

sposób nast˛epuj ˛

acy:

• A

= dom(A

) = A = dom(A);

• dla predykatów P ∈ σ niech: interpretacja P w A

b˛edzie identyczna z interpre-

tacj ˛

a P w A;

• dla n-argumentowego symbolu funkcyjnego f ∈ σ niech F

b˛edzie wykresem

funkcji f

, czyli F

, . . . , a

n−1

, a

) wtedy i tylko wtedy, gdy

, . . . , a

n−1

) = a

;

• dla stałej indywidualnej c ∈ σ, niech C

(a) wtedy i tylko wtedy, gdy c

= a.

Dla ka˙zdej formuły ψ o n zmiennych wolnych w j˛ezyku o sygnaturze σ istnieje

wtedy formuła ψ

w j˛ezyku o sygnaturze σ

taka, ˙ze dla wszystkich A oraz wszyst-

kich a

, . . . , a

n−1

∈ dom(A): A |= ψ[a

, . . . , a

n−1

] wtedy i tylko wtedy, gdy A

, . . . , a

n−1

W konsekwencji, dla dowolnych A, B ∈ Str

: A ≡ B wtedy i tylko wtedy, gdy

≡ B

Te wiadomo´sci wystarczaj ˛

a do sformułowania nast˛epnej własno´sci logik abstrak-

cyjnych.

∗ ∗ ∗

Powiemy, ˙ze logika L dopuszcza zast ˛

apienie symboli funkcyjnych oraz stałych

indywidualnych poprzez symbole relacyjne, gdy dla dowolnej σ:

• dla ka˙zdej ϕ ∈ L(σ) istnieje ψ ∈ L(σ

) taka, ˙ze dla wszystkich A ∈ Str

ϕ wtedy i tylko wtedy, gdy A

ψ.

Je´sli logika L ma powy˙zsz ˛

a własno´s´c, to formuł˛e ψ istniej ˛

ac ˛

a na mocy definicji

wy˙zej b˛edziemy oznacza´c przez ϕ

Powiemy, ˙ze logika L jest regularna, gdy:

• L ma własno´s´c spójników Boolowskich;

• L ma własno´s´c relatywizacji;

• L dopuszcza zast ˛

apienie symboli funkcyjnych oraz stałych indywidualnych po-

przez symbole relacyjne.

Nast˛epuj ˛

ace poj˛ecia przenosimy z KRP na wypadek logik abstrakcyjnych:

• zdanie ϕ ∈ L(σ) nazywamy spełnialnym w logice L, gdy M od

6= ∅;

• zbiór Φ ⊆ L(σ) nazywamy spełnialnym w logice L, gdy

ϕ∈Φ

M od

6= ∅;

• zdanie ϕ ∈ L(σ) nazywamy prawdziwym w logice L, gdy M od

= Str

;

• piszemy Φ |=

ϕ, gdy ka˙zdy L-model wszystkich zda´n z Φ jest tak˙ze L-mode-

lem ϕ (czyli gdy M od(Φ) =

T{M od(ψ) : ψ ∈ Φ} ⊆ M od(ϕ)).

Mówimy, ˙ze logika L ma własno´s´c:

• Löwenheima-Skolema, gdy ka˙zde zdanie L-spełnialne ma model przeliczalny.

• zwarto´sci, gdy dla dowolnego Φ ⊆ L(σ), je´sli ka˙zdy sko´nczony podzbiór zbioru

Φ jest L-spełnialny, to Φ jest L-spełnialny.

2.2. Algebraiczna charakteryzacja elementarnej równowa˙zno´sci

Jest rzecz ˛

a wa˙zn ˛

a (oraz interesuj ˛

ac ˛

a), ˙ze poj˛ecia semantyczne mo˙zemy charakte-

ryzowa´c w terminach matematycznych. W szczególno´sci, okazuje si˛e, ˙ze podstawowe
poj˛ecia semantyczne mog ˛

a zosta´c scharakteryzowane w (prostych) terminach algebra-

icznych.

Niech A, B ∈ Str

. Mówimy, ˙ze f jest cz˛e´sciowym izomorfizmem A w B, gdy:

• f jest injekcj ˛

a o dziedzinie dom(f ) zawartej w dom(A) oraz zbiorze warto´sci

rng(f ) zawartym w dom(B)

• dla dowolnego n-argumentowego predykatu P ∈ σ oraz dowolnych elementów

, . . . , a

n−1

∈ dom(f ): P

, . . . , a

n−1

) wtedy i tylko wtedy, gdy

(f (a

), . . . , f (a

n−1

));

• dla dowolnego n-argumentowego symbolu funkcyjnego F ∈ σ oraz dowol-

nych a

, . . . , a

n−1

∈ dom(f ): F

, . . . , a

n−1

) = a wtedy i tylko wtedy,

gdy F

(f (a

), . . . , f (a

n−1

)) = f (a);

• dla dowolnej stałej indywidualnej c ∈ σ oraz a ∈ dom(f ): c

= a wtedy i tylko

wtedy, gdy c

= f (a).

Przez P art(A, B) b˛edziemy oznacza´c rodzin˛e wszystkich cz˛e´sciowych izomorfi-

zmów z A w B.

Gdy σ jest czysto relacyjna oraz a

, . . . , a

n−1

∈ dom(A), b

, . . . , b

n−1

∈ dom(B),

oraz f ∈ P art(A, B) jest taki, ˙ze f (a

) = b

dla wszystkich i < n, to dla ka˙zdej for-

muły atomowej ψ o n zmiennych wolnych zachodzi: A |= ψ[a

, . . . , a

n−1

] wtedy i

tylko wtedy, gdy B |= ψ[b

, . . . , b

n−1

Pojedyncze cz˛e´sciowe izomorfizmy nie zachowuj ˛

a jednak (w powy˙zszym sensie)

dowolnych

formuł. Jak si˛e oka˙ze, dopiero pewne rodziny cz˛e´sciowych izomorfizmów

pozwalaj ˛

a o takim zachowywaniu dowolnych formuł przes ˛

adza´c, a tym samym rodziny

takie pozwalaj ˛

a scharakteryzowa´c elementarn ˛

a równowa˙zno´s´c struktur relacyjnych.

B˛edziemy identyfikowa´c odwzorowania z ich (teorio-mnogo´sciowymi) wykresami,

czyli odwzorowanie f identyfikujemy z wykresem {(x, f (x)) : x ∈ dom(f )}.

Powiemy, ˙ze A oraz B s ˛

a sko ´nczenie izomorficzne, gdy istnieje ci ˛

ag (I

)

n∈ω

nast˛epuj ˛

acych własno´sciach:

• Ka˙zdy I

jest niepustym zbiorem cz˛e´sciowych izomorfizmów z A w B.

• Je´sli f ∈ I

n+1

oraz a ∈ dom(A), to istnieje g ∈ I

taki, ˙ze f ⊆ g oraz

a ∈ dom(g).

• Je´sli f ∈ I

n+1

oraz b ∈ dom(B), to istnieje g ∈ I

taki, ˙ze f ⊆ g oraz

b ∈ rng(g).

Je´sli rodzina (I

)

n∈ω

ma powy˙zsze własno´sci, to piszemy: (I

)

n∈ω

: A ∼

Je´sli A oraz B s ˛

a sko´nczenie izomorficzne, to piszemy A ∼

Powiemy, ˙ze A oraz B s ˛

a cz˛e´sciowo izomorficzne, gdy istnieje zbiór I taki, ˙ze:

• I jest niepustym zbiorem cz˛e´sciowych izomorfizmów z A w B.

• Je´sli f ∈ I oraz a ∈ dom(A), to istnieje g ∈ I taki, ˙ze f ⊆ g oraz a ∈ dom(g).

• Je´sli f ∈ I oraz b ∈ dom(A), to istnieje g ∈ I taki, ˙ze f ⊆ g oraz b ∈ rng(g).

Je´sli rodzina I ma powy˙zsze własno´sci, to piszemy: I : A ∼

B. Je´sli A oraz B s ˛

sko´nczenie izomorficzne, to piszemy A ∼

Zachodz ˛

a nast˛epuj ˛

ace fakty:

• Je´sli A ∼

= B, to A ∼

• Je´sli A ∼

B, to A ∼

• Je´sli A ∼

B oraz A jest sko´nczona, to A ∼

= B.

• Je´sli A ∼

B oraz A i B s ˛

a co najwy˙zej przeliczalne, to A ∼

= B.

Charakterystyk˛e elementarnej równowa˙zno´sci, która nie odwołuje si˛e do własno´sci

j˛ezyka podaje T

WIERDZENIE

RAÏSSÉ

’

• Dla dowolnej sko´nczonej σ oraz A, B ∈ Str

: A ≡ B wtedy i tylko wtedy, gdy

A ∼

Przypomnijmy poj˛ecie kwantyfikatorowego rz˛edu formuły:

• qr(ϕ) = 0, gdy ϕ jest atomowa;

• qr(¬ϕ) = qr(ϕ)

• qr(ϕ ∨ ψ) = max{qr(ϕ), qr(ψ)} (podobnie dla innych funktorów dwuargu-

mentowych);

• qr(∃xϕ) = qr(ϕ) + 1.

Powiemy, ˙ze struktury A oraz B s ˛

a m-izomorficzne, gdy istnieje ci ˛

ag I

, . . . , I

niepustych zbiorów cz˛e´sciowych izomorfizmów z A w B taki, ˙ze:

• Je´sli n + 1 6 m, f ∈ I

n+1

oraz a ∈ dom(A), to istnieje g ∈ I

taki, ˙ze f ⊆ g

oraz a ∈ dom(g).

• Je´sli n + 1 6 m, f ∈ I

n+1

oraz b ∈ dom(B), to istnieje g ∈ I

taki, ˙ze f ⊆ g

oraz b ∈ rng(g).

Je´sli I

, . . . , I

jest ci ˛

agiem o powy˙zszych własno´sciach, to piszemy (I

)

n6m

A ∼

B. Je´sli A oraz B s ˛

a m-izomorficzne, to piszemy A ∼

W dowodzie twierdzenia Fraïssé’go wykorzystujemy nast˛epuj ˛

ace fakty:

• Niech (I

)

n∈ω

: A ∼

B. Wtedy dla ka˙zdej formuły ϕ o k zmiennych wolnych:

je´sli qr(ϕ)

6 n, f ∈ I

oraz a

, . . . a

k−1

∈ dom(f ):

|= ϕ[a

, . . . a

k−1

] wtedy i tylko wtedy, gdy B |= ϕ[f (a

), . . . f (a

k−1

)].

• Je´sli A ∼

B, to A oraz B spełniaj ˛

a te same zdania o rz˛edzie kwantyfikatoro-

wym

6 m.

• Dla ka˙zdych n i r istnieje tylko sko´nczenie wiele klas równowa˙zno´sci wzgl˛edem

relacji równowa˙zno´sci logicznej w zbiorze wszystkich formuł o r zmiennych
wolnych i o rz˛edzie kwantyfikatorowym

6 n.

• Je´sli A ≡ B, to A ∼

• Je´sli A i B spełniaj ˛

a te same zdania o rz˛edzie kwantyfikatorowym

6 m, to

A ∼

• Niech σ b˛edzie sko´nczona i czysto relacyjna. Wtedy dla ka˙zdych struktur A, B ∈

Str

nast˛epuj ˛

ace warunki s ˛

a równowa˙zne:

1. A ∼

2. A i B spełniaj ˛

a te same zdania o rz˛edzie kwantyfikatorowym

6 m.

2.3. Twierdzenia Lindströma

W tym punkcie rozwa˙zamy logiki regularne L takie, ˙ze L

ωω

6 L. Poka˙zemy m.in.,

˙ze L

ωω

jest

6-maksymaln ˛

a logik ˛

a o wybranych naturalnych własno´sciach.

Je´sli ϕ jest zdaniem L

ωω

sygnatury σ, to przez ϕ

∗

b˛edziemy oznacza´c zdanie z L

o tych samych modelach, co ϕ, czyli takie, ˙ze M od

ωω

= M od

(ϕ

∗

). Dla zbioru Φ

zda´n j˛ezyka L

ωω

(ustalonej sygnatury σ) niech Φ

∗

= {ϕ

∗

: ϕ ∈ Φ}.

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˙zna go rozło˙zy´c na cz˛e´sci i ´sledzi´c uwa˙znie ka˙zd ˛

a z tych cz˛e´sci, a potem

u´swiadomi´c sobie, jak składaj ˛

a si˛e one w cało´s´c.

EMAT

Je´sli L jest zwarta oraz Φ ∪ {ϕ} jest zbiorem zda´n logiki L sygnatury σ takim, ˙ze

Φ |=

ϕ, to istnieje sko´nczony zbiór Φ

⊆ Φ taki, ˙ze Φ

ϕ.

OWÓD

Niech L b˛edzie zwarta. Poniewa˙z L ma własno´s´c spójników Boolowskich, istnieje

formuła ¬ϕ. Dokładniej, powinni´smy pisa´c np.: ¬

ϕ, ale poniewa˙z istotne dalej b˛ed ˛

jedynie własno´sci semantyczne logiki, upraszczamy ten pedantyczny zapis.

Skoro Φ |=

ϕ, to zbiór Φ ∪ {¬ϕ} nie jest spełnialny. Na mocy zwarto´sci L,

istnieje sko´nczony podzbiór Φ

⊆ taki, ˙ze Φ

∪{¬ϕ} nie jest spełnialny. Wtedy jednak

ϕ, co ko´nczy dowód lematu 1.

EMAT

Niech L b˛edzie zwarta oraz ψ ∈ L(σ). Wtedy istnieje sko´nczony zbiór σ

⊆ σ

taki, ˙ze dla wszystkich A, B ∈ Str

: je´sli A

∼

= B

, to A |=

ψ wtedy i tylko

wtedy, gdy B |=

ψ.

OWÓD

Ograniczymy si˛e do przypadku, gdy σ jest czysto relacyjna (tylko taki przypadek

b˛edzie nam pó´zniej potrzebny).

Wybierzmy nowe symbole jednoargumentowe (predykaty): U , V oraz jednoar-

gumentowy symbol funkcyjny f . Zbudujemy teraz zbiór Φ zda´n w sygnaturze σ ∪
{U, V, f }, „mówi ˛

acych”, ˙ze f jest izomorfizmem podstruktury generowanej przez U

w podstruktur˛e generowan ˛

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

• ∀x

. . . ∀x

((U (x

)∧. . .∧U (x

)) → (R(x

, . . . , x

) ≡ R(f (x

), . . . , f (x

)))

(ostatni z warunków zapisujemy dla ka˙zdego n-argumentowego predykatu R ∈ σ).
U˙zywamy tu symbolu = dla predykatu identyczno´sci; nie nale˙zy go oczywi´scie myli´c
z symbolem = u˙zywanym dla relacji identyczno´sci w metaj˛ezyku.

Wtedy zachodzi:

(1)

∗

(ψ

≡ ψ

Udowodnimy (1). Je´sli A ∈ Str

jest taka, ˙ze (A, U

, V

, f

) |=

∗

(czyli

(A, U

, V

, f

) |= Φ), to: U

oraz V

s ˛

a niepuste, a f

jest izomorfizmem

]

na [V

]

. Przypominamy, ˙ze stosujemy nast˛epuj ˛

ace konwencje notacyjne:

• A oznacza dom(A)

• U

oznacza interpretacj˛e predykatu U w A

• [U

]

oznacza podstruktur˛e struktury A, której uniwersum jest zbiór U

i której

relacje otrzymujemy z relacji w A, ograniczaj ˛

ac je do U

Na mocy własno´sci izomorfizmu (zobacz: definicja logik abstrakcyjnych) mamy:

]

ψ wtedy i tylko wtedy, gdy [V

]

ψ. Poniewa˙z L ma własno´s´c rela-

tywizacji (zobacz: definicja logik regularnych), wi˛ec: (A, U

) |=

wtedy i tylko

wtedy, gdy (A, V

) |=

. Poniewa˙z L ma własno´s´c spójników Boolowskich (zo-

bacz: definicja logik regularnych) oraz własno´s´c reduktów (zobacz: definicja logik abs-
trakcyjnych), wi˛ec: (A, U

, V

, f

) |=

≡ ψ

. To ko´nczy dowód warunku (1).

Na mocy zwarto´sci L otrzymujemy sko´nczony zbiór Φ

⊆ Φ taki, ˙ze:

(2)

∗

(ψ

≡ ψ

Poniewa˙z Φ składa si˛e ze zda´n pierwszego rz˛edu, mo˙zemy wybra´c sko´nczony zbiór

⊆ σ taki, ˙ze Φ

składa si˛e z σ

-zda´n (czyli zda´n z j˛ezyka o sygnaturze σ

). Poka-

˙zemy, ˙ze σ

spełnia tez˛e lematu 2.

Niech A, B ∈ Str

i niech π : A

∼

= B

. Mo˙zemy zało˙zy´c, ˙ze dziedziny

tych struktur, czyli A i B s ˛

a rozł ˛

aczne: A ∩ B = ∅. Gdyby tak nie było, to wzi˛eli-

by´smy izomorficzn ˛

a kopi˛e B o uniwersum rozł ˛

acznym zA, korzystaj ˛

ac z własno´sci

izomorfizmu (zobacz: definicja logik abstrakcyjnych).

Zdefiniujemy struktur˛e (C, U

, V

, f

) ∈ Str

σ∪{U,V,f }

. Uniwersum tej struktury

to C = A ∪ B. Jej relacje (i jedn ˛

a funkcj˛e) definiujemy nast˛epuj ˛

aco:

• R

= R

∪ R

dla R ∈ σ [uwaga: σ jest czysto relacyjna]

• U

= A

• V

= B

• f

definiujemy tak, aby f

= π.

Wtedy (C, U

, V

, f

) jest modelem Φ

, a wi˛ec mamy tak˙ze:

(C, U

, V

, f

) |=

∗
0

Na mocy (2) dostajemy: (C, U

, V

, f

) |=

(ψ

≡ ψ

Poniewa˙z [U

]

= A oraz [V

]

= B, wi˛ec (skoro L ma własno´s´c spójników

Boolowskich oraz relatywizacji): A |=

ψ wtedy i tylko wtedy, gdy B |=

ψ. To

ko´nczy dowód lematu 2.

Niech A, B ∈ Str

. Powiemy, ˙ze A jest L-równowa˙zna z B, gdy dla ka˙zdego

σ-zdania ψ z L: A |=

ψ wtedy i tylko wtedy, gdy B |=

ψ. Je´sli A i B s ˛

a L-

równowa˙zne, to piszemy A ≡

B. Relacja elementarnej równowa˙zno´sci pokrywa si˛e

z relacj ˛

a L

ωω

-równowa˙zno´sci i b˛edzie, jak dotychczas oznaczana przez ≡.

EMAT

Niech L b˛edzie zwarta. Je´sli ka˙zde dwie elementarnie równowa˙zne struktury s ˛

tak˙ze L-równowa˙zne, to L ∼ L

ωω

OWÓD

Poniewa˙z L

ωω

6 L (co zakładali´smy na pocz ˛

atku rozwa˙za´n w całym tym punkcie),

wi˛ec musimy pokaza´c, ˙ze L

6 L

ωω

, czyli ˙ze dla ka˙zdego σ oraz ka˙zdego zdania

ψ ∈ L(σ) istnieje σ-zdanie pierwszego rz˛edu ϕ takie, ˙ze M od

ωω

(ϕ) = M od

(ψ).

Niech ψ b˛edzie zdaniem spełnialnym. W przeciwnym przypadku mo˙zemy wzi ˛

a´c

za ϕ np. zdanie ∀x ¬x = x i teza lematu b˛edzie trywialnie spełniona.

Twierdzimy, ˙ze:
(1)

Dla ka˙zdej A ∈ M od

(ψ) istnieje σ-zdanie ϕ

∈ L(σ) takie, ˙ze A |= ϕ

oraz ϕ

∗
A

|= ψ.

Dowód (1) przeprowadzimy metod ˛

a wprost. Niech A ∈ M od

(ψ). Wtedy zacho-

dzi: T h(A)

∗

ψ. Jest tak, poniewa˙z je´sli B |=

T h(A)

∗

, czyli B |= T h(A), to

≡ B. Z zało˙zenia mamy A ≡

B, a wi˛ec B |=

ψ.

Na mocy zwarto´sci L istnieje liczba r oraz zdania ϕ

, . . . , ϕ

∈ T h(A) takie, ˙ze

{ϕ

∗

, . . . , ϕ

∗

} |=

ψ. Niech ϕ

b˛edzie koniunkcj ˛

a ϕ

∧ . . . ∧ ϕ

. Wtedy ϕ

∈ T h(A),

czyli A |= ϕ

oraz ϕ

∗
A

ψ. To ko´nczy dowód (1).

Na mocy (1) otrzymujemy teraz:
(2)

M od

(ψ) =

∈M od

(ψ)

M od

(ϕ

∗
A

Poka˙zemy, ˙ze istniej ˛

a A

, . . . , A

∈ M od

(ψ) takie, i˙z:

(3)

M od

(ψ) = M od

(ϕ

∗
A

) ∪ . . . ∪ M od

(ϕ

∗
A

W przeciwnym przypadku (tj. gdyby (3) miało nie zachodzi´c), dla ka˙zdej sko´nczo-

nej liczby modeli A

, . . . , A

∈ M od

(ψ) mieliby´smy:

M od

(ϕ

∗
A

) ∪ . . . ∪ M od

(ϕ

∗
A

) & M od

(ψ).

Wtedy ka˙zdy sko´nczony podzbiór zbioru {¬ψ} ∪ {¬ϕ

∗
A

: A ∈ M od

(ψ)} byłby

spełnialny, a wi˛ec na mocy zwarto´sci L cały ten zbiór byłby spełnialny, co daje sprzecz-
no´s´c z (2).

Na mocy (3) otrzymujemy:
M od

(ψ) = M od

ωω

(ϕ

)∪. . .∪M od

ωω

(ϕ

) = M od

ωω

(ϕ

∨. . .∨ϕ

Dla ϕ o postaci ϕ

∨ . . . ∨ ϕ

zachodzi zatem M od

ωω

= M od

(ψ). To ko´nczy

dowód lematu 3.

I T

WIERDZENIE

INDSTRÖMA

Niech L b˛edzie regularna i L

ωω

6 L. Je´sli L jest zwarta i ma własno´s´c Löwenheima-

Skolema, to L ∼ L

ωω

OWÓD

Wystarczy pokaza´c, ˙ze L

6 L

ωω

Ponadto, na mocy lematu 3 wystarczy pokaza´c, ˙ze dla wszystkich σ:
(F)

Dla wszystkich A, B ∈ Str

, je´sli A ≡ B, to A ≡

Mo˙zemy przy tym ograniczy´c si˛e do sygnatur relacyjnych σ, z nast˛epuj ˛

acego po-

wodu. Je´sli (

F) zachodzi dla sygnatur relacyjnych σ, to gdy A ≡ B przechodzimy

do σ

, A

oraz B

i otrzymujemy A

≡ B

. Teraz (

F) zachodzi dla sygnatur rela-

cyjnych σ

i mamy: A

≡

. Na mocy własno´sci zamiany symboli funkcyjnych i

stałych indywidualnych na predykaty (zobacz: definicja logiki regularnej), dla dowol-
nego ψ ∈ L(σ) nast˛epuj ˛

ace warunki s ˛

a równowa˙zne:

• A |=

• A

• B

(poniewa˙z A

≡

)

• B |=

ψ,

a zatem zachodzi A ≡

Dowód (

F) dla sygnatur relacyjnych σ poprowadzimy nie wprost. Przypu´s´cmy, ˙ze

dla pewnych A, B ∈ Str

oraz pewnej ψ ∈ L(σ):

(1)

≡ B, A |=

ψ oraz B |=

¬ψ

(jak pami˛etamy, powinni´smy wła´sciwie pisa´c np. ¬

; korzystamy z tego, ˙ze L ma

własno´s´c spójników Boolowskich).

Wybieramy ψ spełniaj ˛

ac ˛

a (1) oraz (na mocy lematu 2) sko´nczon ˛

a sygnatur˛e σ

⊆

σ. Wtedy „znaczenie ψ zale˙zy tylko od sko´nczenie wielu symboli”.

Skoro A ≡ B, to oczywi´scie tak˙ze A

≡ B σ

, wi˛ec na mocy twierdzenia

Fraïssé’go struktury A

oraz B

s ˛

a sko´nczenie izomorficzne. Otrzymujemy

zatem, dla odpowiedniego (I

)

n∈ω

(2)

)

n∈ω

: A σ

∼

, A |=

ψ, B |=

¬ψ.

Istota dowodu zasadza si˛e w tym, aby otrzyma´c teraz (na mocy własno´sci zwarto´sci

oraz własno´sci Löwenheima-Skolema) struktury przeliczalne A

oraz B

takie, ˙ze:

(3)

∼

, A

ψ, B

¬ψ.

Gdy otrzymamy (3), to twierdzenie b˛edzie udowodnione: poniewa˙z przeliczalne

cz˛e´sciowo izomorficzne struktury A

oraz B

s ˛

a izomorficzne, a zatem,

na mocy wyboru σ

mamy: A

ψ wtedy i tylko wtedy, gdy B

ψ, a to jest

sprzeczno´s´c z (3). Trzeba zatem odrzuci´c przypuszczenie dowodu nie wprost warunku
(F) i twierdzenie zachodzi.

Trzeba wi˛ec jedynie udowodni´c (3). Dowód mo˙ze sprawia´c wra˙zenie nieco zawi-

łego. B˛edziemy, intuicyjnie mówi ˛

ac, podawa´c „opis” warunku (2) w logice L.

Mo˙zemy zało˙zy´c, ˙ze A i B, czyli dziedziny struktur A i, odpowiednio, B, s ˛

a roz-

ł ˛

aczne. Pami˛etajmy tak˙ze, ˙ze sygnatura σ jest czysto relacyjna.

Tworzymy sygnatur˛e σ

dodaj ˛

ac do σ nowe symbole:

• jednoargumentowy symbol funkcyjny f

• jednoargumentowe predykaty P, U, V

• dwuargumentowe predykaty <, I

• trójargumentowy predykat G.

Zbudujemy struktur˛e C ∈ Str

, której uniwersum C b˛edzie zawierało uniwersa

struktur A oraz B, a tak˙ze (jako elementy) wszystkie cz˛e´sciowe izomorfizmy I

. W

ten sposób L „opisze” sko´nczon ˛

a izomorficzno´s´c (I

)

n∈ω

: A σ

∼

Niech zatem:

• (a) C = A ∪ B ∪ ω ∪

n∈ω

• (b) U

= A oraz [U

]

Cσ

= A

• (c) V

= B oraz [V

]

Cσ

= B

• (d) <

jest naturalnym porz ˛

adkiem w ω, a f

ω jest funkcj ˛

a poprzednika,

czyli f

(n + 1) = n, a f

(0) = 0

• (e) P

n∈ω

• (f) I

(n, p) wtedy i tylko wtedy, gdy n ∈ ω oraz p ∈ I

• (g) G

(p, a, b) wtedy i tylko wtedy, gdy P

(p), a ∈ dom(p) oraz p(a) = b.

Teraz zbudujemy koniunkcj˛e χ sko´nczenie wielu poni˙zszych zda´n (i)–(viii) z L(σ

dla której C b˛edzie 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) → ∀x

. . . x

∀y

. . . y

((G(p, x

, y

) ∧ . . . ∧ G(p, x

, y

)) →

(R(x

, . . . , x

) ≡ R(y

, . . . y

))))

dla ka˙zdego n-argumentowego predykatu R ∈ σ

• (iv) aksjomaty cz˛e´sciowego porz ˛

adku dla < oraz fakt,˙ze pole < jest uporz ˛

adko-

wane przez < wraz z funkcj ˛

a 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´sli x jest w polu <, to I

= {p : P (p) ∧ I(x, p)} 6= ∅)

• (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´c, własno´s´c rozszerzania cz˛e´sciowych 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´c, własno´s´c rozszerzania cz˛e´sciowych izomorfizmów „w tył”)

• (viii) ∃x U (x) ∧ ∃y V (y) ∧ ψ

∧ (¬ψ)

(pami˛etamy, ˙ze U

= A, V

= B oraz A |=

ψ i B |=

¬ψ).

Uwaga: tu (i wcze´sniej) u˙zywamy predykatu identyczno´sci =, którego nie nale˙zy

myli´c z (metajezykowym) symbolem relacji identyczno´sci =.

Na mocy (i)–(iii), G opisuje wykres cz˛e´sciowego izomorfizmu z σ

-podstruktury

generowanej przez U w σ

-podstruktur˛e generowan ˛

a przez V .

Wybieramy now ˛

a stał ˛

a indywidualn ˛

a c. Termy c, f (c), f (f (c)), . . . b˛edziemy ozna-

cza´c f

c, f

c, . . .. Niech Ψ = {χ} ∪ {f

n+1

c < f

; n ∈ ω}. Ka˙zdy sko´nczony

podzbiór zbioru Ψ ma model, a mianowicie model C

= (C, c

), gdzie c

jest wystar-

czaj ˛

aco du˙z ˛

a liczb ˛

a naturaln ˛

a. Na mocy zwarto´sci logiki L istnieje model (D, c

) dla

całego zbioru Ψ. Zbiór D zawiera niesko´nczony ci ˛

ag <

-zst˛epuj ˛

acy, a mianowicie:

. . . (f

. Potrzebujemy przeliczalnego modelu o tej własno´sci.

Nie mo˙zemy jednak skorzysta´c bezpo´srednio z własno´sci Löwenheima-Skolema, bo
dotyczy ona tylko pojedynczych zda´n, a zbiór Ψ jest niesko´nczonym zbiorem zda´n.

Rozszerzamy teraz sygnatur˛e σ

∪ {c} o nowy jednoargumentowy predykat Q.

Niech ϑ b˛edzie (σ

∪ {c, Q})-zdaniem:

Q(c) ∧ ∀x (Q(x) → (f (x) < x ∧ Q(f (x))))

(wida´c, ˙ze Q jest podzbiorem pola <: Q zawiera c i ka˙zdy element Q ma bezpo´sredni
poprzednik, który tak˙ze nale˙zy do Q).

Niech Q

= {(f

: n ∈ ω}. Wtedy (D, c

, Q

) |=

χ ∧ ϑ.

Poniewa˙z χ ∧ ϑ jest spełnialna, wi˛ec na mocy własno´sci Löwenheima-Skolema

istnieje (co najwy˙zej) przeliczalny model (E, c

, Q

) dla χ ∧ ϑ.

Skoro w E zachodzi (viii), to U

6= ∅ oraz V

6= ∅. Poniewa˙z σ jest relacyjna,

wi˛ec U

oraz V

s ˛

a uniwersami podstruktur. Niech:

• A

= [U

]

Eσ

• B

= [V

]

Eσ

Poka˙zemy, ˙ze (co najwy˙zej) przeliczalne struktury A

oraz B

spełniaj ˛

a (3).

Na mocy (viii) mamy: E |=

oraz E |=

(¬ψ)

, a st ˛

ad otrzymujemy (na mocy

własno´sci relatywizacji):

(4)

ψ,

¬ψ.

Z warunków (i)–(iii) wiemy, ˙ze ka˙zdy p ∈ P

odpowiada cz˛e´sciowemu izomor-

fizmowi z A

w B

(b˛edziemy ka˙zdy taki cz˛e´sciowy izomorfizm oznacza´c

przez p).

Poniewa˙z (E, c

, Q

) |= ϑ, wi˛ec dla ka˙zdego n ∈ ω element e

= (f

nale˙zy

do Q

oraz elementy e

tworz ˛

a ci ˛

ag zst˛epuj ˛

acy:

. . . e

Niech I = {p :

istnieje n taka, ˙ze I

, p)}. Na mocy (v) otrzymujemy, ˙ze

I 6= ∅. Na mocy (vi) oraz (vii) otrzymujemy, ˙ze I ma własno´s´c rozszerzania w przód i
w tył.

Dostajemy zatem:
(5)

I : A

∼

Teraz (4) i (5) daj ˛

a ł ˛

acznie (3). Tym samym, dowód I twierdzenia Lindströma jest

zako´nczony.

Udowodnimy jeszcze dwa lematy, który b˛ed ˛

a potrzebne w dowodzie II twierdzenia

Lindströma.

EMAT

Niech L b˛edzie logik ˛

a regularn ˛

a, L

ωω

6 L. Niech L b˛edzie zwarta i niech ma

własno´s´c Löwenheima-Skolema. Niech wreszcie σ

b˛edzie sko´nczon ˛

a sygnatur ˛

a czy-

sto relacyjn ˛

a, c stał ˛

a indywidualn ˛

a spoza σ

oraz ψ niech b˛edzie σ

-zdaniem logiki L.

Niech dla ka˙zdego m ∈ ω istniej ˛

a struktury A

, B

takie, ˙ze:

(F)

∼

, A

ψ, B

¬ψ.

Wtedy istnieje σ

-zdanie χ

, gdzie σ

∪ {<, c} ⊆ σ

oraz σ

jest sko´nczona, takie,

˙ze:

• (a) Je´sli A |=

, to (A, <

) jest cz˛e´sciowym porz ˛

adkiem, a c

elementem A

o sko´nczonej liczbie <

-poprzedników.

• (b) Dla ka˙zdego m ∈ ω istnieje A taka, ˙ze A |= χ

oraz c

ma co najmniej m

-poprzedników.

OWÓD

W oznaczeniach poprzedniego dowodu, niech σ = σ

, σ

= σ

∪ {c} oraz χ

niech b˛edzie koniunkcj ˛

a χ i zdania stwierdzaj ˛

acego, ˙ze c le˙zy w polu <.

Najpierw udowodnimy (b). Niech dla danego m ∈ ω struktury A

, B

spełniaj ˛

(F) oraz niech (I

)

n6m

: A

∼

= B

Definiujemy C tak, jak w dowodzie I twierdzenia Lindströma, z nast˛epuj ˛

acymi mo-

dyfikacjami:

• (i) <

jest naturalnym porz ˛

adkiem na {0, 1, . . . , m}

• (ii) P

n6m

Niech c

= m. Wtedy (C, c

) spełnia (b).

Dla dowodu (nie wprost) (a), przypu´s´cmy, ˙ze istnieje model (D, c

) dla χ

, w któ-

rym c

ma niesko´nczenie wiele <

-poprzedników. Tak jak w dowodzie I twierdzenia

Lindströma, z (D, c

) otrzymujemy dwie izomorficzne struktury A

i B

takie, ˙ze:

ψ oraz B

¬ψ. To daje sprzeczno´s´c (izomorficzne modele musz ˛

a spełnia´c

dokładnie te same zdania), a wi˛ec przypuszczenie dowodu nie wprost trzeba odrzuci´c.
Tym samym dowód (a) oraz całego lematu jest zako´nczony.

EMAT

Niech L b˛edzie logik ˛

a regularn ˛

a, L

ωω

6 L. Niech σ b˛edzie sko´nczon ˛

a sygnatur ˛

czysto relacyjn ˛

a. Je´sli dla ψ ∈ L(σ) nie istnieje zdanie pierwszego rz˛edu o tych samych

modelach, co ψ, to dla ka˙zdego m ∈ ω istniej ˛

a struktury A

, B

∈ Str

takie, ˙ze:

(F)

∼

, A

ψ oraz B

¬ψ.

OWÓD

Załó˙zmy, ˙ze ψ jest spełnialna. W przeciwnym przypadku, teza lematu spełniona

jest trywialnie: M od

(ψ) = M od

ωω

(∃v ¬v = v).

Przeprowadzimy dowód nie wprost. Przypu´s´cmy, ˙ze dla pewnego m ∈ ω oraz

wszystkich struktur A, B ∈ Str

(1)

je´sli A ∼

B, to A |=

ψ wtedy i tylko wtedy, gdy B |=

ψ.

Niech ϕ

, . . . , ϕ

b˛ed ˛

a wszystkimi nierównowa˙znymi logicznie zdaniami pierw-

szego rz˛edu o rz˛edzie kwantyfikatorowym

6 m. Pami˛etamy, ˙ze je´sli σ b˛edzie sko´n-

czon ˛

a sygnatur ˛

a czysto relacyjn ˛

a, to istnieje tylko sko´nczenie wiele takich nierówno-

wa˙znych logicznie formuł (dowodzimy tego faktu w KRP, przez indukcj˛e po zło˙zono´sci
formuł). Wtedy:

(2)

A ∼

B wtedy i tylko wtedy, gdy dla wszystkich 0

6 i 6 k mamy:

|= ϕ

wtedy i tylko wtedy, gdy B |= ϕ

Dla A ∈ Str

niech ϕ

b˛edzie koniunkcj ˛

a wszystkich zda´n ze zbioru:

{ϕ

: 0 6 i 6 k ∧ A |= ϕ

} ∪ {¬ϕ

: 0 6 i 6 k ∧ A |= ¬ϕ

Na mocy (2) mamy wtedy, dla dowolnej B:
(3)

A ∼

B wtedy i tylko wtedy, gdy B |= ϕ

Niech ϕ b˛edzie alternatyw ˛

a (sko´nczenie wielu!) zda´n ϕ

, dla których zachodzi

|= ψ, czyli ϕ jest zdaniem:

(4)

W{ϕ

: A ∈ Str

∧ A |= ψ}.

Poka˙zemy, ˙ze:
(5)

M od

(ψ) = M od

ωω

(ϕ)

i uzyskamy sprzeczno´s´c z przypuszczeniem dowodu nie wprost.

Je´sli B jest modelem ψ, to ϕ

nale˙zy do alternatywy (4) (jest jednym z jej czło-

nów). Poniewa˙z B |= ϕ

, wi˛ec B |= ϕ.

Je´sli, z drugiej strony, B |= ϕ, to (na mocy (4)) istnieje A taka, ˙ze A |=

ψ oraz

|= ϕ

. Na mocy (3) mamy wtedy A ∼

B, a na mocy (1) mamy B |=

ψ.

Mamy st ˛

ad sprzeczno´s´c, gdy˙z równowa˙zno´s´c: B |=

ψ wtedy i tylko wtedy, gdy

|= ϕ oznacza, ˙ze M od

(ψ) = M od

ωω

(varphi). Tak wi˛ec, przypuszczenie do-

wodu nie wprost musimy odrzuci´c, co ko´nczy dowód lematu 5.

II Twierdzenie Lindströma

Przed sformułowaniem II twierdzenia Lindströma trzeba wprowadzi´c kilka poj˛e´c,

których twierdzenie to dotyczy. Zakładamy, ˙ze czytelnik ma podstawowe wiadomo´sci
dotycz ˛

ace elementarnej teorii rekursji, a wi˛ec ˙ze zna np. poj˛ecie zbioru rekurencyjnego,

zbioru rekurencyjnie przeliczalnego, funkcji rekurencyjnej, itp.

Powiemy, ˙ze logika L jest efektywna, gdy dla ka˙zdej rekurencyjnej sygnatury σ

zbiór L(σ) jest rekurencyjny oraz dla ka˙zdego zdania ψ ∈ L(σ) istnieje sko´nczona
σ

⊆ σ taka, ˙ze ψ ∈ L(σ

Niech logiki L i L

b˛ed ˛

a efektywne. Piszemy:

• (a) L 6

ef f

wtedy i tylko wtedy, gdy istnieje funkcja rekurencyjna F taka, ˙ze

dla ka˙zdego ψ ∈ L(σ) mamy: F (ψ) ∈ L

(σ) oraz M od

(ψ) = M od

(F (ψ)).

• (b) L ∼

ef f

wtedy i tylko wtedy, gdy L

ef f

oraz L

ef f

L. Je´sli

L ∼

ef f

, to mówimy, ˙ze L i L

s ˛

a efektywnie równowa˙zne.

Dla przykładu:

• L

ωω

, logika drugiego rz˛edu L

, słaba logika drugiego rz˛edu L

, logika L(Q

)

(czyli logika z kwantyfikatorem „istnieje nieprzeliczalnie wiele”) s ˛

a efektywne

• L

nie jest efektywna

• L

ωω

ef f

• L

ef f

Mówimy, ˙ze logika L jest efektywnie regularna, gdy L jest efektywna oraz dla

ka˙zdej rekurencyjnej sygnatury σ zachodz ˛

a nast˛epuj ˛

ace warunki:

• (i) istniej ˛

a funkcje rekurencyjne ϕ 7→ ¬ϕ oraz (ϕ, ψ) 7→ ϕ ∨ ψ (i podobnie dla

pozostałych spójników)

• (ii) dla ka˙zdego jednoargumentowego predykatu U istnieje funkcja rekurencyjna

ϕ 7→ ϕ

• (iii) istnieje funkcja rekurencyjna ϕ 7→ ϕ

(przy tym sygnatura σ

musi by´c

rekurencyjna).

Niech logika L b˛edzie efektywna. Mówimy, ˙ze zbiór zda´n prawdziwych logiki

L jest rekurencyjnie przeliczalny, gdy dla ka˙zdej rekurencyjnej sygnatury σ zbiór
{ϕ ∈ L(σ) : ∅ |=

ϕ} jest rekurencyjnie przeliczalny. Mówi ˛

ac, ˙ze ten ostatni zbiór

jest rekurencyjnie przeliczalny mamy oczywi´scie na my´sli to, ˙ze zbiór kodów jego
elementów (uzyskanych przez jak ˛

a´s funkcj˛e rekurencyjn ˛

a, czyli np. przez numeracj˛e

Gödlowsk ˛

a) jest rekurencyjnie przeliczalny.

II T

WIERDZENIE

INDSTRÖMA

Niech L b˛edzie efektywnie regularna i L

ωω

ef f

L. Je´sli L ma własno´s´c Löwen-

heima-Skolema oraz zbiór zda´n prawdziwych logiki L jest rekurencyjnie przeliczalny,
to L

ωω

∼

ef f

OWÓD

Niech L spełnia zało˙zenia twierdzenia. Poka˙zemy, ˙ze L

ef f

ωω

w dwóch kro-

kach:

• (∗) Najpierw poka˙zemy, ˙ze spełniony jest nast˛epuj ˛

acy warunek:

(F)

Dla ka˙zdej rekurencyjnej sygnatury σ oraz ka˙zdego ψ ∈ L(σ) istnieje

ϕ ∈ L

ωω

(σ) takie, ˙ze M od

(ψ) = M od(ϕ).

• (∗∗) Potem poka˙zemy, ˙ze przej´scie od ψ do φ jest efektywne.

Poniewa˙z L jest efektywna, wi˛ec wystarczy rozwa˙za´c sko´nczone sygnatury re-

kurencyjne. Poniewa˙z dla L istnieje efektywny odpowiednik własno´sci zast˛epowania
symboli funkcyjnych i stałych indywidualnych przez predykaty, mo˙zemy ograniczy´c
si˛e do sygnatur σ czysto relacyjnych.

Niech zatem σ b˛edzie: rekurencyjna, sko´nczona i relacyjna.
Poprowadzimy dowód kroku (∗) metod ˛

a nie wprost, korzystaj ˛

ac z lematów 4 i 5

oraz z Twierdzenia Traktenbrota.

Przypuszczamy zatem, ˙ze (

F) nie zachodzi, czyli ˙ze ψ ∈ L(σ) oraz ˙ze ˙zadne

zdanie pierwszego rz˛edu nie ma dokładnie tych samych modeli co ψ.

Na mocy lematu 5, dla ka˙zdej m istniej ˛

a A

, B

∈ Str

takie, ˙ze:

• A

∼

• A

• B

¬ψ.

Spełnione s ˛

a wi˛ec zało˙zenia lematu 4. Istniej ˛

a zatem: sygnatura σ

oraz zdanie χ

z tezy tego lematu.

Rozszerzamy σ

przez dodanie jednoargumentowego predykatu W i rozwa˙zamy

zdanie ϑ ∈ L(σ

∪ {W }) o nast˛epuj ˛

acej postaci:

∧ ∃x W (x) ∧ ∀x (W (x) → x < c).

Na mocy własno´sci zdania χ

mamy wtedy:

• (a) Je´sli A ∈ Str

∪{W }

oraz A |=

ϑ, to zbiór W

jest niepusty i sko´nczony.

• (b) Dla ka˙zdej m > 1 istnieje A taka, ˙ze A |= ϑ oraz W

ma dokładnie m

elementów.

Tak wi˛ec, je´sli A przebiega wszystkie modele ϑ, to W

przebiega wszystkie (nie-

puste) zbiory sko´nczone (pami˛etajmy, ˙ze wszystkie rozwa˙zane logiki maj ˛

a własno´s´c

izomorfizmu).

Z powy˙zszych warunków (a) i (b) otrzymamy sprzeczno´s´c z przypuszczeniem do-

wodu nie wprost.

Na mocy twierdzenia Traktenbrota istnieje rekurencyjna i sko´nczona sygnatura σ

taka, ˙ze zbiór wszystkich σ

-zda´n prawdziwych we wszystkich strukturach sko´nczo-

nych (tej sygnatury) nie jest zbiorem rekurencyjnie przeliczalnym.

Mo˙zemy zało˙zy´c, ˙ze σ

jest czysto relacyjna i rozł ˛

aczna z σ

∪ {W }.

Niech F b˛edzie odwzorowaniem rekurencyjnym ϕ 7→ F (ϕ), ze zbioru L(σ

) w

L(σ

) tak ˛

a, ˙ze M od(ϕ) = M od(F (ϕ)). Wtedy dla wszystkich zda´n ϕ ∈ L(σ

• ()

ϕ jest prawdziwe we wszystkich strukturach sko´nczonych (sygnatury

) wtedy i tylko wtedy, gdy |=

ϑ → (F (ϕ))

Aby udowodni´c równowa˙zno´s´c (

), trzeba dowie´s´c implikacji prostej oraz odwrot-

nej.

⇒ Niech ϕ b˛edzie prawdziwe we wszystkich strukturach sko´nczonych oraz A ∈

Str

∪{W }∪σ

b˛edzie taka, ˙ze A |=

ϑ. Na mocy (a), W

jest niepusty i sko´nczony, a

wi˛ec [W

]

Aσ

ϕ, a st ˛

ad [W

]

Aσ

F (ϕ). Wtedy A σ

(F (ϕ))

⇐ Na mocy (b), dla ka˙zdej m > 1 istnieje A taka, ˙ze A |= ϑ i W

ma dokładnie

m elementów. St ˛

ad A |=

(F (ϕ))

, czyli A |=

. W konsekwencji, [

]

Aσ

|= ϕ.

To ko´nczy dowód (

), a tym samym dowód kroku (∗).

Przechodzimy do dowodu kroku (∗∗). Niech g

b˛edzie funkcj ˛

a rekurencyjn ˛

a, przy-

pisuj ˛

ac ˛

a numery (np. numery Gödlowskie) zdaniom logiki L, czyli zdaniom ustalonej

sygnatury rekurencyjnej σ. Na mocy faktu, ˙ze zbiór zda´n prawdziwych logiki L jest
rekurencyjnie przeliczalny, dla ka˙zdej rekurencyjnej sygnatury σ istnieje dwuargumen-
towa relacja rekurencyjna, powiedzmy R, taka, ˙ze dla wszystkich zda´n ϕ ∈ L(σ):

• |=

ϕ wtedy i tylko wtedy, gdy ∃m R(m, g

(ϕ)).

Ustalmy wyliczenie hψ

: n ∈ ωi wszystkich σ-zda´n logiki L

ωω

takie, ˙ze przypo-

rz ˛

adkowanie n 7→ g

ωω

(ψ

) jest rekurencyjne. Niech G b˛edzie funkcj ˛

a rekurencyjn ˛

tak ˛

a, ˙ze dla σ-zda´n logiki L:

• G(g

(ϕ)) = ((µhm, ni)R(m, g

(ϕ ≡

(ψ

)

)))

(tu hi jest np. pierwotnie rekurencyjn ˛

a funkcj ˛

a koduj ˛

ac ˛

a (pary) Cantora, a ()

jest pier-

wotnie rekurencyjn ˛

a funkcj ˛

a rzutu, na pierwszy argument pary; µ x [. . .] jest efektyw-

nym µ-operatorem, czytanym: „najmniejsze x takie, ˙ze [. . .]”). Powy˙zej zaznaczyli´smy
wyra´znie, ˙ze bierzemy spójnik równowa˙zno´sci z logiki L oraz, ˙ze rozwa˙zamy „prze-
kład” formuły ψ

na stosowne zdanie logiki L.

Niech ϕ

∗

b˛edzie formuł ˛

a ψ

G(g

σ
L

(ϕ))

. Wtedy rekurencyjne odwzorowanie ϕ 7→ ϕ

∗

po´swiadcza, ˙ze L

ef f

ωω

Dowód II twierdzenia Lindströma został tym samym zako´nczony.

Przypomnijmy jeszcze sformułowanie twierdzenia Traktenbrota, na które powołu-

jemy si˛e w powy˙zszym dowodzie (jego dowód podajemy w Preliminariach matema-
tycznych

, w dziale dotycz ˛

acym matematycznych modeli obliczalno´sci).

WIERDZENIE

RAKTENBROTA

. Istnieje sko´nczona sygnatura σ taka,

˙ze zbiór wszystkich zda´n (j˛ezyka KRP o sygnaturze σ) prawdziwych we

wszystkich strukturach sko´nczonych nale˙z ˛

acych do Str

nie jest rekuren-

cyjnie przeliczalny.

Oprócz powy˙zszych twierdze´n Lindströma, znaleziono cały szereg innych jeszcze

twierdze´n, charakteryzuj ˛

acych logiki abstrakcyjne maksymalne je´sli chodzi o wybrane

zestawy własno´sci. Twierdzenia te dotycz ˛

a zarówno logik z uogólnionymi kwantyfika-

torami, jak i logik infinitarnych. Tak˙ze logiki wy˙zszych rz˛edów mog ˛

a by´c oczywi´scie

traktowane jako logiki abstrakcyjne w omówionym wy˙zej sensie.

2.4. Kilka przykładów

Wspominali´smy ju˙z na Seminarium Zakładu Logiki Stosowanej UAM o logikach

z uogólnionymi kwantyfikatorami. Dla przypomnienia, podajmy garstk˛e informacji o
niektórych takich logikach.

Mostowski rozwa˙zał tzw. kwantyfikatory numeryczne Q

, gdzie α jest liczb ˛

a po-

rz ˛

adkow ˛

a. Znaczenie formuły Q

xϕ(x) okre´sla si˛e nast˛epuj ˛

aco:

• M |= Q

xϕ(x) wtedy i tylko wtedy, gdy zbiór {a ∈ dom(M) : M |= ϕ(x)[a]}

ma moc nie mniejsz ˛

a od ℵ

W szczególno´sci, Q

jest kwantyfikatorem, za pomoc ˛

a którego wyrazi´c mo˙zna po-

j˛ecia: niesko´nczenie wiele oraz sko´nczenie wiele, poniewa˙z formuła Q

xϕ(x) jest speł-

niona w strukturze M wtedy i tylko wtedy, gdy w dom(M) istnieje co najmniej ℵ

obiektów, spełniaj ˛

acych formuł˛e ϕ(x). Jak pami˛etamy z elementarnego kursu logiki,

poj˛e´c tych nie mo˙zna wyrazi´c w klasycznej logice pierwszego rz˛edu.

Mostowski formułuje pewne warunki, które musz ˛

a by´c spełnione, aby tak wprowa-

dzone poj˛ecie miało porz ˛

adn ˛

a (i zamierzon ˛

a) semantyk˛e. Do warunków takich nale˙zy

to, ˙ze je´sli M |= Q

xϕ(x) oraz struktury M i N s ˛

a izomorficzne, to zachodzi równie˙z

|= Q

xϕ(x). Odpowiada to intuicjom zwi ˛

azanym z kwantyfikatorem (numerycz-

nym): ma on charakteryzowa´c jedynie liczb˛e obiektów, nie przes ˛

adzaj ˛

ac niczego o ich

jako´sci.

Kwantyfikatory numeryczne Mostowskiego rozumie´c mo˙zna w sposób relacyjny:

kwantyfikatorem (jednoargumentowym) jest rodzina Q par zbiorów (U, X), gdzie X ⊆
U oraz je´sli (U, X) ∈ Q i |X| = |Y |, |U − X| = |V − Y |, to (V, Y ) ∈ Q. Symbol |X|
oznacza, przypomnijmy, moc zbioru X. Dla przykładu:

= {(U, X) : |X| > ℵ

Kwantyfikatory tak rozumiane mog ˛

a by´c traktowane jako operacje Q spełniaj ˛

ace

nast˛epuj ˛

ace warunki:

• Je´sli ϕ(x, −

→

y ) jest formuł ˛

a, to formuł ˛

a jest równie˙z Qxϕ(x,

−

→

y ).

• M |= Qxϕ(x, −

→

y )[b, −

→

a ] wtedy i tylko wtedy, gdy:

(dom(M), {b : M |= ϕ(x, −

→

y )[b, −

→

a ]}) ∈ Q.

Je´sli L

ωω

oznacza klasyczn ˛

a logik˛e pierwszego rz˛edu, to niech L

ωω

(Q) oznacza

jej rozszerzenie otrzymane przez dodanie tak rozumianego kwantyfikatora Q.

Mostowski udowodnił, ˙ze L

ωω

) nie jest (efektywnie) aksjomatyzowalna. Niech

θ b˛edzie zdaniem:

∀x¬Q

y (y < x)

j˛ezyka L

ωω

) i niech Π b˛edzie aksjomatyk ˛

a arytmetyki Peana (w j˛ezyku L

ωω

), a

modelem standardowym tej arytmetyki. Wtedy dla ka˙zdego zdania φ j˛ezyka L

ωω

mamy:

• N

|= φ wtedy i tylko wtedy, gdy dla ka˙zdego M, je´sli M |= Π, to

|= (θ → φ).

Poniewa˙z, jak wiadomo, nie ma efektywnej procedury arytmetycznej dla rozstrzy-

gania lewej strony tej równowa˙zno´sci, wi˛ec nie istnieje pełna metoda dowodowa dla
L

ωω

Postawiony przez Mostowskiego problem, czy L

ωω

) jest aksjomatyzowalna

został rozwi ˛

azany przez Keislera.

Mostowski podał tak˙ze teorio-modelow ˛

a charakterystyk˛e kwantyfikatorów pierw-

szego rz˛edu: dowolne rozszerzenie logiki pierwszego rz˛edu otrzymane przez dodanie
jednoargumentowego kwantyfikatora, które spełnia warunek:

• ka˙zde zdanie, które ma model niesko´nczony, ma te˙z model ka˙zdej mocy niesko´n-

czonej

jest równowa˙zne z logik ˛

a pierwwszego rz˛edu.

Uj˛ecie Mostowskiego doczekało si˛e wkrótce uogólnienia, w pracach Lindströma

(1969), gdzie rozwa˙za si˛e nie tylko kwantyfikatory jednoargumentowe, lecz równie˙z
wieloargumentowe. Takimi s ˛

a, dla przykładu:

• K

WANTYFIKATOR

ÄRTIGA

. I = {(U, X, Y ) : |X| = |Y |}

• K

WANTYFIKATOR

ESCHERA

. R = {(U, X, Y ) : |X|

6 |Y |}.

Te kwantyfikatory nie mog ˛

a zosta´c wyra˙zone w formalizmie Mostowskiego. Defi-

nicja Lindströma ma, w uproszczeniu, posta´c nast˛epuj ˛

ac ˛

(Lokalnym) kwantyfikatorem uogólnionym na M typu hk

, . . . , k

i nazywamy do-

woln ˛

a n-arn ˛

a relacj˛e pomi˛edzy podzbiorami M

, . . . , M

Uogólnionym kwantyfikatorom po´swi˛ecili´smy osobny wykład. W wi˛ekszo´sci przy-

padków była mowa o tzw. kwantyfikatorach uogólnionych monadycznych binarnych,
czyli typu h1, 1i.

Kwantyfikatory rozwa˙zane przez Mostowskiego były typu h1i, kwantyfikatory Här-

tiga i Reschera s ˛

a typu h1, 1i.

W 1959 roku Henkin rozwa˙zał inne rodzaje kwantyfikatorów, ró˙zne od kwantyfi-

katorów numerycznych Mostowskiego.

Pami˛etamy, ˙ze przy tworzeniu prefiksowej postaci normalnej formuły j˛ezyka ra-

chunku predykatów wszystkie kwantyfikatory poprzedzaj ˛

a matryc˛e formuły. Przy sko-

lemizacji takiej formuły eliminujemy kwantyfikatory egzystencjalne, wprowadzaj ˛

nowe symbole funkcyjne (dla funkcji Skolema).

Symbol funkcyjny f wprowadzony przez eliminacj˛e kwantyfikatora ∃ z prefiksu

kwantyfikatorowego Q

. . . Q

(gdzie Q

s ˛

a kwantyfikatorami klasycznymi: ∀ oraz

∃) ma tyle argumentów, ile kwantyfikatorów ogólnych poprzedza ów eliminowany
kwantyfikator ∃ w prefiksie Q

. . . Q

. Powstaje problem, czy ta procedura dobrze

opisuje sytuacje, w których dokonujemy wyborów niezale˙znych. Henkin wprowadził
uogólnienie tej procedury, dopuszczaj ˛

ac prefiksy cz˛e´sciowo uporz ˛

adkowane lub ina-

czej prefiksy rozgał˛ezione, za pomoc ˛

a których mo˙zna wyrazi´c zale˙zno´sci, których nie

mo˙zna przedstawi´c w sposób liniowy. Kwantyfikator Henkina ma posta´c nast˛epuj ˛

ac ˛

∀u——∃v

∀x——∃y

φ(x, y, u, v)

Cz˛e´sciowy porz ˛

adek prefiksu ma oddawa´c sytuacj˛e, gdy dokonujemy wyborów

niezale˙znych. Semantyk˛e dla tego kwantyfikatora ustala si˛e nast˛epuj ˛

aco:

Kwantyfikator Henkina

to kwantyfikator typu h4i taki, ˙ze:

{R ⊆ M

: istniej ˛

a funkcje

f, g na M takie,˙ze

dla dowolnych

a, b ∈ M (a, f (a), b, f (b)) ∈ R}.

J˛ezyk z kwantyfikatorem Henkina ma moc wyra˙zania istotnie wi˛eksz ˛

a ni˙z j˛ezyk

klasycznego rachunku predykatów. Mo˙zna pokaza´c, ˙ze kwantyfikator Q

Mostow-

skiego jest definiowalny przez kwantyfikator Henkina. Poj˛ecie „mocy wyra˙zania” j˛e-
zyka było obja´snione wcze´sniej

Dalszych uogólnie´n dokonał w latach siedemdziesiatych XX wieku Barwise. Roz-

wa˙zał m.in. rozgał˛ezione prefiksy, w których wyst˛epowały uogólnione kwantyfikatory
(w sensie Lindströma).

Oto jeszcze kilka dalszych kwantyfikatorów uogólnionych:

∀

= {M },

∃

= {X ⊆ M : X 6= ∅},

(∃

≥n

)

= {X ⊆ M : |X| ≥ n},

)

= {X ⊆ M : |X| ≥ ℵ

)

= {X ⊆ M : |X| > |M − X|},

(Kwantyfikator Reschera),

)

= {X ⊆ M : |X| = |M |},

(Kwantyfikator Changa).

Wida´c zatem, ˙ze równie˙z „zwykłe” kwantyfikatory mo˙zna uwa˙za´c za kwantyfika-

tory uogólnione (co jest do´s´c oczywiste — dobre uogólnienie powinno uwzgl˛ednia´c
przypadki wyj´sciowe).

Przez L

oznacza´c teraz b˛edziemy j˛ezyk KRP z kwantyfikatorem Q. Interpretacje

wyznaczone b˛ed ˛

a przez semantyczn ˛

a charakterystyk˛e Q. Dla j˛ezyka L

z ustalon ˛

interpretacj ˛

a semantyczn ˛

a Q b˛edziemy te˙z u˙zywa´c terminu „logika L

”. Niech ℵ

b˛e-

dzie α-t ˛

a moc ˛

a niesko´nczon ˛

a (gdzie α jest liczb ˛

a porz ˛

adkow ˛

a). Zamiast ℵ

piszemy

czasem ω. Je´sli κ, λ s ˛

a niesko´nczonymi liczbami kardynalnymi, to przez L

κλ

rozu-

miemy j˛ezyk w którym dopuszczalne s ˛

a koniunkcje i alternatywy długo´sci mniejszej

ni˙z κ oraz prefiksy kwantyfikatorowe długo´sci mniejszej ni˙z λ. Tak wi˛ec, L

ωω

to j˛e-

zyk KRP, klasycznej logiki pierwszego rz˛edu. Przez L

∞λ

rozumiemy j˛ezyk, w którym

dopuszczalne s ˛

a koniunkcje i alternatywy dowolnej długo´sci oraz prefiksy kwantyfika-

torowe długo´sci mniejszej ni˙z λ.

WANTYFIKATOR

„

ISTNIEJE NIESKO ´

NCZENIE WIELE

”

Wyra˙zenie Q

x α(x) czytamy: istnieje niesko´nczenie wiele x takich, ˙ze α(x).

Semantyka Q

wyznaczona jest przez warunek:

|= Q

x α(x) wtedy i tylko wtedy, gdy zbiór {a ∈ dom(A) : A |= α[a]} jest

niesko´nczony.

Oto niektóre własno´sci L

• Standardowy model arytmetyki PA mo˙zna scharakteryzowa´c w L

z dokładno-

´sci ˛

a do izomorfizmu.

Wystarczy do aksjomatów dyskretnego liniowego porz ˛

adku < doda´c aksjomat:

∀x¬Q

y y < x.

• W L

nie zachodzi górne twierdzenie Löwenheima-Skolema.

• L

nie jest aksjomatyzowalna.

• W L

nie zachodzi twierdzenie o zwarto´sci.

• W L

zachodzi dolne twierdzenie Löwenheima-Skolema.

• Pełno´s´c (systemu dowodowego z niesko´nczonymi dowodami) dla L

mo˙zna

otrzyma´c przez dodanie reguły infinitarnej:

∃

x α(x), ∃

x α(x), . . .

x α(x)

• Dowolna przeliczalna ℵ

-kategoryczna teoria w L

bez modeli sko´nczonych

jest zupełna.

• Teoria g˛estych liniowych porz ˛

adków jest zupełna w L

• L

jest fragmentem L

, co wida´c z równowa˙zno´sci:

x α(x) ≡

n<ω

∃

x α(x).

WANTYFIKATOR

„

ISTNIEJE NIEPRZELICZALNIE WIELE

”

Wyra˙zenie Q

x α(x) czytamy: istnieje nieprzeliczalnie wiele x takich, ˙ze α(x).

Semantyka Q

wyznaczona jest przez warunek:

|= Q

x α(x) wtedy i tylko wtedy, gdy zbiór {a ∈ dom(A) : A |= α[a]} jest

nieprzeliczalny.

Ograniczamy si˛e do interpretacji nieprzeliczalnych.
Tak jak w L

definiowalne jest poj˛ecie sko´nczono´sci, tak w L

definiowalne jest

poj˛ecie przeliczalno´sci.

Oto niektóre własno´sci L

• Teoria g˛estych liniowych porz ˛

adków nie jest zupełna w L

• Górne twierdzenie Löwenheima-Skolema nie zachodzi w L

. Dolne twierdze-

nie LS zachodzi w nast˛epuj ˛

acej wersji: je´sli teoria w L

(mocy co najwy˙zej ℵ

)

ma model, to ma model mocy ℵ

• Ka˙zda ℵ

-kategoryczna teoria w L

(mocy co najwy˙zej ℵ

) jest zupełna.

• Teoria ciał algebraicznie domkni˛etych charakterystyki zero jest zupełna w L

• L

jest (!) aksjomatyzowalna.

WANTYFIKATOR

HANGA

Wyra˙zenie Q

x α(x) czytamy: istnieje tyle x takich, ˙ze α(x) ile jest obiektów w

całym uniwersum.

Semantyka Q

wyznaczona jest przez warunek:

|= Q

x α(x) wtedy i tylko wtedy, gdy zbiór {a ∈ dom(A) : A |= α[a]} ma tak ˛

sam ˛

a moc, jak zbiór dom(A).

Oto niektóre własno´sci L

• W modelach mocy ℵ

kwantyfikator Q

ma tak ˛

a sam ˛

a interpretacj˛e, jak kwan-

tyfikator Q

• Teoria g˛estych porz ˛

adków liniowych nie jest zupełna w L

• Teoria ciał algebraicznie domkni˛etych charakterystyki zero jest zupełna w L

[Teoria ta dopuszcza eliminacj˛e kwantyfikatorów ∃ i Q

• Je´sli przeliczalna teoria w L

ma model, którego moc jest liczb ˛

a kardynaln ˛

nast˛epnikow ˛

a, to ma model mocy ℵ

• Je´sli przeliczalna teoria w L

ma model mocy ℵ

, to ma modele ka˙zdej mocy

niesko´nczonej.

• Niech V al

b˛edzie zbiorem wszystkich zda´n L

prawdziwych w modelach

mocy ℵ

i niech V al

b˛edzie zbiorem wszystkich zda´n L

prawdziwych w

modelach mocy ℵ

. Wtedy (przy zało˙zeniu uogólnionej hipotezy kontinuum):

1. V al

oraz V al

s ˛

a rekurencyjnie przeliczalne.

2. V al

∩ V al

jest zbiorem wszystkich L

-tautologii.

WANTYFIKATOR

„

JEST WI ˛

ECEJ

NI ˙

B”

Wyra˙zenie Q

x α(x)β(x) czytamy: jest wi˛ecej x takich, ˙ze α(x) ni˙z x takich, ˙ze

β(x).

Semantyka Q

wyznaczona jest przez warunek:

|= Q

x α(x)β(x) wtedy i tylko wtedy, gdy moc zbioru {a ∈ dom(A) : A |=

α[a]} jest wi˛eksza od mocy zbioru {a ∈ dom(A) : A |= β[a]}.

Oto niektóre własno´sci L

• Standardowy model arytmetyki PA mo˙zna scharakteryzowa´c w L

z dokład-

no´sci ˛

a do izomorfizmu.

• L

nie jest aksjomatyzowalna.

• W L

nie zachodzi: ani dolne ani górne twierdzenie Löwenheima-Skolema,

ani twierdzenie o zwarto´sci.

• Q

oraz Q

s ˛

a definiowalne w L

• L

jest logik ˛

a o znacznej „mocy wyra˙zania”: mo˙zna w niej sformułowa´c np.

zdanie, które ma model wtedy i tylko wtedy, gdy fałszywa jest uogólniona hipo-
teza kontinuum.

WANTYFIKATOR

ENKINA

Wyra˙zenie Q

(x, y, u, v)α(x, y, u, v) jest skrótem dla formuły z nast˛epuj ˛

acym

cz˛e´sciowo uporz ˛

adkowanym prefiksem kwantyfikatorowym:

∀u——∃v

∀x——∃y

α(x, y, u, v)

Semantyka dla tego kwantyfikatora wyznaczona jest przez warunek:
A

|= Q

xyuv α(x, y, u, v) wtedy i tylko wtedy, gdy istniej ˛

a funkcje f oraz g

(okre´slone na dom(A) i o warto´sciach w dom(A)) takie, ˙ze A |= α(x, f (x), u, g(u)).

Oto niektóre własno´sci L

• Kwantyfikatory Q

, Q

oraz Q

s ˛

a definiowalne w L

• L

nie jest aksjomatyzowalna.

• W L

nie zachodzi twierdzenie o zwarto´sci.

• W L

nie zachodzi ani dolne, ani górne twierdzenie Löwenheima-Skolema.

Widzimy wi˛ec, ˙ze równie˙z L

ma znaczn ˛

a „moc wyra˙zania”.

∗ ∗ ∗

Niektóre z wymienionych wy˙zej logik (z uogólnionymi kwantyfikatorami) s ˛

a upo-

rz ˛

adkowane nast˛epuj ˛

aco pod wzgl˛edem mocy wyra˙zania (strzałka oznacza zachodze-

nie relacji ≺):

→

ωω

→

(tu I jest kwantyfikatorem Härtiga, a Q

jest kwantyfikatorem wi˛ekszo´sci most:

xα(x)β(x) ma semantyk˛e odpowiadaj ˛

ac ˛

a warunkowi, ˙ze wi˛ekszo´s´c obiektów, które

spełniaj ˛

a α(x), spełnia β(x)).

∗ ∗ ∗

Na pocz ˛

atku drugiej połowy XX wieku rozpocz˛eto równie˙z intensywne badania

logik infinitarnych. Wspominali´smy ju˙z, ˙ze pewne poj˛ecia s ˛

a niewyra˙zalne w L

ωω

czyli w klasycznej logice pierwszego rz˛edu. S ˛

a one natomiast wyra˙zalne w L

αβ

, dla

stosownie dobranych α oraz β. Przypomnijmy par˛e przykładów:

• w L

scharakteryzowa´c mo˙zna model standardowy arytmetyki Peana;

• w L

scharakteryzowa´c mo˙zna klas˛e wszystkich zbiorów sko´nczonych;

• teoria uporz ˛

adkowanych ciał archimedesowych jest w L

sko´nczenie aksjo-

matyzowalna;

• predykat prawdziwo´sci formuł j˛ezyka o przeliczalnej liczbie symboli jest defi-

niowalny w L

;

• poj˛ecie dobrego porz ˛

adku nie jest definiowalne w L

, jest natomiast definio-

walne (pojedyncz ˛

a formuł ˛

a) w L

Jak wiadomo, logiki infinitarne, w których dopuszcza si˛e niesko´nczone prefiksy

kwantyfikatorowe s ˛

a bli˙zsze logice drugiego rz˛edu, z wszelkimi tego faktu konsekwen-

cjami, a wi˛ec, w szczególno´sci, brakiem pełno´sci. Dla L

zachodzi twierdzenie

Scotta o niedefiniowalno´sci predykatu prawdziwo´sci w tym˙ze j˛ezyku; definiowalno´s´c
jest tu rozumiana w odpowiedni sposób, z wykorzystaniem kodowa´n w klasie wszyst-
kich zbiorów dziedzicznie przeliczalnych. W´sród logik infinitarnych o sko´nczonych
prefiksach kwantyfikatorowych szczególne miejsce zajmuje L

. Zachodzi w niej

twierdzenie o pełno´sci, gdy na obecn ˛

a w niej infinitarn ˛

a reguł˛e wnioskowania pozwa-

laj ˛

ac ˛

a wywnioskowa´c koniunkcj˛e

V Φ ze zbioru przesłanek Φ narzucimy warunek,

aby Φ był przeliczalny. Warunek ten jest istotny: istnieje nieprzeliczalny zbiór zda´n
j˛ezyka L

, który nie ma modelu, a którego ka˙zdy przeliczalny podzbiór ma model.

Przykład ten pokazuje jednocze´snie, ˙ze ani w L

, ani w ˙zadnej z logik L

αβ

, gdzie

α > ω

, nie zachodzi twierdzenie o zwarto´sci. Rozwa˙zano jednak stosowne modyfika-

cje tego twierdzenia i wykazano, i˙z zachodzenie tych uogólnionych wersji twierdzenia
o zwarto´sci powi ˛

azane jest z istnieniem du˙zych liczb kardynalnych.

W L

dowoln ˛

a przeliczaln ˛

a struktur˛e z przeliczaln ˛

a liczb ˛

a relacji mo˙zna scha-

rakteryzowa´c z dokładno´sci ˛

a do izomorfizmu, jak wiadomo ze słynnego twierdzenia

Scotta o izomorfizmie. Własno´sci semantyczne modeli dla logik L

αω

i L

∞ω

(np. ele-

mentarn ˛

a równowa˙zno´s´c) mo˙zna charakteryzowa´c metodami algebraicznymi (twier-

dzenie Karp o cz˛e´sciowych izomorfizmach).

Pierwsze zastosowania infinitarnych reguł inferencji znale´z´c mo˙zna (w mniej lub

bardziej ´swiadomej formie) m.in. w pracach Poincarégo, Löwenheima, Carnapa (zob.
te˙z np. podr˛ecznik Ajdukiewicza z 1928 roku). Wraz z wyborem finitystycznego para-
dygmatu logiki pierwszego rz˛edu reguły takie usuni˛ete zostaj ˛

a z tego paradygmatu.

Doł ˛

aczenie do aparatury inferencyjnej ω-reguły pozwala, jak wiadomo, przeprowa-

dzi´c w przypadku pewnych teorii dowody ich zupełno´sci. W przypadku pewnych teorii
jednak nawet tak silne ´srodki dowodowe nie wystarczaj ˛

a: porównajmy w tym kon-

tek´scie uwagi Mostowskiego (Mostowski 1967, s. 110; w pierwszym akapicie autor
odnosi si˛e do — z góry skazanych na niepowodzenie — prób uzyskania jakiej´s charak-
terystyki teorii mnogo´sci przy u˙zyciu infinitarnych metod dowodowych, w drugim —
do prób mocniejszego ugruntowania teorii mnogo´sci np. w logice drugiego rz˛edu):

Wszystkie te wyniki pokazuj ˛

a, ˙ze teoria mnogo´sci oparta na aksjomatyce Zermelo-

Fraenkla jest niezupełna i to w bardzo silnym stopniu. Oczywi´scie nikt nie oczeki-
wał, ˙ze oka˙ze si˛e ona zupełna, ale te˙z nikt zapewne nie spodziewał si˛e, ˙ze oka˙ze si˛e

ona tak słaba. Dowody niezale˙zno´sci przeprowadzone metod ˛

a Cohena pokazuj ˛

˙ze — w odró˙znieniu od arytmetyki liczb naturalnych — nie usuniemy niezupeł-

no´sci wzmacniaj ˛

ac reguły wnioskowania np. przez przyj˛ecie tzw. reguły ω. Niezu-

pełno´s´c aksjomatycznej teorii mnogo´sci porówna´c mo˙zna raczej do niezupełno´sci
teorii grup lub ciał lub podobnych teorii algebraicznych. Nikt nie dziwi si˛e, ˙ze
te teorie s ˛

a niezupełne. Ich aksjomatyki były od pocz ˛

atku sformułowane tak, by

istniały dla nich ró˙znorodne modele. W przypadku aksjomatów teorii mnogo´sci
intencja była odmienna, ale wyniki s ˛

a niemal takie same.

Istniej ˛

a próby oparcia teorii mnogo´sci (i wielu innych teorii matematycznych) na

logice drugiego rz˛edu. Wydaje mi si˛e, ˙ze próby te jakkolwiek mog ˛

a przynie´s´c cie-

kawe rezultaty formalne, nie doprowadz ˛

a do wyja´snienia podstaw teorii mnogo´sci.

W logice drugiego rz˛edu wyst˛epuje bowiem poj˛ecie dowolnej własno´sci. Reguły
wnioskowania i aksjomaty logiki drugiego rz˛edu maj ˛

a charakteryzowa´c to poj˛e-

cie. Otó˙z jest jasne, ˙ze poj˛ecie to w równym stopniu domaga si˛e sprecyzowania,
jak poj˛ecie zbioru. Poniewa˙z matematycy z zasady dopuszczaj ˛

a tylko własno´sci

ekstensjonalne, wi˛ec nie ma ˙zadnej ró˙znicy mi˛edzy poj˛eciem zbioru a poj˛eciem
własno´sci rozpatrywanym w logice drugiego rz˛edu. W ten sposób opieraj ˛

ac teori˛e

mnogo´sci na logice drugiego rz˛edu nie wyja´sniamy poj˛ecia zbioru, lecz sprowa-
dzamy je do innego, w zasadzie mu równowa˙znego poj˛ecia.

Formuły logiki pierwszego rz˛edu L

ωω

kodowa´c mo˙zna liczbami naturalnymi lub,

co na jedno wychodzi, zbiorami dziedzicznie sko´nczonymi, tj. elementami zbioru H(ω).
Z kolei, formuły logiki L

kodowa´c mo˙zna elementami zbioru H(ω

), tj. zbio-

rami dziedzicznie przeliczalnymi. Tak˙ze dowody w L

kodowa´c mo˙zna elementami

H(ω

Dowody w logice L

maj ˛

a długo´s´c przeliczaln ˛

a. Mo˙zna jednak poda´c przykład

zbioru zda´n Γ oraz zdania σ z tego j˛ezyka takich, ˙ze Γ |= σ, ale nie istnieje dowód σ z
Γ w L

. Zbiór Γ mo˙zna dobra´c w ten sposób, aby był on Σ

na H(ω

Zbiór H(ω

) jest domkni˛ety na tworzenie przeliczalnych podzbiorów oraz ci ˛

agów.

Jednak fakt wspomniany w poprzednim akapicie wskazuje i˙z, mówi ˛

ac w uproszczeniu,

H(ω

) nie jest domkni˛ety ze wzgl˛edu na operacj˛e odpowiadaj ˛

ac ˛

a kodowaniu dowodów

z dowolnych Σ

na H(ω

) zbiorów formuł. Naturalne jest w tej sytuacji poszukiwanie

takich zbiorów A zast˛epuj ˛

acych H(ω

), które byłyby domkni˛ete na operacje odpowia-

daj ˛

ace kodowaniom dowodów w A oraz rozwa˙zanie tylko takich formuł, które maj ˛

kody w A. Była to jedna z motywacji do rozpatrywania tzw. dopuszczalnych fragmen-
tów L

logiki L

Barwise odkrył, ˙ze istniej ˛

a przeliczalne zbiory (admissible sets) A ⊆ H(ω

), które

spełniaj ˛

a powy˙zsze warunki. S ˛

a to wi˛ec takie uogólnienia zbiorów dziedzicznie sko´n-

czonych, na których (jako na zbiorach kodów formuł) mo˙zliwe i sensowne jest upra-
wianie (uogólnionej) teorii rekursji oraz teorii dowodu. Udowodnił tak˙ze swoje zna-
mienite twierdzenie o zwarto´sci: je´sli A jest przeliczalnym zbiorem dopuszczalnym, to
ka˙zdy zbiór formuł j˛ezyka L

b˛ed ˛

acy Σ

na A, którego ka˙zdy podzbiór (b˛ed ˛

acy jedno-

cze´snie elementem A) ma model, sam równie˙z ma model. Twierdzenie Barwise’a ma
mnogie zastosowania, m.in. pozwala np. udowodni´c, ˙ze ka˙zdy przeliczalny przechodni
model dla ZFC ma wła´sciwe rozszerzenie ko´ncowe. Prace Barwise’a to swego rodzaju
unifikacja rozwa˙za´n w teorii modeli, teorii rekursji oraz teorii mnogo´sci.

Szczególnie przydatna dla bada´n zbiorów dopuszczalnych okazała si˛e wersja teorii

mnogo´sci KP zaproponowana przez Kripke’go i Platka w połowie lat sze´s´cdziesi ˛

tych XX wieku. Jest ona teori ˛

a elementarn ˛

a, ze stał ˛

a pozalogiczn ˛

a ∈, b˛ed ˛

ac ˛

a pew-

nym osłabieniem teorii mnogo´sci Zermelo-Fraenkla. Nie ma w niej aksjomatu zbioru
pot˛egowego, a szczególn ˛

a rol˛e pełni ˛

a schematy aksjomatów ∆

-separation

oraz ∆

collection

(odpowiedniki schematów aksjomatów wyró˙zniania i zast˛epowania), w któ-

rych wyst˛epuj ˛

a formuły klasy ∆

. Zbiory przechodnie A takie, ˙ze (A, ∈) jest modelem

KP nazywane s ˛

a zbiorami dopuszczalnymi (admissible sets). Rozwa˙za si˛e tak˙ze teori˛e

KPU, czyli teori˛e KP z atomami.

Uwagi ko ´ncowe

Powy˙zsze notatki maj ˛

a charakter kompilacyjny. Przygotowano je tak˙ze z my´sl ˛

o pracownikach Zakładu Logiki Stosowanej UAM, dla ułatwienia im wykonywania
posługi dydaktycznej w zakresie logiki. Korzystali´smy m.in. z nast˛epuj ˛

acych ´zró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´sci. Studia Logica 20, 99–116.

• Pogorzelski, W.A. 1975. Klasyczny rachunek zda´n. Zarys teorii. Pa´nstwowe Wy-

dawnictwo Naukowe, Warszawa.

• Pogorzelski, W.A. 1981. Klasyczny rachunek kwantyfikatorów. Zarys teorii. Pa´n-

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 ˛

a z tej pracy.]

• Rasiowa, H., Sikorski, R. 1963. The mathematics of metamathematics. Pa´nstwowe

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.

• 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´n znale´z´c mo˙zna w wymienionych

wy˙zej pracach. Na razie nie ma monografii w j˛ezyku polskim, która przedstawiałaby
w sposób systematyczny którykolwiek ze wspomnianych wy˙zej paradygmatów meta-
logiki (algebraiczny i semantyczny).

∗ ∗ ∗

Postawmy na zako´nczenie tych notatek kilka przykładowych pyta´n, na które ma

próbowa´c odpowiedzie´c przygotowywana monografia:

1. Czy mo˙zliwa jest unifikacja obu wspomnianych paradygmatów?

2. Jakie ewentualne korzy´sci mogłaby przynie´s´c?

3. Jakie s ˛

a zwi ˛

azki mi˛edzy matematycznymi podstawami metalogiki a czynionymi

w metalogice zało˙zeniami filozoficznymi?

4. Jakie s ˛

a inspiracje/motywacje dla tworzenia nowych poj˛e´c metalogicznych?

5. Jaki jest status takich poj˛e´c, jak np.: stała logiczna w obu paradygmatach?

Nie podamy w tych notatkach odpowiedzi na powy˙zsze pytania. Ograniczymy si˛e

jedynie do kilku wskazówek. Nie s ˛

a to przy tym uwagi podane w jakikolwiek systema-

tyczny sposób, maj ˛

a one na razie charakter zebranych ad hoc konstatacji.

1. Paradygmat algebraiczny jest rozwini˛ety w przypadku rachunków zdaniowych.

Z kolei, paradygmat nazwany tu semantycznym, za punkt wyj´scia bierze j˛ezyki
pierwszego rz˛edu. Oczywi´scie, paradygmat algebraiczny mo˙ze by´c stosowany
tak˙ze w przypadku j˛ezyków pierwszego rz˛edu, jak pokazuje np. prezentacja tej
problematyki w The mathematics of metamathematics. Dla wła´sciwego algebra-
icznego uj˛ecia systemów logicznych z kwantyfikatorami potrzebujemy jednak
algebr (np. algebr Boole’a) z niesko´nczonymi operacjami. Wykorzystywane s ˛

w takich uj˛eciach np. algebry cylindryczne lub algebry kwantyfikatorowe.

Mo˙zna si˛e zastanawia´c, jakie operacje algebraiczne wyznaczane s ˛

a poprzez po-

rz ˛

adek w klasie logik abstrakcyjnych (w rozumieniu punktu drugiego tych nota-

tek).

2. W paradygmacie algebraicznym wychodzimy od operacji konsekwencji, w usta-

lonym j˛ezyku. Reprezentacje semantyczne (semantyka matrycowa) wyznaczone
s ˛

a w du˙zym stopniu przez algebr˛e tego j˛ezyka. Z kolei, w paradygmacie nazy-

wanym tu semantycznym punktem wyj´scia jest (aksjomatycznie charakteryzo-
wana) relacja spełniania. Status formuł (i zda´n) jest tu inny ni˙z w paradygmacie
algebraicznym: zdaniom logik abstrakcyjnych odpowiadaj ˛

a klasy struktur rela-

cyjnych (modeli).

Mówi ˛

ac Humanistycznie, gł˛eboko m˛etnie, unifikacja obu paradygmatów mia-

łaby na celu wykrycie (oraz wykorzystanie) ewentualnych warunków zgodno´sci
mi˛edzy: przej´sciem od operacji konsekwencji do semantyki (w paradygmacie
algebraicznym), a przej´sciem od relacji spełniania do operacji konsekwencji (w
paradygmacie semantycznym).

3. To bardzo trudne pytanie. Zwykle w charakterze przykładu zwi ˛

azków mi˛edzy

czynionymi w logice (oraz metalogice) zało˙zeniami filozoficznymi a wykorzy-
stywan ˛

a na tym obszarze matematyczn ˛

a aparatur ˛

a poj˛eciow ˛

a podaje si˛e zale˙zno-

´sci ł ˛

acz ˛

ace intuicjonizm (oraz ró˙zne wersje konstruktywizmu) z wybranymi dla

intuicjonizmu strukturami matematycznymi (algebraicznymi, topologicznymi,
itd.), w odró˙znieniu od stosownej reprezentacji matematycznej dla logiki kla-
sycznej.

Ju˙z sama matematyczna kodyfikacja metalogiki (w ka˙zdym z omówionych wy-

˙zej paradygmatów) implikuje przyj˛ecie okre´slonego stanowiska filozoficznego.

Dla przykładu, trudno sobie wyobrazi´c, aby istniały rozumne powody dla upra-
wiania parakonsystentnej metalogiki (cho´c systemy logiki parakonsystentnej mo-
g ˛

a mie´c wa˙zkie aplikacje).

Osobnym problemem jest np. dopuszczanie (lub nie) mo˙zliwo´sci stosowania w
metalogice rozumowa´n nieefektywnych, np. u˙zywanie aksjomatu wyboru, le-
matu Königa, ró˙znych form aksjomatu wyró˙zniania.

4. Na Seminarium Zakładu Logiki Stosowanej UAM mówili´smy ju˙z o problema-

tyce dotycz ˛

acej wyłaniania si˛e poj˛e´c metalogicznych, takich jak np.: pełno´s´c,

ró˙zne rodzaje zupełno´sci, kategoryczno´s´c, zwarto´s´c. Wspominali´smy np. o roz-
dzieleniu (pocz ˛

atkowo uto˙zsamianych) poj˛e´c odpowiadaj ˛

acych, w dzisiejszej

terminologii, kategoryczno´sci oraz zupełno´sci. W tym kontek´scie warto rów-
nie˙z zwróci´c uwag˛e np. na rol˛e niektórych twierdze´n 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 ˛

acego, ˙ze nie istnieje charakterystyka stałych logicznych lo-

giki klasycznej, spełniaj ˛

aca pewne naturalne wymogi. Jak widzieli´smy, dla lo-

giki intuicjonistycznej taka charakterystyka istnieje. W tym kontek´scie wa˙zne s ˛

te˙z uwagi Pogorzelskiego i Wojtylaka dotycz ˛

ace mo˙zliwo´sci uzyskania po˙z ˛

ada-

nych charakterystyk stałych logicznych logiki klasycznej za cen˛e rozszerzenia
rozumienia poj˛ecia operacji konsekwencji.

Wnioskiem z twierdze´n Lindströma jest m.in. to, ˙ze klasyczna logika pierwszego
rz˛edu jest maksymaln ˛

a logik ˛

a (regularn ˛

a!), która nie odró˙znia mocy niesko´nczo-

nych i która jest zwarta. Czy z tego mamy tak˙ze jakiekolwiek wnioski na temat
stałych logicznych (logiki pierwszego rz˛edu)?