First order logic: if A sentence is satisfiable then it is satisfiable in the natural number + even function

first-order-logiclogicmodel-theorynatural numberssatisfiability

Let $\Sigma=\{R(,),f(),g(,)\}$ and let f,and g be functions, and R a relation in FOL logic without equallity.

Prove or disprove:

  1. if $\phi$ is satisfiable and a universal sentence, then there is a model N where its domain is the natural numbers, and f is a function which its image is the even natural numbers.

  2. if $\phi$ is satisfiable and a sentence, then there is a model N where its domain is the natural numbers, and f is a function which its image is the even natural numbers.

I believe that the first one is true, because we can convert it to a herbrand model, and then replace each with an even number, then add to the domain the odd natural numbers.

The second seems to be a false statement, But I look for such sentence. Probably it is related somehow that an $\aleph_{0}$ elements are missing

Edit:
g is a binary function.

Best Answer

I have almost no experience with FOL without equality, so I may be mistaken, but I believe both are true. In fact, any countable consistent theory has such a model. I assume that your $f,g$ are unary and $R$ is binary, but if they have different arities, the same solution should still work, with obvious modifications.

It suffices to find a countable model such that the range of $f$ is infinite and co-infinite.

By Lowenheim-Skolem, fix any countable (possibly finite) model $M$ and any $x_0\in M$ and $y_0:= f^M(x_0)$. Choose sequences $(x_n)_{n\in \mathbf N}, (y_n)_{n\in \mathbf N}$ such that $x_n,y_n$ are distinct and $x_n,y_n\notin M$ for $n>0$. Let $M'=M\cup \{x_n,y_n\mid n\in \mathbf N\}$.

Define $M'$ as en extension of $M$ in the following way: $f^{M'}(x_n)=y_n$, $g^{M'}(x_n)=g^M(x_0)$, $f^{M'}(y_n)=f^M(y_0)$, $g^{M'}(y_n)=g^M(y_0)$, $R^{M'}(x_n,x_m)=R^M(x_0,x_0)$, $R^{M'}(x_n,y_m)=R^M(x_0,y_0)$, $R^{M'}(x_n,z)=R^M(x_0,z)$ etc.

Then $M\equiv M'$ by an Ehrenfeucht-Fraisse argument: the duplicator can choose $x_0$ in response to any $x_n$ (including $x_0$), $y_0$ in response to any $y_n$, and $z$ in response to any $z\in M$.

$M'$ is then the desired model, since $\{y_n\mid n\in \mathbf N\}$ is contained in the range of $f^{M'}$, while $\{x_n\mid n>0\}$ is contained in its complement.

Related Question