## First order logic: formulas, models, tautologies

### Exercise 1

Let $${\mathfrak A} =\langle{\mathbb N}, p^{\mathfrak A}, q^{\mathfrak A}\rangle$$, where:

$$\langle a,b\rangle \in p^{\mathfrak A}$$ iff $$a+b\geq 6$$;

$$\langle a,b\rangle \in q^{\mathfrak A}$$ iff $$b=a+2$$.

Check if formulas

1. $$\forall x p(x,y) \to \exists x q(x,y)$$;
2. $$\forall x p(x,y) \to \forall x q(x,y)$$;
3. $$\forall x p(x,y) \to \exists x q(x,z)$$;

are satisfied under the valuation $$v(y) = 7$$, $$v(z) = 1$$ in structure $${\mathfrak A}$$.

### Exercise 2

Let $${\mathfrak A} = \langle {\mathbb Z}, f^{\mathfrak A}, r^{\mathfrak A}\rangle$$ and $${\mathfrak B} = \langle {\mathbb Z}, f^{\mathfrak B}, r^{\mathfrak B}\rangle$$, where $$f^{\mathfrak A}(m,n) = \min(m,n)$$ for $$m,n\in{\mathbb Z}$$, and $$r^{\mathfrak A}$$ is the relation $$\geq$$;

$$f^{\mathfrak B}(m,n) = m^2+n^2$$ for $$m,n\in{\mathbb Z}$$, and $$r^{\mathfrak B}$$ is the relation $$\leq$$.

Check if formulas

1. $$\forall y(\forall x(r(z,f(x,y))\to r(z,y)))$$;
2. $$\forall y(\forall x(r(z,f(x,y)))\to r(z,y))$$,

are satisfied under the valuation $$v(z) =5$$, $$v(y)=7$$ in structures $${\mathfrak A}$$ and $${\mathfrak B}$$.

### Exercise 3

Is formula $$\forall x(\lnot r(x,y)\to\exists z(r(f(x,z),g(y))))$$ satisfied under the valuation $$v(x) =3$$, $$w(x) = 6$$ and $$u(x) = 14$$

1. in the structure $${\mathfrak A} = \langle {\mathbb N}, r^{\mathfrak A}\rangle$$, where $$r^{\mathfrak A}$$ is the divisibility relation?
2. in the structure $${\mathfrak B} = \langle {\mathbb N}, r^{\mathfrak B}\rangle$$, where $$r^{\mathfrak B}$$ is the congruency modulo 7?

### Exercise 4

In which structures is the formula $$\exists y (y\neq x)$$ satisfied?
And the formula $$\exists y (y\neq y)$$ obtained by naive substitution of $$y$$ to $$x$$?

### Exercise 5

Give examples of models and valuations such that the formula
$$p(x,f(x)) \to \forall x\exists y\, p(f(y),x)$$

is:
a) satisfied;
b) not satisfied.

### Exercise 6

Check if the following formulas are tautologies an if they are satisfiable:

1. $$\exists x\forall y(p(x) \vee q(y)) \to \forall y(p(f(y))\vee q(y))$$;
2. $$\forall y(p(f(y))\vee q(y)) \to \exists x\forall y(p(x) \vee q(y))$$;
3. $$\exists x(\forall y q(y)\to p(x))\to \exists x\forall y(q(y)\to p(x))$$;
4. $$\exists x(\forall y q(y)\to p(x)) \to\exists x(q(x)\to p(x))$$.

### Exercise 7

Let $$f$$ be a function symbol of arity two, that is not used in the formula $$\varphi$$.
Show that the formula $$\forall x\exists y \varphi$$ is satisfiable if and only if the formula $$\forall x \varphi(f(x)/y)$$ is satisfiable.

### Exercise 8

Show that the formula $$\forall x\exists y\,p(x,y)\wedge \forall x\neg p(x,x) \wedge \forall x\forall y\forall z(p(x,y)\wedge p(y,z)\to p(x,z))$$ has only infinite models.

### Exercise 9

For each $$n$$ give a closed formula $$\varphi_n$$ such that $${\mathfrak A}\models\varphi_n$$ iff $${\mathfrak A}$$ has exactly $$n$$ elements.

### Exercise 10

Show that for each finite structure $${\mathfrak A}$$ over a finite signature there exists a set of first order formulas $$\Delta$$ such that $${\mathfrak A}\models\Delta$$ and for all structures satisfying $${\mathfrak B}\models\Delta$$ it holds that $${\mathfrak B}\cong{\mathfrak A}.$$

### Exercise 11

Is it true that $${\mathfrak A} \models \exists x\,\varphi$$ implies existence of a term $$t$$ such that $${\mathfrak A} \models \varphi[t/x]$$?

### Exercise 12

Let $$\varphi = \forall x\forall y\,(y=f(g(x))\to(\exists u\,(u=f(x)\land y=g(u))))$$ and $$\psi = \forall x\,[f(g(f(x)))=g(f(f(x)))]$$. Does it hold that
$$\{\psi\}\models\varphi$$?

Hint
In exercises of the form "Show that the set of formulas $$\Delta$$ is independent", one has to prove that for each $$\varphi\in\Delta,$$ $$\Delta\setminus\{\varphi\}\not\models\varphi,$$ by showing a model of $$\Delta\setminus\{\varphi\},$$ which is not a model of $$\varphi.$$

### Exercise 13

Show that the set of axioms of equivalence relation

$$\left\{\begin{array}[]{c}\forall x\forall y(Exy\to Eyx)\\ \forall x\ Exx\\ \forall x\forall y\forall z((Exy\land Eyz)\to Exz)\end{array}\right\}$$

is independent.

### Exercise14

Show that the set of axioms of linear orders

$$\left\{\begin{array}[]{c}\forall x\forall y((x\leq y)\lor(y\leq x))\\ \forall x\forall y((x\leq y\land y\leq x)\to x=y)\\ \forall x\forall y\forall z((x\leq y\land y\leq z)\to x\leq z)\end{array}\right\}$$

is independent.

### Exercise 15

Show that the set of axioms of of group theory (in multiplicative notation, over signature
$$\Sigma^{F}_{{2}}=\{*\},\Sigma^{F}_{0}=\{ 1\}$$)

$$\left\{\begin{array}[]{c}\forall x((1*x=x)\land(x*1=x))\\ \forall x\forall y\forall z((x*y)*z=x*(y*z))\\ \forall x\exists y((x*y=1)\land(y*x=1))\end{array}\right\}$$

is independent.

### Exercise 16

Show that the formula $$(\forall x\exists y\ Exy)\to(\exists x\forall y\ Exy)$$ is not a tautology.

### Exercise 17

Show that the formula

$$(\forall x\forall y((f(x)=f(y))\to(x=y)))\to(\forall x\exists y(f(y)=x))$$

is not a tautology. Does its negation have a finite model?

### Exercise18

Show that the formula $$\exists x\exists y\exists u\exists v((\lnot u=x)\lor(\lnot v=y))\land(f(x,y)=f(u,v))$$ is not a tautology. How many non-isomorphic finite models does this formula have?

### Exercise 19

Show that the following formulas are tautologies:

• $$(\exists y p(y) \to \forall z q(z)) \to \forall y\forall z(p(y)\to q(z))$$;
• $$(\forall x\exists y r(x,y) \to \exists x\forall y r(y,x))\to \exists x\forall y(r(x,y) \to r(y,x))$$;
• $$\forall x\exists y((p(x)\to q(y))\to r(y)) \to ((\forall x p(x)\to \forall y q(y))\to \exists y r(y))$$;
• $$\forall x(p(x)\to \exists y q(y))\to \exists y(\exists x p(x)\to q(y))$$.

### Exercise 20

Does it hold that
$$\{\forall x\underbrace{f\ldots f}_n(x)= x~|~n=2,3,5,7\}\models\forall x \underbrace{f\ldots f}_{11}(x)= x$$?