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