3
$\begingroup$

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?

$\endgroup$

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
8
  • $\begingroup$ 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? $\endgroup$ Dec 21, 2021 at 6:14
  • 1
    $\begingroup$ @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. $\endgroup$ Dec 21, 2021 at 12:29
  • $\begingroup$ 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. $\endgroup$ Dec 21, 2021 at 16:07
  • $\begingroup$ @UmbertoCavasinni Oh, you're absolutely right, sorry! I'll fix it. $\endgroup$ Dec 21, 2021 at 16:21
  • 1
    $\begingroup$ @UmbertoCavasinni yes, I believe so. $\endgroup$ Jan 17, 2022 at 21:22

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .