Una fórmula satisfacible a partir de una secuencia infinita de fórmulas

Question

Dejemos que $\lbrace\varphi_n\rbrace_{n\geq 1}$ sea una secuencia de fórmulas semánticamente no equivalentes s.t. $\vDash \varphi_{n+1} \to \varphi_{n}$ . ¿Existe una fórmula $\psi$ s.t. $(\lbrace\varphi_n\rbrace_{n\geq 1}\vDash \psi) \land (\forall n\geq 1.\psi\vDash \varphi_{n})$ ?

Creo que no existe tal $\psi$ pero todavía no puedo formular la prueba. Suponiendo que tal $\psi$ existe y utilizando el teorema de la compacidad podemos tener un subconjunto finito $\Delta \subset \lbrace\varphi_n\rbrace_{n\geq 1}$ s.t. $\forall n\geq 1.\Delta \vDash \varphi_{n}$ pero no veo de dónde se supone que viene una contradicción.

Answer 1

Creo que esto cuenta como un contraejemplo, aunque probablemente las cosas se aclaren si el cartel original aclara algunos puntos menores sobre los que pregunté en los comentarios.

Entonces, tomemos el conjunto de todas las variables proposicionales como $\{p_{n} : n\in\mathbb{N}\setminus\{0\}\}$ y definir $$\varphi_{n}=\bigwedge_{i=1}^{n}p_{i};$$ son ciertamente no equivalentes, y también satisfacen $\vDash\varphi_{n+1}\rightarrow\varphi_{n}$ (en realidad $\varphi_{m}\vDash\varphi_{n}$ por cada $m\geq n$ ). Pero no puede haber ninguna fórmula $\psi$ que satisface las propiedades deseadas: si $\psi\vDash\varphi_{n}$ para cada $n\geq 1$ , dejemos que $p_{i_{1}}, ... , p_{i_{n}}$ sean las variables en $\psi$ ; si $\psi$ no es una contradicción, tome una valoración $\nu$ tal que $\nu(\psi)=1$ y definir $\nu'$ tal que $\nu'(p_{i})=\nu(p_{i})$ , para $i\leq M=\max\{i_{1}, ... , i_{n}\}$ y $\nu'(p_{i})=0$ para $i>M$ . Entonces $\nu'(\psi)=1$ pero $\nu(\varphi_{i})=0$ , para $i>M$ , por lo que debemos tener que $\psi$ es una contradicción.

Pero entonces no puedes tener $\{\varphi_{n} : n\in\mathbb{N}\setminus\{0\}\}\vDash\psi$ : tomar la valoración $\nu$ tal que $\nu(p_{i})=1$ para cada $i\in\mathbb{N}\setminus\{0\}$ y está claro que $\nu(\psi)=0$ pero $\nu(\varphi_{i})=1$ para cada $i\geq 1$ .

Answer 2

A continuación asumo que "sintácticamente no equivalente" es una errata en lugar de "semánticamente no equivalente", ya que de lo contrario, como comentó GVT más arriba, el problema es trivial.

---

De hecho, nunca puede haber tal $\psi$ - esencialmente, ninguna conjunción infinita no trivial es expresable por una oración de primer orden.

Para ver esto, supongamos lo contrario y consideremos la teoría $$T=\{\neg\psi\}\cup\{\varphi_i:i\in\mathbb{N}\}.$$ Si esto es finitamente satisfacible, entonces por compacidad es satisfacible y cualquier modelo de $T$ testigos $\{\varphi_i:i\in\mathbb{N}\}\not\models\psi$ . Así que sólo tenemos que demostrar que $T$ es finitamente satisfacible.

Supongamos que $T_0\subset T$ es finito. WLOG, $T_0$ tiene la forma $\{\neg\psi\}\cup\{\varphi_i: i\le n\}$ para algunos $n$ . Por la suposición de la $\varphi_i$ s, esto es semánticamente equivalente a la frase $\neg\psi\wedge\varphi_n$ . Ahora bien, si $\neg\psi\wedge\varphi_n$ fueran insatisfacibles, esto significaría que $\varphi_n\models\psi$ . Pero como $\psi\models\varphi_i$ por cada $i\in\mathbb{N}$ esto daría, por ejemplo $\varphi_n\models\varphi_{n+1}$ que - desde $\varphi_{n+1}\models\varphi_n$ por supuesto - implicaría $\varphi_n\equiv\varphi_{n+1}$ contradiciendo la supuesta falta de equivalencia.

(Tenga en cuenta que estoy escribiendo, por ejemplo, " $\varphi_{n+1}\models\varphi_n$ " en lugar de " $\models\varphi_{n+1}\rightarrow\varphi_n$ ." Por supuesto, son equivalentes, y me resulta más fácil pensar en la primera).