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 $\le$ 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

{{{3}}}

Ćwiczenie 4

Udowodnić, że klasa wszystkich (skończonych lub nieskończonych ) grafów

$\mathfrak{𝔄}=⟨A,E⟩,$ 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,E⟩,$ 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

{{{3}}}

Ćwiczenie 8

{{{3}}}

\end{small}