Satisfiability problem

Question

Let $L$ be a first order language with equality such as $F0 = \{a,b\}, F1=\{g,h,f\}, F2=\{f\}, R1=\{S,T\}$ and $R2=\{R,Q\}$. Let $A$ be a structure of $L$ defined by:

• the domain of $A$ is the set of integer numbers $\mathbb{Z} = \{...,-1,0,1,...\}$
• $a^A = 0, b^A = 4$
• $g^A(n) = n^2, n \in \mathbb{Z}$
• $h^A(n) = n + 1, n \in \mathbb{Z}$
• $f^A(n) = 2n, n \in \mathbb{Z}$
• $f^A(n,m) = n - m, n, m \in \mathbb{Z}$
• $S^A = \{n \in \mathbb{Z} \mid$ $n$ $is$ $even\}$
• $T^A = \{n \in \mathbb{Z} \mid n\ge0\}$
• $Q^A = \{(n,m) \in \mathbb{Z}^2 \mid n\le m \}$
• $R^A = \{(-2,3),(5,4)\}$

Consider the following interpretations $s\small{i}$ $: Var → \mathbb{Z}$ for $i = 1,2,3$ and where:

• $s\small{1}$ $(z) = 2$, for all $z \in Var$
• $s\small{2}$ $(z) = 0$, for all $z \in Var$
• $s\small{3}$ $(z) = 3$, for all $z \in Var$

For each of the formulas $φ$ that follows and for each of the $\small{si}$ interpretations, tell if $A⊨s\small{i}$ $φ$, for $i = 1,2,3$:

• $∃x \space T(f(z,x))$
• $∀z \space (z=a) ∨ (f(z)=a)$
• $∀x \space (S(x) → ¬S(g(h(x))))$
• $∀x∀y \space (R(x,y) → (S(y)∧S(z)))$

EDIT: I tried to solve 1) but I don't know if I'm doing it correctly. Here is my solution.

Answer 1

Hint

Try to rewrite the problem following the proposed interpretation.

For 1) : $∃x T(f(z,x))$, you are asked to check if :

$A, s_1 \vDash ∃x T(f(z,x))$.

But $|A| = \mathbb Z$ and $f^A(n,m)$ is $n−m$ and $T^A(n)$ is $n \ge 0$ and $s_1(z)=2$.

Thus, you have to show :

if $\mathbb Z \vDash ∃x \ [(2 - x) \ge 0)]$ or not.

The same with $s_2$ and $s_3$.

---

For 3) : $∀x (S(x) → ¬S(g(h(x))))$, with $h^A(n)=n+1, g^A(n)=n^2$ and $S^A$ meaning "$n$ is even", we have :

for all $n$, if $n$ is even, then $(n+1)^2$ is odd.