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