Operator konsekwencji

Operator konsekwencji – pojęcie wprowadzone do logiki przez Alfreda Tarskiego. Motywacją dla jego wprowadzenia była formalizacja pojęcia konsekwencji określonego zbioru przesłanek.

Definicja

Niech $E$ będzie dowolnym zbiorem. Operatorem konsekwencji w zbiorze $E$ jest funkcja $𝐂𝐧:𝒫(E)\to 𝒫(E)$ spełniająca warunki:

Szablon:Wzór

Szablon:Wzór

Szablon:Wzór

dla $X,Y\subseteq E,$

przy czym Szablon:LinkWzór i Szablon:LinkWzór implikują, że

Szablon:Wzór

Co więcej, warunki Szablon:LinkWzór – Szablon:LinkWzór, równoważne są warunkowi:

Szablon:Wzór

Zbiory sprzeczne

Zbiór $X\subseteq E$ jest $𝐂𝐧$-sprzeczny, jeśli

$𝐂𝐧(X)=E$

Zbiór, który nie jest $𝐂𝐧$-sprzeczny, jest $𝐂𝐧$-niesprzeczny.

Teorie, zupełność

Punkty stałe operatora konsekwencji nazywa się czasem jego teoriami.

Teoria $𝐂𝐧$-zupełna, to maksymalna teoria $𝐂𝐧$-niesprzeczna:

$X\in 𝐂𝐦𝐩𝐥(𝐂𝐧)\iff X=𝐂𝐧(X)\ne E\wedge \underset{Y⊋X}{\bigwedge }𝐂𝐧(Y)=E$

Uwaga.

Rodzina ${𝐓𝐡}_{𝐂𝐧}$ wszystkich $𝐂𝐧$-teorii z działaniami

$X\sqcap Y=X\cap Y\text{i}X\bigsqcup Y=𝐂𝐧(X\cup Y),X,Y\in {𝐓𝐡}_{𝐂𝐧}$

jest kratą zupełną.

dowód.

1. Jeśli $X_j,j\in J,$ są teoriami, to

$𝐂𝐧(\bigcap _{j\in J}{X}_j)\subseteq \bigcap _{j\in J}𝐂𝐧(X_j)=\bigcap _{j\in J}{X}_j\subseteq 𝐂𝐧\left(\bigcap _{j\in J}{X}_j\right).$

W szczególności część wspólna dwóch teorii jest teorią, czyli w rodzinie teorii zbiór $X\cap Y$ jest kresem dolnym pary teorii $X\text{i}Y.$ Aby pokazać, że $𝐂𝐧(X\cup Y)$ jest kresem górnym pary teorii $X\text{i}Y,$ niech $Z$ będzie teorią ograniczającą obie te teorie z góry. Wówczas $𝐂𝐧(X\cup Y)\subseteq 𝐂𝐧(Z)=Z,$ co kończy dowód.

2. Zupełność. Jeśli $X_j,j\in J,$ są teoriami, to $\bigcap _{j\in J}{X}_j={𝐢𝐧𝐟}_{j\in J}{X}_j$ oraz $𝐂𝐧\left(\bigcup _{j\in J}{X}_j\right)={𝐬𝐮𝐩}_{j\in J}{X}_j.◻$

Krata ${𝐓𝐡}_{𝐂𝐧}$ nie musi być rozdzielna.

Zwartość

Operator konsekwencji jest zwarty, jeśli każdy zbiór $𝐂𝐧$-sprzeczny zawiera skończony $𝐂𝐧$-sprzeczny podzbiór.

Twierdzenia Lindenbauma

Dla zwartych operatorów konsekwencji zachodzi następujące twierdzenie:

Twierdzenie (Lindenbaum)

Załóżmy, że $𝐂𝐧$ jest zwarta. Jeśli $X$ jest niesprzeczne, to istnieje zupełna teoria zupełna $X^{\star }$ zawierająca $X.$

Znane także w nieco ogólniejszej wersji pod postacią:

Twierdzenie (relatywne tw. Lindenbauma)

Niech $X$ będzie teorią i niech $e\in ̸X$ będzie takie, że dla jakiegokolwiek $Y$ z tego, że $e\in 𝐂𝐧(Y)$ wynika, że $e\in 𝐂𝐧(Y_0),$ dla pewnego skończonego $Y_0\subseteq Y.$ Wówczas istnieje teoria $X^{\star }$ zawierająca $X,$ dla której $e\in 𝐂𝐧(X^{\star }\cup \{c\})$ o ile tylko $c\in ̸X^{\star }.$

Oba twierdzenia łatwo się dowodzi z Lematu Kuratowskiego-Zorna. Okazuje się jednak, że są one równoważne Pewnikowi Wyboru.

Niech bowiem $𝒜$ będzie parami rozłączną niepustą rodziną zbiorów niepustych, niech $E=\bigcup 𝒜$ i niech $𝐂𝐧(X)=\{\begin{array}{cc}X,& \text{ jeśli }|A\cap X|⩽1\text{ dla }A\in 𝒜\\ E,& \text{ w przc. wyp.}\end{array}.$ $𝐂𝐧(X)$ jest zwarty i $\varnothing$ jest $𝐂𝐧$-niesprzeczne. Istnieje zatem $𝐂𝐧$-zupełna teoria $X^{\star }.$ $\mathrm{\#}(X^{\star }\cap A)⩽2,A\in 𝒜.$ Gdyby dla pewnego $A\in 𝒜$ przekrój $X^{\star }\cap A$ był pusty, to zbiór $X^{\star }\cup \{a\}$ byłby niesprzecznym rozszerzeniem zbioru $X^{\star },$ co jest niemożliwe.

To wystarczy, bowiem pierwsze z twierdzeń Lindenbauma wynika z twierdzenia drugiego.

Finitarność

Operator konsekwencji jest finitarny, jeśli

$e\in 𝐂𝐧(X)\Rightarrow \underset{X_0\subseteq X}{\bigvee }(X_0\text{- skończony}\wedge e\in 𝐂𝐧(X_0))$

Uwaga.

Finitarny operator konsekwencji ze skończonym zbiorem sprzecznym jest zwarty.

Dowód.

Niech $X^{\star }=\{e_1,\dots ,e_n\}$ będzie skończonym zbiorem sprzecznym i niech dany będzie dowolny sprzeczny $X.$ Wówczas $e_1,\dots ,e_n\in E=𝐂𝐧(X),$ skąd z finitarności, istnieją $X_1,\dots ,X_n\subseteq X,$ dla których $e_1\in 𝐂𝐧(X_1),\dots ,e_n\in 𝐂𝐧(X_n).$ Wówczas jednak, $X_0=X_1\cup \dots \cup X_n\subseteq X$ jest sprzeczny.

$◻$

Uwaga ta jest o tyle istotna, że zazwyczaj rozpatrywane operatory konsekwencji są finitarne i mają wręcz jedno-, góra dwuelementowe zbiory sprzeczne.

W niektórych przypadkach, istnieje operacja $N:E\to E$ o tej własności, że

$e\in 𝐂𝐧(X)\iff 𝐂𝐧(X\cup \{Ne\})e\in E,X\subseteq E.$

Wówczas zachodzi:

Fakt. Operator $𝐂𝐧$ jest finitarny wtedy i tylko wtedy, gdy jest zwarty.

Pokazać jedynie trzeba, że jeśli operator ten jest finitarny, to jest skończony. Niech zatem $e\in 𝐂𝐧(X).$ Wówczas $𝐂𝐧(X\cup \{Ne\})$ jest sprzeczny. Istnieje zatem skończony $X_0\subseteq X,$ dla którego $𝐂𝐧(X_0\cup \{Ne\})$ jest sprzeczny. To jednak znaczy, że $e\in 𝐂𝐧(X_0),$ co kończy dowód.

Strukturalność

Jeśli $E$ jest zbiorem formuł pewnego języka zdaniowego, to operator konsekwencji $𝐂𝐧$ jest strukturalny, jeśli dla dowolnego homomorfizmu $h$ języka zachodzi:

$e\in 𝐂𝐧(X)\Rightarrow h(e)\in 𝐂𝐧(h\stackrel{}{`}\stackrel{}{`}X),$ dla $e\in E,X\subseteq E.$

Komentarze

Z każdym systemem formalnym $𝔖$ związany jest operator konsekwencji ${𝐂𝐧}_{𝔖}$ (zob. systemów formalnych). Z drugiej strony, mając operator konsekwencji $𝐂𝐧$ w zbiorze $E,$ można rozważać system formalny ${𝔖}_{𝐂𝐧}=⟨E,\{{⊢}_{𝐂𝐧}\},𝐂𝐧(\varnothing )⟩,$ gdzie ${⊢}_{𝐂𝐧}=\{⟨\mathrm{\Pi },e⟩:e\in 𝐂𝐧(\mathrm{\Pi })\}.$ Wówczas ${𝐂𝐧}_{({𝔖}_{𝐂𝐧})}=𝐂𝐧.$ Ponadto, wychodząc od systemu formalnego $𝔖$ i następnie konstruując w wyżej wymieniony sposób system ${𝔖}^{\star }$ dla ${𝐂𝐧}_{𝔖},$ okaże się, że systemy $𝔖$ i ${𝔖}^{\star }$ są równoważne. Można powiedzieć nawet więcej: systemy formalne są równoważne wtedy i tylko wtedy, gdy wyznaczają te same operatory konsekwencji.

Zobacz też

• rachunek zdaniowy
• system formalny

Bibliografia

• M.Omyła, Zarys Logiki Niefregowskiej, PWN, Warszawa, 1986.
• W.A.Pogorzelski, Elementarny Słownik Logiki Formalnej, Rozprawy Uniwersytetu Warszawskiego, Białystok, 1989