# Infinitary logic doesn’t have (finite) Robinson property: a counterexample

logicmodel-theory

Given a standard definition of an abstract logic $$\mathcal{L}_A$$ (cfr. Barwise & Feferman, Model-theoretic Logics, Springer-Verlag, 1985), let $$E_A(\sigma)$$ be the class of $$\mathcal{L}_A$$-sentences for a signature $$\sigma$$. Two $$\sigma$$-structures are $$\mathcal{L}_A$$-equivalent iff they satisfy the same sentences in $$E_A(\sigma)$$.

The finite Robinson property is defined as follows: given two signatures $$\sigma$$ and $$\sigma'$$, for all $$\varphi \in E_A(\sigma)$$, $$\varphi' \in E_A(\sigma')$$ and $$\Psi \subseteq E_A(\sigma \cap \sigma')$$, if $$\Psi \cup \{\varphi\}$$ and $$\Psi \cup \{\varphi'\}$$ are both satisfiable and every two $$(\sigma \cap \sigma')$$-models of $$\Psi$$ are $$\mathcal{L}_A$$-equivalent, then $$\Psi \cup \{\varphi, \varphi'\}$$ is satisfiable.

Let $$\mathcal{L}_{\omega_1\omega}$$ the abstract logic obtained from first-order logic allowing countably-long disjunctions (hence also conjunctions). An exercise in Keisler's Model Theory for Infinitary Logic: Logic with Countable Conjunctions
and Finite Quantifiers
(North Holland Publishing Company, 1971) says that $$\mathcal{L}_{\omega_1\omega}$$ has finite Robinson property if $$\Psi$$ in the above definition is countable, otherwise not. So it exists an uncountable $$\Psi$$ which is a counterexample to the property. Any suggestion?

Let $$\sigma = \{P,(c_\alpha)_{\alpha<\omega_1},f\}$$, and let $$\sigma' = \{P,(c_\alpha)_{\alpha<\omega_1},(d_n)_{n<\omega}\}$$. Here $$P$$ is a unary relation symbol, $$f$$ is a unary function symbol, and the $$c_\alpha$$ and $$d_n$$ are constant symbols. Then $$\sigma\cap \sigma' = \{P,(c_\alpha)_{\alpha<\omega_1}\}$$ Now define: \begin{align*}\Psi &= \{P(c_\alpha)\land P(c_\beta)\land c_\alpha\neq c_\beta\mid \alpha<\beta<\omega_1\}\cup \{\exists x_1\dots\exists x_n(\bigwedge_{i=1}^n \lnot P(x_i)\land \bigwedge_{i\neq j} x_i\neq x_j)\mid n<\omega\}\\ \varphi &: (\forall x\, (P(x)\rightarrow \lnot P(f(x)))\land (\forall x\forall y\, (f(x) = f(y)\rightarrow x = y))\\ \varphi' &: \forall x\, (\lnot P(x)\rightarrow \bigvee_{n<\omega} (x = d_n)) \end{align*}
A model of $$\Psi$$ has $$\omega_1$$-many distinct elements named by constants and satisfying $$P$$ (as well as possibly other elements satisfying $$P$$), and infinitely many elements satisfying $$\lnot P$$. I claim that any two such models, say $$M$$ and $$N$$, are $$\mathcal{L}_{\omega_1,\omega}(\sigma\cap \sigma')$$-equivalent. Since any sentence of $$\mathcal{L}_{\omega_1,\omega}$$ only mentions countably many symbols, it suffices to show that for any countable signature $$\sigma^*\subseteq (\sigma\cap \sigma')$$, the reducts $$M|_{\sigma^*}$$ and $$N|_{\sigma^*}$$ are $$\mathcal{L}_{\omega_1,\omega}(\sigma^*)$$-equivalent. Now $$M|_{\sigma^*}$$ and $$N|_{\sigma^*}$$ consist of countably-many distinct elements named by constants and satisfying $$P$$, infinitely many other elements satisfying $$P$$, and infinitely many elements satisfying $$\lnot P$$. By the infinite Ehrenfeucht-Fraïssé game, $$M|_{\sigma^*}$$ and $$N|_{\sigma^*}$$ are $$L_{\infty,\omega}(\sigma^*)$$-equivalent.
A model of $$\Psi\cup \{\varphi\}$$ is a model $$M$$ of $$\Psi$$ together with an injective function $$f\colon M\to M$$ which maps $$P$$ into $$\lnot P$$. This is satisfiable, e.g. by taking $$P$$ to be $$\omega_1$$, with $$c_\alpha = \alpha$$, taking $$\lnot P$$ to be a disjoint set $$X$$ of size $$\aleph_1$$, and taking $$f = g\cup g^{-1}$$, where $$g$$ is a bijection $$X\to \omega_1$$.
A model of $$\Psi\cup \{\varphi'\}$$ is a model $$M$$ of $$\Psi$$ such that every element of $$\lnot P$$ is named by some constant $$d_n$$. This is satisfiable, e.g. by taking $$P$$ to be $$\omega_1$$, with $$c_\alpha = \alpha$$, taking $$\lnot P$$ to be a disjoint countably infinite set, each element of which is the interpretation of one of the constants $$d_n$$.
But $$\Psi\cup \{\varphi,\varphi'\}$$ is not satisfiable, because $$\varphi$$ forces $$\lnot P$$ to be uncountable, while $$\varphi'$$ forces $$\lnot P$$ to be countable.