Logika dla informatyków/Ćwiczenia 4

Linek z wykładu 8 do cwiczenia 4. Nazwa linku: "c"

Ćwiczenie 1

Wykazać, że dla dostatecznie dużych $q$ istnieje zdanie o randze kwantyfikatorowej $q$ definiujące porządek liniowy o mocy $2^{q}.$

Ćwiczenie 2

Adaptując dowód Faktu #qqudowodnić, że struktury Parser nie mógł rozpoznać (błąd składni): {\displaystyle \<\{1-1/n | n=1,2,\dots\},\leq\>} oraz Parser nie mógł rozpoznać (błąd składni): {\displaystyle \<\bigcup_{n=1}^\infty\{1-1/n,1+1/n,3-1/n\},\leq\>} , gdzie $\leq$ jest w obu wypadkach standardowym porządkiem liczb wymiernych, są elementarnie równoważne.

Wywnioskować stąd, że pojęcie dobrego porządku nie jest wyrażalne w logice pierwszego rzędu. (Zupełnie inny dowód tego faktu poznamy w Rozdziale 8.

Ćwiczenie 3

Niech $R$ będzie jednoargumentowym symbolem relacyjnym. Udowodnić, że klasa wszystkich takich struktur ${\mathfrak {A}}=\langle A,R\rangle$, że $|R|=|A-R|$, nie jest aksjomatyzowalna żadnym zbiorem zdań pierwszego rzędu.

Ćwiczenie 4

Udowodnić, że klasa wszystkich (skończonych lub nieskończonych ) grafów ${\mathfrak {A}}=\langle A,E\rangle ,$ w których istnieją dwa wierzchołki o równych sobie, skończonych stopniach, nie jest aksjomatyzowalna żadnym zdaniem pierwszego rzędu.

Ćwiczenie 5

Udowodnić, że klasa wszystkich (skończonych lub nieskończonych) grafów ${\mathfrak {A}}=\langle A,E\rangle ,$ których każdy skończony podgraf jest planarny, nie jest aksjomatyzowalna żadnym zdaniem pierwszego rzędu.

Ćwiczenie 6

Pokazać, że klasa wszystkich relacji równoważności, których wszystkie skończone klasy abstrakcji mają parzystą moc, nie jest aksjomatyzowalna żadnym zdaniem pierwszego rzędu.

Ćwiczenie 7

Dane są dwie struktury relacyjne ${\mathfrak {A}}=\langle U,R^{\mathfrak {A}}\rangle$ i ${\mathfrak {B}}=\langle U,R^{\mathfrak {B}}\rangle$ nad sygnaturą złożoną z jednego dwuargumentowego symbolu relacyjnego. Ich nośnikiem jest $U=\{1,2,\dots ,15\}$, relacja $R^{\mathfrak {A}}(x,y)$ zachodzi wtedy i tylko wtedy, gdy $x|y$, a relacja $R^{\mathfrak {B}}(x,y)$ \wtw, gdy $x\equiv y{\pmod {2}}.$

Ustalić, jaką minimalną rangę kwantyfikatorową ma zdanie Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \var\varphi} takie, że Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \mathfrak A\models\var\varphi} i Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \mathfrak B\not\models\var\varphi.}

Ćwiczenie 8

Dane są dwie sześcioelementowe struktury relacyjne ${\mathfrak {A}}$ i ${\mathfrak {B}}$ nad sygnaturą złożoną z jednego dwuargumentowego symbolu relacyjnego. Struktury są narysowane poniżej jako grafy skierowane:

Ustalić, jaką minimalną rangę kwantyfikatorową ma zdanie Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \var\varphi} takie, że Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \mathfrak A\models\var\varphi} i Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \mathfrak B\not\models\var\varphi.}