Craig interpolation guarantees an interpolant θ using only shared vocabulary when φ ⊨ ψ. What does the Lyndon strengthening add to this guarantee?
AThe interpolant θ may use vocabulary from φ or ψ exclusively, relaxing the shared-vocabulary requirement
BThe Lyndon version guarantees the interpolant is logically equivalent to both φ and ψ, not merely implied by one and implying the other
CThe interpolant can be chosen so that any predicate occurring positively in θ occurs positively in both φ and ψ, and any predicate occurring negatively in θ occurs negatively in both
DThe Lyndon version eliminates the need for an interpolant by providing a direct constructive proof of φ → ψ
Craig's theorem restricts vocabulary: θ uses only symbols shared by φ and ψ. Lyndon adds a polarity constraint on top of this: shared symbols must appear in θ with the same directional role they have in both φ and ψ. A predicate appearing positively in θ must appear positively in both φ and ψ; similarly for negative occurrences. This is strictly stronger — every Lyndon interpolant is a Craig interpolant, but not every Craig interpolant satisfies the Lyndon polarity condition.
Question 2 Multiple Choice
Why does polarity preservation in the Lyndon interpolant matter beyond being a technical refinement of Craig's theorem?
AIt reduces the computational complexity of finding the interpolant from exponential to polynomial
BIt ensures the interpolant is always a Horn clause, making it efficiently computable
CControlled polarity enables sharper definability results: explicit definitions derived from implicit ones can be chosen with controlled monotonicity properties that Craig interpolation alone cannot guarantee
DIt eliminates quantifier alternations in the interpolant, simplifying its logical structure
Polarity encodes monotonicity: a predicate appearing only positively is monotone increasing in that position — adding elements to its extension can only help the formula hold. The Lyndon theorem guarantees the interpolant preserves this structure. This has direct consequences for Beth definability: when constructing an explicit definition from an implicit one, the Lyndon version guarantees the definition has controlled monotonicity properties. Craig interpolation restricts vocabulary but leaves the directional behavior of that vocabulary unconstrained.
Question 3 True / False
Craig interpolation applies primarily to propositional logic and can seldom be extended to first-order logic.
TTrue
FFalse
Answer: False
Craig interpolation applies to first-order logic. Craig's original 1957 result was proven for first-order logic; propositional logic is a special case. Both the Craig and Craig-Lyndon versions hold in first-order settings, where the theorem is fundamental to model theory — connecting to Beth definability, completeness results, and the structural properties of logical entailment between theories.
Question 4 True / False
The Craig-Lyndon theorem is strictly stronger than Craig's theorem: every Lyndon interpolant satisfies Craig's vocabulary condition, but a Craig interpolant need not satisfy the Lyndon polarity condition.
TTrue
FFalse
Answer: True
This is the precise logical relationship between the two results. Craig guarantees: an interpolant exists using only shared vocabulary. Lyndon guarantees: an interpolant exists using shared vocabulary AND with polarity constraints respected. Any interpolant satisfying the Lyndon condition automatically satisfies Craig (it uses shared vocabulary), but an interpolant guaranteed only by Craig might have predicates appearing in the wrong polarity. The Lyndon theorem makes strictly more promises about the interpolant's internal logical structure.
Question 5 Short Answer
In your own words, what does it mean for a predicate symbol to appear 'positively' in a formula, and why does the Lyndon theorem's polarity constraint make it a stronger result than Craig's original theorem?
Think about your answer, then reveal below.
Model answer: A predicate occurs positively in a formula if it appears in a context where extending its interpretation (adding more elements that satisfy it) can only help the formula be satisfied — roughly, not under an odd number of negations. It occurs negatively when restricting its interpretation helps. Craig's theorem constrains only which symbols appear in the interpolant (shared vocabulary). Lyndon additionally constrains how they appear: positively-occurring symbols in the interpolant must occur positively in both φ and ψ. This preserves the monotonicity structure of the entailment, which Craig interpolation leaves unconstrained.
The practical consequence: in formal verification and definability theory, monotonicity (positive polarity) is a useful structural property. A formula monotone in predicate P is preserved when P's extension grows, enabling certain inference rules and optimizations. The Lyndon theorem guarantees the 'common content' of an entailment can be expressed while respecting these directional constraints. This is what enables the stronger Beth-definability applications mentioned in the explainer — the explicit definition can be chosen with controlled monotonicity, not merely with controlled vocabulary.