Egzamin z logiki, 13/06/2001 | Informatyka MIMUW

Niech $\Sigma$ będzie sygnaturą składającą się z jednego jednoargumentowego symbolu funkcyjnego $f.$ Czy klasa wszystkich algebr $\mathbb{A}$ nad $\Sigma$ takich, że $f^{\mathbb{A}}$ jest bijekcją, jest rozmaitością algebr?
Niech $\mathbb{Z}=\langle Z,+^{\mathbb{Z}},*^{\mathbb{Z}},-^{{\mathbb{Z}}},0^{\mathbb{Z}},1^{\mathbb{Z}}\rangle$ będzie zwykłym pierścieniem liczb całkowitych, oraz niech $\mathcal{Z}$ będzie najmniejszą rozmaitością algebr zawierającą $\mathbb{Z}.$ W jaki sposób należy określić operacje w zbiorze $\mathbb{Z}[X]$ wielomianów jednej zmiennej $X$ nad $\mathbb{Z},$ aby tak otrzymana algebra była wolna w $\mathcal{Z}$ nad pewnym jednoelementowym zbiorem wolnych generatorów? (Wystarczy podać jeden sposób.)
Niech $\mathbb{Q}=\langle Q,+^{\mathbb{Q}},*^{\mathbb{Q}},0^{\mathbb{Q}},1^{\mathbb{Q}}\rangle$ będzie pierścieniem liczb wymiernych, przy czym wszystkie operacje i stałe mają swoje zwykłe znaczenie. Udowodnić, że jeśli $h:\mathbb{Q}\to\mathbb{Q}$ jest homomorfizmem, to $h=\mathrm{id}.$
Niech $\varphi _{1},\varphi _{2},\dots$ oraz $\psi$ będą zdaniami na pewną ustaloną sygnaturą. Niech $T$ będzie zbiorem zdań

$\{\varphi _{2}\to\varphi _{1},\varphi _{3}\to(\varphi _{1}\land\varphi _{2}),\varphi _{4}\to(\varphi _{1}\land\varphi _{2}\land\varphi _{3}),\dots\}.$

Czy musi istnieć $n$ takie, że dla każdego $\psi$ , $T\models\psi$ implikuje $\varphi _{n}\models\psi$ ?
Niech $\mathcal{C}$ będzie klasą wszystkich grafów, skończonych i nieskończonych, które zawierają cykl. Udowodnić, że klasa $\mathcal{C}$ nie jest definiowalna.
Niech $\mathbb{N}$ będzie standardowym modelem arytmetyki, nad standardową sygnaturą, składającą się z symboli $+,*,0,1,\leq.$

Napisać formułę $\varphi(x,y)$ nad sygnaturą arytmetyki definiującą funkcję $y=\lfloor\log _{2}x\rfloor,$ tzn. taką, że dla wszystkich wartościowań $v:X\to\omega$

$\mathbb{N}\models\varphi[v]\ \ \text{wtw}\ \ v(y)=\lfloor\log _{2}v(x)\rfloor.$
Niech $\mathbb{Z}_{n}=\langle\{ 0,1,\dots,n-1\},+^{{\mathbb{Z}_{n}}}\rangle,$ gdzie $+\in\Sigma^{F}_{2}$ , a $+^{{\mathbb{Z}_{n}}}$ jest operacją dodawania modulo $n.$

Ile jest różnych funkcji dwóch argumentów $x$ i $y$ , definiowalnych za pomocą termów $t(x,y)$ w algebrze $\mathbb{Z}_{n}?$
Niech $FINSAT_{\Sigma}$ będzie zbiorem wszystkich tych zdań logiki pierwszego rzędu nad pewną skończoną sygnaturą $\Sigma,$ które są spełnialne w pewnej skończonej strukturze nad $\Sigma.$

Udowodnić, że zbiór $FINSAT_{\Sigma}$ jest algorytmicznie generowalny.
Niech $\mathbb{A}$ będzie algebrą, której krata kongruencji ma następującą postać:

$\xymatrix{&*+{A\times A}&\\ *+{r_{1}}\ar[ur]&&*+{r_{2}}\ar[ul]\\ &*+{\mathrm{id}_{A}}\ar[ul]\ar[ur]}$ \xymatrix Align Align \ar Align Align \ar Align \ar \ar

Udowodnić, że algebra $\mathbb{A}/r_{1}$ ma tylko dwie kongruencje: relację totalną i identyczność.
Niech $\mathbb{F}=\langle\omega^{\omega},\circ,\mathrm{id}\rangle$ będzie algebrą, w której $\omega^{\omega}$ to zbiór wszystkich funkcji z liczb naturalnych w liczby naturalne, $\circ$ to operacja składania funkcji (dla przypomnienia: $(f\circ g)(x)=f(g(x))$ ), zaś $\mathrm{id}$ to funkcja identycznościowa.

Udowodnić, że

$\mathbb{F}\models\forall f([\exists g\, g\circ f=\mathrm{id}]\to[\forall g_{1}\forall g_{2}\,((f\circ g_{1}=f\circ g_{2})\to g_{1}=g_{2})]).$

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ć.
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ę 8 punktów (w tym co najmniej 3 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, któ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, podpisanej imieniem, nazwiskiem i numerem indeksu.