Intermediate logic

From Wikipedia, the free encyclopedia

In mathematical logic, an intermediate logic (also called superintuitionistic) is a propositional logic extending intuitionistic logic. Classical logic is the strongest consistent intermediate logic, whence the name (the logics are intermediate between intuitionistic logic and classical logic).

There is a continuum of different intermediate logics. Specific intermediate logics are often constructed by adding one or more axioms to intuitionistic logic (IPC), or by a semantical description. Examples of intermediate logics include:

  • the logic of the weak excluded middle (KC, Jankov's logic, De Morgan logic): IPC + ¬¬P ∨ ¬P
  • Gödel-Dummett logic (LC): IPC + (P → Q) ∨ (Q → P)
  • Kreisel-Putnam logic: IPC + (¬P → (Q ∨ R)) → ((¬P → Q) ∨ (¬P → R))
  • Medvedev's logic of finite problems (LM or ML)
  • realizability logics
  • Scott's logic: IPC + ((¬¬P → P) → (P ∨ ¬P)) → (¬¬P ∨ ¬P)
  • Smetanich's logic: IPC + (¬Q → P) → (((P → Q) → P) → P)

The tools for studying intermediate logics are similar to those used for intuitionistic logic, such as Kripke semantics. For example, Gödel-Dummett logic has a simple semantic characterization in terms of total orders.

[edit] Semantics

Given a Heyting algebra γ, the set of propositional formulas that are valid on γ is an intermediate logic. Conversely, given an intermediate logic it is possible to construct its Lindenbaum algebra which would be a Heyting algebra.

An intuitionistic Kripke frame F is a partially ordered set, and Kripke model M is a Kripke frame with valuation such that \{x\mid M,x\Vdash p\} is an upper subset of F. The set of propositional formulas that are valid in F is an intermediate logic. Given an intermediate logic Σ it is possible to construct a Kripke model M such that the logic of M is Σ (this construction is called canonical model). A Kripke frame with this property may not exist, but a general frame always does.

[edit] Relation to modal logics

Main article: Modal companion

Let A be a propositional formula. The Gödel-Tarski translation of A is defined recursively as follows:

  • T(p_n) = \Box p_n
  • T(\neg A) = \Box \neg T(A)
  • T(A \and B) = T(A) \and T(B)
  • T(A \vee B) = T(A) \vee T(B)
  • T(A \to B) = \Box (T(A) \to T(B))

If Λ is a modal logic extending S4 then ρΛ = {A | T(A) ∈ Λ} is an intermediate logic, and Λ is called a modal companion of ρΛ. In particular:

  • IPC = ρS4
  • KC = ρS4.2
  • LC = ρS4.3
  • CPC = ρS5

For every intermediate logic Σ there are many modal logics Λ such that Σ = ρΛ.

[edit] References

  • Toshio Umezawa. On logics intermediate between intuitionistic and classical predicate logic. Journal of Symbolic Logic, 24(2):141–153, June 1959.
  • Alexander Chagrov, Michael Zakharyaschev. Modal Logic. Oxford University Press, 1997.
Retrieved from "http://en.wikipedia.org../../../i/n/t/Intermediate_logic.html"
In other languages