Let $Fv[\phi]$ be the free variables of $\phi$. Suppose there are 2 formulas $A,B$ such that $Fv[A] \subseteq \{x,y\}$ and $Fv[B] \subseteq \{x,y\}$.

Prove/Disprove: $T \nvdash A\wedge B$ iff there exists a structure $M$ such that $M\models T \cup \neg(A\wedge B)$

I'm pretty sure it is wrong. My reasoning is that if that even though there is no structure such that when $ M \models T$, then $M \models A \wedge B$, that doesn't necessarily mean that there is no variable assignment $v$ such that $M, v \models A \wedge B$. So what we need is formulas such that for each structure $M$ that models $T$ there exists an assignment $v_1$ such that $M, v_1 \models A \wedge B$, and also and assignment $v_2$ such that $M, v_2 \not\models A \wedge B$. However, I cannot find such formulas and I'd like an example.



Found a counterexample:

$$T= \emptyset$$

$$ A = B = p(x)\vee\neg p(y)$$

works here

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.