Logika pierwszego rzędu: formalizowanie własności

Zad. 1

Dla każdej z par struktur:

$\langle {\mathbb N},\leq\rangle$ i

$\langle \{m-{1\over n}\ |\ m,n\in{\mathbb N}-\{0\}\}, \leq\rangle$ ;

$\langle {\mathbb N}, +\rangle$ i

$\langle {\mathbb Z}, +\rangle$ ;

$\langle {\mathbb N}, \leq\rangle$ i

$\langle {\mathbb Z}, \leq\rangle$ ,

wskaż zdanie prawdziwe w jednej z nich a w drugiej nie.

Zad. 2

Napisać takie zdania $\varphi$ i $\psi$ , że:

zdanie $\varphi$ jest prawdziwe w modelu ${\mathfrak A} = \langle {\mathbb Z}, +, 0 \rangle$ , ale nie w modelu ${\mathfrak B} = \langle {\mathbb N}, +, 0 \rangle$ ;
zdanie $\psi$ jest prawdziwe w modelu ${\mathfrak B} = \langle {\mathbb Z}, +, 0 \rangle$ , ale nie w modelu ${\mathfrak C} = \langle {\mathbb Q}, +, 0 \rangle$ .

Zad. 3

Wskazać formułę pierwszego rzędu:

spełnialną w ciele liczb rzeczywistych ale nie w ciele liczb wymiernych;
spełnialną w algebrze ${\mathbb N}$ z mnożeniem, ale nie w algebrze ${\mathbb N}$ z dodawaniem;
spełnialną w $\langle \{a,b\}^*,\cdot,\varepsilon\rangle$ ale nie w $\langle \{a,b,c\}^*,\cdot,\varepsilon\rangle$ .

Definicje pomocnicze

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 $\mathfrak{N}=\langle\mathbb{N},*^{\mathfrak{N}},+^{\mathfrak{N}},0^{\mathfrak{N}},1^{\mathfrak{N}},\leq^{\mathfrak{N}}\rangle.$

Zad. 4

Podać przykład zdania $\varphi$ (sygnatura też jest do wyboru) takiego, że $Spec(\varphi)=Spec(\lnot\varphi).$

Zad. 5

Podać przykład zdania $\varphi$ (sygnatura też jest do wyboru) takiego, że $Spec(\varphi)=\{ n^{2}~/~n\in\mathbb{N}\}.$

Zad. 6

Podać przykład zdania $\varphi$ (sygnatura też jest do wyboru) takiego, że $Spec(\varphi)=\{ 2*n~/~n\in\mathbb{N}\}.$

Zad. 7

Podać przykład zdania $\varphi$ (sygnatura też jest do wyboru) takiego, że $Spec(\varphi)=\{ n~/~n\in\mathbb{N}\ n$ jest liczbą złożoną $\}$ .

Zad. 8

Podać przykład zdania $\varphi$ (sygnatura też jest do wyboru) takiego, że $Spec(\varphi)=\{ 2^{n}~/~n\in\mathbb{N}\}.$

Zad. 9

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

Zad. 10

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

Zad. 11

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

Zad. 12

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

Zad. 13

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

Zad. 14

Znaleźć formułę $\varphi(x,y)$ stwierdzającą w standardowym modelu arytmetyki, że $x$ jest względnie pierwsze z $y.$

Zad. 15

Znaleźć formułę $\varphi(x,y,z)$ stwierdzającą w standardowym modelu arytmetyki, że $z$ jest największym wspólnym dzielnikiem $x$ i $y.$

Zad. 16

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

Zad. 17

Rozważamy skończone skierowane cykle $\mathfrak{C}$ (ta litera to gotyckie C, w rozwiązaniu można pisać zwykłe C) nad sygnaturą składającą się z jednego dwuargumentowego symbolu relacyjnego $E$ .

Udowodnić, że dla każdego naturalnego $n$ istnieje formuła $\varphi_n(x,y,z)$ logiki pierwszego rzędu, w której występują tylko trzy zmienne (które można rekwantyfikować tak często jak potrzeba), takie że dla każdego skończonego cyklu $\mathfrak{C}$ zachodzi równoważność: $\mathfrak{C},x:a,y:b,z:c\models\varphi_n(x,y,z)$ wtw $\mathfrak{C}$ ma $3n$ krawędzi, a skierowane odległości z $a$ do $b$ , z $b$ do $c$ i z $c$ do $a$ wszystkie wynoszą po $n$ .

Zad. 18

Rozważamy skończone drzewa binarne $\mathfrak{T}$ (ta litera to gotyckie T, w rozwiązaniu można pisać zwykłe T) nad sygnaturą składającą się z dwóch dwuargumentowych symboli relacyjnych $L$ i $P$ , przy czym $L(x,y)$ oznacza że $y$ to lewy syn ojca $x$ , podobnie dla $P$ oznaczającego prawego syna. Każdy wiechołek może mieć 0, 1 lub 2 synów, zawsze najwyżej jednego lewego jednego prawego.

Udowodnić, że dla każdego naturalnego $n$ istnieje zdanie $\varphi _{n}$ logiki pierwszego rzędu, w którym występują tylko dwie zmienne (które można rekwantyfikować tak często jak potrzeba), takie że dla każdego skończonego drzewa binarnego $\mathfrak{T}$ zachodzi równoważność: $\mathfrak{T}\models\varphi _{n}$ wtw $\mathfrak{T}$ jest pełnym drzewem binarnym o głębokości $n$ .

Informatyka MIMUW