Informatyka MIMUW

Exercise 1

For each pair of structures below give a closed formula that holds in one structure but not in the other:

• $\langle {\mathbb N},\leq\rangle$ and $\langle \{m-{1\over n}\ |\ m,n\in{\mathbb N}-\{0\}\}, \leq\rangle$;
• $\langle {\mathbb N}, +\rangle$ and $\langle {\mathbb Z}, +\rangle$;
• $\langle {\mathbb N}, \leq\rangle$ and $\langle {\mathbb Z}, \leq\rangle$.

Exercise 2

Give examples of closed formulas $\varphi$ and $\psi$ such that

• $\varphi$ holds in ${\mathfrak A} = \langle {\mathbb Z}, +, 0 \rangle$, but not in ${\mathfrak B} = \langle {\mathbb N}, +, 0 \rangle$;
• $\psi$ holds in ${\mathfrak B} = \langle {\mathbb Z}, +, 0 \rangle$, but not in ${\mathfrak C} = \langle {\mathbb Q}, +, 0 \rangle$.

Exercise 3

Give an example of a first order formula

• satisfiable in the field of real numbers, but not in the field of rational numbers;
• satisfiable in the algebra ${\mathbb N}$ with multiplication, but not in the algebra ${\mathbb N}$ with addition;
• satisfiable in $\langle \{a,b\}^*,\cdot,\varepsilon\rangle$, but not in $\langle \{a,b,c\}^*,\cdot,\varepsilon\rangle$.

Exercise 4

Give an example of a closed formula $\varphi$ (over a signature of your choice) such that $Spec(\varphi)=Spec(\lnot\varphi).$

Exercise 5

Give an example of a closed formula $\varphi$ (over a signature of your choice) such that $Spec(\varphi)=\{ n^{2}~/~n\in\mathbb{N}\}.$

Exercise 6

Give an example of a closed formula $\varphi$ (over a signature of your choice) such that $Spec(\varphi)=\{ 2*n~/~n\in\mathbb{N}\}.$

Exercise 7

Give an example of a closed formula $\varphi$ (over a signature of your choice) such that $Spec(\varphi)=\{ n~/~n\in\mathbb{N}$ and $n$ is not a prime number$\}$.

Exercise 8

Give an example of a closed formula $\varphi$ (over a signature of your choice) such that $Spec(\varphi)=\{ 2^{n}~/~n\in\mathbb{N}\}.$

Exercise 9

Give an example of a closed formula $\varphi$ (over a signature of your choice) such that for each natural number $n,$ $\varphi$ has exactly $n$ non-isomorphic models of cardinality $n.$

Exercise 10

Give an example of a closed formula $\varphi$ (over a signature of your choice) such that for each natural number $n,$ $\varphi$ has exactly $2^{n}$ non-isomorphic models of cardinality $n.$

Exercise 11

Give an example of a closed formula $\varphi$ (over a signature of your choice) such that for each natural number $n,$ $\varphi$ has exactly $n!$ non-isomorphic models of cardinality $n.$

Exercise 12

For a given $k\in\mathbb{N},$ give an example of a closed formula $\varphi$ (over a signature of your choice) such that for each natural number $n,$ $\varphi$ has exactly ${n \choose k}$ non-isomorphic models of cardinality $n.$

Exercise 13

For a given $k\in\mathbb{N},$ give an example of a closed formula $\varphi$ (over a signature of your choice) such that for each natural number $n,$ $\varphi$ has exactly $n^{k}$ non-isomorphic models of cardinality $n.$

Exercise 14

Give a formula $\varphi(x,y)$ that holds in the standard model of arithmetics iff $x$ and $y$ are co-prime.

Exercise 15

Give a formula $\varphi(x,y,z)$ that holds in the standard model of arithmetics iff $z$ is the greatest common divisor of $x$ and $y.$

Exercise 16

Give a formula $\varphi(x,y,z)$ that holds in the standard model of arithmetics iff $y$ is the greater number that is a power of a prime, which does not divide $x.$

Exercise 17

Consider finite directed cycles $\mathfrak{C}$ over the signature containing a single binary relational symbol $E$.

Show that for each natural number $n$ there is a first order formula $\varphi_n(x,y,z)$ using only three variables (which can be requantified as often as needed) such that for each finite cycle $\mathfrak{C}$ the following equivalence holds: $\mathfrak{C},x:a,y:b,z:c\models\varphi_n(x,y,z)$ iff $\mathfrak{C}$ has $3n$ edges, and the directed distances from $a$ to $b$, form $b$ to $c$, and from $c$ to $a$ are all equal to $n$.

Exercise 18

Consider finite binary trees $\mathfrak{T}$ over the signature consisting of two binary relational symbols $L$ i $P$, where $L(x,y)$ means that $y$ is the left son of $x$, and similarly $P$ denotes the right son. Each node can have 0, 1 or 2 sons, always at most one left and at most one right.

Show that for each natural $n$ there is a closed first order formula $\varphi _{n}$ using only two variables (which can be requantified as often as needed) such that for each finite binary tree $\mathfrak{T}$ the following equivalence holds: $\mathfrak{T}\models\varphi _{n}$ iff $\mathfrak{T}$ is the full binary tree of depth $n$.