Informatyka MIMUW

1. 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ą.

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

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

4. Przypuśćmy, że $\Delta$ jest zbiorem zdań nad sygnaturą $\Sigma,$ który ma tylko modele nieskończone, 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).
5. 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ą.

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

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

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

Czas na rozwiązanie zadań to 3 godziny od chwili ich rozdania. Wolno używać dowolnych notatek i podręczników, natomiast nie wolno ściągać. Osoby złapane na ściąganiu będziemy usuwać z egzaminu.

Wszystkie zadania są oceniane w skali 0-1-2-3 punkty, przy czym ważne jest uzasadnienie odpowiedzi. Na piątkę trzeba 10 punktów (w tym 4 zadania na co najmniej 2 punkty), na czwórkę 7 punktów (w tym co najmniej 2 zadania na co najmniej 2 punkty), a na trójkę 5 punktów (w tym co najmniej 2 zadania na co najmniej 2 punkty lub jedno zadanie na 3 punkty). Każdej osobie, kóra odda więcej niż cztery zadania, do wyniku zostaną policzone najsłabsze cztery spośród nich, tak więc nie opłaca się oddawać więcej niż czterech zadań.

Każde zadanie proszę napisać na osobnej kartce, podpianej imieniem, nazwiskiem i numerem indeksu.

Oceny z egzaminu zostaną wpisane tylko tym studentom, którzy dostarczą indeks z wpisanym zaliczeniem z ćwiczeń.