Logika dla informatyków/Ćwiczenia 8

\subsection*{Ćwiczenia}\begin{small}

1. Wskazać przykład takiego zbioru $\Delta$ zdań logiki pierwszego rzędu,że każde dwa jego \textit{przeliczalne} modele są izomorficzne, aleistnieją dwa \textit{nieprzeliczalne}, nieizomorficzne ze soba modelezbioru $\Delta .$
2. Udowodnić, że dla każdej struktury skończonej Parser nie mógł rozpoznać (nieznana funkcja „\strA”): {\displaystyle \strA} nad skończonąsygnaturą istnieje taki zbiór $\Delta$ zdań pierwszego rzędu,że Parser nie mógł rozpoznać (nieznana funkcja „\strA”): {\displaystyle \strA\models\Delta} i dla każdej struktury Parser nie mógł rozpoznać (nieznana funkcja „\strB”): {\displaystyle \strB\models\Delta} zachodzi Parser nie mógł rozpoznać (nieznana funkcja „\strB”): {\displaystyle \strB\cong\strA.}

1. Niech $\Sigma$ będzie skończoną sygnaturą. Udowodnić, że dlakażdego zbioru zdań $\Delta$ nad $\Sigma ,$ następujące dwa warunkisą równoważne
   • $\Delta$ ma wyłącznie skończone modele.
   • $\Delta$ ma z dokładnością do izomorfizmu skończenie wiele modeli.

\item Udowodnić, że klasa wszystkich struktur izomorficznych zestrukturą postaci \mbox{</math>\strA=\langle\mathcal{P}\begin{eqnarray*}A\end{eqnarray*},\cup,\cap,\subseteq\rangle</math>}, gdzie $\cup ,\cap$ oraz$\subseteq$ są odpowiednio sumą, przecięciem i zawieraniem zbiorów,nie jest aksjomatyzowalna żadnym zbiorem zdań pierwszego rzędu.

\item Pokazać, że jeśli klasa ${\mathcal {A}}$ struktur nad sygnaturą$\Sigma$ jest aksjomatyzowalna pewnym zbiorem zdań logiki pierwszegorzędu, oraz jej dopełnienie składające sięze struktur sygnatury $\Sigma ,$ ktore nie należą do ${\mathcal {A}}$ teżjest aksjomatyzowalne, to każda z tych klas jest w istocie aksjomatyzowalna\textit{jednym} zdaniem pierwszego rzędu.

{\em Wskazówka:\/} Założyć, że pierwsza klasa jest aksjomatyzowalnaprzez $\Delta$, a druga przez $\Delta ',$ ale żaden skończony podzbiór$\Delta$ nie jest aksjomatyzacją ${\mathcal {A}}.$ Pokazać, że$\Delta \cup \Delta '$ spełnia założenia twierdzenia o zwartości.

\item 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 istniejetakie zdanie Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \var\varphi} , że Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \Delta\models\var\varphi} orazParser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \Delta'\models\lnot\var\varphi.}

{\em Wskazówka:\/} Pokazać, że jeśli teza nie zachodzi, to$\Delta \cup \Delta '$ spełnia założenia twierdzenia o zwartości.

\item Niech Parser nie mógł rozpoznać (błąd składni): {\displaystyle Spec\begin{eqnarray*}\var\varphi\end{eqnarray*}} oznacza zbiór mocy wszystkich skończonych modeli formuły Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \var\varphi.} Pokazać, że jeśli $\Delta$ jest takim zbiorem zdań, iż dlakażdego Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \var\varphi\in\Delta} zbiór Parser nie mógł rozpoznać (błąd składni): {\displaystyle Spec\begin{eqnarray*}\lnot\var\varphi\end{eqnarray*}} jest skończony,oraz jeśli $\Delta \models \psi ,$ to także Parser nie mógł rozpoznać (błąd składni): {\displaystyle Spec\begin{eqnarray*}\lnot\psi\end{eqnarray*}} jestskończony.

\end{small}