Kolokwium 2015/2016

Zadanie 1

Liniowy porządek (ścisły) \(\mathfrak{A}=\langle A, < \rangle\) nazwiemy całkiem niegęstym, jeśli dla każdych dwóch elementów \(x,y\in A\) takich że \(x < y\), istnieje tylko skończenie wiele elementów \(z\in A\) spełniających warunek \(x < z < y\).

Udowodnij, że nie istnieje żaden zbiór \(\Delta\) zdań logiki pierwszego rzędu nad sygnaturą składającą się wyłącznie z symbolu \( < \), taki, że \(\mathfrak{A}\models\Delta\) wtedy i tylko wtedy, gdy \(\mathfrak{A}\) jest całkiem niegęstym porządkiem liniowym.

Szkic rozwiązania

Uwaga ogólna: \(\langle\mathbb{Z}, < \rangle\) jest całkiem niegęstym porządkiem.

Rozwiązanie I.

Przypuśćmy,że \(\Delta\) to żądana aksjomatyzacja. Do sygnatury dodajemy dwie nowe stałe \(c,d\). Niech

\(\bar\Delta=\Delta\cup\{\exists x_1\ldots\exists
x_n\bigwedge_{i\neq j}x_i\neq x_j)\land \bigwedge_{i}c < x_i < d\}\).

Pokazujemy, że \(\bar\Delta\) spełnia założenia twierdzenia o zwartości: niech \(\Delta_0\subseteq\bar\Delta\) będzie dowolny, skończony.

Niech \(N\) to maksymalna liczna kwantyfikatorów w zdaniach z \(\Delta_0\), pochodzących spoza \(\Delta\). Wówczas interpretujemy \(c\) i \(d\) jako dwa elementy \(\langle\mathbb{Z}, < \rangle\) odległe od siebie o więcej niż \(N\), np. \(0\) i \(N+1\). Tak rozszerzony model \(\langle\mathbb{Z}, < \rangle\) spełnia \(\Delta_0\), bo między interpretacjami nowych stałych jest dostatecznie wiele elementów.

Na mocy twierdzenia o zwartości \(\bar\Delta\) ma model. Zawiera on nieskończenie wiele elementów pomiędzy interpretacjami \(c\) i \(d\), czyli nie jest całkiem niegęsty. Sprzeczność.

Rozwiązanie II.

Niech \(\mathfrak{A}=\langle A, < \rangle\) będzie dowolnym całkiem niegęstym porządkiem i niech \(a\in A\). Niech \(d(x,y)\) dla \(x,y\in A\) oznacza \(1+|\{z\in A~|~x < z < y~lub~y < z < x\}|\).

Wówczas \(A=\bigcup_{n\in\mathbb{N}}\{x\in A~|~d(x,a)\leq n\}\). Rzeczywiście, gdyby pewne \(b\in A\) nie należało do zbioru po prawej, to liczba elementów między nim a \(a\) byłaby niekończona, co jest niemożliwe w porządku całkiem niegęstym.

Zatem \(A\) jest zbiorem skończonym lub przeliczalnym, jako przeliczlna suma zbiorów skończonych.

Stąd wynika, że nie istnieje nieprzliczalny porządek całkiem niegęsty, oraz istnieje taki porządek mocy \(\aleph_0\). Tymczasem z twierdzenia Skolema-Loewenheima wynika, że gdyby istniał zbiór zdań \(\Delta\) z treści zadania, to, mając model nieskończony, musiałby mieć także modele nieprzeliczalne. Sprzeczność.

Zadanie 2

Dla danego zdania \(\varphi\) logiki pierwszego rzędu niech \(spec(\varphi)=\{n\in\mathbb{N}~|~\)istnieje model \(\varphi\) mocy \(n\}\).

Dla danego zbioru \(A\subseteq\mathbb{N}\) niech \(A^\Sigma=\{\sum^r_{i=1}a_i~|~r\geq1,~a_1,\ldots,a_r\in A\}.\)

Dla danego zdania \(\varphi,\) skonstruuj zdanie \(\psi\) takie, że \(spec(\psi)=spec(\varphi)^\Sigma.\) Można przy tym założyć, że \(\varphi\) nie zawiera symboli funkcyjnych oraz rozszerzyć sygnaturę.

Szkic rozwiązania

Niech \(E\) będzie nowym symbolem relacji dwuargumentowej oraz \(x\) nową zmienną, dotąd nie występującą w \(\varphi\).

Niech \(\alpha\) będzie koniunkcją wszystkich trzech standardowych aksjomatów, orzekających, że \(E\) jest relacją równoważności.

Napiszemy teraz zdanie \(\psi\) orzekające, że podstruktura indukowana przez każdą z klas abstrakcji \(E\) jest modelem \(\varphi\), co powoduje, że moc każdego skończonego modelu \(\psi\) musi być sumą mocy pewnej skończonej liczby modeli \(\varphi\), oraz, że każda taka suma da się zrealizować jako moc modelu \(\psi\).

Zdanie to ma postać \(\forall x\varphi_{[x]}\), gdzie \(\varphi_{[x]}\) jest zdaniem \(\varphi\) zrelatywizowanym do klasy abstrakcji \(x\). Polega to na zastąpieniu każdej podformuły postaci \(\forall y\,\gamma\) podformułą \(\forall y(E(x,y)\to\gamma)\) oraz każdej podformuły postaci \(\exists y\,\gamma\) podformułą \(\exists y(E(x,y)\land\gamma)\).

Zadanie 3

Zadanie dotyczy klasycznej logiki zdaniowej. Niech \(\Delta,\Gamma\) będą dwoma zbiorami formuł spełniającymi \(\Gamma\models\Delta\). Udowodnij następujące nieskończone rozszerzenie Twierdzenia o interpolacji.

Istnieje zbiór \(\Theta\) taki, który zawiera wyłącznie zmienne zdaniowe, które występują zarówno w \(\Gamma\) jak i w \(\Delta\), oraz spełniający \(\Gamma\models\Theta\) i \(\Theta\models\Delta.\)

Szkic rozwiązania

Rozwiązanie I.

Niech \(\Delta=\{\varphi_1,\varphi_2,\ldots\}\).

Dla każdego \(i\) mamy zatem \(\Gamma\models\varphi_i\). Z twierdzenia o zwartości istnieje skończony podzbiór \(\Gamma_i\subseteq\Gamma\) taki, że \(\Gamma_i\models\varphi_i.\)

\(\bigwedge\Gamma_i\) jest jednym zdaniem i spełnia \(\bigwedge\Gamma_i\models\varphi_i\).

Ze standardowego twierdzenia o interpolacji wynika, że istnieje zdanie \(\vartheta_i\), zawierające tylko wspólne zmienne zdaniowe \(\Gamma_i\) i \(\varphi_i\), dla którego \(\Gamma_i\models\vartheta_i\) i \(\vartheta_i\models\varphi_i\).

Żądanym zbiorem jest \(\Theta=\{\vartheta_1,\vartheta_2,\ldots\}\).

Rozwiązanie II.

Naśladujemy dowód twierdzenia o interpolacji dla pojedynczych formuł spełniających \(\models\varphi\to\psi\). Interpolant był konstruowany przez sekwencję eliminacji zbędnych zmiennych z \(\varphi\), przy czym krok eliminacji zmiennej \(q\) opierał się na tym, że w powyższej sytuacji zachodzą implikacje

\(\models(\varphi[\bot/q]\lor\varphi[\top/q])\to\psi\)
i
\(\models\varphi\to (\varphi[\bot/q]\lor\varphi[\top/q])\).

Zatem krokiem w konstrukcji interpolantu jest zastąpnie \(\varphi\) przez \(\varphi[\bot/q]\lor\varphi[\top/q])\). Ten krok można lekko zmodyfikować, deklarując, że jeśli \(q\) nie występuje w \(\varphi\), to efektem kroku jest niezmienione \(\varphi\), zamiast formalnie wynikającej formuły \(\varphi\lor\varphi\).

Mając do czynienia ze zbiorami, musimy wykonać każdy taki (zmodyfikowany) krok na wszystkich formułach z \(\Gamma\) jednocześnie, oraz musimy wykonać (w pesymistycznym przypadku) nieskończenie wiele takich kroków. Każda z formuł w \(\Gamma\) zawiera jednak tylko skończenie wiele zmiennych, więc po skończenie wielu krokach stabilizuje się, bo późniejsze kroki jej już nie modyfikują. Zatem zbiór \(\Gamma\) po wykonaniu wszystkich nieskończenie wielu kroków jest dobrze zdefiniowany, a rozumowanie identyczne jak w dowodzie zwykłego twierdzenia o interpolacji pokazuje, że otrzymany zbiór jest pożądanym \(\Theta\).