Fact-checked by Grok 2 weeks ago

Intermediate logic

Intermediate logic, also known as superintuitionistic logic, is a branch of consisting of propositional logics that properly extend while remaining strictly contained within . These logics form consistent axiomatic extensions of closed under substitution and , capturing intermediate degrees of deductive strength between the constructive principles of and the full bivalence of classical reasoning. The study of intermediate logics emerged in the early 20th century alongside the development of by and Arend Heyting, who sought to formalize constructive mathematics without the . In 1932, demonstrated that IPC lacks a finite characteristic matrix semantics by constructing an infinite sequence of successively stronger intermediate logics, each defined using finite many-valued semantics with increasing numbers of truth values. This result highlighted the richness of the lattice of intermediate logics, later shown by V.V. Jankov in 1968 to contain continuum many distinct logics via Jankov's theorem, which associates each finite frame with a unique intermediate logic via characteristic formulas. Semantically, intermediate logics are characterized by Kripke models that are intuitionistic frames (partially ordered sets with persistent valuations) where certain formulas are valid, but not all classical tautologies hold. Notable examples include the Gödel-Dummett logic (), which adds the linearity (p \to q) \lor (q \to p) and is complete with respect to linearly ordered Kripke frames; and the Kreisel-Putnam logic (KP), which adds the ( \neg p \to (q \lor r) ) \to ( ( \neg p \to q ) \lor ( \neg p \to r ) ) and is the maximal intermediate logic with the disjunction property. Algebraically, intermediate logics correspond to non-trivial varieties of Heyting algebras via Birkhoff's variety theorem, linking logical extensions to substructural properties of pseudoboolean algebras. These logics have applications in , interpretations (e.g., via S4 extensions), and , particularly in and realizability models.

Foundations

Definition

Intermediate logics, also known as intermediate propositional logics, form a class of superintuitionistic logics that lie strictly between intuitionistic propositional calculus (IPC) and classical propositional calculus (CPC). Formally, an intermediate logic L is a set of propositional formulas that contains all theorems of , is closed under and uniform substitution, and satisfies \text{[IPC](/page/IPC)} \subsetneq L \subsetneq \text{[CPC](/page/CPC)}, ensuring it properly extends IPC without reaching the full strength of CPC. Superintuitionistic logics represent the broader category encompassing all consistent extensions of , including both intermediate logics and itself; within this framework, intermediate logics are precisely the proper extensions of that remain properly contained in , preserving the constructive principles of while incorporating additional validities. These logics maintain closure under the standard intuitionistic rules of inference, such as (A, A \to B \vdash B) and uniform substitution, but introduce new theorems beyond those of . Any intermediate logic L can be axiomatized as IPC augmented by a set of additional axiom schemata \Gamma that are consistent with the intuitionistic rules, yielding L = \text{IPC} + \Gamma, where the schemata ensure the resulting system remains sound relative to intuitionistic semantics. This axiomatic presentation highlights how intermediate logics bridge the gap between IPC and by selectively validating certain classical principles without adopting all of them. A key distinction of intermediate logics from CPC lies in their rejection of the double negation axiom \neg \neg p \to p, which is invalid in IPC and remains absent in all intermediate logics, thereby preserving the intuitionistic interpretation of negation as refutability rather than the classical bivalence. This absence ensures that intermediate logics do not collapse to CPC, maintaining a strict hierarchy in the lattice of superintuitionistic logics.

Historical Development

The origins of intermediate logics lie in the development of during the 1920s and 1930s, spearheaded by and his student Arend Heyting. Brouwer's , articulated in works such as his 1927 address "On the Foundations of Mathematics," challenged by rejecting the and prioritizing mental constructions over abstract existence, thereby laying the groundwork for non-classical systems positioned between intuitionistic propositional logic (IPC) and classical propositional logic (CPC). Heyting formalized these ideas in his 1930 paper "Die formalen Regeln der intuitionistischen Logik," providing the first for and enabling subsequent explorations of logics extending IPC without reaching full classical strength. A pivotal milestone came in 1932 with Kurt Gödel's paper "Zum intuitionistischen Aussagenkalkül," where he introduced the concept of intermediate logics through the double-negation translation, embedding into while demonstrating an infinite sequence of such logics and proving the undecidability of certain extensions of . This work highlighted the richness of the logical space between and , showing that no finite set of truth values could characterize completely. Gödel's contributions shifted focus toward the structural properties and extensions of these systems, influencing later undecidability results. Concurrently, Georg Kreisel's work on , including his 1951 analysis of non-finitist proofs and interpretations of intuitionistic arithmetic, examined degrees of constructive strength and undecidability in systems intermediate between finitist and classical methods, emphasizing the varying "unwindability" of proofs in non-classical settings. The and saw significant progress in understanding the structure of intermediate logics, particularly through V. P. Jankov's introduction of (or Jankov) formulas in his paper and their utilization in his 1968 paper "Constructing a sequence of strongly independent superintuitionistic propositional calculi." These formulas, derived from finite frames, enabled the axiomatization of specific intermediate logics and demonstrated the existence of continuum many such logics forming a under inclusion. Jankov's approach, building on earlier frame-based methods, provided tools for classifying extensions of and analyzing their decidability and finite model properties. Post-1980s developments focused on connections to and computational aspects. Alexander Chagrov and Michael Zakharyaschev's 1997 monograph and related papers, such as their 1995 survey on modal companions, established embeddings of intermediate logics into classical modal systems like S4, revealing deep correspondences that facilitated algebraic and frame-based characterizations. Their work on the independent axiomatizability of modal and intermediate logics advanced the classification of extensions. In recent decades up to 2025, research has emphasized proof-theoretic and computational dimensions, with cut-free calculi for logics enabling automated analysis, as shown in Sergei N. Artëmov and Roman Kuznets's 2011 paper on proof analysis in these systems. Integrations with have supported verification in non-classical settings.

Semantics

Kripke Semantics

provides a possible-worlds for logics, building directly on the originally developed for intuitionistic propositional logic (). A Kripke frame for IPC is a pair (W, R), where W is a nonempty set of worlds and R is a partial order on W (reflexive and transitive). A Kripke model extends this with a valuation V assigning to each p an upset in the poset, meaning V(p) \subseteq W such that if w \in V(p) and w R v, then v \in V(p). The forcing relation \Vdash between worlds and formulas is defined inductively: for atomic p, w \Vdash p if and only if w \in V(p); w \Vdash \phi \land \psi if w \Vdash \phi and w \Vdash \psi; w \Vdash \phi \lor \psi if w \Vdash \phi or w \Vdash \psi; w \Vdash \phi \to \psi if for all v with w R v, if v \Vdash \phi then v \Vdash \psi; and w \Vdash \neg \phi if for all v with w R v, v \not\Vdash \phi. This forcing relation satisfies (or monotonicity): if w \Vdash \phi and w R v, then v \Vdash \phi, for any \phi. A \phi is valid in if it is forced at every world in every model on that frame; the logic of of frames is the set of all valid formulas therein. is precisely the logic of the class of all such Kripke frames, with and holding: a is provable in if and only if it is valid in all intuitionistic Kripke models. Kripke-complete intermediate logics extend this semantics by restricting to subclasses of Kripke frames defined by additional properties on the accessibility relation R, such as directedness (for any u, v there exists w with u R w and v R w) or (for any u, v, w with u R v and u R w, there exists x with v R x and w R x). These properties correspond to specific s: for instance, directedness validates the axiom of weak excluded middle, while relates to certain disjunction properties. While algebraic semantics applies to all intermediate logics, Kripke completeness holds only for a proper subclass of them. For Kripke-complete intermediate logics L, the class of frames validating L is elementary, meaning the class is definable by a set of sentences over the frame language. Soundness and completeness extend to Kripke-complete intermediate logics: for any such L, if a (or ) is provable in L, it is valid in all models over in the class for L; conversely, if consistent with L, it has a countermodel in that class. The class of validating L is elementary, ensuring the semantics is robust and decidable in many cases. Moreover, Kripke-complete intermediate logics, known as canonical logics, are complete with respect to their canonical . The for a Kripke-complete intermediate logic L is constructed as a Kripke model where the worlds are the L-saturated sets of formulas—maximal L-consistent sets closed under L-provable consequences and disjunctions—with the order given by inclusion (\Delta \leq \Gamma if \Delta \subseteq \Gamma). The forcing is defined by provability: \Delta \Vdash p p \in \Delta for p, extended inductively to formulas while preserving . This model serves as the "largest" model for L, validating exactly the theorems of L and providing a basis for proofs via the Lindenbaum-Tarski adapted to the poset structure.

Algebraic Semantics

Algebraic semantics for intermediate logics is provided by Heyting algebras, which serve as the algebraic models for intuitionistic propositional logic (IPC) and its extensions. A Heyting algebra is a bounded distributive equipped with a binary implication operation → satisfying the residuation condition: for all elements a, b, c, a ∧ b ≤ c if and only if a ≤ b → c. Equivalently, b → c is the maximum element x such that x ∧ b ≤ c. In this semantics, propositional variables are interpreted as elements of the algebra, and complex formulas are built using the lattice operations (∧ for , ∨ for disjunction, 0 for falsehood, 1 for truth) and → for ; negation is defined as ¬a = a → 0. A formula φ is valid in a Heyting algebra H if its interpretation [[φ]]_H equals the top element 1 under every valuation. Intermediate logics, which lie strictly between IPC and classical propositional logic, correspond to varieties of Heyting algebras—classes closed under subalgebras, homomorphic images, and products—generated by specific algebras or classes thereof. Every intermediate logic L is complete with respect to the variety Var(L) of Heyting algebras it defines: a formula ϕ belongs to L if and only if it is valid in all algebras of Var(L). For instance, extensions may involve pseudocomplemented Heyting algebras or those generated by adding relations that enforce additional s, such as those yielding intermediate principles like the Gödel-Dummett , though the full variety is determined by the logic's s. The definability theorem ensures that each such variety V is precisely the class of Heyting algebras validating the logic Log(V) generated by V. The Lindenbaum-Tarski algebra plays a central role in this framework. For , it is the free on countably many generators, representing the quotient of propositional formulas by under intuitionistic rules. For an intermediate logic L extending , the Lindenbaum-Tarski algebra is obtained by extending this with additional relations imposed by L's axioms, yielding a whose captures L's semantics. This construction ensures algebraic completeness, as the free algebra embeds the logic's theorems. Duality theory provides a deeper connection between syntax and semantics. Esakia duality establishes a dual equivalence between the category of Heyting algebras and the category of Esakia spaces—compact, totally order-disconnected topological spaces equipped with a continuous partial order. Under this duality, varieties of Heyting algebras correspond to classes of Esakia spaces closed under certain operations, and intermediate logics are reflected as subclasses of these spaces satisfying additional topological or order conditions. This Stone-type duality facilitates the study of logical properties through geometric and topological tools.

Properties

Lattice Structure

The set Int of all intermediate logics, ordered by inclusion, forms a complete distributive , with intuitionistic propositional logic () as the least element and classical propositional logic () as the greatest element. In this , the meet operation for two intermediate logics L and M is defined as their L \cap M, which consists of all formulas provable in both logics. The join L \vee M is the deductive closure of the union L \cup M, comprising all formulas that follow from axioms in either L or M using the inference rules of . This structure admits significant complexity, including uncountable ascending chains of length up to the first uncountable ordinal \omega_1, reflecting the potential for transfinite extensions in the order. The width of the is $2^{\aleph_0}, corresponding to many incomparable elements and maximal chains, which underscores the vast diversity of intermediate logics beyond countable generations. A notable sublattice consists of those intermediate logics finitely generated by finite sets of axioms over . Since the propositional language is countable, there are only countably many such finite axiom sets, yielding a countable sublattice in stark contrast to the full 's cardinality of $2^{\aleph_0}. This countable sublattice highlights the distinction between recursively axiomatizable logics and the uncountable totality of extensions. The cardinality of Int is precisely $2^{\aleph_0}, establishing that there are uncountably many intermediate logics. This result, originally due to Jankov, relies on the construction of Jankov formulas, which are characteristic formulas derived from finite rooted frames and serve to axiomatize distinct extensions of , separating the lattice into continuum many pairwise incomparable elements.

Conservativity and Extensions

Every intermediate propositional logic can be extended to an intermediate predicate logic by adding its axioms to intuitionistic predicate logic (IQC). This extension is conservative over , meaning it proves no new propositional theorems: any propositional formula provable in the predicate extension is already provable in . Intermediate predicate logics are obtained by extending intuitionistic predicate logic with the axioms of a propositional intermediate logic. The base intuitionistic predicate logic includes standard quantifier axioms, such as \forall x (\phi \to \psi) \to (\forall x \phi \to \psi) where x is not free in \psi, alongside the usual rules of and . Additional propositional axioms are then incorporated to define the specific intermediate extension. The extension problem—given intermediate logics L and M (typically specified by finite axiom sets), determining whether M extends L—is undecidable and \Pi_1^0-complete. This follows from the undecidability of recognizing whether a finite axiomatization yields a consistent superintuitionistic logic that properly extends without equaling .

Examples

Notable Intermediate Logics

One prominent example of an intermediate logic is the , often denoted as . This logic extends intuitionistic propositional logic () by adjoining the axiom schema (\phi \to \psi) \vee (\psi \to \phi), which enforces a form of in implications. is semantically characterized as the set of formulas valid on linearly ordered Kripke frames, where the accessibility relation is a , distinguishing it from the tree-like structures typical of intuitionistic semantics. Originally introduced by in his 1932 note on intuitionistic propositional calculus, captures reasoning in linearly ordered domains and serves as a bridge toward without fully embracing excluded middle. Another key intermediate logic is the Kreisel-Putnam logic, denoted KP. It arises from IPC by adding the axiom schema (\neg p \to (q \vee r)) \to ((\neg p \to q) \vee (\neg p \to r)), which addresses disjunction distribution under negation in a controlled manner. This axiom, introduced by Georg Kreisel and Hilary Putnam in 1957, ensures the logic preserves the disjunction property while allowing branching in its Kripke frames, specifically those permitting finite branching without infinite ascending chains. KP exemplifies how intermediate logics can model constructive reasoning with limited non-intuitionistic commitments, and it possesses the finite model property, aiding decidability studies. Jankov logic, often referred to as J or associated with the weak excluded middle (KC in some notations), extends with the axiom schema \neg p \vee \neg\neg p. This formula, explored by Vadim Jankov in 1968, weakens the classical by allowing a disjunction that holds constructively in certain contexts without implying full tertium non datur. Semantically, it corresponds to Kripke frames where every node has a successor satisfying the weak condition, and Jankov's work used characteristic formulas derived from finite frames to demonstrate its position among the continuum many intermediate logics. The logic highlights the role of finite frame characterizations in axiomatizing intermediate systems, rejecting full classical negation while admitting partial De Morgan-like principles. Smetanich logic, denoted SmL, is defined as the extension of IPC by the axiom schema (\neg q \to p) \to ((p \to q) \to p) \to p. This axiom, named after A. S. Smetanich, imposes a constraint on implication and negation that prevents the full adoption of excluded middle, positioning SmL as one of the strongest proper intermediate logics, equivalent to the three-valued Gödel logic or the logic of here-and-there models. In Kripke semantics, SmL is complete for two-layered frames with a total order within layers, allowing validation on structures that reject classical tautologies like q \vee \neg q while incorporating limited branching. It rejects the full law of excluded middle, as models exist where neither q nor \neg q is forced at the root, underscoring its role in equilibrium and non-monotonic reasoning applications. The family of bounded depth logics, denoted BD_n for each n, consists of intermediate logics valid precisely on Kripke frames of depth at most n. These logics are axiomatized by explicit schemata extending , such as the finite chain axiom for linear orders of length n+1: the disjunction \bigvee_{i=1}^{n+1} (p_1 \to \cdots \to p_i), which ensures no implications chain beyond depth n. Developed in extensions of Gödel's work on finite models, BD_n logics illustrate the of intermediate systems by semantic depth, with each providing a step toward as n increases, while maintaining completeness for their restricted frames.

Disjunction and Existence Properties

The disjunction property (DP) is a key meta-logical feature of certain logics, stating that if a formula of the form \phi \lor \psi is provable in the logic L, denoted L \vdash \phi \lor \psi, then either L \vdash \phi or L \vdash \psi. This property underscores a form of constructivity, requiring explicit proof of one disjunct rather than merely their joint possibility. Intuitionistic propositional logic (IPC) satisfies the DP, as originally shown by Gödel in his analysis of intuitionistic systems. Among intermediate logics, which extend IPC but remain strictly weaker than classical propositional logic (CPC), the DP is preserved by some but not all; for instance, Scott logic (SL), obtained by adding the axiom (( \neg\neg p \to p ) \to (p \lor \neg p)) \to (p \lor \neg\neg p) to IPC, possesses the DP. In contrast, many intermediate logics fail the , illustrating their partial departure from full constructivity. For example, the Gödel-Dummett logic () does not satisfy the . Logics with the form a proper subclass of intermediate logics; there exist continuum many such logics, including infinite descending chains under inclusion, but no single maximal intermediate logic enjoys the exclusively, as extensions can maintain it up to certain points without reaching . The implications of the are significant for understanding constructivity in intermediate logics. It implies the consistency of the logic, since assuming L \vdash \bot \lor \bot would force L \vdash \bot, leading to triviality; more broadly, the DP distinguishes fully constructive systems like from non-constructive ones like , which fails it because CPC proves p \lor \neg p without proving either disjunct. In intermediate logics, the failure of DP in some cases (e.g., ) highlights their hybrid nature, retaining some classical inferences while preserving aspects of intuitionistic proof requirements. The existence property (EP), or witness property, extends the DP to the predicate setting as its dual: if L \vdash \exists x \, \phi(x), then there exists a term t such that L \vdash \phi(t). Like the DP, the EP is satisfied by IPC in its quantified form (often denoted QIPC) and by certain intermediate predicate logics, reflecting the requirement for explicit witnesses in existential proofs. However, not all intermediate predicate logics with the DP have the EP, and vice versa; for example, some constructed extensions lack one while retaining the other, showing their independence in general. The joint possession of DP and EP characterizes heightened constructivity, akin to that in IPC, but many intermediate logics, such as those incorporating classical principles partially, fail at least one. A notable result characterizes intermediate logics with the as precisely those embeddable into via specific that preserve provability, ensuring their theorems align with intuitionistic constructivity without introducing non-constructive elements. This highlights the 's role in bounding the expressive power of intermediate extensions.

Relations to Other Logics

Connection to Modal Logics

The connection between intermediate logics and logics is established primarily through the Gödel-Tarski , also known as the Gödel or , which provides a faithful embedding of intuitionistic propositional logic () and its superintuitionistic extensions into classical logics. This , originally introduced by Gödel in 1933 and proven fully faithful by McKinsey and Tarski in 1948, maps intuitionistic formulas to formulas by prefixing the necessity operator \square (often interpreted as "necessarily" or "provable") to subformulas in a specific way, preserving theorems and enabling the study of intermediate logics using semantic tools. The translation \rho is defined recursively as follows: for atomic propositions p, \rho(p) = \square p; for , \rho(\neg \phi) = \neg \square \rho(\phi); for , \rho(\phi \to \psi) = \square (\rho(\phi) \to \rho(\psi)); and it extends monotonically to and disjunction by \rho(\phi \land \psi) = \rho(\phi) \land \rho(\psi) and \rho(\phi \lor \psi) = \rho(\phi) \lor \rho(\psi), with \rho(\bot) = \bot. This construction ensures that IPC is logically equivalent to the image of \rho in the S4, meaning \mathrm{IPC} \vdash \phi if and only if \mathrm{S4} \vdash \rho(\phi). For logics, which extend IPC, the translation \rho embeds each such logic L into its modal companion—a modal logic extending S4—preserving theorems in the sense that L \vdash \phi if and only if the modal companion \vdash \rho(\phi). This embedding generalizes Glivenko's theorem, which relates classical and intuitionistic logics via , by showing that every intermediate logic faithfully embeds into a corresponding via \rho, allowing correspondences to characterize intermediate logic properties. Intermediate logics can thus be viewed as modal logics over an intuitionistic base, where the translations connect them to extensions of S4 up to S5; for instance, the classical propositional logic (CPC) embeds into S5 via \rho. Specific correspondences highlight this link: the logic LC (Dummett's logic, axiomatized by IPC plus (p \to q) \lor (q \to p)) corresponds to the modal logic S4.3, which adds the confluence axiom \Diamond p \to \Diamond \Diamond q \to \Diamond \Diamond p (or equivalently, \square(\square p \to q) \to \square(\square q \to p)) to S4 and characterizes confluent (or linear) frames. These modal companions facilitate the transfer of results, such as completeness and decidability, between the two frameworks.

Comparison with Intuitionistic and Classical Logics

Intermediate logics extend intuitionistic propositional logic (IPC) while remaining strictly weaker than classical propositional logic (CPC), resulting in distinct expressive power. Like IPC, they reject the law of excluded middle (p \lor \neg p) and double negation elimination (\neg \neg p \to p), principles that underpin the bivalent truth values of CPC. These rejections preserve the intuitionistic emphasis on constructive validity, where truth requires an effective proof rather than mere non-falsity. However, intermediate logics can incorporate additional axioms that are classically valid but intuitionistically invalid, such as the Gödel-Dummett axiom (p \to q) \lor (q \to p) in the logic LC, allowing for greater expressivity in capturing intermediate degrees of inference without collapsing to full classical strength. In terms of decidability, both and admit effective decision procedures for theoremhood, with IPC's decidability following from its finite model property via Kripke frames and CPC from truth-table methods. Intermediate logics present a sharper contrast: while there are infinitely many decidable ones (e.g., those with the finite frame property, like and Kreisel-Putnam logic ), the collection of all intermediate logics forms a , uncountable in . The collection of all intermediate logics has . There are only countably many decidable logics, as their sets of theorems are recursive and there are only countably many recursive subsets of the set of formulas. Thus, the vast majority of intermediate logics are undecidable. This uncountability was established through the construction of distinct logics via finite rooted Kripke frames, highlighting the richness beyond recursive enumeration. Semantically, the differences manifest clearly in Kripke models over partially ordered frames. IPC is sound and complete with respect to persistent valuations—where if a proposition p holds at a world w, it holds at all accessible worlds w' \geq w—on arbitrary posets. CPC, by contrast, is characterized by total valuations on trivial frames (e.g., single-world models where every proposition is either true or false outright). Intermediate logics impose additional constraints on the class of posets, such as requiring (confluent orders) for , thereby validating formulas on restricted frames that bridge the persistent but partial truths of IPC and the exhaustive totality of CPC. These semantic restrictions enable precise characterizations of intermediate expressivity without invoking full bivalence. Philosophically, intermediate logics mediate between the constructivist epistemology of IPC, which demands explicit constructions for existential claims, and the realist ontology of CPC, which assumes objective truth independent of proof. This balancing act makes them suitable for domains where strict constructivity is overly restrictive yet classical explosion from contradiction is undesirable, such as fuzzy reasoning in approximate knowledge representation. For instance, Gödel logic, an infinite-valued fuzzy logic based on the minimum t-norm, coincides with an intermediate logic and supports graded truth without full bivalence. Similarly, certain paraconsistent extensions of intermediate logics tolerate inconsistencies in belief revision or inconsistent databases, avoiding the principled rejection of explosion in pure paraconsistent systems while retaining constructive elements. No single intermediate logic is recursively axiomatizable in a way that captures all others without introducing undecidability, underscoring their inherent diversity beyond IPC.