Craig interpolants for inifinite set of implications

Question

Suppose we have an infinite set of first-order sentences $\{\alpha_i\}_{i=1}^{\omega}$ and first-order sentence $\beta$ such that for all $i$,

\begin{align*} \alpha_i \vDash \beta \end{align*}

I wonder if there is always a sentence $\theta$ satisfying the following two conditions:

1. For all $i$, $\alpha_i\vDash \theta$ and $\theta\vDash\beta$
2. $ns(\theta)\subseteq \bigcup_i ns(\alpha_i) \cap ns(\beta)$, where $ns(\phi)$ is a set of all non-logical symbols occuring in $\phi$

This is obviously true for any finite set of $\alpha_i$, as $\theta$ is simply a Craig interpolant of $\bigvee_{i=1}^n \alpha_i$ and $\beta$. Does it hold in the countable case?

Answer 1

Here is a counterexample. $f$ is a unary function symbol, $a$ and $b$ are constant symbols, and $R$ is a unary relation symbol.

For $n\geq 1$, let $\alpha_n$ be the sentence $$f^n(a) = b$$

Let $\beta$ be the sentence $$\forall x\, (R(x) \rightarrow R(f(x))) \rightarrow (R(a)\rightarrow R(b)).$$

For any $n$, $\alpha_n$ itself serves as an interpolant between $\alpha_n$ and $\beta$. But there is no sentence $\theta$ as desired in your question.

Proof: Suppose for contradiction that we have such a sentence $\theta$. For every $n$, let $M_n\models \alpha_n$ be a structure in the vocabulary $(f,a,b)$ such that $f^n(a) = b$, but $f^m(a)\neq b$ for all $m<n$. Since $\alpha_n\models \theta$ for all $n$, also $M_n\models \theta$. By compactness, the theory $\{\theta\}\cup \{f^n(a) \neq b\}$ is consistent. Let $N$ be a model. Now expand $N$ to a structure $N'$ in the vocabulary $(f,a,b,R)$ by interpreting $R^{N'} = \{f^n(a)\mid n\in \mathbb{N}\}$. So $N\models \forall x\, (R(x)\rightarrow R(f(x)))$, and $N\models R(a)$, but $N\not\models R(b)$. That is, $N\not\models \beta$. This contradicts our assumption that $\theta\models \beta$.

Answer 2

I'd like to provide an intuition behind Alex's answer.

First, rename $a \rightarrow 0, b \rightarrow w, f \rightarrow s$. Let's see, what we get:

Vocabulary: $<0,s,R,w>$

The formulae become: $$\alpha_i: s(s(s(...(0)...) = w$$ $$\beta: R(0) \wedge \forall x(R(x) \rightarrow R(s(x))) \rightarrow R(w) $$

Now the idea becomes clear: we consider a language of arithmetic with unary relation symbol $R$, $\alpha_i$ informally states that $w$ is a natural number, $\beta$ is very close to the induction principle.

The proof is closely related to construction of non-standard model of arithmetic.

The counterexample is a non-standard model of arithmetic M, where 0 is interpreted as zero, $s$ is a successor function, and $w$ is some non-standard integer. Relation $R(x)$ is nothing but "$x$ - is a natural number". Of course, $M \models \theta$ must hold too.

Hope it helps!