Informatyka MIMUW

Zad. 1

Niech $f$ będzie jednoargumentowym symbolem funcji i niech
$\mathcal{A}=\bigcup_{n\in \mathbb{N}}Mod(\forall x f^n(x) =x)$,
gdzie $f^n(x)$ to $n$-krotne złożenie $f(\ldots(f(x))\ldots)$.
Wykazać, że ani $\mathcal{A}$ nie można zdefiniować żadnym zbiorem zdań logiki pierwszego rzędu, ani
dopełnienia $\mathcal{A}$ nie można zdefiniować pojedynczym zdaniem logiki pierwszego rzędu.

Zad. 2

Niech dany będzie niesprzeczny, skończony zbióor zdań $\Delta$ nad pewną ustaloną i również
skończoną sygnaturą $\Sigma$. Wykazać, że istnieje zbiór $\Delta_0\subseteq\Delta$ taki, że $\Delta_0\models\Delta$, a ponadto zdania w $\Delta_0$ są niezależne: dla każdego $\varphi\in\Delta_0$ mamy $\Delta_0\setminus\{\varphi\}\not\models\Delta_0$.

Zad. 3

Niech $\mathfrak{H}^n$ to struktura której uniwersum to hiperkostka $H^n=\{0,1\}^n$, a jednyna relacja dwuargumentowa $E^{\mathfrak{H}^n}$ jest zdefiniowana tak:

$E^{\mathfrak{H}^n}(x,y)$ wtw, gdy $x$ i $y$ różnią się dokładnie na jednej pozycji.

Jakie jest maksymalne $m$ takie, że gracz II ma strategię wygrywającą w grze Ehrenfeuchta $G_m(\mathfrak{H}^4,\mathfrak{H}^3)$?