Talk:Constructive proof

From Wikipedia, the free encyclopedia

It seems to me that this, existence theorem and nonconstructive proof all cover the same ground. It would be better to merge all three, I think, and get one substantive article.

Charles Matthews 17:37, 10 Nov 2003 (UTC)

A good section on Boyer-Moore theory and the Boyer-Moore theorem prover would help here. There's a whole area of sucessful constructive mathematics that needs to be covered.

One big problem with constructive proofs is that they tend to require case analysis and become bulky. With machine assistance, this is less of a problem.

John Nagle 13:37, 21 Feb 2006 (PST)

[edit] Why is the proof based on uncountability nonconstructive?

The statement that the set of algebraic numbers is countable is equivalent to the statement that there exists an algorithm that enumerates them all with increasing precision, i.e. it outputs the decimal approximation of each consecutive number with precision growing by 1 in each turn. We can now use diagonalization to construct a decimal expansion of a real number where each digit is different from the respective digit of the respective algebraic number in the enumerating sequence. This procedure produces a transitive number and it is well-defined: it can produce any digit of the decimal expansion upon request. That allows us to compare the number to any rational number and to create a Dedekind section out of it. What is nonconstructive here?

Well, sure, but that's a diagonal argument, and it is not the same as the proof based on uncountability. As the article says:

We may distinguish three different problems. The first is that of proving the existence of transcendental numbers (without necessarily providing a specimen). The second is that of giving an example of a transcendental number by a construction specially designed for the purpose. The third, which is much more difficult, is that of proving that some number given independently ... is transcendental.

So "algebraics are countable, reals are uncountable, therefore transcendentals exist" is a (non-constructive) solution to the first, your proof is a solution to the second (we could include it in the article as such), and a proof that pi is transcendental is a solution to the third. On the other hand, perhaps we should just find a better example. 192.75.48.150 15:12, 24 July 2006 (UTC)