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.

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

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