śr., 10/03/2012 - 12:24 — fmurlak
### Exercise 1

### Exercise 2

### Exercise 3

Auxiliary definitions

### Exercise 4

### Exercise 5

### Exercise 6

### Exercise 7

### Exercise 8

### Exercise 9

### Exercise 10

### Exercise 11

### Exercise 12

### Exercise 13

### Exercise 14

### Exercise 15

### Exercise 16

### Exercise 17

### Exercise 18

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\).

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\).

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\).

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.\)

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

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

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

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\(\}\).

Give an example of a closed formula \(\varphi\) (over a signature of your choice) such that \(Spec(\varphi)=\{ 2^{n}~/~n\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\) non-isomorphic models of cardinality \(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 \(2^{n}\) non-isomorphic models of cardinality \(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!\) non-isomorphic models of cardinality \(n.\)

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.\)

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.\)

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

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.\)

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.\)

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\).

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\).