Logika dla informatyków/Ćwiczenia 8

Ćwiczenie 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 sobą modele zbioru $\Delta .$

Ćwiczenie 2

Udowodnić, że dla każdej struktury skończonej ${\mathfrak {A}}$ nad skończoną sygnaturą istnieje taki zbiór $\Delta$ zdań pierwszego rzędu,że ${\mathfrak {A}}\models \Delta$ i dla każdej struktury ${\mathfrak {B}}\models \Delta$zachodzi ${\mathfrak {B}}\cong {\mathfrak {A}}.$

Ćwiczenie 3

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.

Ćwiczenie 4

Udowodnić, że klasa wszystkich struktur izomorficznych zestrukturą postaci ${\mathfrak {A}}=<{\mathcal {P}}(A),\cup ,\cap ,\subseteq >$, gdzie $\cup ,\cap$ oraz$\subseteq$ są odpowiednio sumą, przecięciem i zawieraniem zbiorów, nie jest aksjomatyzowalna żadnym zbiorem zdań pierwszego rzędu.

Ćwiczenie 5

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

Wskazówka: Założyć, że pierwsza klasa jest aksjomatyzowalna przez $\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.

Ćwiczenie 6

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

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

Ćwiczenie 7

Niech Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle Spec(\var\varphi)} 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ż dla każdego Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \var\varphi\in\Delta} zbiór Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle Spec(\lnot\var\varphi)} jest skończony, oraz jeśli $\Delta \models \psi ,$ to także $Spec(\lnot \psi )$ jest skończony.