First-Order Logic: Non-Normal Model of Sentences True in all Normal Models?

Question

Let $\mathcal{L}$ be a first-order language with quantifier $\forall$, connectives $\neg$ and $\rightarrow$, a two-place predicate $E$ and a one-place function symbol $f$. There are no other constants, predicates or function symbols. Say a $\mathcal{L}$-structure is normal iff it interprets $E$ by the identity relation. Let $\Sigma^N$ be the set of sentences true in all normal $\mathcal{L}$-structures.

Can we find a model of $\Sigma^N$ which is not normal? If so (which is my hunch), is there any other set of sentences so that the only models of that set are normal?

Suggestions to further reading just as welcome as full answers, been searching for a while now.

Thanks! Best wishes,

Leon

Answer 1

In a way, the model $M_2 = \{0,1\}$ with $E$ the complete equivalence relation ($xEy$ for all $x,y$) is generic, because we ought to be able to separate $0$ and $1$ if we are to be able to separate anything using $\Sigma^N$.

With the given signature, the only basic formula we can have is $f^n(x) E f^m(y)$ for $m,n \ge 0$. Because of the universal nature of $E$, these will all be true in our model. They will also all be true for the single-element model $M_1$. That is, $M_1$ and $M_2$ are elementarily equivalent. Since this is a normal model, it follows that $M_1 \models \Sigma^N$ and hence so does $M_2$.

---

As to the question if any other set of sentences has only normal models, we can of course take any inconsistent theory. Other than that, I don't think there will be much hope.

Namely, we can prove the following:

Let $M$ be a model of a signature $(c_\alpha)_\alpha, (R_\beta)_\beta, (f_\gamma)_\gamma$ containing a relation $E$ interpreted as equality ($E^M = \{(m,m): m \in M\}$).

Let $S = \coprod_{m \in M} S_m$ with each $S_m$ a set such that $m \in S_m$, and declare:

• $E^S = \bigcup_{m \in M} S_m \times S_m$ (each $S_m$ is an equivalence class intuitively replacing $m$);
• For all $\alpha$, $c_\alpha^S = c_\alpha^M$;
• For all $\beta$, $R_\beta^S(s_1, \ldots, s_n) \iff R_\beta^M(m_1, \ldots, m_n)$ where $s_i \in S_{m_i}$;
• For all $\gamma$, $f_\gamma^S(s_1, \ldots, s_n) = f_\gamma^M(m_1, \ldots, m_n)$ where $s_i \in S_{m_i}$.

Then $M$ and $S$ are elementarily equivalent.

Thus any theory with a normal model ($M$) will also have a non-normal model ($S$). In other words, we cannot distinguish equality from any other equivalence relation in first-order logic without equality.