## First order logic: formalizing properties

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

Auxiliary definitions
Spectrum $$Spec(\varphi)$$ of a closed formula $$\varphi$$ is the set of natural numbers $$n$$ such that $$\varphi$$ has a model of cardinality $$n.$$

The standard model of arithmetics is the structure $$\mathfrak{N}=\langle\mathbb{N},*^{\mathfrak{N}},+^{\mathfrak{N}},0^{\mathfrak{N}},1^{\mathfrak{N}},\leq^{\mathfrak{N}}\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$$.