Teoria modeli dla logiki pierwszego rzędu, tw. o zwartości, tw. Skolema-Loewenheima

Zad. 1

Wskazać przykład takiego zbioru \(\Delta\) zdań logiki pierwszego rzędu, że każde dwa jego przeliczalne modele są izomorficzne, ale istnieją dwa nieprzeliczalne, nieizomorficzne ze soba modele zbioru \(\Delta.\)

Zad. 2

Niech \(\Sigma\) będzie skończoną sygnaturą. Udowodnić, że dla każdego zbioru zdań \(\Delta\) nad \(\Sigma,\) następujące dwa warunki są równoważne

\(\Delta\) ma wyłącznie skończone modele.
\(\Delta\) ma z dokładnością do izomorfizmu skończenie wiele modeli.

Zad. 3

Pokazać, że jeśli klasa \(\mathcal{A}\) struktur nad sygnaturą \(\Sigma\) jest aksjomatyzowalna zbiorem zdań logiki pierwszego rzędu i jej dopełnienie \(Mod(\Sigma)\setminus\mathcal{A}\) struktur sygnatury \(\Sigma,\) ktore nie nalezą do \(\mathcal{A},\) też jest aksjomatyzowalne zbiorem zdań logiki pierwszego rzędu, to obie klasy są w istocie aksjomatyzowalne jednym zdaniem logiki pierwszego rzędu.

Wskazówka

Założyć, że pierwsza klasa jest aksjomatyzowalna przez \(\Delta\), a druga przez \(\Delta',\) ale żaden kończony podzbiór \(\Delta\) nie jest aksjomatyzacją \(\mathcal{A}.\) Pokazać, że \(\Delta\cup\Delta'\) spełnia założenia twierdzenia o zwartości.

Zad. 4

Pokazać następujące twierdzenie Robinsona:
Jeśli \(\Delta,\Delta'\) są spełnialnymi zbiorami zdań nad pewną sygnaturą \(\Sigma,\) zaś \(\Delta\cup\Delta'\) nie jest spełnialny, to istnieje takie zdanie \(\varphi\), że \(\Delta\models\varphi\) oraz \(\Delta'\models\lnot\varphi.\)

Wskazówka

Pokazać, że jeśli teza nie zachodzi, to \(\Delta\cup\Delta'\) spełnia założenia twierdzenia o zwartości.

Zad. 5

Niech \(Spec(\varphi)\) oznacza zbiór mocy wszystkich skończonych modeli formuły \(\varphi.\)
Pokazać, że jeśli \(\Delta\) jest takim zbiorem zdań, iż dla każdego \(\varphi\in\Delta\) zbiór \(Spec(\lnot\varphi)\) jest skończony, oraz jeśli \(\Delta\models\psi,\) to także \(Spec(\lnot\psi)\) jest skończony.

Zad. 6

Pokazać, że klasa wszystkich relacji równoważności, które mają skończenie wiele klas abstrakcji, nie jest aksjomatyzowalna.

Rozwiązanie

Przypuśmy, że taki zbiór zdań \(\Delta\) istnieje. Dodajemy do \(\Delta\) zbiór zdań
\(\{\exists x_1\ldots\exists x_n \bigwedge_{i\neq j}\lnot E(x_i,x_j)~|~n\in\mathbb{N}\}\).
Ten nowy zbiór spełnia założenia twierdzenia o zwartości: każdy jego skończony podzbiór jest spełnialny, bo dołączone zdanie \(\exists x_1\ldots\exists x_n \bigwedge_{i\neq j}\lnot E(x_i,x_j)\) orzeka, że relacja równoważności \(E\) ma co najmniej \(n\) klas abstrakcji, więc skończenie wiele takich zdań da się spełnić w strukturze, która ma dostatecznie dużą, skończoną liczbę klas abstrakcji.

Zatem cały zbiór ma model, który oczywiście ma nieskończenie wiele klas abstrakcji - sprzeczność.

Zad. 7

Udowodnić, że klasa wszystkich struktur \(\mathbb{A}=\langle A,E^{\mathbb{A}}\rangle\) nad sygnaturą składającą się z jednego dwuargumentowego symbolu relacyjnego \(E\) i takich, że \(E^{\mathbb{A}}\) jest zbiorem skończonym, nie jest aksjomatyzowalna.

Zad. 8

Pokazać, że klasa wszystkich algebr \(\mathbb{A}=\langle A,f^{\mathbb{A}}\rangle,\) gdzie \(f\) jest symbolem jednoragumentowej funkcji, oraz takich, że \(|\vec{f}(A)|< |A|\) nie jest aksjomatyzowalna.

Rozwiązanie

Przypuśmy, że taki zbiór zdań \(\Delta\) istnieje. Dodajemy do \(\Delta\) zbiór zdań
\(\{\exists x_1\exists x_2\ldots\exists x_{n-1}\exists x_n \bigwedge_{i\neq j}f(x_i)\neq f(x_j)~|~n\in\mathbb{N}\}\).
Ten nowy zbiór spełnia założenia twierdzenia o zwartości: każdy jego skończony podzbiór jest spełnialny, bo skończona liczba dołożonych zdań orzeka, że obraz \(f\) jest co najmniej pewnej skończonej mocy.

Zatem cały zbiór ma model, który oczywiście jest nieskończony. Ze względu na sygnaturę, ma też model przeliczalny \(\mathfrak{A}\), na mocy twierdzenia Skolema-Loewenheima. W \(\mathfrak{A}\) obraz \(f^{\mathfrak{A}}\) jest też przeliczalny, zatem \(\mathfrak{A}\) nie należy do badanej klasy - sprzeczność.

Zad. 9

Udowodnić, że klasa wszystkich struktur \(\mathbb{A}=\langle A,E^{\mathbb{A}}\rangle\) nad sygnaturą składającą się z jednego dwuargumentowego symbolu relacyjnego \(E\) i takich, że \(|\{(a,b)\in A\times A~/~(a,b)\in E^{\mathbb{A}}\}|< |\{(a,b)\in A\times A~/~(a,b)\notin E^{\mathbb{A}}\}|,\) nie jest aksjomatyzowalna.

Zad. 10

Udowodnić, że klasa wszystkich struktur \(\mathbb{A}=\langle A,r^{\mathbb{A}}\rangle,\) gdzie \(r\in\Sigma^{R}_{1}\) oraz takich, że \(|r^{\mathbb{A}}|=|A\setminus r^{\mathbb{A}}|\) nie jest aksjomatyzowalna.

Zad. 11

Udowodnić następujące tw. Hessenberga:
Dla każdej nieskończonej mocy \(\mathfrak{m}\) zachodzi \(\mathfrak{m}^2=\mathfrak{m}.\)

Wskazówka

Napisać zdanie pierwszego rzędu, z którego wynika, że uniwersum modelu jest mocy nie mniejszej niż moc jego kartezjańskiego kwadratu. Pokazać, że zdanie to ma model nieskończony i skorzystać z tw. Skolema-Loewenheima.

Zad. 12

Udowodnić, że klasa wszystkich struktur \(\mathbb{A}=\langle A,r^{\mathbb{A}}\rangle,\) gdzie \(r\in\Sigma^{R}_{1}\) oraz takich, że \(|r^{\mathbb{A}}|=2^{{|A\setminus r^{\mathbb{A}}|}}\) nie jest aksjomatyzowalna.

Zad. 13

Udowodnić, że klasa wszystkich struktur izomorficznych do struktury postaci \(\mathbb{A}=\langle\mathcal{P}(A),\cup^{\mathbb{A}},\cap^{\mathbb{A}},\subseteq^{\mathbb{A}}\rangle,\) gdzie \(\cup^{\mathbb{A}},\cap^{\mathbb{A}}\) oraz \(\subseteq^{\mathbb{A}}\) są odpowiednio prawdziwymi sumą, przecięciem i zawieraniem zbiorów, nie jest aksjomatyzowalna.

Rozwiązanie

W tej klasie są struktury nieskończone, oraz sygnatura jest skończona. Gdyby ta klasa była aksjomatyzowalna zbiorem zdań logiki pierwszego rzędu, to w myśl tw. Skolema-Loewenheima powinna być w niej także struktura przeliczalna. Takiej jednak nie ma.

Zad. 14

Sygnatura składa się z dwuargumentowego symbolu funkcyjnego \(\circ\), jednoargumentowego symbolu funkcyjnego \(inv\) i symbolu stałej \(id\). Model \(\mathfrak{F}\) (ta litera to gotyckie F, w rozwiązaniu można pisać zwykłe F) nad tą sygnaturą nazywamy grupą bijekcji, gdy jego uniwersum stanowi zbiór wszystkich bijekcji \(f:A\to A\) dla pewnego zbioru \(A,\) a operacje mają następujące interpretacje: \(\circ^{\mathfrak{F}}\) to operacja składania funkcji, \(inv^{\mathfrak{F}}\) to operacja brania funkcji odwrotnej, a \(id^{\mathfrak{F}}\) to funkcja indentycznościowa z \(A\) w \(A\).

Udowodnić, że nie istnieje zbiór \(\Gamma\) zdań logiki pierwszego rzędu taki, że \(\mathfrak{B}\models\Gamma\) wtedy i tylko wtedy, gdy \(\mathfrak{B}\) jest izomorficzny do pewnej grupy bijekcji.

Rozwiązanie

Zad. 15

Pokazać, że nie istnieje zdanie \(\varphi\) logiki pierwszego rzędu o tej własności, że dla każdego nieskierowanego (skończonego lub nie) grafu \(\mathfrak{G}\) zachodzi równoważność: \(\mathfrak{G}\models\varphi\) wtw każdy wierzchołek \(\mathfrak{G}\) należy do pewnego (skończonego) cyklu w tym grafie.

Rozwiązanie

Przypuśmy, że taki zbiór zdań \(\Delta\) istnieje. Uzupełniamy sygnaturę o nową stałą \(c\) i dodajemy do \(\Delta\) zbiór zdań
\(\{\lnot\exists x_1\exists x_2\ldots\exists x_{n-1}\exists x_n E(c,x_1)\land E(x_1,x_2)\land E(x_2,x_3)\land\ldots\land E(x_{n-1},x_n)\land E(x_n,c)~|~n\in\mathbb{N}\}\).
Ten nowy zbiór spełnia założenia twierdzenia o zwartości: każdy jego skończony podzbiór jest spełnialny, bo skończona liczba dołożonych zdań orzeka, że \(c\) nie leży na cyklu o kilku skończonych mocach, więc modelem może być skończony cykl o dostatecznie dużej liczbie wierzchołków.
Zatem całość ma model, a to jest sprzeczność, bo w nim \(c\) nie leży na żadnym cyklu.

Zad. 16

Czy dla każdego zbioru zdań \(\Delta\) istnieje minimalny ze względu na zawieranie podzbiór \(\Delta'\subseteq\Delta\) spełniający \(\Delta'\models\Delta\)?

Odpowiedź

NIE

Przykładem takiego zbioru \(\Delta\) jest \(\{\exists x_1\dots x_n \bigwedge_{1\leq i < j \leq n}x_i\neq x_j~:~n\in\mathbb{N}\}.\)

Zad. 17

Czy dla każdego zbioru zdań \(\Delta\) takiego, że \(\Delta\models\varphi\), gdzie \(\varphi\) jest zdaniem, istnieje minimalny ze względu na zawieranie podzbiór \(\Delta'\subseteq\Delta\) spełniający \(\Delta'\models\varphi\)?

Zad. 18

Pokazać, że dla każdego skończonego zbioru zdań \(\Delta\) istnieje podzbiór \(\Delta'\subseteq\Delta\) spełniający \(\Delta'\models\Delta\) oraz niezależny, tzn. dla każdego \(\varphi\in\Delta'\) zachodzi \(\Delta'\setminus\{\varphi\}\not\models\varphi\).

Zad. 19

Niech \(f\) będzie jednoargumentowym symbolem funcji i niech \(\mathcal{A}=\bigcup_{n\in\mathbb{N}}Mod(\forall x\underbrace{f\ldots
f}_n(x)=x).\)

Wykazać, że ani \(\mathcal{A}\) nie można zdefiniować żadnym zbiorem zdań logiki pierwszego rzędu, ani dopełnienia \(\mathcal{A}\) nie można zdefiniować pojedynczym zdaniem logiki pierwszego rzędu.

Informatyka MIMUW