Added to Favorites

Related Searches

Definitions

Nearby Words

In the philosophy of mathematics, constructivism asserts that it is necessary to find (or "construct") a mathematical object to prove that it exists. When one assumes that an object does not exist and derives a contradiction from that assumption, one still has not found the object and therefore not proved its existence, according to constructivists. See constructive proof.

Constructivism is often confused with intuitionism, but in fact, intuitionism is only one kind of constructivism. Intuitionism maintains that the foundations of mathematics lie in the individual mathematician's intuition, thereby making mathematics into an intrinsically subjective activity. Constructivism is not based on this view of intuition, and is entirely consonant with an objective view of mathematics.

For instance, in Heyting arithmetic, one can prove that for any proposition p which does not contain quantifiers, $forall\; x,y,z,ldots\; in\; mathbb\{N\}\; :\; 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 which 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 is the assertion that every even number (greater than 2) is the sum of two prime numbers. 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. 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.

By rejecting the law of the excluded middle as an axiom, the remaining logical system has an existence property which classical logic does not: whenever $exists\_\{xin\; X\}\; P(x)$ is proven constructively, then in fact $P(a)$ is proven constructively for (at least) one particular $ain\; X$, often called a witness. Thus the proof of the existence of a mathematical object is tied to the possibility of its construction.

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)\; |f(i)\; -\; f(j)|\; le\; \{1\; over\; n\}$

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\_\{i=0\}^n\; \{1\; over\; i!\},\; ;\; 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\; \{1\; over\; n\}$

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 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 functions), 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.

To take the algorithmic interpretation above would seem at odds with classical notions of cardinality. By enumerating algorithms, we can show classically that the computable numbers are countable. And yet Cantor's diagonal argument 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 between the real numbers and natural numbers, one constructs a real number which 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 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), so this fails to produce the required bijection. In short, one who takes the view that real numbers are effectively computable interprets Cantor's result as showing that the real numbers are not recursively enumerable.

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. In fact the cardinality of sets fails to be totally ordered (see Cantor–Bernstein–Schroeder theorem).

Nevertheless, not every mathematician accepts that Bishop did so successfully, since his book is necessarily more complicated than a classical analysis text would be.

More recently, the formalism of constructivist mathematics has been gaining increased credibility since natural applications for it have been found in typed lambda calculi, topos theory and categorical logic, which are extremely notable subjects in foundational mathematics and computer science.

- Errett Bishop
- Paul Lorenzen
- A.A. Markov (constructive mathematics and logic)
- Leopold Kronecker (old constructivism)
- L.E.J. Brouwer (intuitionism)
- Arend Heyting (intuitionistic logic)
- Saul Kripke (intuitionistic logic)

- A. S. Troelstra (1991), "A History of Constructivism in the 20th Century", University of Amsterdam, ITLI Prepublication Series ML-91-05, http://staff.science.uva.nl/~anne/hhhist.pdf, A detailed survey for specialists: §1 Introduction, §2 Finitism & §2.2 Actualism, §3 Predicativism and Semi-Intuitionism, §4 Brouwerian Intuitionism, §5 Intuitionistic Logic and Arithmetic, §6 Intuitionistic Analysis and Stronger Theories, §7 Constructive Recursive Mathematics, §8 Bishop's Constructivism, §9 Concluding Remarks. Approximately 80 references.
- Solomon Feferman (1997), Relationships between Constructive, Predicative and Classical Systems of Analysis, http://math.stanford.edu/~feferman/papers/relationships.pdf. A detailed survey for specialists. 22 references.

Wikipedia, the free encyclopedia © 2001-2006 Wikipedia contributors (Disclaimer)

This article is licensed under the GNU Free Documentation License.

Last updated on Sunday October 05, 2008 at 20:01:31 PDT (GMT -0700)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

This article is licensed under the GNU Free Documentation License.

Last updated on Sunday October 05, 2008 at 20:01:31 PDT (GMT -0700)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

Copyright © 2015 Dictionary.com, LLC. All rights reserved.