All Topics  
Intuitionistic logic

 

 
   Email Print
   Bookmark   Link
 

 

Intuitionistic logic
 
 
  Topics Intuitionistic logic Topic Home

Intuitionistic logic, or constructivist logic, is the symbolic logic
Symbolic logic

Symbolic logic is the area of mathematics which studies the purely formal properties of strings of symbols. The interest in this area springs from two sources....
 system originally developed by Arend Heyting
Arend Heyting

Arend Heyting was a Netherlands mathematician and logician. He was a student of L.E.J. Brouwer at the Universiteit van Amsterdam, and did much to put intuitionistic logic on a footing where it could become part of mathematical logic....
 to provide a formal basis for Brouwer
Luitzen Egbertus Jan Brouwer

Luitzen Egbertus Jan Brouwer ['l?yt.s?n ?x.'b??.t?s j?n 'b??u.??] , usually cited as L. E. J. Brouwer but known to his friends as Bertus, was a Netherlands mathematician and philosopher, a graduate of the University of Amsterdam, who worked in topology, set theory, measure theory and complex analysis....
's programme of intuitionism
Intuitionism

In the philosophy of mathematics, intuitionism, or neointuitionism , is an approach to mathematics as the constructive mental activity of humans....
. The system preserves justification
Theory of justification

Theory of justification is a part of epistemology that attempts to understand the justification of propositions and beliefs. Epistemologists are concerned with various epistemic features of belief, which include the ideas of justification, warrant, rationality, and probability....
, rather than truth
Truth

semantic fields for the word truth extend from honesty, good faith, and sincerity in general, to agreement with fact or reality in particular....
, across transformations yielding derived propositions. From a practical point of view, there is also a strong motivation for using intuitionistic logic, since it has the existence property, making it also suitable for other forms of mathematical constructivism.

syntax
Syntax

In linguistics, syntax is the study of the principles and rules for constructing Sentence s in natural languages. In addition to referring to the discipline, the term syntax is also used to refer directly to the rules and principles that govern the sentence structure of any individual language, as in "the Irish syntax"....
 of formulć of intuitionistic logic is similar to propositional logic or first-order logic
First-order logic

First-order logic is a formal deductive system used in mathematics, philosophy, linguistics, and computer science. It goes by many names, including: first-order predicate calculus , the lower predicate calculus, the language of first-order logic or predicate logic....
.






Discussion
Ask a question about 'Intuitionistic logic'
Start a new discussion about 'Intuitionistic logic'
Answer questions from other users
Full Discussion Forum



Encyclopedia


Intuitionistic logic, or constructivist logic, is the symbolic logic
Symbolic logic

Symbolic logic is the area of mathematics which studies the purely formal properties of strings of symbols. The interest in this area springs from two sources....
 system originally developed by Arend Heyting
Arend Heyting

Arend Heyting was a Netherlands mathematician and logician. He was a student of L.E.J. Brouwer at the Universiteit van Amsterdam, and did much to put intuitionistic logic on a footing where it could become part of mathematical logic....
 to provide a formal basis for Brouwer
Luitzen Egbertus Jan Brouwer

Luitzen Egbertus Jan Brouwer ['l?yt.s?n ?x.'b??.t?s j?n 'b??u.??] , usually cited as L. E. J. Brouwer but known to his friends as Bertus, was a Netherlands mathematician and philosopher, a graduate of the University of Amsterdam, who worked in topology, set theory, measure theory and complex analysis....
's programme of intuitionism
Intuitionism

In the philosophy of mathematics, intuitionism, or neointuitionism , is an approach to mathematics as the constructive mental activity of humans....
. The system preserves justification
Theory of justification

Theory of justification is a part of epistemology that attempts to understand the justification of propositions and beliefs. Epistemologists are concerned with various epistemic features of belief, which include the ideas of justification, warrant, rationality, and probability....
, rather than truth
Truth

semantic fields for the word truth extend from honesty, good faith, and sincerity in general, to agreement with fact or reality in particular....
, across transformations yielding derived propositions. From a practical point of view, there is also a strong motivation for using intuitionistic logic, since it has the existence property, making it also suitable for other forms of mathematical constructivism.

Syntax

The syntax
Syntax

In linguistics, syntax is the study of the principles and rules for constructing Sentence s in natural languages. In addition to referring to the discipline, the term syntax is also used to refer directly to the rules and principles that govern the sentence structure of any individual language, as in "the Irish syntax"....
 of formulć of intuitionistic logic is similar to propositional logic or first-order logic
First-order logic

First-order logic is a formal deductive system used in mathematics, philosophy, linguistics, and computer science. It goes by many names, including: first-order predicate calculus , the lower predicate calculus, the language of first-order logic or predicate logic....
. However, intuitionistic connective
Logical connective

In logic, two sentences may be joined by means of a logical connective to form a compound sentence. The truth-value of the compound is uniquely determined by the truth-values of the simpler sentences....
s are not interdefinable in the same way as in classical logic
Classical logic

Classical logic identifies a class of formal logics that have been most intensively studied and most widely used. They are characterised by a number of properties; non-classical logics are those that lack one or more of these properties, which are:...
, hence their choice matters. In intuitionistic propositional logic it is customary to use ?, ?, ?, ? as the basic connectives, treating ¬ as the abbreviation . In intuitionistic first-order logic both quantifiers ?, ? are needed.

Many tautologies
Tautology (logic)

In propositional logic, a tautology is a propositional formula that is true under any possible Valuation of its propositional variables. For example, the propositional formula is a tautology, because the statement is true for any valuation of A....
 of classical logic can no longer be proven within intuitionistic logic. Examples include not only the law of excluded middle
Law of excluded middle

In logic, the law of the excluded middle states that the propositional calculus formula "P ? ?P" can be deduced from the calculus under investigation....
 , but also Peirce's law
Peirce's law

Peirce's law in logic is named after the philosopher and logician Charles Sanders Peirce. It was taken as an Axiom#Mathematics in his first axiomatisation of propositional logic....
 , and even double negation elimination. In classical logic, both and also are theorems. In intuitionistic logic, only the former is a theorem: double negation can be introduced, but it cannot be eliminated.

The observation that many classically valid tautologies are not theorems of intuitionistic logic leads to the idea of weakening the proof theory of classical logic.

Sequent calculus

Gentzen
Gerhard Gentzen

Gerhard Karl Erich Gentzen was a Germany mathematician and logician.He was one of Hermann Weyl's students at the University of G?ttingen from 1929 to 1933....
 discovered that a simple restriction of his system LK (his sequent calculus for classical logic) results in a system which is sound and complete with respect to intuitionistic logic. He called this system LJ.

Hilbert-style calculus

Intuitionistic logic can be defined using the following Hilbert-style calculus
Hilbert-style deduction system

In logic, especially mathematical logic, a Hilbert-style deduction system is a type of system of Deductive reasoning attributed to Gottlob Frege and David Hilbert....
. Compare with the deduction system at Propositional calculus#Alternative calculus
Propositional calculus

In logic and mathematics, a propositional calculus or logic is a formal system in which formulae representing propositional formulas can be formed by combining atomic formula propositions using logical connectives, and a system of formal proof rules allows certain formul? to be established as "theorem"....
.

In propositional logic, the inference rule is modus ponens
Modus ponens

In classical logic, modus ponendo ponens is a valid, simple argument form sometimes referred to as affirming the antecedent or the law of detachment....
  • MP: from f and f ? ? infer ?
and the axioms are
  • THEN-1: f ? (? ? f)
  • THEN-2: (f ? (? ? ?)) ? ((f ? ?) ? (f ? ?))
  • AND-1: f ? ? ? f
  • AND-2: f ? ? ? ?
  • AND-3: f ? (? ? (f ? ?))
  • OR-1: f ? f ? ?
  • OR-2: ? ? f ? ?
  • OR-3: (f ? ?) ? ((? ? ?) ? (f ? ? ? ?))
  • FALSE: ? ? f
To make this a system of first-order predicate logic, the generalization rules
Generalization (logic)

Generalization is an rule of inference of predicate calculus which states that:"Generalization" can be abbreviated as GEN. The inference rule can be summarized as the sequentbut this gives rise to an important restriction: the Deduction theorem cannot be applied to it to deriveThis formula is wrong because x has an unbound instance...
  • ?-GEN: from ? ? f infer ? ? (?x f), if x is not free in ?
  • ?-GEN: from f ? ? infer (?x f) ? ?, if x is not free in ?
are added, along with the axioms
  • PRED-1: (?x f(x)) ? f(t), if no free occurrence of x in f is bound by a quantifier quantifying a variable occurring in the term t
  • PRED-2: f(t) ? (?x f(x)), with the same restriction as for PRED-1


Optional connectives

Negation
If one wishes to include a connective ¬ for negation rather than consider it an abbreviation for f ? ?, it is enough to add:
  • NOT-1′: (f ? ?) ? ¬f
  • NOT-2′: ¬f ? (f ? ?)


There are a number of alternatives available if one wishes to omit the connective ? (false). For example, one may replace the three axioms FALSE, NOT-1′, and NOT-2′ with the two axioms
  • NOT-1: (f ? ?) ? ((f ? ¬?) ? ¬f)
  • NOT-2: f ? (¬f ? ?)
as at Propositional calculus#Axioms
Propositional calculus

In logic and mathematics, a propositional calculus or logic is a formal system in which formulae representing propositional formulas can be formed by combining atomic formula propositions using logical connectives, and a system of formal proof rules allows certain formul? to be established as "theorem"....
. Alternatives to NOT-1 are (f ? ¬?) ? (? ? ¬f) or (f ? ¬f) ? ¬f.

Equivalence
The connective ? for equivalence may be treated as an abbreviation, with f ? ? standing for (f ? ?) ? (? ? f). Alternatively, one may add the axioms

  • IFF-1: (f ? ?) ? (f ? ?)
  • IFF-2: (f ? ?) ? (? ? f)
  • IFF-3: (f ? ?) ? ((? ? f) ? (f ? ?))


IFF-1 and IFF-2 can, if desired, be combined into a single axiom (f ? ?) ? ((f ? ?) ? (? ? f)) using conjunction.

Relation to classical logic
The system of classical logic is obtained by adding any one of the following axioms:

  • f ? ¬f (Law of the excluded middle. May also be formulated as (f ? ?) ? ((¬f ? ?) ? ?).)
  • ¬¬f ? f (Double negation elimination)
  • ((f ? ?) ? f) ? f (Peirce's law)


In general, one may take as the extra axiom any classical tautology that is not valid in the two-element Kripke frame (in other words, that is not included in Smetanich's logic
Intermediate logic

In mathematical logic, a superintuitionistic logic is a propositional logic extending intuitionistic logic. Classical logic is the strongest consistent superintuitionistic logic....
).

Another relationship is given by the Gödel–Gentzen negative translation
Gödel–Gentzen negative translation

In proof theory, the G?del?Gentzen negative translation is a method for embedding classical first-order logic into intuitionistic logic first-order logic....
, which provides an embedding
Embedding

In mathematics, an embedding is one instance of some mathematical structure contained within another instance, such as a group that is a subgroup....
 of classical first-order logic into intuitionistic logic: a first-order formula is provable in classical logic if and only if its Gödel–Gentzen translation is provable intuitionistically. Therefore intuitionistic logic can instead be seen as a means of extending classical logic with constructivist semantics.

Non-interdefinability of operators

In classical propositional logic, it is possible to take one of conjunction
Logical conjunction

In logic and/or mathematics, logical conjunction or and is a two-place logical operation that results in a value of true if both of its operands are true, otherwise a value of false....
, disjunction
Logical disjunction

File:ORGate2.pngIn logic and mathematics, or, also known as logical disjunction or inclusive disjunction is a logical operator that results in true whenever one or more of its operands are true....
, or implication
Material conditional

The material conditional, also known as the material implication or truth functional conditional, expresses a property of certain conditionals in logic....
 as primitive, and define the other two in terms of it together with negation, such as in Lukasiewicz
Jan Lukasiewicz

Jan Lukasiewicz was a Poland mathematician born in Lw?w, Galicia , Austria-Hungary . His major mathematical work centred on mathematical logic....
's three axioms of propositional logic. It is even possible to define all four in terms of a sole sufficient operator
Sole sufficient operator

A sole sufficient operator or a sole sufficient connective is an operator that is sufficient by itself to generate all of the operators in a specified class of operators....
 such as the Peirce arrow (NOR) or Sheffer stroke
Sheffer stroke

The Sheffer stroke, written "|" or "?", in the subject matter of boolean functions or propositional calculus, denotes a logical operation that is equivalent to the logical negation of the logical conjunction operation, expressed in ordinary language as "not both"....
 (NAND). Similarly, in classical first-order logic, one of the quantifiers can be defined in terms of the other and negation.

These are fundamentally consequences of the law of bivalence, which makes all such connectives merely boolean function
Boolean function

In mathematics, a Boolean function is a function of the form f : Bk ? B, where B =  is a Boolean domain and k is a nonnegative integer called the arity of the function....
s. The law of bivalence does not hold in intuitionistic logic, only the law of non-contradiction. As a result none of the basic connectives can be dispensed with, and the above axioms are all necessary. Most of the classical identities are only theorems of intuitionistic logic in one direction, although some are theorems in both directions. They are as follows:

Conjunction versus disjunction:
Conjunction versus implication:
Disjunction versus implication:
Universal versus existential quantification:


So, for example, "a or b" is a stronger statement than "if not a, then b", whereas these are classically interchangeable. On the other hand, "neither a nor b" is equivalent to "not a, and also not b".

If we include equivalence in the list of connectives, some of the connectives become definable from others:
In particular, and are complete bases of intuitionistic connectives.

As shown by Alexander Kuznetsov, either of the following defined connectives can serve the role of a sole sufficient operator for intuitionistic logic:


Semantics

The semantics are rather more complicated than for the classical case. A model theory can be given by Heyting algebra
Heyting algebra

In mathematics, Heyting algebras are special partially ordered sets that constitute a generalization of Boolean algebra s, named after Arend Heyting....
s or, equivalently, by Kripke semantics
Kripke semantics

Kripke semantics is a formal semantics for non-classical logic systems created in the late 1950s and early 1960s by Saul Kripke, beginning when he was a teenager....
.

Heyting algebra semantics

In classical logic, we often discuss the truth values that a formula can take. The values are usually chosen as the members of a Boolean algebra. The meet and join operations in the Boolean algebra are identified with the ? and ? logical connectives, so that the value of a formula of the form A ? B is the meet of the value of A and the value of B in the Boolean algebra. Then we have the useful theorem that a formula is a valid sentence of classical logic if and only if its value is 1 for every valuation
Valuation

Valuation may refer to:*Valuation , the determination of the economic value of an asset or liability*Valuation , the determination of the ethic or philosophic value of an object ...
—that is, for any assignment of values to its variables.

A corresponding theorem is true for intuitionistic logic, but instead of assigning each formula a value from a Boolean algebra, one uses values from a Heyting algebra
Heyting algebra

In mathematics, Heyting algebras are special partially ordered sets that constitute a generalization of Boolean algebra s, named after Arend Heyting....
, of which Boolean algebras are a special case. A formula is valid in intuitionistic logic if and only if it receives the value of the top element for any valuation on any Heyting algebra.

It can be shown that to recognize valid formulas, it is sufficient to consider a single Heyting algebra whose elements are the open subsets of the real line R. In this algebra, the ? and ? operations correspond to set intersection and union, and the value assigned to a formula A ? B is int(AC ? B), the interior
Interior (topology)

In mathematics, the interior of a set S consists of all Topology glossary#Ps of S that are intuitively "not on the edge of S". A point that is in the interior of S is an interior point of S....
 of the union of the value of B and the complement
Complement (set theory)

In discrete mathematics and predominantly in set theory, a complement is a concept used in comparisons of sets to refer to the unique values of one set in relation to another....
 of the value of A. The bottom element is the empty set Ř, and the top element is the entire line R. Negation is as usual defined as ¬A = A ? Ř, so the value of ¬A reduces to int(AC), the interior of the complement of the value of A, also known as the exterior
Exterior (topology)

In topology, the exterior of a subset S of a topological space X is the union of all open sets of X which are disjoint from S. It is itself an open set....
 of A. With these assignments, intuitionistically valid formulas are precisely those that are assigned the value of the entire line.

For example, the formula ¬(A ? ¬A) is valid, because no matter what set X is chosen as the value of the formula A, the value of ¬(A ? ¬A) can be shown to be the entire line:

Value(¬(A ? ¬A)) =
int((Value(A ? ¬A))C) =
int((Value(A) n Value(¬A))C) =
int((X n int((Value(A))C))C) =
int((X n int(XC))C)


A theorem of topology
Topology

Topology is a major area of mathematics that has emerged through the development of concepts from geometry and set theory, such as those of space, dimension, shape, transformation and others....
 tells us that int(XC) is a subset of XC, so the intersection is empty, leaving:

int(ŘC) = int(R) = R


So the valuation of this formula is true, and indeed the formula is valid.

But the law of the excluded middle, A ? ¬A, can be shown to be invalid by letting the value of A be . Then the value of ¬A is the interior of , which is , and the value of the formula is the union of and , which is , not the entire line.

The interpretation
Interpretation (logic)

In logic an interpretation gives meaning to an artificial or formal language or to a Sentence of such a language by assigning a denotation to each non-logical symbol in that language or in that sentence....
 of any intuitionistically valid formula in the infinite Heyting algebra described above results in the top element, representing true, as the valuation of the formula, regardless of what values from the algebra are assigned to the variables of the formula. Conversely, for every invalid formula, there is an assignment of values to the variables that yields a valuation that differs from the top element. No finite Heyting algebra has both these properties.

Kripke semantics


Building upon his work on semantics of modal logic
Modal logic

A modal logic is any system of mathematical logic#Formal logic that attempts to deal with notions of possibility and necessity. Traditionally, there are three "modes" or "moods" or "modalities" of the Copula to be, namely, Logical possibility, probability, and Necessary_and_sufficient_conditions#Necessary_conditions....
, Saul Kripke
Saul Kripke

Saul Aaron Kripke is an American philosophy and logician, now emeritus from Princeton University. He teaches as distinguished professor of philosophy at CUNY Graduate Center....
 created another semantics for intuitionistic logic, known as Kripke semantics or relational semantics .

Relation to other logics


Intutionistic logic is related by duality
Duality (mathematics)

In mathematics, duality has numerous meanings. Generally speaking, duality is a metamathematics Involution . Some duality concepts are closely related and there are explicit theorems governing their relationships....
 to a paraconsistent logic
Paraconsistent logic

A paraconsistent logic is a logical system that attempts to deal with contradictions in a discriminating way. Alternatively, paraconsistent logic is the subfield of logic that is concerned with studying and developing paraconsistent systems of logic....
 known as Brazilian, anti-intuitionistic or dual-intuitionistic logic.

See also


External links

  • Stanford Encyclopedia of Philosophy
    Stanford Encyclopedia of Philosophy

    The Stanford Encyclopedia of Philosophy is a Open access online encyclopedia of philosophy maintained by Stanford University. The SEP was initially developed with U.S....
    : "" -- by Joan Moschovakis.