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

Informatyka MIMUW