Informatyka MIMUW

O zadaniach. Zadania są podzielone na kilka grup. Niektóre zadania są dosyć trudne. Pewne zadania powtarzają się w kilku grupach, aby zachęcić studentów do rozwiązania ich różnymi metodami.
Przy niektórych zadaniach (z działów ,,Tw. o zwartości” i ,,Tw. Skolema-Löwenheima”) należy się posłużyć pełną wersją twierdzenia Skolema-Löwenheima poniżej, która zostanie podana na najbliższym wykładzie:
Jeśli $\Delta$ jest zbiorem zdań nad sygnaturą $\Sigma$ który ma nieskończony model, to $\Delta$ ma model dowolnej mocy $\mathfrak{m}\geq|\Sigma|.$

Formalizowanie zadanych własności. Spektrum $Spec(\varphi)$ zdania $\varphi$ to zbiór wszystkich liczb naturalnych $n$ takich, ze $\varphi$ ma model o mocy $n.$ Standardowy model arytmetyki to struktura $\mathbb{N}=\langle\omega,*^{\mathbb{N}},+^{\mathbb{N}},0^{\mathbb{N}},1^{\mathbb{N}},\leq^{\mathbb{N}}\rangle.$

1. Podać przykład zdania $\varphi$ (sygnatura też jest do wyboru) takiego, że $Spec(\varphi)=Spec(\lnot\varphi).$
2. Podać przykład zdania $\varphi$ (sygnatura też jest do wyboru) takiego, że $Spec(\varphi)=\{ n^{2}~/~n\in\mathbb{N}\}.$
3. Podać przykład zdania $\varphi$ (sygnatura też jest do wyboru) takiego, że $Spec(\varphi)=\{ 2*n~/~n\in\mathbb{N}\}.$
4. Podać przykład zdania $\varphi$ (sygnatura też jest do wyboru) takiego, że $Spec(\varphi)=\{ n~/~n\in\mathbb{N}\ \text{i $n$ jest liczb"a z"lo"ron"a}\}.$$n$ jest liczbą złożoną}.
5. Podać przykład zdania $\varphi$ (sygnatura też jest do wyboru) takiego, że $Spec(\varphi)=\{ 2^{n}~/~n\in\mathbb{N}\}.$
6. Podać przykład zdania $\varphi$ (sygnatura też jest do wyboru) takiego, że dla każdego naturalnego $n,$ $\varphi$ ma dokładnie $n$ nieizomorficznych modeli mocy $n.$
7. Podać przykład zdania $\varphi$ (sygnatura też jest do wyboru) takiego, że dla każdego naturalnego $n,$ $\varphi$ ma dokładnie $2^{n}$ nieizomorficznych modeli mocy $n.$
8. Podać przykład zdania $\varphi$ (sygnatura też jest do wyboru) takiego, że dla każdego naturalnego $n,$ $\varphi$ ma dokładnie $n!$ nieizomorficznych modeli mocy $n.$
9. Dla ustalonego $k\in\mathbb{N},$ podać przykład zdania $\varphi$ (sygnatura też jest do wyboru) takiego, że dla każdego naturalnego $n,$ $\varphi$ ma dokładnie ${n \choose k}$ nieizomorficznych modeli mocy $n.$
10. Dla ustalonego $k\in\mathbb{N},$ podać przykład zdania $\varphi$ (sygnatura też jest do wyboru) takiego, że dla każdego naturalnego $n,$ $\varphi$ ma dokładnie $n^{k}$ nieizomorficznych modeli mocy $n.$
11. Znaleźć formułę $\varphi(x,y)$ stwierdzającą w standardowym modelu arytmetyki, że $x$ jest względnie pierwsze z $y.$
12. Znaleźć formułę $\varphi(x,y,z)$ stwierdzającą w standardowym modelu arytmetyki, że $z$ jest największym wspólnym dzielnikiem $x$ i $y.$
13. Znaleźć formułę $\varphi(x,y,z)$ stwierdzającą w standardowym modelu arytmetyki, że $y$ jest największą liczbą, będącą potęgą liczby pierwszej, która dzieli $x.$

Szukanie modeli dla zadanych formuł. W zadaniach ,,Pokazać, że zbiór zdań $\Delta$ jest niezależny”, należy za każdym razem udowodnić, że dla każdego $\varphi\in\Delta,$ $\Delta\setminus\{\varphi\}\not\models\varphi,$ poprzez wskazanie modelu $\Delta\setminus\{\varphi\},$ który nie jest modelem $\varphi.$

1. Pokazać, że zbiór aksjomatów relacji równoważności

   $\left\{\begin{array}[]{c}\forall x\forall y(Exy\to Eyx)\\ \forall x\ Exx\\ \forall x\forall y\forall z((Exy\land Eyz)\to Exz)\end{array}\right\}$

   jest niezależny.

2. Pokazać, że zbiór aksjomatów liniowych porządków

   $\left\{\begin{array}[]{c}\forall x\forall y((x\leq y)\lor(y\leq x))\\ \forall x\forall y((x\leq y\land y\leq x)\to x=y)\\ \forall x\forall y\forall z((x\leq y\land y\leq z)\to x\leq z)\end{array}\right\}$

   jest niezależny.

3. Pokazać, że zbiór aksjomatów teorii grup (w zapisie multiplikatywnym, nad sygnaturą

   $\Sigma^{F}_{{2}}=\{*\},\Sigma^{F}_{0}=\{ 1\}$)
   $\left\{\begin{array}[]{c}\forall x((1*x=x)\land(x*1=x))\\ \forall x\forall y\forall z((x*y)*z=x*(y*z))\\ \forall x\exists y((x*y=1)\land(y*x=1))\end{array}\right\}$

   jest niezależny.

4. Pokazać, że zdanie $(\forall x\exists y\ Exy)\to(\exists x\forall y\ Exy)$ nie jest tautologią.
5. Pokazać, że zdanie

   $(\forall x\forall y((f(x)=f(y))\to(x=y)))\to(\forall x\exists y(f(y)=x))$

   nie jest tautologią. Czy jego negacja ma model skończony?

6. Pokazać, że zdanie $\exists x\exists y\exists u\exists v((\lnot u=x)\lor(\lnot v=y))\land(f(x,y)=f(u,v))$ nie jest tautologią. Ile nieizomorficznych modeli skończonych ma to zdanie?

Tw. Fraïssé, gra Ehrenfeuchta.

1. Udowodnić, że klasa wszystkich struktur $\mathbb{A}=\langle A,r^{\mathbb{A}}\rangle,$ gdzie $r\in\Sigma^{R}_{1}$ oraz takich, że $|r^{\mathbb{A}}|=|A\setminus r^{\mathbb{A}}|$ nie jest aksjomatyzowalna.
2. 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 $|\{(a,b)\in A\times A~/~(a,b)\in E^{\mathbb{A}}\}|< |\{(a,b)\in A\times A~/~(a,b)\notin E^{\mathbb{A}}\}|,$ nie jest aksjomatyzowalna.
3. 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 zbiorem skończonym, nie jest definiowalna.
4. Pokazać, że klasa wszystkich relacji równoważności, które mają skończenie wiele klas abstrakcji, nie jest aksjomatyzowalna.

Tw. o zwartości.

1. Pokazać, że jeśli klasa $\mathcal{A}$ struktur nad sygnaturą $\Sigma$ jest aksjomatyzowalna i jej dopełnienie $Mod(\Sigma)\setminus\mathcal{A}$ struktur sygnatury $\Sigma,$ ktore nie nalezą do $\mathcal{A},$ jest aksjomatyzowalne, to obie klasy są w istocie definiowalne.

   Wskazówka: Założyć, że pierwsza klasa jest aksjomatyzowalna przez $\Delta$, a druga przez $\Delta^{{\prime}},$ ale żaden skończony podzbiór $\Delta$ nie jest aksjomatyzacją $\mathcal{A}.$ Pokazać, że $\Delta\cup\Delta^{{\prime}}$ spełnia założenia tw. o zwartości.

2. Pokazać następujące tw. Robinsona: Jeśli $\Delta,\Delta^{{\prime}}$ są spełnialnymi zbiorami zdań nad pewną sygnaturą $\Sigma,$ zaś $\Delta\cup\Delta^{{\prime}}$ nie jest spełnialny, to istnieje zdanie $\varphi$ takie, że $\Delta\models\varphi$ oraz $\Delta^{{\prime}}\models\lnot\varphi.$

   Wskazówka: Założyć, że dla każdego $\varphi$ takiego, że $\Delta\models\varphi$ zachodzi $\Delta^{{\prime}}\not\models\lnot\varphi.$ Pokazć, że w tej sytuacji $\Delta^{{\prime}}\cup\{\varphi\}$ jest spełnialny, a stąd, że $\Delta\cup\Delta^{{\prime}}$ spełnia zalożenia tw. o zwartości.

3. Pokazać, że jeśli $\Delta$ jest pewnym zbiorem zdań $\varphi$ takich, że $Spec(\lnot\varphi)$ jest skończone, oraz $\Delta\models\psi,$ to także $Spec(\lnot\psi)$ jest skończone.
4. Pokazać, że klasa wszystkich relacji równoważności, które mają skończenie wiele klas abstrakcji, nie jest aksjomatyzowalna.
5. 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 zbiorem skończonym, nie jest aksjomatyzowalna.
6. Pokazać, że klasa wszystkich algebr $\mathbb{A}=\langle A,f^{\mathbb{A}}\rangle,$ gdzie $f$ jest symbolem jednoragumentowej funkcji, oraz takich, że $|\vec{f}(A)|< |A|$ nie jest aksjomatyzowalna.
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 $|\{(a,b)\in A\times A~/~(a,b)\in E^{\mathbb{A}}\}|< |\{(a,b)\in A\times A~/~(a,b)\notin E^{\mathbb{A}}\}|,$ nie jest aksjomatyzowalna.
8. Udowodnić, że klasa wszystkich struktur $\mathbb{A}=\langle A,r^{\mathbb{A}}\rangle,$ gdzie $r\in\Sigma^{R}_{1}$ oraz takich, że $|r^{\mathbb{A}}|=|A\setminus r^{\mathbb{A}}|$ nie jest aksjomatyzowalna.

Tw. Skolema-Löwenheima.

1. Udowodnić, że klasa wszystkich struktur $\mathbb{A}=\langle A,r^{\mathbb{A}}\rangle,$ gdzie $r\in\Sigma^{R}_{1}$ oraz takich, że $|r^{\mathbb{A}}|=2^{{|A\setminus r^{\mathbb{A}}|}}$ nie jest aksjomatyzowalna.
2. Udowodnić, że klasa wszystkich struktur izomorficznych do struktury postaci $\mathbb{A}=\langle\mathcal{P}(A),\cup^{\mathbb{A}},\cap^{\mathbb{A}},\subseteq^{\mathbb{A}}\rangle,$ gdzie $\cup^{\mathbb{A}},\cap^{\mathbb{A}}$ oraz $\subseteq^{\mathbb{A}}$ są odpowiednio prawdziwymi sumą, przecięciem i zawieraniem zbiorów, nie jest aksjomatyzowalna.
3. Udowodnić następujące tw. Hessenberga: Dla każdej nieskończonej mocy $\mathfrak{m}$ zachodzi $\mathfrak{m}^{2}=\mathfrak{m}.$

   Wskazówka: Napisać zdanie pierwszego rzędu, z którego wynika, że uniwersum modelu jest mocy nie mniejszej niż moc jego kartezjańskiego kwadratu. Pokazać, że zdanie to ma model nieskończony i skorzystać z tw. Skolema-Löwenheima.