Intuitionism
From Wikipedia, the free encyclopedia
In the philosophy of mathematics, intuitionism, or neointuitionism (opposed to preintuitionism), is an approach to mathematics as the constructive mental activity of humans. That is, mathematics does not consist of analytic activities wherein deep properties of existence are revealed and applied. Instead, logic and mathematics are the application of internally consistent methods to realize more complex mental constructs.
Contents 
[edit] Truth and proof
The fundamental distinguishing characteristic of intuitionism is its interpretation of what it means for a mathematical statement to be true. As the name suggests, in Brouwer's original intuitionism, the truth of a statement is taken to be equivalent to the mathematician being able to intuit the statement. The vagueness of the intuitionistic notion of truth often leads to misinterpretations about its meaning. Kleene formally defined intuitionistic truth from a realist position, however Brouwer would likely reject this formalization as meaningless, given his rejection of the realist/Platonist position. Intuitionistic truth therefore remains somewhat ill defined. Regardless of how it is interpreted, intuitionism does not equate the truth of a mathematical statement with its provability. However, because the intuitionistic notion of truth is more restrictive than that of classical mathematics, the intuitionist must reject some assumptions of classical logic to ensure that everything he/she proves is in fact intuitionistically true. This gives rise to intuitionistic logic.
To claim an object with certain properties exists is, to an intuitionist, to claim to be able to construct a certain object with those properties. Any mathematical object is considered to be a product of a construction of a mind, and therefore, the existence of an object is equivalent to the possibility of its construction. This contrasts with the classical approach, which states that the existence of an entity can be proved by refuting its nonexistence. For the intuitionist, this is not valid; the refutation of the nonexistence does not mean that it is possible to find a constructive proof of existence. As such, intuitionism is a variety of mathematical constructivism; but it is not the only kind.
As well, to say A or B, to an intuitionist, is to claim that either A or B can be proved. In particular, the law of excluded middle, A or not A, is disallowed since one can construct, via Gödel's incompleteness theorems, a mathematical statement that can be neither proven nor disproved.
The interpretation of negation is also different. In classical logic, the negation of a statement asserts that the statement is false; to an intuitionist, it means the statement is refutable (i.e., that there is a proof that there is no proof of it). The asymmetry between a positive and negative statement becomes apparent. If a statement P is provable, then it is certainly impossible to prove that there is no proof of P; however, just because there is no proof that P is not true, we cannot conclude from this absence that there is a proof of P. Thus P is a stronger statement than notnotP.
Intuitionistic logic substitutes constructability for abstract truth and is associated with a transition from the proof to model theory of abstract truth in modern mathematics. The logical calculus preserves justification, rather than truth, across transformations yielding derived propositions. It has been taken as giving philosophical support to several schools of philosophy, most notably the Antirealism of Michael Dummett. Thus, contrary to the first impression its name might convey, and as realized in specific approaches and disciplines (e.g. Fuzzy Sets and Systems), intuitionist mathematics is more not less rigorous than conventionally founded mathematics where, ironically, the foundational elements which Intutionism attempts to construct/refute/refound are taken as intuitively given.
[edit] Intuitionism and infinity
Among the different formulations of intuitionism, there are several different positions on the meaning and reality of infinity.
The term potential infinity refers to a mathematical procedure in which there is an unending series of steps. After each step has been completed, there is always another step to be performed. For example, consider the process of counting: 1, 2, 3, ...
The term actual infinity refers to a completed mathematical object which contains an infinite number of elements. An example is the set of natural numbers, .
In Cantor's formulation of set theory, there are many different infinite sets, some of which are larger than others. For example, the set of all real numbers is larger than , because any procedure that you attempt to use to put the natural numbers into onetoone correspondence with the real numbers will always fail: there will always be an infinite number of real numbers "left over". Any infinite set that can be placed in onetoone correspondence with the natural numbers is said to be "countable". Infinite sets larger than this are said to be "uncountable".
Cantor's approach to set theory (in revised form) is the foundation of modern mainstream mathematics.
Intuitionism was created, in part, as a reaction to Cantor's set theory. All forms of intuitionism reject the reality of uncountable infinite sets.
Modern constructive set theory does include the axiom of infinity from ZermeloFraenkel set theory (or a revised version of this axiom), and includes the set N of natural numbers. Most modern constructive mathematicians accept the reality of countably infinite sets (however, see Alexander EseninVolpin for a counterexample).
Brouwer rejected the concept of actual infinity, but admitted the idea of potential infinity.
 "According to Weyl 1946, 'Brouwer made it clear, as I think beyond any doubt, that there is no evidence supporting the belief in the existential character of the totality of all natural numbers ... the sequence of numbers which grows beyond any stage already reached by passing to the next number, is a manifold of possibilities open towards infinity; it remains forever in the status of creation, but is not a closed realm of things existing in themselves. That we blindly converted one into the other is the true source of our difficulties, including the antinomies  a source of more fundamental nature than Russell's vicious circle principle indicated. Brouwer opened our eyes and made us see how far classical mathematics, nourished by a belief in the 'absolute' that transcends all human possibilities of realization, goes beyond such statements as can claim real meaning and truth founded on evidence." (Kleene (1952): Introduction to Metamathematics, p. 4849)
Finitism is an extreme version of Intuitionism that rejects the idea of potential infinity. According to Finitism, a mathematical object does not exist unless it can be constructed from the natural numbers in a finite number of steps.
[edit] History of Intuitionism
Intuitionism's history can be traced to two controversies in nineteenth century mathematics.
The first of these was the invention of transfinite arithmetic by Georg Cantor and its subsequent rejection by a number of prominent mathematicians including most famously his teacher Leopold Kronecker — a confirmed finitist.
The second of these was Gottlob Frege's effort to reduce all of mathematics to a logical formulation via set theory and its derailing by a youthful Bertrand Russell, the discoverer of Russell's paradox. Frege had planned a three volume definitive work, however shortly after the first volume had been published, Russell sent Frege a letter outlining his paradox which demonstrated that one of Frege's rules of selfreference was selfcontradictory. Frege, the story goes, plunged into depression and did not publish the second and third volumes of his work as he had planned. For more see Davis (2000) Chapters 3 and 4: Frege: From Breakthrough to Despair and Cantor: Detour through Infinity. See van Heijenoort for the original works and Heijenoort's commentary.
These controversies are strongly linked as the logical methods used by Cantor in proving his results in transfinite arithmetic are essentially the same as those used by Russell in constructing his paradox. Hence how one chooses to resolve Russell's paradox has direct implications on the status accorded to Cantor's transfinite arithmetic.
In the early twentieth century L. E. J. Brouwer represented the intuitionist position and David Hilbert the formalist position — see van Heijenoort. Kurt Gödel offered opinions referred to as Platonist (see various sources re Gödel). Alan Turing considers: "nonconstructive systems of logic with which not all the steps in a proof are mechanical, some being intuitive" (Turing (1939) Systems of Logic Based on Ordinals in Undecidable, p. 210) Later, Stephen Cole Kleene brought forth a more rational consideration of intuitionism in his Introduction to Metamathematics (1952).
[edit] Contributors to intuitionism
[edit] Branches of intuitionistic mathematics
 Intuitionistic logic
 Intuitionistic arithmetic
 Intuitionistic type theory
 Intuitionistic set theory
 Intuitionistic analysis
[edit] See also
 Antirealism
 BHK interpretation
 BrouwerHilbert controversy
 Computability logic
 Constructive logic
 CurryHoward isomorphism
 Foundations of mathematics
 Fuzz (Mathematics and Computer Science)
 Game semantics
 Model Theory
 Intuition (knowledge)
 Ultraintuitionism
[edit] Further reading
 "Analysis." Encyclopædia Britannica. 2006. Encyclopædia Britannica 2006 Ultimate Reference Suite DVD 15 June 2006, "Constructive analysis" (Ian Stewart, author)
 W. S. Anglin, Mathematics: A Concise history and Philosophy, SpringerVerlag, New York, 1994.
 In Chapter 39 Foundations, with respect to the 20th century Anglin gives very precise, short descriptions of Platonism (with respect to Godel), Formalism (with respect to Hilbert), and Intuitionism (with respect to Brouwer).
 Martin Davis (ed.) (1965), The Undecidable, Raven Press, Hewlett, NY. Compilation of original papers by Gödel, Church, Kleene, Turing, Rosser, and Post.
 Martin Davis (2000). Engines of Logic: Mathematicians and the origin of the Computer (1st edition ed.). W. W. Norton & Company, New York. ISBN 0393322297 pbk..
 John W. Dawson Jr., Logical Dilemmas: The Life and Work of Kurt Gödel, A. K. Peters, Wellesley, MA, 1997.
 Less readable than Goldstein but, in Chapter III Excursis, Dawson gives an excellent "A Capsule History of the Development of Logic to 1928".
 Rebecca Goldstein, Incompleteness: The Proof and Paradox of Kurt Godel, Atlas Books, W.W. Norton, New York, 2005.
 In Chapter II Hilbert and the Formalists Goldstein gives further historical context. As a Platonist Gödel was reticent in the presence of the logical positivism of the Vienna Circle. She discusses Wittgenstein's impact and the impact of the formalists. Goldstein notes that the intuitionists were even more opposed to Platonism than Formalism.
 van Heijenoort, J., From Frege to Gödel, A Source Book in Mathematical Logic, 18791931, Harvard University Press, Cambridge, MA, 1967. Reprinted with corrections, 1977. The following papers appear in van Heijenoort:

 L.E.J. Brouwer, 1923, On the significance of the principle of excluded middle in mathematics, especially in function theory [reprinted with commentary, p. 334, van Heijenoort]
 Andrei Nikolaevich Kolmogorov, 1925, On the principle of excluded middle, [reprinted with commentary, p. 414, van Heijenoort]
 L.E.J. Brouwer, 1927, On the domains of definitions of functions, [reprinted with commentary, p. 446, van Heijenoort]
 Although not directly germane, in his (1923) Brouwer uses certain words defined in this paper.
 L.E.J. Brouwer, 1927(2), Intuitionistic reflections on formalism, [reprinted with commentary, p. 490, van Heijenoort]
 Jacques Herbrand, (1931b), "On the consistency of arithmetic", [reprinted with commentary, p. 618ff, van Heijenoort]
 From van Heijenoort's commentary it is unclear whether or not Herbrand was a true "intuitionist"; Gödel (1963) asserted that indeed "...Herbrand was an intuitionist". But van Heijenoort says Herbrand's conception was "on the whole much closer to that of Hilbert's word 'finitary' ('finit') that to "intuitionistic" as applied to Brouwer's doctrine".
 Hesseling, Dennis E. (2003). Gnomes in the Fog. The Reception of Brouwer's Intuitionism in the 1920s. Birkhäuser. ISBN 3764365366.
 Arend Heyting: Heyting, Arend (1971) [1956]. Intuitionism: An Introduction (3d rev. ed. ed.). Amsterdam: NorthHolland Pub. Co. ISBN 0720422396.
 Kleene, Stephen C. (1991) [1952]. Introduction to MetaMathematics (Tenth impression 1991 ed.). Amsterdam NY: NorthHolland Pub. Co. ISBN 0720421039.
 In Chapter III A Critique of Mathematic Reasoning, §11. The paradoxes, Kleene discusses Intuitionism and Formalism in depth. Throughout the rest of the book he treats, and compares, both Formalist (classical) and Intuitionist logics with an emphasis on the former. Extraordinary writing by an extraordinary mathematician.
 Stephen Cole Kleene and Richard Eugene Vesley, The Foundations of Intuistionistic Mathematics, NorthHolland Publishing Co. Amsterdam, 1965. The lead sentence tells it all "The constructive tendency in mathematics...". A text for specialists, but written in Kleene's wonderfullyclear style.
 Constance Reid, Hilbert, Copernicus  SpringerVerlag, 1st edition 1970, 2nd edition 1996.
 Definitive biography of Hilbert places his "Program" in historical context together with the subsequent fighting, sometimes rancorous, between the Intuitionists and the Formalists.
 Paul Rosenbloom, The Elements of Mathematical Logic, Dover Publications Inc, Mineola, New York, 1950.
 In a style more of Principia Mathematica  many symbols, some antique, some from German script. Very good discussions of intuitionism in the following locations: pages 5158 in Section 4 Many Valued Logics, Modal Logics, Intuitionism; pages 6973 Chapter III The Logic of Propostional Functions Section 1 Informal Introduction; and p. 146151 Section 7 the Axiom of Choice.
[edit] Secondary References
 A. A. Markov (1954) Theory of algorithms. [Translated by Jacques J. SchorrKon and PST staff] Imprint Moscow, Academy of Sciences of the USSR, 1954 [i.e. Jerusalem, Israel Program for Scientific Translations, 1961; available from the Office of Technical Services, U.S. Dept. of Commerce, Washington] Description 444 p. 28 cm. Added t.p. in Russian Translation of Works of the Mathematical Institute, Academy of Sciences of the USSR, v. 42. Original title: Teoriya algorifmov. [QA248.M2943 Dartmouth College library. U.S. Dept. of Commerce, Office of Technical Services, number OTS 6051085.]
 A secondary reference for specialists: Markov opined that "The entire significance for mathematics of rendering more precise the concept of algorithm emerges, however, in connection with the problem of a constructive foundation for mathematics....[p. 3, italics added.] Markov believed that further applications of his work "merit a special book, which the author hopes to write in the future" (p. 3). Sadly, said work apparently never appeared.
[edit] External links
Look up intuitionism in Wiktionary, the free dictionary. 