Open main menu
Home
Random
Recent changes
Special pages
Community portal
Preferences
About Wikipedia
Disclaimers
Incubator escapee wiki
Search
User menu
Talk
Dark mode
Contributions
Create account
Log in
Editing
Intermediate logic
Warning:
You are not logged in. Your IP address will be publicly visible if you make any edits. If you
log in
or
create an account
, your edits will be attributed to your username, along with other benefits.
Anti-spam check. Do
not
fill this in!
{{Short description|Propositional logic extending intuitionistic logic}} In [[mathematical logic]], a '''superintuitionistic logic''' is a [[propositional logic]] extending [[intuitionistic logic]]. [[Classical logic]] is the strongest [[consistent]] superintuitionistic logic; thus, consistent superintuitionistic logics are called '''intermediate logics''' (the logics are intermediate between intuitionistic logic and classical logic).<ref>{{SpringerEOM|title=Intermediate logic|id=Intermediate_logic}}.</ref> ==Definition== A superintuitionistic logic is a set ''L'' of propositional formulas in a countable set of variables ''p''<sub>''i''</sub> satisfying the following properties: :1. all [[Intuitionistic logic#Axiomatization|axioms of intuitionistic logic]] belong to ''L''; :2. if ''F'' and ''G'' are formulas such that ''F'' and ''F'' → ''G'' both belong to ''L'', then ''G'' also belongs to ''L'' (closure under [[modus ponens]]); :3. if ''F''(''p''<sub>1</sub>, ''p''<sub>2</sub>, ..., ''p''<sub>''n''</sub>) is a formula of ''L'', and ''G''<sub>1</sub>, ''G''<sub>2</sub>, ..., ''G''<sub>''n''</sub> are any formulas, then ''F''(''G''<sub>1</sub>, ''G''<sub>2</sub>, ..., ''G''<sub>''n''</sub>) belongs to ''L'' (closure under substitution). Such a logic is intermediate if furthermore :4. ''L'' is not the set of all formulas. ==Properties and examples== There exists a [[cardinality of the continuum|continuum]] of different intermediate logics and just as many such logics exhibit the [[Disjunction and existence properties|disjunction property]] (DP). Superintuitionistic or intermediate logics form a [[complete lattice]] with intuitionistic logic as the [[bottom element|bottom]] and the inconsistent logic (in the case of superintuitionistic logics) or classical logic (in the case of intermediate logics) as the top. Classical logic is the only [[atom (order theory)|coatom]] in the lattice of superintuitionistic logics; the lattice of intermediate logics also has a unique coatom, namely '''SmL'''{{citation needed|date=February 2024}}. 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 order]]s. Specific intermediate logics may be given by semantical description. Others are often given by adding one or more axioms to intuitionistic logic (usually denoted as intuitionistic propositional calculus '''IPC''', but also '''Int''', '''IL''' or '''H'''). Examples include: * Classical logic ('''CPC''', '''Cl''', '''CL'''): := {{nowrap|'''IPC''' + ¬¬''p'' → ''p''}} (Double-negation elimination, DNE) := {{nowrap|'''IPC''' + (¬''p'' → ''p'') → ''p''}} ([[Consequentia mirabilis]]) := {{nowrap|'''IPC''' + ''p'' ∨ ¬''p''}} ([[Principle of excluded middle]], PEM) Generalized variants of the above (but actually equivalent principles over intuitionistic logic) are, respectively, := {{nowrap|'''IPC''' + (¬''p'' → ¬''q'') → (''q'' → ''p'')}} (inverse [[contraposition]] principle) := {{nowrap|'''IPC''' + ((''p'' → ''q'') → ''p'') → ''p''}} ([[Peirce's law|Peirce's principle]] PP, compare to Consequentia mirabilis) := {{nowrap|'''IPC''' + (''q'' → ''p'') → ((¬''q'' → ''p'') → ''p'')}} (another schema generalizing Consequentia mirabilis) := {{nowrap|'''IPC''' + ''p'' ∨ (''p'' → ''q'')}} (following from PEM via [[principle of explosion]]) * Smetanich's logic ('''SmL'''): := {{nowrap|'''IPC''' + (¬''q'' → ''p'') → (((''p'' → ''q'') → ''p'') → ''p'')}} (a conditional PP) * [[Gödel logic|Gödel-Dummett logic]] ([[Michael Dummett|Dummett]] 1959) ('''LC''' or '''G''', see extensions below): := {{nowrap|'''IPC''' + (''p'' → ''q'') ∨ (''q'' → ''p'')}} (Dirk Gently’s principle, DGP, or linearity) := {{nowrap|'''IPC''' + (''p'' → (''q'' ∨ ''r'')) → ((''p'' → ''q'') ∨ (''p'' → ''r''))}} (a form of [[independence of premise]] IP) := {{nowrap|'''IPC''' + ((''p'' ∧ ''q'') → ''r'') → ((''p'' → ''r'') ∨ (''q'' → ''r''))}} (Generalized 4th [[De Morgan's laws#In intuitionistic logic|De Morgan's law]]) * Bounded depth 2 ('''BD'''<sub>''2''</sub>, see generalizations below. Compare with ''p'' ∨ (''p'' → ''q'')): := {{nowrap|'''IPC''' + ''p'' ∨ (''p'' → (''q'' ∨ ¬''q''))}} * [[V. A. Jankov|Jankov]]'s logic (1968){{sfn|Terwijn|2006}} or [[Augustus De Morgan|De Morgan]] logic ('''KC'''): := {{nowrap|'''IPC''' + ¬¬''p'' ∨ ¬''p''}} (weak PEM, a.k.a. WPEM) := {{nowrap|'''IPC''' + (''p'' → ''q'') ∨ (¬''p'' → ¬''q'')}} (a weak DGP) := {{nowrap|'''IPC''' + (''p'' → (''q'' ∨ ¬''r'')) → ((''p'' → ''q'') ∨ (''p'' → ¬''r''))}} (a variant, with negation, of a form of IP) := {{nowrap|'''IPC''' + ¬(''p'' ∧ ''q'') → (¬''q'' ∨ ¬''p'')}} (4th [[De Morgan's laws#In intuitionistic logic|De Morgan's law]]) * [[Dana Scott|Scott]]'s logic ('''SL'''): := {{nowrap|'''IPC''' + ((¬¬''p'' → ''p'') → (''p'' ∨ ¬''p'')) → (¬¬''p'' ∨ ¬''p'')}} (a conditional WPEM) * [[Georg Kreisel|Kreisel]]–[[Hilary Putnam|Putnam]] logic ('''KP'''): := {{nowrap|'''IPC''' + (¬''p'' → (''q'' ∨ ''r'')) → ((¬''p'' → ''q'') ∨ (¬''p'' → ''r''))}} (the other variant, with negation, of a form of IP) This list is, for the most part, not any sort of ordering. For example, '''LC''' is known not to prove all theorems of '''SmL''', but it does not directly compare in strength to '''BD'''<sub>''2''</sub>. Likewise, e.g., '''KP''' does not compare to '''SL'''. The list of equalities for each logic is by no means exhaustive either. For example, as with WPEM and De Morgan's law, several forms of DGP using conjunction may be expressed. Even (¬¬''p'' ∨ ¬''p'') ∨ (¬¬''p'' → ''p''), a further weakening of WPEM, is not a theorem of '''IPC'''. It may also be worth noting that, taking all of intuitionistic logic for granted, the equalities notably rely on explosion. For example, over mere [[minimal logic]], as principle PEM is already equivalent to Consequentia mirabilis, but there does not imply the stronger DNE, nor PP, and is not comparable to DGP. Going on: * logics of bounded depth ('''BD'''<sub>''n''</sub>): :{{nowrap|'''IPC''' + ''p<sub>n</sub>'' ∨ (''p<sub>n</sub>'' → (''p''<sub>''n''−1</sub> ∨ (''p''<sub>''n''−1</sub> → ... → (''p''<sub>2</sub> ∨ (''p''<sub>2</sub> → (''p''<sub>1</sub> ∨ ¬''p''<sub>1</sub>)))...)))}} * [[Kurt Gödel|Gödel]] ''n''-valued logics ('''G'''<sub>''n''</sub>): :'''LC''' + '''BD'''<sub>''n''−1</sub> := '''LC''' + '''BC'''<sub>''n''−1</sub> * logics of bounded cardinality ('''BC'''<sub>''n''</sub>): :<math>\textstyle\mathbf{IPC}+\bigvee_{i=0}^n\bigl(\bigwedge_{j<i}p_j\to p_i\bigr)</math> * logics of bounded top width ('''BTW'''<sub>''n''</sub>): :<math>\textstyle\mathbf{IPC}+\bigvee_{i=0}^n\bigl(\bigwedge_{j<i}p_j\to\neg\neg p_i\bigr)</math> * logics of bounded width, also known as the logic of bounded anti-chains, Ono (1972) ('''BW'''<sub>''n''</sub>, '''BA'''<sub>''n''</sub>): :<math>\textstyle\mathbf{IPC}+\bigvee_{i=0}^n\bigl(\bigwedge_{j\ne i}p_j\to p_i\bigr)</math> * logics of bounded branching (Gabbay & de Jongh, 1974{{sfn|Gabbay|De Jongh|1974}}) ('''T'''<sub>''n''</sub>, '''BB'''<sub>''n''</sub>): :<math>\textstyle\mathbf{IPC}+\bigwedge_{i=0}^n\bigl(\bigl(p_i\to\bigvee_{j\ne i}p_j\bigr)\to\bigvee_{j\ne i}p_j\bigr)\to\bigvee_{i=0}^np_i</math> Furthermore: * [[Realizability]] logics * [[Yuri T. Medvedev|Medvedev]]'s logic of finite problems ('''LM''', '''ML'''):{{sfn|Medvedev|1962}}{{sfn|Medvedev|1963}}{{sfn|Medvedev|1966}} defined semantically as the logic of all [[Kripke semantics|frames]] of the form <math>\langle\mathcal P(X)\setminus\{X\},\subseteq\rangle</math> for [[finite set]]s ''X'' ("Boolean hypercubes without top"), not known to be recursively axiomatizable * ... The propositional logics '''SL''' and '''KP''' do have the disjunction property DP. Kleene realizability logic and the strong Medvedev's logic do have it as well. There is no unique maximal logic with DP on the lattice. Note that if a consistent theory validates WPEM but still has independent statements when assuming PEM, then it cannot have DP. ==Semantics== Given a [[Heyting algebra]] ''H'', the set of [[propositional formula]]s that are valid in ''H'' is an intermediate logic. Conversely, given an intermediate logic it is possible to construct its [[Lindenbaum–Tarski algebra]], which is then a Heyting algebra. An intuitionistic [[Kripke frame]] ''F'' is a [[partially ordered set]], and a Kripke model ''M'' is a Kripke frame with valuation such that <math>\{x\mid M,x\Vdash p\}</math> is an [[upper set|upper subset]] of ''F''. The set of propositional formulas that are valid in ''F'' is an intermediate logic. Given an intermediate logic ''L'' it is possible to construct a Kripke model ''M'' such that the logic of ''M'' is ''L'' (this construction is called the ''canonical model''). A Kripke frame with this property may not exist, but a [[general frame]] always does. ==Relation to modal logics== {{main|Modal companion}} Let ''A'' be a propositional formula. The ''Gödel–[[Alfred Tarski|Tarski]] translation'' of ''A'' is defined recursively as follows: *<math> T(p_n) = \Box p_n </math> *<math> T(\neg A) = \Box \neg T(A) </math> *<math> T(A \land B) = T(A) \land T(B) </math> *<math> T(A \vee B) = T(A) \vee T(B) </math> *<math> T(A \to B) = \Box (T(A) \to T(B)) </math> If ''M'' is a [[modal logic]] extending '''S4''' then {{nowrap begin}}ρ''M'' = {''A'' | ''T''(''A'') ∈ ''M''}{{nowrap end}} is a superintuitionistic logic, and ''M'' is called a ''modal companion'' of ρ''M''. In particular: *'''IPC''' = ρ'''S4''' *'''KC''' = ρ'''S4.2''' *'''LC''' = ρ'''S4.3''' *'''CPC''' = ρ'''S5''' For every intermediate logic ''L'' there are many modal logics ''M'' such that ''L'' = ρ''M''. == See also == * [[List of logic systems]] ==Notes== <references /> ==References== *{{cite book |last1= Chagrov |first1=Alexander |last2= Zakharyaschev |first2=Michael |year=1997 |title=Modal Logic |publisher=[[Clarendon Press]] |location=Oxford |pages=605 |isbn=9780198537793 }} *{{cite journal |last=Medvedev |first=Yu T. |date=1962 |title=[Finite Problems] |quote=English translation of XXXVIII 356(20) by Elliott Mendelson. |language=ru |journal=Soviet Mathematics |volume=3 |issue=1 |pages=227–230 |url=https://webspace.science.uu.nl/~ooste110/studsemIntMod/MedvedevProblems.pdf |doi=10.2307/2272084 |jstor=2272084 }} *{{cite journal |last=Medvedev |first=Yu T. |date=1963 |title=[Interpretation of logical formulas by means of finite problems and its relation to the readability theory] |quote=English translation of XXXVIII 356(21) by Sue Ann Walker. |language=ru |journal=Soviet Mathematics |volume=4 |issue=1 |pages=180–183 |url=https://webspace.science.uu.nl/~ooste110/studsemIntMod/MedvedevProblems.pdf |doi=10.2307/2272084 |jstor=2272084 }} *{{cite journal |last=Medvedev |first=Yu T. |date=1966 |title=[Interpretation of logical formulas by means of finite problems] |quote=English translation of XXXVIII 356(22) by Sue Ann Walker |language=ru |journal=Soviet Mathematics |volume=7 |issue=4 |pages=857–860 |url=https://webspace.science.uu.nl/~ooste110/studsemIntMod/MedvedevProblems.pdf |doi=10.2307/2272084 |jstor=2272084 }} *{{cite journal |last=Terwijn |first=Sebastiaan A. |year=2006 |title=Constructive Logic and the Medvedev Lattice |url=https://projecteuclid.org/download/pdf_1/euclid.ndjfl/1143468312 |journal=[[Notre Dame Journal of Formal Logic]] |volume=47 |issue=1 |pages=73–82 |doi=10.1305/ndjfl/1143468312 |jstor= }} *{{cite journal |last=Umezawa |first=Toshio |date=June 1959|title= On logics intermediate between intuitionistic and classical predicate logic |jstor=2964756 |journal=[[Journal of Symbolic Logic]] |volume=24 |issue=2 |pages=141–153 |doi=10.2307/2964756 |s2cid=13357205 }} *{{cite journal |last1=Gabbay |first1=D. M. |last2=De Jongh |first2=D. H. J. |title=A sequence of decidable finitely axiomatizable intermediate logics with the disjunction property |journal=Journal of Symbolic Logic |date=1974 |volume=39 |issue=1 |pages=67‒78 |doi=10.2307/2272344 |jstor=2272344 |url=https://www.cambridge.org/core/product/D855962FCAC7D77F5C5C12994BC74656 }} ==External links== *{{SpringerEOM|title=Intermediate logic|id=Intermediate_logic}} {{Non-classical logic}} [[Category:Systems of formal logic]] [[Category:Propositional calculus]] [[Category:Non-classical logic]]
Edit summary
(Briefly describe your changes)
By publishing changes, you agree to the
Terms of Use
, and you irrevocably agree to release your contribution under the
CC BY-SA 4.0 License
and the
GFDL
. You agree that a hyperlink or URL is sufficient attribution under the Creative Commons license.
Cancel
Editing help
(opens in new window)
Pages transcluded onto the current version of this page
(
help
)
:
Template:Citation needed
(
edit
)
Template:Cite book
(
edit
)
Template:Cite journal
(
edit
)
Template:Main
(
edit
)
Template:Non-classical logic
(
edit
)
Template:Nowrap
(
edit
)
Template:Nowrap begin
(
edit
)
Template:Nowrap end
(
edit
)
Template:Sfn
(
edit
)
Template:Short description
(
edit
)
Template:SpringerEOM
(
edit
)