-
Niech \(\mathbb{A}=\langle\omega\setminus\{ 0\},\mathrm{nwd}^{\mathbb{A}}\rangle\) będzie algebrą, gdzie \(\mathrm{nwd}\in\Sigma^{F}_{2},\) przy czym dla wszystkich \(m,n\in\omega\)
\(\mathrm{nwd}^{\mathbb{A}}(m,n)=\text{najwi"ekszy wsp"olny dzielnik $m$ i $n$.}\)\(m\) i \(n\).
Napisać formułę \(\varphi(x)\) nad \(\Sigma\) definiującą własność ,,być liczbą pierwszą”, tj., taką, że dla wszystkich wartościowań \(v:X\to\omega\)
\(\mathbb{X}\models\varphi[v]\ \ \text{wtw}\ \ \text{$v(x)$ jest liczb"a pierwsz"a.}\)\(v(x)\) jest liczbą pierwszą.
-
Niech \(\mathbb{Y}=\langle\omega,S^{\mathbb{Y}},\beta^{\mathbb{Y}},\leq^{\mathbb{Y}}\rangle\) będzie strukturą nad sygnaturą \(\Sigma,\) która składa się z symboli \(S\in\Sigma^{F}_{1},\) \(\beta\in\Sigma^{F}_{3}\) oraz \(\leq\in\Sigma^{R}_{2},\) przy czym dla każdych \(n,t,p,i\in\omega\)
\(\displaystyle S^{\mathbb{Y}}(n) =n+1\) S Y n = + n 1 \(\displaystyle \beta^{\mathbb{Y}}(t,p,i) =\text{$\beta$}(t,p,i),\)\(\beta\) t p i β Y t p i = β t p i
gdzie \(\beta\) to funkcja beta Gödla, znana z wykładu, zaś \(\leq^{\mathbb{Y}}\) to zwykła nierówność.
Napisać formułę \(\varphi(x,y,z)\) nad \(\Sigma\) definiującą dodawanie, tj., taką, że dla wszystkich wartościowań \(v:X\to\omega\)
\(\mathbb{Y}\models\varphi[v]\ \ \text{wtw}\ \ v(x)+v(y)=v(z).\)
-
Wykazać, że jeśli klasa \(\mathcal{A}\) struktur pewnej ustalonej sygnatury \(\Sigma\) nie jest aksjomatyzowalna, to klasa \(Mod(\Sigma)\setminus\mathcal{A},\) złożona z wszystkich tych struktur sygnatury \(\Sigma,\) które nie należą do \(\mathcal{A},\) nie jest definiowalna.
Podać taki przykład aksjomatyzowalnej klasy \(\mathcal{A}\) nad sygnaturą \(\Sigma\) (którą też można sobie wybrać), że \(Mod(\Sigma)\setminus\mathcal{A}\) nie jest aksjomatyzowalna.
-
Przypuśćmy, że \(\Delta\) jest zbiorem zdań nad sygnaturą \(\Sigma,\) który ma model nieskończony, oraz, że każde dwa przeliczalne modele \(\Delta\) są izomorficzne (o takich \(\Delta\) mówi się, że są \(\aleph _{0}\)-kategoryczne). Udowodnić, że dla każdego zdania \(\varphi\) nad \(\Sigma,\) albo \(\Delta\models\varphi\) albo \(\Delta\models\lnot\varphi\) (innymi słowy, \(\Delta\) jest zupełny).
-
Równość \(s=t\) nazywamy normalną, gdy \(FV(s)=FV(t),\) tj., w \(s\) i \(t\) występują dokładnie te same zmienne.
Przypuśćmy, że \(E\) jest zbiorem równości normalnych, oraz że \(E\vdash _{{eq}}s=t.\) Udowodnić, że \(s=t\) też jest równością normalną.
-
Niech \(\varphi\) będzie zdaniem
\(\forall x\forall y\,(y=f(g(x))\to(\exists u\,(u=f(x)\land y=g(u))))\)
oraz niech \(\psi\) będzie zdaniem
\(\forall x\,[f(g(f(x)))=g(f(f(x)))].\)
Czy \(\{\psi\}\models\varphi?\)
-
Udowodnić, że klasa wszystkich struktur \(\mathbb{A}=\langle A,E^{\mathbb{A}}\rangle\) nad sygnaturą składającą się z jednego dwuargumentowego symbolu relacyjnego \(E\) i takich, że \(E^{\mathbb{A}}\) jest relacją równoważności, która ma wyłącznie klasy abstrakcji parzystej mocy, nie jest definiowalna.
-
Niech \(\mathbb{A}\) będzie algebrą wolną ze zbiorem wolnych generatorów \(G\), w pewnej klasie \(\mathcal{A}.\) Udowodnić, że dla każdej relacji równoważności \(r\subseteq G\times G\) istnieje kongruencja \(\bar{r}\subseteq A\times A\) taka, że \(\bar{r}\cap(G\times G)=r.\) (Można to wyrazić stwierdzeniem, że \(r\) roszerza się do kongruencji w \(\mathbb{A}.\))
Wykorzystując przestrzenie liniowe nad ciałem \(\mathbb{R}\) jako przykład, udowodnić, że może istnieć wiele różnych kongruencji \(\bar{r},\) rozszerzających daną relację równoważności \(r\) w \(G.\)
- Opisać wszystkie kongruencje algebry \(\mathbb{A}=\langle\{ 0,1,2,3\},\min^{\mathbb{A}},\max^{\mathbb{A}}\rangle,\) gdzie \(\min,\max\in\Sigma^{F}_{2}\), a \(\min^{\mathbb{A}},\max^{\mathbb{A}}\) są odpowiednio operacjami maksimum i minimum.
-
Niech \(\mathbb{P}=\langle\mathcal{P}(\omega),\cap^{\mathbb{P}},\cup^{\mathbb{P}}\rangle\) będzie kratą podzbiorów \(\omega\) ze zwykłymi działaniami teoriomnogościowymi. Udowodnić, że \(\mathbb{P}\times\mathbb{P}\cong\mathbb{P}.\)