Syntactics of Intermediate Logics
In the study of formal systems, intermediate logics occupy the space between intuitionistic logic and classical logic. Most of these systems are constructed by taking intuitionistic propositional calculus (IPC)—also referred to as Int, IL, or H—and adding one or more specific axioms to it. By introducing these additional principles, logicians can create a variety of systems that vary in strength and properties.
Key Facts
- Intermediate logics are formed by adding axioms to Intuitionistic Propositional Calculus (IPC).
- Classical Logic is the most well-known intermediate logic, achieved by adding the Principle of Excluded Middle (PEM) or Double-Negation Elimination (DNE) to IPC.
- Many intermediate logics, such as Gödel-Dummett logic and Jankov's logic, provide different strengths of linearity or negation.
- Certain logics are defined by structural constraints, such as bounded depth or bounded width.
- The Disjunction Property (DP) is a key characteristic held by logics like Scott's logic (SL) and Kreisel-Putnam logic (KP).
Classical Logic and its Equivalents
Classical logic (CPC, Cl, or CL) is the most prominent extension of IPC. It can be defined by adding any one of several equivalent axioms. The most common include Double-negation elimination (DNE), where $\neg\neg p \to p$; the Principle of excluded middle (PEM), where $p \vee \neg p$; or Consequentia mirabilis, where $(\neg p \to p) \to p$.
There are several generalized variants that are equivalent to these principles over intuitionistic logic. These include Peirce's principle (PP), the inverse contraposition principle, and variants of material implication such as $p \vee (p \to q)$.
[ไม่มีภาพประกอบ]
Notable Intermediate Logics
Beyond classical logic, several distinct systems exist, each introducing unique logical behaviors.
Gödel-Dummett Logic (LC or G)
This logic is characterized by the Dirk Gently’s principle (DGP), also known as linearity: $(p \to q) \vee (q \to p)$. It can also be expressed through a form of independence of premise (IP) or a generalized 4th De Morgan's law.
Jankov's Logic (KC)
Also known as De Morgan logic, KC is defined by the weak Principle of Excluded Middle (WPEM): $\neg\neg p \vee \neg p$. It also validates the 4th De Morgan's law and a specific form of double-negation shift.
Other Specialized Logics
- Smetanich's logic (SmL): Defined by a conditional version of Peirce's principle.
- Scott's logic (SL): Defined by a conditional version of WPEM.
- Kreisel-Putnam logic (KP): Defined by a specific variant of the independence of premise involving negation.
Logics of Bounded Structure
Some intermediate logics are defined by restricting the structural properties of their underlying frames, such as depth, cardinality, or width.
| Logic Type | Notation | Defining Characteristic |
|---|---|---|
| Bounded Depth | BDn | Restricts the maximum depth of the logical frame. |
| Gödel n-valued | Gn | Combination of LC and BDn-1. |
| Bounded Cardinality | BCn | Limits the number of elements in the frame. |
| Bounded Top Width | BTWn | Restricts the width of the top of the frame. |
| Bounded Width | BWn / BAn | Limits the size of anti-chains (Ono, 1972). |
| Bounded Branching | Tn / BBn | Restricts the branching factor (Gabbay & de Jongh, 1974). |
Realizability and the Disjunction Property
Realizability logics, such as Medvedev's logic of finite problems (LM or ML), are defined semantically using frames of Boolean hypercubes without a top element. It is currently unknown if LM is recursively axiomatizable.
A significant property in these systems is the Disjunction Property (DP), which states that if a logic proves $p \vee q$, it must prove either $p$ or $q$. This property is held by SL, KP, Kleene realizability logic, and strong Medvedev's logic. However, any consistent theory that validates WPEM but remains independent when assuming PEM cannot possess the DP.
Frequently Asked Questions
What is the relationship between IPC and Classical Logic?
Classical logic is an extension of Intuitionistic Propositional Calculus (IPC). It is created by adding axioms like the Principle of Excluded Middle (PEM) or Double-Negation Elimination (DNE) to the base intuitionistic system.
What is the Disjunction Property (DP)?
The Disjunction Property is a characteristic of certain logics where, if the system proves a disjunction (p or q), it must be able to prove at least one of the individual components (either p or q) independently.
How does Gödel-Dummett logic differ from IPC?
Gödel-Dummett logic (LC) adds the principle of linearity, $(p \to q) \vee (q \to p)$, to IPC, making it stronger than intuitionistic logic but weaker than classical logic.
What are bounded depth logics?
Bounded depth logics (BDn) are intermediate logics where the depth of the frames is restricted to a specific integer n, preventing infinite chains of logical implications.
Is Medvedev's logic recursively axiomatizable?
No, it is currently not known whether Medvedev's logic of finite problems (LM) can be recursively axiomatized.