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

  1. \(\Delta\) ma wyłącznie skończone modele.
  2. \(\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.

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

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.

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.

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}.\)

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.

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.

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.

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\)?

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.