3
$\begingroup$

Let us consider a first-order predicate (or a propositional formula) K to be "intermediate" between A and B iff it is weaker than A and stronger than B (thus, A logically entails B). Does always exist a Craig interpolant I of A and B such that I is logically equivalent to K? In other words, are Craig interpolants sufficient to represent all intermediate predicates?

$\endgroup$
1
  • $\begingroup$ Would you consider B to be an intermediate between A and B? $\endgroup$ – Elchanan Solomon Dec 15 '11 at 19:15
2
$\begingroup$

I have found the answer of the question by myself, and (of course) is no. A trivial example is A = false and B = true, whose only Craig interpolants are A and B themselves. In this case, any formula K is intermediate between A and B. More generally, if A and B are two PL formulas, B is a logical consequence of A, and A and B are not logically equivalent, K $\stackrel{def}{=}$ (x $\land$ A) $\lor$ ($\neg$ x $\land$ B) is intermediate between A and B for a propositional letter x not occurring in both A and B. Indeed, it is A $\Rightarrow$ K, K $\Rightarrow$ B, but K has different truth value in at least a pair of assignments which differ only by the truth value of x (otherwise, A and B would be logically equivalent). Therefore, no interpolant exists which is logically equivalent to K.

$\endgroup$

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.