Craig interpolation

Craig interpolation In mathematical logic, Craig's interpolation theorem is a result about the relationship between different logical theories. Roughly stated, the theorem says that if a formula φ implies a formula ψ, and the two have at least one atomic variable symbol in common, then there is a formula ρ, called an interpolant, such that every non-logical symbol in ρ occurs both in φ and ψ, φ implies ρ, and ρ implies ψ. The theorem was first proved for first-order logic by William Craig in 1957. Variants of the theorem hold for other logics, such as propositional logic. A stronger form of Craig's interpolation theorem for first-order logic was proved by Roger Lyndon in 1959;[1][2] the overall result is sometimes called the Craig–Lyndon theorem.

Conteúdo 1 Exemplo 2 Lyndon's interpolation theorem 3 Proof of Craig's interpolation theorem 4 Formulários 5 Referências 6 Further reading Example In propositional logic, deixar {displaystyle varphi =lnot (Pland Q)para (lnot Rland Q)} {displaystyle psi =(Sto P)lor (Sto lnot R)} .

Então {estilo de exibição varphi } tautologically implies {estilo de exibição psi } . This can be verified by writing {estilo de exibição varphi } in conjunctive normal form: {displaystyle varphi equiv (Plor lnot R)land Q} .

Desta forma, E se {estilo de exibição varphi } detém, então {displaystyle Plor lnot R} detém. Por sua vez, {displaystyle Plor lnot R} tautologically implies {estilo de exibição psi } . Because the two propositional variables occurring in {displaystyle Plor lnot R} occur in both {estilo de exibição varphi } e {estilo de exibição psi } , Isso significa que {displaystyle Plor lnot R} is an interpolant for the implication {displaystyle varphi to psi } .

Lyndon's interpolation theorem Suppose that S and T are two first-order theories. As notation, let S ∪ T denote the smallest theory including both S and T; the signature of S ∪ T is the smallest one containing the signatures of S and T. Also let S ∩ T be the intersection of the languages of the two theories; the signature of S ∩ T is the intersection of the signatures of the two languages.

Lyndon's theorem says that if S ∪ T is unsatisfiable, then there is an interpolating sentence ρ in the language of S ∩ T that is true in all models of S and false in all models of T. Além disso, ρ has the stronger property that every relation symbol that has a positive occurrence in ρ has a positive occurrence in some formula of S and a negative occurrence in some formula of T, and every relation symbol with a negative occurrence in ρ has a negative occurrence in some formula of S and a positive occurrence in some formula of T.

Proof of Craig's interpolation theorem We present here a constructive proof of the Craig interpolation theorem for propositional logic.[3] Formalmente, the theorem states: If ⊨φ → ψ then there is a ρ (the interpolant) such that ⊨φ → ρ and ⊨ρ → ψ, where atoms(r) ⊆ atoms(Phi) ∩ atoms(ψ). Here atoms(Phi) is the set of propositional variables occurring in φ, and ⊨ is the semantic entailment relation for propositional logic.

Prova. Assume ⊨φ → ψ. The proof proceeds by induction on the number of propositional variables occurring in φ that do not occur in ψ, denotado |atoms(Phi) − atoms(ψ)|.

Base case |atoms(Phi) − atoms(ψ)| = 0: Desde |atoms(Phi) − atoms(ψ)| = 0, we have that atoms(Phi) ⊆ atoms(Phi) ∩ atoms(ψ). Moreover we have that ⊨φ → φ and ⊨φ → ψ. This suffices to show that φ is a suitable interpolant in this case.

Let’s assume for the inductive step that the result has been shown for all χ where |atoms(χ) − atoms(ψ)| = n. Agora suponha que |atoms(Phi) − atoms(ψ)| = n+1. Pick a q ∈ atoms(Phi) but q ∉ atoms(ψ). Now define: φ' := f[⊤/q] ∨ φ[⊥/q] Here φ[⊤/q] is the same as φ with every occurrence of q replaced by ⊤ and φ[⊥/q] similarly replaces q with ⊥. We may observe three things from this definition: ⊨φ' → ψ (1) |atoms(φ') − atoms(ψ)| = n (2) ⊨φ → φ' (3) A partir de (1), (2) and the inductive step we have that there is an interpolant ρ such that: ⊨φ' → ρ (4) ⊨ρ → ψ (5) But from (3) e (4) we know that ⊨φ → ρ (6) Por isso, ρ is a suitable interpolant for φ and ψ.

QED Since the above proof is constructive, one may extract an algorithm for computing interpolants. Using this algorithm, if n = |atoms(φ') − atoms(ψ)|, then the interpolant ρ has O(exp(n)) more logical connectives than φ (see Big O Notation for details regarding this assertion). Similar constructive proofs may be provided for the basic modal logic K, intuitionistic logic and μ-calculus, with similar complexity measures.

Craig interpolation can be proved by other methods as well. No entanto, these proofs are generally non-constructive: model-theoretically, via Robinson's joint consistency theorem: in the presence of compactness, negation and conjunction, Robinson's joint consistency theorem and Craig interpolation are equivalent. proof-theoretically, via a sequent calculus. If cut elimination is possible and as a result the subformula property holds, then Craig interpolation is provable via induction over the derivations. algebraically, using amalgamation theorems for the variety of algebras representing the logic. via translation to other logics enjoying Craig interpolation. Applications Craig interpolation has many applications, among them consistency proofs, model checking,[4] proofs in modular specifications, modular ontologies.

References ^ Lyndon, Rogério (1959), "An interpolation theorem in the predicate calculus", Jornal do Pacífico de Matemática, 9: 129-142, doi:10.2140/pjm.1959.9.129. ^ Troelstra, Anne Sjerp; Schwichtenberg, Helmut (2000), Basic Proof Theory, Cambridge tracts in theoretical computer science, volume. 43 (2ª edição), Cambridge University Press, p. 141, ISBN 978-0-521-77911-1. ^ Harrison pgs. 426–427 ^ Vizel, Y.; Weissenbacher, G.; Malik, S. (2015). "Boolean Satisfiability Solvers and Their Applications in Model Checking". Anais do IEEE. 103 (11): 2021–2035. doi:10.1109/JPROC.2015.2455034. S2CID 10190144. Further reading John Harrison (2009). Handbook of Practical Logic and Automated Reasoning. Cambridge, Nova york: Cambridge University Press. ISBN 978-0-521-89957-4. Hinman, P. (2005). Fundamentos de lógica matemática. A K Peters. ISBN 1-56881-262-0. Dov M. Gabbay; Larisa Maksimova (2006). Interpolation and Definability: Modal and Intuitionistic Logics (Guias de lógica de Oxford). Oxford science publications, Clarendon Press. ISBN 978-0-19-851174-8. Eva Hoogland, Definability and Interpolation. Model-theoretic investigations. PhD thesis, Amsterdã 2001. C. Craig, Three uses of the Herbrand-Gentzen theorem in relating model theory and proof theory, O Diário da Lógica Simbólica 22 (1957), não. 3, 269–285. Categorias: Mathematical logicLemmas