Logika dla informatyków/Ćwiczenia 8

Ćwiczenie 1

Wskazać przykład takiego zbioru $\mathrm{\Delta }$ zdań logiki pierwszego rzędu, że każde dwa jego przeliczalne modele są izomorficzne, ale istnieją dwa nieprzeliczalne, nieizomorficzne ze sobą modele zbioru $\mathrm{\Delta }.$

Ćwiczenie 2

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

Ćwiczenie 3

Niech $\mathrm{\Sigma }$ będzie skończoną sygnaturą. Udowodnić, że dla każdego zbioru zdań $\mathrm{\Delta }$ nad $\mathrm{\Sigma },$ następujące dwa warunki są równoważne

• $\mathrm{\Delta }$ ma wyłącznie skończone modele.
• $\mathrm{\Delta }$ ma z dokładnością do izomorfizmu skończenie wiele modeli.

Ćwiczenie 4

Udowodnić, że klasa wszystkich struktur izomorficznych zestrukturą postaci $\mathfrak{𝔄}=<{𝒫}(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 ${𝒜}$ struktur nad sygnaturą$\mathrm{\Sigma }$ jest aksjomatyzowalna pewnym zbiorem zdań logiki pierwszego rzędu, oraz jej dopełnienie składające się ze struktur sygnatury $\mathrm{\Sigma }$, które nie należą do ${𝒜}$ 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 $\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.

Ćwiczenie 6

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 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 $\mathrm{\Delta }\cup {\mathrm{\Delta }}^{\prime }$ 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 $\mathrm{\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 $\mathrm{\Delta }\models \psi ,$ to także $Spec(\mathrm{\neg }\psi )$ jest skończony.