egzamin | Informatyka MIMUW

Niech $\mathbb{A}=\langle\omega\setminus\{ 0\},\mathrm{nwd}^{\mathbb{A}},1^{\mathbb{A}}\rangle$ będzie algebrą, gdzie $\mathrm{nwd}\in\Sigma^{F}_{2}$ oraz $1\in\Sigma^{F}_{0},$ 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$,

zaś $1^{\mathbb{A}}$ to zwykła jedynka.

Napisać formułę $\varphi(x)$ nad $\Sigma$ definiującą własność ,,być kwadratem liczby pierwszej”, tj., taką, że dla wszystkich wartościowań $v:X\to\omega$

$\mathbb{X}\models\varphi[v]\ \ \text{wtw}\ \ \text{$v(x)$ jest kwadratem liczby pierwszej.}$$v(x)$ jest kwadratem liczby pierwszej.

Niech $\mathbb{X}=\langle\omega,+^{\mathbb{X}}, beta^{\mathbb{X}},0^{\mathbb{X}},1^{\mathbb{X}}\rangle$ będzie strukturą nad sygnaturą $\Sigma,$ która składa się z symboli $0,1\in\Sigma^{F}_{0}$ i $+,\beta\in\Sigma^{F}_{2},$ przy czym dla każdych $t,p\in\omega$

$\beta^{\mathbb{X}}(t,p)=\text{$\beta$}(t,p),$

gdzie $\beta$ to funkcja beta Gödla, znana z wykładu, zaś $+^{\mathbb{X}},0^{\mathbb{X}},1^{\mathbb{X}}$ to zwykłe dodawanie, 0 i 1.

Napisać formułę $\varphi(x,y,z)$ nad $\Sigma$ definiującą mnożenie, tj., taką, że dla wszystkich wartościowań $v:X\to\omega$

$\mathbb{X}\models\varphi[v]\ \ \text{wtw}\ \ v(x)*v(y)=v(z).$

Niech $\mathbb{Y}=\langle\omega,S^{\mathbb{Y}},\beta^{\mathbb{Y}}\rangle$ będzie strukturą nad sygnaturą $\Sigma,$ która składa się z dwóch symboli $S\in\Sigma^{F}_{1}$ i $\beta\in\Sigma^{F}_{2},$ przy czym dla każdych $n,t,p\in\omega$

$\displaystyle S^{\mathbb{Y}}(n) =n+1$ ⁢ S Y n = + n 1 $\displaystyle \beta^{\mathbb{Y}}(t,p) =\text{$\beta$}(t,p),$$\beta$ t p ⁢ β Y t p = ⁢ β t p

gdzie $\beta$ to funkcja beta Gödla, znana z wykładu.

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

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

Niech $\Sigma$ będzie zwykłą sygnaturą ciał, wzbogaconą o jeden jednoargumentowy symbol relacyjny $A.$ Rozpatrujemy struktury postaci $\mathbb{R}_{A}=\langle R,+^{\mathbb{R}},*^{\mathbb{R}},-^{\mathbb{R}},0^{\mathbb{R}},1^{\mathbb{R}},A\rangle,$ gdzie $R$ to zbiór liczb rzeczywistych, wszystkie operacje mają zwykłe interpretacje, zaś $A\subseteq R$ jest dowolny.

Napisać zdanie pierwszego rzędu $\varphi$ nad $\Sigma$ takie, że $\mathbb{R}_{A}\models\varphi$ wtw $A$ jest zbiorem domkniętym.

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

Rozważmy algebrę $\mathbb{A}=\langle\omega,f^{\mathbb{A}},\rangle,$ gdzie $f\in\Sigma^{F}_{2}$ oraz

$f^{\mathbb{A}}(m,n)=m\;\;(\textrm{mod}n)=\text{reszta z dzielenia $m$ przez $n$},$$m$ przez $n$

przy czym przyjmujemy, że $m\;\;(\textrm{mod}0)=m$ dla każdego $m.$
Udowodnić, że w tej algebrze są tylko dwie kongruencje.
[Szkic dowodu: Niech $\sim$ będzie kongruencją.
(*) Jeśli $m\sim n$ dla pewnych $0< m< n,$ to wtedy $m=m\;\;(\textrm{mod}n)\sim n\;\;(\textrm{mod}n)=0,$ więc $m,n$ są kongruentne z $0.$
(**) Jeśli $m\sim 0$ dla pewnego $m>0,$ to dla każdego $0< i< m$ mamy $i=(m+i)\;\;(\textrm{mod}m)\sim m+i\;\;(\textrm{mod}0)=m+i,$ więc $i\sim 0$ na mocy (*).
(***) Jeśli $m\sim 0$ dla pewnego $m>0,$ to dla każdego $n>m$ mamy $n=n\;\;(\textrm{mod}0)\sim n\;\;(\textrm{mod}m)< m< n,$ więc $n\sim 0$ na mocy (*).
(****) Jeśli teraz $m\sim n$ dla pewnych $m\neq n,$ to albo jedno z $m,n$ jest zerem i na mocy (**) i (***) wszystkie liczby są kongruentne z $0,$ albo $m,n$ są niezerowe, ale wtedy na mocy (*) $m\sim 0$ i znowu jesteśmy w przypadku poprzednim.
Szkoda by mi było wyrzucić to zadanie, ale chyba jest za trudne.]

Opisać wszystkie kongruencje grupy $\mathbb{Z}_{4}.$

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

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 punkty. Na piątkę wystarcza 7 punktów, na czwórkę 5 punktów, a na trójkę 4 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ń.