MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

3 added 561 characters in body

The terms "constructive" and "non-constructive" proofs have much wider application than discrete mathematics and algorithms for finite sets. And they can have have several meanings. A non-constructive proof proves that something exists but gives no way to construct the object. For example, one can prove existence of transcendentasl numbers by a simple countability argument. This proof does not give you a single example, it is non-constructive. And such proofs are actually abundant in mathematics. See, for example MR1852188 M. Kontsevich, D. Zagier, Periods.

Liouville's proof of existence of transcendental numbers is constructive. Some results do not have any constructive proof at all, I mean the things related to Hahn-Banach. For example, every vector space has a basis. But you cannot really give an example of a basis of the vector space R over Q. By giving an example, I mean you define the set in the sense that for every number you can tell whether it is in the set or not.

Another example, of different sort. There are famous theorems in number theory which say that certain inequalities or equations have finitely many solutions. But sometimes the proof does not tell in principle how to obtain ANY upper estimate. These are non-constructive proofs. Then people spend a lot of efforts to give an explicit estimate. Here constructive proofs sometimes exist, sometimes not.

In Analysis, we all know that every continuous function on a compact set has a maximum. But there are plenty of interesting continuous functions on interesting compact sets, for which we know nothing else (how many maxima? Is the absolute maximum less than 10 or not, and don't know how to answer these questions). Here existence of a maximum is a typical non-constructive proof.

In the beginning of XX century some mathematicians did not recognize non-constructive proofs as valid. They In particular, they did not accept unlimited application of the axiom of choice. Some did not accept uncountable sets at all.

This gave the origin to a kind of mathematics which in known under the names Constructive mathematics in USSR and Intuitionism elsewhere. Roughly speaking in Intuitionism only those existence proofs are recognized which give an algorithm to construct them. For example, in Intuitionist mathematics it is not always true that a bounded increasing sequence has a limit.

If you are interested, there is a nice little book

MR0075147 Heyting, A. Intuitionism. An introduction. North-Holland Publishing Co., Amsterdam, 1956. viii+133 pp.

which gives a very readable introduction.

When I was a student in 1970-s, some ordinary mathematicians (I mean non-logicians) in some places were still concerned with these issues.

2 added 1402 characters in body

The terms "constructive" and "non-constructive" proofs have much wider application than discrete mathematics and algorithms for finite sets. And they can have have several meanings.And such proofs are actually abundant in mathematics. See, for exampleMR1852188 M. Kontsevich, D. Zagier, Periods.

same existence of transcendental numbers is constructive.of the vector space R over Q. By giving an example, I mean you define the set in the sensethat for every number you can tell whether it is in the set or not.

Another example, of different sort. There are famous theorems in number theory which say that certain inequalitiesor equations have finitely many solutions. But sometimes the proof does not tell in principlehow to obtain ANY upper estimate. These are non-constructive proofs. Then people spend a lotof efforts to give an explicit estimate. Here constructive proofs sometimes exist, sometimes not.

In the beginning of XX century some mathematicians did not recognize non-constructive proofs as valid. They did not accept unlimited application of the axiom of choice.

This gave the origin to a kind of mathematics which in known under the names Constructivemathematics in USSR and Intuitionism elsewhere. Roughly speaking in Intuitionism only thoseexistence proofs are recognized which give an algorithm to construct them.

If you are interested, there is a nice little book

MR0075147 Heyting, A. Intuitionism. An introduction. North-Holland Publishing Co., Amsterdam, 1956. viii+133 pp.

which gives a very readable introduction.

When I was a student in 1970-s, some ordinary mathematicians (I mean non-logicians) in some places were still concerned with these issues.

1

The terms "constructive" and "non-constructive" proofs have much wider application than discrete mathematics. And they can have have several meanings. A non-constructive proof proves that something exists but gives no way to construct the object. For example, one can prove existence of transcendentasl numbers by a simple countability argument. This proof does not give you a single example, it is non-constructive. Liouville's proof of the same is constructive. Some results do not have any constructive proof at all, I mean the things related to Hahn-Banach. For example, every vector space has a basis. But you cannot really give an example of a basis of the vector space R over Q.

In the beginning of XX century some mathematicians did not recognize non-constructive proofs as valid.