Informatyka MIMUW

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.

Zadanie 1 (10 punktów)

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.

Zadanie 2 (10 punktów)

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.

Zadanie 3 (10 punktów, po 5 za każdą z części)

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

Zadanie 4 (10 punktów)

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

Zadanie 5 (10 punktów)

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