Constructivism (mathematics)
   HOME

TheInfoList



OR:

In the
philosophy of mathematics The philosophy of mathematics is the branch of philosophy Philosophy (from , ) is the systematized study of general and fundamental questions, such as those about existence, reason, knowledge, values, mind, and language. Such quest ...
, constructivism asserts that it is necessary to find (or "construct") a specific example of a mathematical object in order to prove that an example exists. Contrastingly, in
classical mathematics In the foundations of mathematics, classical mathematics refers generally to the mainstream approach to mathematics, which is based on classical logic and ZFC set theory. It stands in contrast to other types of mathematics such as constructive math ...
, one can prove the
existence Existence is the ability of an entity to interact with reality. In philosophy Philosophy (from , ) is the systematized study of general and fundamental questions, such as those about existence, reason, knowledge, values, mind, and la ...

existence
of a mathematical object without "finding" that object explicitly, by assuming its non-existence and then deriving a
contradiction In traditional logic, a contradiction occurs when a proposition conflicts either with itself or established fact. It is often used as a tool to detect disingenuous beliefs and bias. Illustrating a general tendency in applied logic, Aristotle's ...

contradiction
from that assumption. Such a
proof by contradiction In logic and mathematics, proof by contradiction is a form of Mathematical proof, proof that establishes the Truth#Formal theories, truth or the Validity (logic), validity of a proposition, by showing that assuming the proposition to be false leads ...
might be called non-constructive, and a constructivist might reject it. The constructive viewpoint involves a verificational interpretation of the
existential quantifier In predicate logic, an existential quantification is a type of Quantifier (logic), quantifier, a logical constant which is interpretation (logic), interpreted as "there exists", "there is at least one", or "for some". It is usually denoted by t ...
, which is at odds with its classical interpretation. There are many forms of constructivism. These include the program of
intuitionism In the philosophy of mathematics, intuitionism, or neointuitionism (opposed to preintuitionism), is an approach where mathematics is considered to be purely the result of the constructive mental activity of humans rather than the discovery of fu ...
founded by Brouwer, the finitism of Hilbert and Bernays, the constructive recursive mathematics of Shanin and Markov, and
Bishop A bishop is an ordained clergy member who is entrusted with a position of Episcopal polity, authority and oversight in a religious institution. In Christianity, bishops are normally responsible for the governance of dioceses. The role or offic ...
's program of constructive analysis. Constructivism also includes the study of constructive set theories such as CZF and the study of
topos theory In mathematics, a topos (, ; plural topoi or , or toposes) is a category (mathematics), category that behaves like the category of Sheaf (mathematics), sheaves of Set (mathematics), sets on a topological space (or more generally: on a Site (math ...
. Constructivism is often identified with intuitionism, although intuitionism is only one constructivist program. Intuitionism maintains that the foundations of mathematics lie in the individual mathematician's intuition, thereby making mathematics into an intrinsically subjective activity. Other forms of constructivism are not based on this viewpoint of intuition, and are compatible with an objective viewpoint on mathematics.


Constructive mathematics

Much constructive mathematics uses
intuitionistic logic Intuitionistic logic, sometimes more generally called constructive logic, refers to systems of symbolic logic that differ from the systems used for classical logic by more closely mirroring the notion of constructive proof. In particular, systems o ...
, which is essentially
classical logic Classical logic (or standard logic or Frege-Russell logic) is the intensively studied and most widely used class of deductive logic. Classical logic has had much influence on analytic philosophy. Characteristics Each logical system in this class ...
without the
law of the excluded middle In logic Logic is the study of correct reasoning. It includes both Mathematical logic, formal and informal logic. Formal logic is the science of Validity (logic), deductively valid inferences or of logical truths. It is a formal science in ...
. This law states that, for any proposition, either that proposition is true or its negation is. This is not to say that the law of the excluded middle is denied entirely; special cases of the law will be provable. It is just that the general law is not assumed as an
axiom An axiom, postulate, or assumption is a statement (logic), statement that is taken to be truth, true, to serve as a premise or starting point for further reasoning and arguments. The word comes from the Ancient Greek word (), meaning 'that whi ...
. The law of non-contradiction (which states that contradictory statements cannot both at the same time be true) is still valid. For instance, in Heyting arithmetic, one can prove that for any proposition ''p'' that ''does not contain quantifiers'', \forall x,y,z,\ldots \in \mathbb : p \vee \neg p is a theorem (where ''x'', ''y'', ''z'' ... are the free variables in the proposition ''p''). In this sense, propositions restricted to the finite are still regarded as being either true or false, as they are in classical mathematics, but this bivalence does not extend to propositions that refer to infinite collections. In fact, L.E.J. Brouwer, founder of the intuitionist school, viewed the law of the excluded middle as abstracted from finite experience, and then applied to the infinite without justification. For instance,
Goldbach's conjecture Goldbach's conjecture is one of the oldest and best-known list of unsolved problems in mathematics, unsolved problems in number theory and all of mathematics. It states that every even and odd numbers, even natural number greater than 2 is the s ...
is the assertion that every even number (greater than 2) is the sum of two
prime number A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only wa ...
s. It is possible to test for any particular even number whether or not it is the sum of two primes (for instance by exhaustive search), so any one of them is either the sum of two primes or it is not. And so far, every one thus tested has in fact been the sum of two primes. But there is no known proof that all of them are so, nor any known proof that not all of them are so; nor is it even known whether ''either'' a proof ''or'' a disproof of Goldbach's conjecture must exist (the conjecture may be ''undecidable'' in traditional ZF set theory). Thus to Brouwer, we are not justified in asserting "either Goldbach's conjecture is true, or it is not." And while the conjecture may one day be solved, the argument applies to similar unsolved problems; to Brouwer, the law of the excluded middle was tantamount to assuming that ''every'' mathematical problem has a solution. With the omission of the law of the excluded middle as an axiom, the remaining
logical system A formal system is an abstract structure used for inferring theorems from axioms according to a set of rules. These rules, which are used for carrying out the inference of theorems from axioms, are the logical calculus of the formal system. A form ...
has an existence property that classical logic does not have: whenever \exists_ P(x) is proven constructively, then in fact P(a) is proven constructively for (at least) one particular a\in X, often called a witness. Thus the proof of the existence of a mathematical object is tied to the possibility of its construction.


Example from real analysis

In classical
real analysis In mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in mod ...
, one way to define a real number is as an
equivalence class In mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in ...
of
Cauchy sequence In mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in m ...
s of
rational number In mathematics, a rational number is a number that can be expressed as the quotient or fraction (mathematics), fraction of two integers, a numerator and a non-zero denominator . For example, is a rational number, as is every integer (e.g. ) ...
s. In constructive mathematics, one way to construct a real number is as a function ''ƒ'' that takes a positive integer n and outputs a rational ''ƒ''(''n''), together with a function ''g'' that takes a positive integer ''n'' and outputs a positive integer ''g''(''n'') such that :\forall n\ \forall i,j \ge g(n)\quad , f(i) - f(j), \le so that as ''n'' increases, the values of ''ƒ''(''n'') get closer and closer together. We can use ''ƒ'' and ''g'' together to compute as close a rational approximation as we like to the real number they represent. Under this definition, a simple representation of the real number ''e'' is: :f(n) = \sum_^n , \quad g(n) = n. This definition corresponds to the classical definition using Cauchy sequences, except with a constructive twist: for a classical Cauchy sequence, it is required that, for any given distance, there exists (in a classical sense) a member in the sequence after which all members are closer together than that distance. In the constructive version, it is required that, for any given distance, it is possible to actually specify a point in the sequence where this happens (this required specification is often called the modulus of convergence). In fact, the standard constructive interpretation of the mathematical statement :\forall n : \exists m : \forall i,j \ge m: , f(i) - f(j), \le is precisely the existence of the function computing the modulus of convergence. Thus the difference between the two definitions of real numbers can be thought of as the difference in the interpretation of the statement "for all... there exists..." This then opens the question as to what sort of function from a
countable In mathematics, a Set (mathematics), set is countable if either it is finite set, finite or it can be made in one to one correspondence with the set of natural numbers. Equivalently, a set is ''countable'' if there exists an injective function fro ...
set to a countable set, such as ''f'' and ''g'' above, can actually be constructed. Different versions of constructivism diverge on this point. Constructions can be defined as broadly as free choice sequences, which is the intuitionistic view, or as narrowly as algorithms (or more technically, the
computable function Computable functions are the basic objects of study in recursion theory, computability theory. Computable functions are the formalized analogue of the intuitive notion of algorithm, algorithms, in the sense that a function is computable if there ex ...
s), or even left unspecified. If, for instance, the algorithmic view is taken, then the reals as constructed here are essentially what classically would be called the computable numbers.


Cardinality

To take the algorithmic interpretation above would seem at odds with classical notions of
cardinality In mathematics, the cardinality of a set (mathematics), set is a measure of the number of Element (mathematics), elements of the set. For example, the set A = \ contains 3 elements, and therefore A has a cardinality of 3. Beginning in the late 19 ...
. By enumerating algorithms, we can show classically that the computable numbers are countable. And yet
Cantor's diagonal argument In set theory Set theory is the branch of mathematical logic that studies Set (mathematics), sets, which can be informally described as collections of objects. Although objects of any kind can be collected into a set, set theory, as a br ...
shows that real numbers have higher cardinality. Furthermore, the diagonal argument seems perfectly constructive. To identify the real numbers with the computable numbers would then be a contradiction. And in fact, Cantor's diagonal argument ''is'' constructive, in the sense that given a
bijection In mathematics, a bijection, also known as a bijective function, one-to-one correspondence, or invertible function, is a function (mathematics), function between the elements of two set (mathematics), sets, where each element of one set is pair ...
between the real numbers and natural numbers, one constructs a real number that doesn't fit, and thereby proves a contradiction. We can indeed enumerate algorithms to construct a function ''T'', about which we initially assume that it is a function from the natural numbers
onto In mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in m ...
the reals. But, to each algorithm, there may or may not correspond a real number, as the algorithm may fail to satisfy the constraints, or even be non-terminating (''T'' is a
partial function In mathematics, a partial function from a Set (mathematics), set to a set is a function from a subset of (possibly itself) to . The subset , that is, the Domain of a function, domain of viewed as a function, is called the domain of defini ...
), so this fails to produce the required bijection. In short, one who takes the view that real numbers are (individually) effectively computable interprets Cantor's result as showing that the real numbers (collectively) are not
recursively enumerable In computability theory, a set ''S'' of natural numbers is called computably enumerable (c.e.), recursively enumerable (r.e.), semidecidable, partially decidable, listable, provable or Turing-recognizable if: *There is an algorithm such that the ...
. Still, one might expect that since ''T'' is a partial function from the natural numbers onto the real numbers, that therefore the real numbers are ''no more than'' countable. And, since every natural number can be trivially represented as a real number, therefore the real numbers are ''no less than'' countable. They are, therefore ''exactly'' countable. However this reasoning is not constructive, as it still does not construct the required bijection. The classical theorem proving the existence of a bijection in such circumstances, namely the Cantor–Bernstein–Schroeder theorem, is non-constructive. It has recently been shown that the Cantor–Bernstein–Schroeder theorem implies the
law of the excluded middle In logic Logic is the study of correct reasoning. It includes both Mathematical logic, formal and informal logic. Formal logic is the science of Validity (logic), deductively valid inferences or of logical truths. It is a formal science in ...
, hence there can be no constructive proof of the theorem.


Axiom of choice

The status of the
axiom of choice In mathematics, the axiom of choice, or AC, is an axiom of set theory equivalent to the statement that ''a Cartesian product#Infinite Cartesian products, Cartesian product of a collection of non-empty sets is non-empty''. Informally put, the a ...
in constructive mathematics is complicated by the different approaches of different constructivist programs. One trivial meaning of "constructive", used informally by mathematicians, is "provable in ZF set theory without the axiom of choice." However, proponents of more limited forms of constructive mathematics would assert that ZF itself is not a constructive system. In intuitionistic theories of
type theory In mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in mo ...
(especially higher-type arithmetic), many forms of the axiom of choice are permitted. For example, the axiom AC11 can be paraphrased to say that for any relation ''R'' on the set of real numbers, if you have proved that for each real number ''x'' there is a real number ''y'' such that ''R''(''x'',''y'') holds, then there is actually a function ''F'' such that ''R''(''x'',''F''(''x'')) holds for all real numbers. Similar choice principles are accepted for all finite types. The motivation for accepting these seemingly nonconstructive principles is the intuitionistic understanding of the proof that "for each real number ''x'' there is a real number ''y'' such that ''R''(''x'',''y'') holds". According to the BHK interpretation, this proof itself is essentially the function ''F'' that is desired. The choice principles that intuitionists accept do not imply the
law of the excluded middle In logic Logic is the study of correct reasoning. It includes both Mathematical logic, formal and informal logic. Formal logic is the science of Validity (logic), deductively valid inferences or of logical truths. It is a formal science in ...
. However, in certain axiom systems for constructive set theory, the axiom of choice does imply the law of the excluded middle (in the presence of other axioms), as shown by the Diaconescu-Goodman-Myhill theorem. Some constructive set theories include weaker forms of the axiom of choice, such as the
axiom of dependent choice In mathematics, the axiom of dependent choice, denoted by \mathsf , is a weak form of the axiom of choice ( \mathsf ) that is still sufficient to develop most of real analysis. It was introduced by Paul Bernays in a 1942 article that reverse mathem ...
in Myhill's set theory.


Measure theory

Classical
measure theory In mathematics, the concept of a measure is a generalization and formalization of Geometry#Length, area, and volume, geometrical measures (length, area, volume) and other common notions, such as mass and probability of events. These seemingly ...
is fundamentally non-constructive, since the classical definition of
Lebesgue measure In Measure (mathematics), measure theory, a branch of mathematics, the Lebesgue measure, named after france, French mathematician Henri Lebesgue, is the standard way of assigning a measure (mathematics), measure to subsets of ''n''-dimensional Eucl ...
does not describe any way how to compute the measure of a set or the integral of a function. In fact, if one thinks of a function just as a rule that "inputs a real number and outputs a real number" then there cannot be any algorithm to compute the integral of a function, since any algorithm would only be able to call finitely many values of the function at a time, and finitely many values are not enough to compute the integral to any nontrivial accuracy. The solution to this conundrum, carried out first in , is to consider only functions that are written as the pointwise limit of continuous functions (with known modulus of continuity), with information about the rate of convergence. An advantage of constructivizing measure theory is that if one can prove that a set is constructively of full measure, then there is an algorithm for finding a point in that set (again see ). For example, this approach can be used to construct a real number that is normal to every base.


The place of constructivism in mathematics

Traditionally, some mathematicians have been suspicious, if not antagonistic, towards mathematical constructivism, largely because of limitations they believed it to pose for constructive analysis. These views were forcefully expressed by
David Hilbert David Hilbert (; ; 23 January 1862 – 14 February 1943) was a German mathematician, one of the most influential mathematicians of the 19th and early 20th centuries. Hilbert discovered and developed a broad range of fundamental ideas in many a ...
in 1928, when he wrote in Grundlagen der Mathematik, "Taking the principle of excluded middle from the mathematician would be the same, say, as proscribing the telescope to the astronomer or to the boxer the use of his fists".
Stanford Encyclopedia of Philosophy The ''Stanford Encyclopedia of Philosophy'' (''SEP'') combines an online encyclopedia of philosophy with scholarly peer review, peer-reviewed publication of original papers in philosophy, freely accessible to Internet users. It is maintained by S ...

Constructive Mathematics
Errett Bishop, in his 1967 work ''Foundations of Constructive Analysis'', worked to dispel these fears by developing a great deal of traditional analysis in a constructive framework. Even though most mathematicians do not accept the constructivist's thesis that only mathematics done based on constructive methods is sound, constructive methods are increasingly of interest on non-ideological grounds. For example, constructive proofs in analysis may ensure witness extraction, in such a way that working within the constraints of the constructive methods may make finding witnesses to theories easier than using classical methods. Applications for constructive mathematics have also been found in typed lambda calculi,
topos theory In mathematics, a topos (, ; plural topoi or , or toposes) is a category (mathematics), category that behaves like the category of Sheaf (mathematics), sheaves of Set (mathematics), sets on a topological space (or more generally: on a Site (math ...
and
categorical logic __NOTOC__ Categorical logic is the branch of mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their ch ...
, which are notable subjects in foundational mathematics and
computer science Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...
. In algebra, for such entities as topoi and
Hopf algebra Hopf is a German surname. Notable people with the surname include: * Eberhard Hopf (1902–1983), Austrian mathematician * Hans Hopf (1916–1993), German tenor * Heinz Hopf (1894–1971), German mathematician * Heinz Hopf (actor) (1934–2001), Sw ...
s, the structure supports an internal language that is a constructive theory; working within the constraints of that language is often more intuitive and flexible than working externally by such means as reasoning about the set of possible concrete algebras and their
homomorphism In algebra, a homomorphism is a morphism, structure-preserving map (mathematics), map between two algebraic structures of the same type (such as two group (mathematics), groups, two ring (mathematics), rings, or two vector spaces). The word ''homo ...
s. Physicist Lee Smolin writes in '' Three Roads to Quantum Gravity'' that topos theory is "the right form of logic for cosmology" (page 30) and "In its first forms it was called 'intuitionistic logic'" (page 31). "In this kind of logic, the statements an observer can make about the universe are divided into at least three groups: those that we can judge to be true, those that we can judge to be false and those whose truth we cannot decide upon at the present time" (page 28).


Mathematicians who have made major contributions to constructivism

*
Leopold Kronecker Leopold Kronecker (; 7 December 1823 – 29 December 1891) was a Germans, German mathematician who worked on number theory, abstract algebra, algebra and mathematical logic, logic. He criticized Georg Cantor's work on set theory, and was quoted b ...
(old constructivism, semi-intuitionism) * L. E. J. Brouwer (founder of intuitionism) * A. A. Markov (forefather of Russian school of constructivism) *
Arend Heyting __NOTOC__ Arend Heyting (; 9 May 1898 – 9 July 1980) was a Dutch mathematician A mathematician is someone who uses an extensive knowledge of mathematics in their work, typically to solve mathematical problems. Mathematicians are conce ...
(formalized intuitionistic logic and theories) * Per Martin-Löf (founder of constructive type theories) * Errett Bishop (promoted a version of constructivism claimed to be consistent with classical mathematics) * Paul Lorenzen (developed constructive analysis)


Branches

* Constructive logic * Constructive type theory * Constructive analysis * Constructive non-standard analysis


See also

* * * * * * * *


Notes


References

* * * * * * * * * * *


External links

*
Stanford Encyclopedia of Philosophy entry
{{DEFAULTSORT:Constructivism (Mathematics) Epistemology