Egzamin z logiki, 04/09/2000 | Informatyka MIMUW

Niech $\mathbb{N}$ będzie standardowym modelem arytmetyki, nad standardową sygnaturą, składającą się z symboli $+,*,0,1,\leq.$

Mówimy, że funkcja $F:\omega\to\omega$ jest definiowalna, gdy istnieje formuła $\varphi(x,y)$ nad sygnaturą arytmetyki taka, że każdego wartościowania $v:X\to\omega$ zachodzi

$\mathbb{N}\models\varphi[v]\ \ \text{wtw}\ \ v(y)=F(v(x)).$

Udowodnić, że jeśli funkcja $F:\omega\to\omega$ jest definiowalna, to jest też definiowalna funkcja $G:\omega\to\omega$ dana wzorem

$G(n)=\begin{cases}0&\text{gdy $n=0,$}\\ F(G(n-1))&\text{gdy $n>0.$}\end{cases}$
Niech $\mathcal{A}$ będzie klasą algebr nad pewną algebraiczną sygnaturą $\Sigma.$ Niech $Spec(\mathcal{A})$ oznacza, tak jak niegdyś na kolokwium, spektrum $\mathcal{A},$ czyli zbiór $\{ n\in\omega~/~\text{istnieje $\mathbb{A}\in\mathcal{A}$ takie, \.{z}e $|A|=n.$}\}.$$\mathbb{A}\in\mathcal{A}$ takie, że $|A|=n.$

Udowodnić, że jeśli $\mathcal{A}$ jest rozmaitością algebr, to $Spec(\mathcal{A})$ jest zamknięte na mnożenie: jeśli $m,n\in Spec(\mathcal{A}),$ to $m\cdot n\in Spec(\mathcal{A}).$

Podać przykład takiej klasy algebr $\mathcal{A}$ nad sygnaturą $\Sigma$ (która też jest do wyboru), która jest definiowalna, ale jej spektrum nie jest zamknięte na mnożenie.
Niech $\Sigma$ będzie sygnaturą algebraiczną, składającą się z jednego symbolu $f\in\Sigma^{F}_{2}.$ Rozpatrujemy algebrę $\mathbb{E}=\langle\omega,f^{\mathbb{E}}\rangle,$ gdzie

$f(x,y)=\begin{cases}x^{{2\cdot y}}&\text{gdy $x\neq 0$ lub $y\neq 0$,}\\ 0&\text{gdy $x=0$ i $y=0$.}\end{cases}$.

Napisać taką formułę pierwszego rzędu $\varphi(x)$ nad $\Sigma,$ z jedną zmienną wolną $x$, która definiuje liczbę $1,$ t.j., taką, że dla każdego wartościowania $v:X\to\omega$ zachodzi $\mathbb{E}\models\varphi[v]$ wtw $v(x)=1.$

Niech dany będzie niesprzeczny, skończony zbiór 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\varphi.$

Podać charakteryzację zbioru wszystkich liczb kardynalnych (mocy) $\mathfrak{n}$ takich, że zachodzi następująca własność:

Dla każdej sygnatury $\Sigma$ i każdej klasy $\mathcal{A}$ struktur nad $\Sigma,$ jeśli klasa $\mathcal{A}$ jest aksjomatyzowalna, to jest też aksjomatyzowalna podklasa $\mathcal{A}$, składająca się ze struktur mocy nie większej niż $\mathfrak{n}.$

Równość $s=t$ nad sygnaturą algebraiczną $\Sigma$ nazywamy dziwną, gdy $FV(s)\cap FV(t)=\emptyset,$ a ponadto żaden z termów $s,t$ nie jest zmienną.
Przypuśćmy, że $E$ jest zbiorem wszystkich równości dziwnych nad $\Sigma,$ oraz że $\mathbb{A}$ jest algebrą nad $\Sigma$ taką, że $\mathbb{A}\models E.$ Udowodnić, że dla każdego $n\in\omega$ i każdego $f\in\Sigma^{F}_{n},$ $f^{\mathbb{A}}$ jest funkcją stałą. Czy z powyższych założeń wynika też, że $|A|=1?$

Niech $\varphi$ będzie zdaniem

$\bigl(\forall x\, f(a_{1}(x),a_{2}(x))=x\bigr)\land\bigl(\forall x\forall y\, a_{1}(f(x,y))=x\land a_{2}(f(x,y))=y\bigr).$

Czy $\varphi$ ma model o co najmniej dwóch elementach?

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 nie zawiera dwóch klas abstrakcji równej mocy, nie jest aksjomatyzowalna.

Niech $\mathbb{B}$ będzie wolną algebrą Boole'a (t.j., algebrą wolną w klasie wszystkich algebr Boole'a) ze zbiorem wolnych generatorów $G$ o mocy $\mathfrak{c}$. Jakiej mocy jest zbiór wszystkich podalgebr $\mathbb{B}?$

Niech sygnatura algebraiczna $\Sigma$ zawiera wyłącznie jeden symbol $f$ operacji jedoargumentowej. Zakładamy, że $3$-elementowa algebra $\mathbb{A}$ nad $\Sigma$ ma dokładnie dwie kongruencje. Udowodnić, że istnieje pojedynczy element $x\in A$ taki, który generuje całą algebrę $\mathbb{A},$ t.j., $[x]=\mathbb{A}.$

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 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, 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, podpisanej imieniem, nazwiskiem i numerem indeksu.