Logika dla informatyków/Ćwiczenia 8

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

1. Wskazać przykład takiego zbioru $\mathrm{\Delta }$ zdań logiki pierwszego rzędu,że każde dwa jego \textit{przeliczalne} modele są izomorficzne, aleistnieją dwa \textit{nieprzeliczalne}, nieizomorficzne ze soba modelezbioru $\mathrm{\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 $\mathrm{\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 $\mathrm{\Sigma }$ będzie skończoną sygnaturą. Udowodnić, że dlakażdego zbioru zdań $\mathrm{\Delta }$ nad $\mathrm{\Sigma },$ następujące dwa warunkisą równoważne
   • $\mathrm{\Delta }$ ma wyłącznie skończone modele.
   • $\mathrm{\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 ${𝒜}$ struktur nad sygnaturą$\mathrm{\Sigma }$ jest aksjomatyzowalna pewnym zbiorem zdań logiki pierwszegorzędu, oraz jej dopełnienie składające sięze struktur sygnatury $\mathrm{\Sigma },$ ktore nie należą do ${𝒜}$ 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 $\mathrm{\Delta }$, a druga przez ${\mathrm{\Delta }}^{\prime },$ ale żaden skończony podzbiór$\mathrm{\Delta }$ nie jest aksjomatyzacją ${𝒜}.$ Pokazać, że$\mathrm{\Delta }\cup {\mathrm{\Delta }}^{\prime }$ spełnia założenia twierdzenia o zwartości.

\item Pokazać następujące twierdzenie Robinsona: Jeśli$\mathrm{\Delta },{\mathrm{\Delta }}^{\prime }$ są spełnialnymi zbiorami zdań nad pewną sygnaturą$\mathrm{\Sigma },$ zaś $\mathrm{\Delta }\cup {\mathrm{\Delta }}^{\prime }$ 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$\mathrm{\Delta }\cup {\mathrm{\Delta }}^{\prime }$ 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 $\mathrm{\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 $\mathrm{\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}