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