2

Let $\lbrace\varphi_n\rbrace_{n\geq 1}$ be a sequence of semantically inequivalent formulas s.t. $\vDash \varphi_{n+1} \to \varphi_{n}$. Is there a formula $\psi$ s.t. $(\lbrace\varphi_n\rbrace_{n\geq 1}\vDash \psi) \land (\forall n\geq 1.\psi\vDash \varphi_{n})$?

I think there is no such $\psi$ but I can't formulate the proof quite yet. By assuming such $\psi$ exists and using compactness theorem we can have a finite subset $\Delta \subset \lbrace\varphi_n\rbrace_{n\geq 1}$ s.t. $\forall n\geq 1.\Delta \vDash \varphi_{n}$ but I can't see where does a contradiction suppose to come from.

gbi1977
  • 389
  • What do you mean by $\lbrace\varphi_n\rbrace_{n\geq 1}\vDash \psi \land \forall n\geq 1.\psi\vDash \varphi_{n}$? It doesn't appear to be well formed to me, because there are two $\vDash$ symbols in the same line. Do you mean $(\lbrace\varphi_n\rbrace_{n\geq 1}\vDash \psi )\land( \forall n\geq 1.\psi\vDash \varphi_{n})$? – user400188 Dec 06 '20 at 21:26
  • @user400188 yes. I'll edit. Explicitly put $\psi$ is semantically entailed from the infinite set of $\varphi_{n}$ and semantically entails any $\varphi_{n}$ – gbi1977 Dec 06 '20 at 21:34
  • One last question, (more for my own sake than for readability of the question), by "syntactical equivalence" of two formulas, do you mean provable equivalence $\dashv\vdash$, or that the formulas are the same strings? – user400188 Dec 06 '20 at 21:49
  • @user400188 The same strings – gbi1977 Dec 06 '20 at 21:52
  • 2
    @gbi1977 Are you sure, that by "syntactically inequivalent" you just meanthat they are different strings? Because, if so, there is an easy example of the described result holding: just take a propositional variable $p$, $\varphi_{n}=\bigwedge_{i=1}^{n}p$ and $\psi=p$. – GVT Feb 15 '21 at 17:21
  • @GVT Yes, in hindsight it does seem like it should have meant semantically inequivalent. I'll edit the question. – gbi1977 Feb 15 '21 at 23:40
  • 1
    @gbi1977 Thank you! Now you have answers to both cases: if "inequivalent" refers merely to different strings, I gave an example in comments to the result and a counterexample in my answer; if it refers to semantically, and syntactically, inequivalence, my counterexample still works, but you also have Noah Schweber's sharper answer, proving there are no cases in which the result holds. – GVT Feb 16 '21 at 15:02

2 Answers2

1

I believe this counts as a counterexample, although things will probably become clearer if the original poster clarifies some minor points I asked about in the comments.

So, take the set of all propositional variables to be $\{p_{n} : n\in\mathbb{N}\setminus\{0\}\}$ and define $$\varphi_{n}=\bigwedge_{i=1}^{n}p_{i};$$ they are certainly inequivalent, and also satisfy $\vDash\varphi_{n+1}\rightarrow\varphi_{n}$ (actually $\varphi_{m}\vDash\varphi_{n}$ for every $m\geq n$). But there can not be any formula $\psi$ satisfying the desired properties: if $\psi\vDash\varphi_{n}$, for every $n\geq 1$, let $p_{i_{1}}, ... , p_{i_{n}}$ be the variables in $\psi$; if $\psi$ is not a contradiction, take a valuation $\nu$ such that $\nu(\psi)=1$ and define $\nu'$ such that $\nu'(p_{i})=\nu(p_{i})$, for $i\leq M=\max\{i_{1}, ... , i_{n}\}$, and $\nu'(p_{i})=0$ for $i>M$. Then $\nu'(\psi)=1$ but $\nu(\varphi_{i})=0$, for $i>M$, so we must have that $\psi$ is a contradiction.

But then you cannot have $\{\varphi_{n} : n\in\mathbb{N}\setminus\{0\}\}\vDash\psi$: take the valuation $\nu$ such that $\nu(p_{i})=1$, for every $i\in\mathbb{N}\setminus\{0\}$, and it is clear that $\nu(\psi)=0$ but $\nu(\varphi_{i})=1$, for every $i\geq 1$.

GVT
  • 518
0

Below I'm assuming that "syntactically inequivalent" is a typo for "semantically inequivalent," since otherwise as GVT commented above the problem is trivial.

In fact, there can never be such a $\psi$ - essentially, no nontrivial infinite conjunction is ever expressible by a first-order sentence.

To see this, suppose otherwise and consider the theory $$T=\{\neg\psi\}\cup\{\varphi_i:i\in\mathbb{N}\}.$$ If this is finitely satisfiable, then by compactness it is satisfiable and any model of $T$ witnesses $\{\varphi_i:i\in\mathbb{N}\}\not\models\psi$. So we just need to show that $T$ is finitely satisfiable.

Suppose $T_0\subset T$ is finite. WLOG, $T_0$ has the form $\{\neg\psi\}\cup\{\varphi_i: i\le n\}$ for some $n$. By assumption on the $\varphi_i$s, this is semantically equivalent to the sentence $\neg\psi\wedge\varphi_n$. Now if $\neg\psi\wedge\varphi_n$ were unsatisfiable, this would mean $\varphi_n\models\psi$. But since $\psi\models\varphi_i$ for every $i\in\mathbb{N}$ this would give e.g. $\varphi_n\models\varphi_{n+1}$, which - since $\varphi_{n+1}\models\varphi_n$ by assumption - would imply $\varphi_n\equiv\varphi_{n+1}$, contradicting the assumed inequivalence.

(Note that I'm writing e.g. "$\varphi_{n+1}\models\varphi_n$" instead of "$\models\varphi_{n+1}\rightarrow\varphi_n$." Of course, these are equivalent, and I find the former easier to think about.)

Noah Schweber
  • 245,398