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 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:

• 
• 
• 
• 
• 

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.