Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
Would you consider B to be an intermediate between A and B? –  Isaac Solomon Dec 15 '11 at 19:15

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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