Dwa z zadań są osnute wokół Lematu Koeniga w następującym sformułowaniu:
Założenie: Graf \(\mathfrak{T}\) (gotyckie T) jest nieskończonym drzewem skierowanym, w którym stopień każdego wierzchołka jest skończony.
Teza: W drzewie \(\mathfrak{T}\) istnieje nieskończona ścieżka.
Sformalizuj jednym zdaniem pełnej logiki drugiego rzędu SO założenie Lematu Koeniga: napisz zdanie \(\varphi\) takie, że jeśli graf skierowany \(\mathfrak{T}\models\varphi,\) to \(\mathfrak{T}\) jest nieskończonym drzewem skierowanym, w którym stopień każdego wierzchołka jest skończony.
Udowodnij, że nie istnieje zbiór zdań \(\Delta\) logiki pierwszego rzędu formalizujący negację tezy Lematu Koeniga, czyli taki, że dla każdego grafu skierowanego \(\mathfrak{T}\), jeśli \(\mathfrak{T}\models\Delta\) to albo \(\mathfrak{T}\) nie jest drzewem, albo nie zawiera nieskończonej ścieżki.
Kwadrat kartezjański \(\mathfrak{G}^2\) grafu \(\mathfrak{G}=\langle G,E^\mathfrak{G}\rangle\) to struktura
\(\langle G\times G,E\rangle\), w której \(\langle(g,h),(g',h')\rangle \in E\) zachodzi wtedy i tylko wtedy, gdy \(\langle g,g'\rangle \in E^\mathfrak{G}\) i \(\langle h,h'\rangle \in E^\mathfrak{G}\).
1. Wykaż, że dla każdego skończonego grafu \(\mathfrak{G}\) o \(n > 1\) wierzchołkach zachodzi \(\mathfrak{G}^2\not\equiv_{n+1}\mathfrak{G}.\)
2. Podaj przykład skończonego grafu \(\mathfrak{G}\) o \(n > 1\) wierzchołkach spełniającego \(\mathfrak{G}^2\equiv_n\mathfrak{G}.\)
Niech zbiór \(X\) będzie spektrum zdania \(\varphi\) nad sygnaturą \(\Sigma\), tzn., niech \(X=\{ n\in\mathbb{N}~/~\)istnieje struktura \(\mathfrak{A}\) mocy \(n\) spełniająca \(\varphi\}.\)
Udowodnij, że zbiór \(\{ m+n~|~m,n\in X\}\) też jest spektrum pewnego zdania \(\psi\) (w konstrukcji wolno powiększyć sygnaturę o nowe symbole).
Dla danej formuły \(\varphi(x)\) w języku arytmetyki skonstruuj formułę \(\#\varphi(x)\), również w języku arytmetyki, o następującej własności:
\((\mathbb{N},x:n)\models \#\varphi(x)\) wtw \(|\{m\in\mathbb{N}~|~(\mathbb{N},x:m)\models\varphi(x)\}|=n.\)