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

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.

• I think it's an elegant counterexample, thanks. Just a question: how can the interpretaion of notP be a singleton in the second e.g.? I think it must be a countable set disjoint from omega, am I wrong? Dec 21, 2021 at 6:14
• @UmbertoCavasinni I never said the $d_n$ name distinct element. But of course there's also a model in which they are distinct, as you suggest. Dec 21, 2021 at 12:29
• Indeed, but I'm not referring to the $d_n$, but to the fact that $\lnot P$ cannot be $\{*\}$ because it has to be infinite. Otherwise I'm missing something. Dec 21, 2021 at 16:07
• @UmbertoCavasinni Oh, you're absolutely right, sorry! I'll fix it. Dec 21, 2021 at 16:21
• @UmbertoCavasinni yes, I believe so. Jan 17, 2022 at 21:22