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?

Best Answer

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.

Related Question