Craig-Lyndon Interpolation Theorem

College Depth 60 in the knowledge graph I know this Set as goal
Unlocks 2 downstream topics
Craig interpolation interpolant consequence

Core Idea

If φ → ψ is a tautology, there exists an interpolant θ (using only symbols common to φ and ψ) such that φ → θ and θ → ψ are both tautologies. The Lyndon version strengthens this: the interpolant can be chosen to preserve the direction of implications in formulas. Interpolation theorems are fundamental for studying definability and relationships between formulas.

Explainer

You already understand Craig interpolation from your prerequisite: when φ logically entails ψ, there is an interpolant θ using only the vocabulary shared by both, with φ ⊨ θ and θ ⊨ ψ. The Craig-Lyndon theorem refines this result by imposing an additional constraint on the interpolant — one that encodes not just *which* predicate symbols appear, but *how* they appear directionally.

The Lyndon strengthening concerns polarity. In a formula, a predicate symbol can appear positively (in a context where increasing its extension can only help the formula hold — for instance, not under any negation), negatively (where decreasing its extension helps), or both. The Lyndon refinement says the 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. This is a strictly stronger claim than bare Craig interpolation: the vocabulary constraint remains, but now the *directional role* of each shared symbol is also preserved.

Why does this refinement matter? In formal verification, modal logic, and definability theory, polarity carries semantic weight: a predicate appearing only positively is monotone in that position. The Lyndon version guarantees that the interpolant's logical structure mirrors the polarity structure of the original entailment, which enables stronger applications. For example, the Lyndon version implies sharper definability results than Craig's version alone — when constructing an explicit definition from an implicit one, the definition can be chosen with controlled monotonicity properties.

Both versions connect to Beth definability: if a theory implicitly defines a predicate (its extension is uniquely determined by the rest of the theory in any model), then that predicate is explicitly definable using the theory's existing vocabulary. The Craig-Lyndon version strengthens this: the explicit definition can be chosen with controlled polarity. Together, these results reveal that the vocabulary-mediated structure of logical entailment is not arbitrary — there is always a principled "common content" mediating any entailment, and its internal directional structure can be isolated and expressed precisely.

Practice Questions 5 questions

Prerequisite Chain

Counting to 10Counting to 20Understanding ZeroThe Number ZeroCounting to FiveOne-to-One CorrespondenceCombining Small Groups Within 5Addition Within 10Addition Within 20Two-Digit Addition Without RegroupingTwo-Digit Addition with RegroupingAddition Within 100Repeated Addition as MultiplicationMultiplication Facts Within 100Division as Equal SharingDivision as Grouping (Measurement Division)Division: Grouping (Repeated Subtraction) ModelDivision: Fair Sharing ModelDivision as Equal SharingDivision as GroupingBasic Division FactsDivision Facts Within 100Two-Digit by One-Digit DivisionDivision with RemaindersRemainders and Quotients in DivisionDivision Word ProblemsIntroduction to Long DivisionFactors and MultiplesPrime and Composite NumbersEquivalent FractionsRelating Fractions and DecimalsDecimal Place ValueReading and Writing DecimalsComparing and Ordering DecimalsAdding and Subtracting DecimalsMultiplying DecimalsDividing DecimalsDividing FractionsMixed Number ArithmeticOrder of OperationsInteger Order of OperationsVariable ExpressionsThe Distributive PropertyVariables and Expressions ReviewIntroduction to PolynomialsAdding and Subtracting PolynomialsMultiplying PolynomialsFactorialPermutationsCombinationsCounting Principles: Addition and Multiplication RulesIntroduction to Graph TheoryPropositional Logic FoundationsLogical Inference and Proof RulesProof Strategies in Discrete MathematicsSoundness and Completeness of Propositional LogicCompactness Theorem for Propositional LogicCompactness Theorem for First-Order LogicBasic Model TheoryCraig Interpolation TheoremCraig-Lyndon Interpolation Theorem

Longest path: 61 steps · 284 total prerequisite topics

Prerequisites (2)

Leads To (1)