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?
$\begingroup$
$\endgroup$
1
-
$\begingroup$ Would you consider B to be an intermediate between A and B? $\endgroup$ – Elchanan Solomon Dec 15 '11 at 19:15
Add a comment
|
$\begingroup$
$\endgroup$
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.
