Informatyka MIMUW

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ść.

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

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