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

Adaptując dowód Faktu #qqudowodnić, że struktury Parser nie mógł rozpoznać (błąd składni): {\displaystyle \<\{1-1/n&nbsp;|&nbsp;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 #zwarciig\leftrightarrowwi. )

1. Niech $R$ będzie jednoargumentowym symbolem relacyjnym.

Udowodnić, że klasa wszystkich takich struktur </math>\mathfrak A=\langle A,R\rangle</math>, że $|R|=|A-R|$, nie jest aksjomatyzowalna żadnym zbiorem zdań pierwszego rzędu.

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

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

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

Dane są dwie struktury relacyjne </math>\mathfrak A=\langle U,R^\mathfrak A\rangle</math> i $\mathfrak{𝔅}=⟨U,R^{\mathfrak{𝔅}}⟩$ nad sygnaturą złożoną z jednego dwuargumentowego symbolu relacyjnego. Ich nośnikiem jest $U=\{1,2,\dots ,15\}$, relacja $R^{\mathfrak{𝔄}}(x,y)$ zachodzi \wtw, gdy $x|y$, a relacja $R^{\mathfrak{𝔅}}(x,y)$ \wtw, gdy $x\equiv y(\mathrm{mod}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.}

1. Dane są dwie sześcioelementowe

struktury relacyjne $\mathfrak{𝔄}$ i $\mathfrak{𝔅}$ nad sygnaturą złożoną z jednego dwuargumentowego symbolu relacyjnego. Struktury są narysowane poniżej jako grafy skierowane:

Parser nie mógł rozpoznać (nieznana funkcja „\begi”): {\displaystyle \begi\prooftree array \justifies c|c \using \textrm{(W )}\endprooftree \xymatrix { *{\ast} \ar@{<->}[r] \ar@{<->}[d] \ar@{<->}[dr] & *{\ast} \ar@{<->}[d] \ar@{<->}[l] \ar@{<->}[dl] & *{\ast} & \\ *{\ast} \ar@{<->}[r] & *{\ast} & *{\ast} & *{\relax} }&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; \xymatrix { *{\ast} \ar@{<->}[d] \ar@{<->}[dr] & *{\ast} & *{\ast} & \\ *{\ast} \ar@{<->}[r] & *{\ast} & *{\ast} & *{\relax} } \end{array} }

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

\end{small}