10
$\begingroup$

I was wondering if it is possible to define exactly what a non-constructive (nc) proof is. I have often seen the concept associated with the use of principles such as the axiom of choice or the law of excluded middle, (and the former implies the latter, this is Diaconescu's theorem). Would it be correct to say that a nc proof is a proof which uses something that implies the principle of excluded middele? Here are another couple of doubts I have on the subject:

1) Often certain types of theorems in analysis are said to be "non-constructive". For example, the Picard–Lindelöf theorem on the existence and uniqueness of solutions for certain types of differential equations is often characterized as such, since it doesn't provide an explicit analytic expression for the solution. However it doesn't seem as though the proof for this theorem relies on any nc principles, rather it relies on the Banach fixed point theorem, which provides a sequence defined by a recurrence relation which converges pointwise to the solution. Although analytically useless, shouldn't this way of defining the solution be formally as constructive as any?

2) Are proofs by contradiction nc? For example, as discussed in this post Is there an intuitionist (i.e., constructive) proof of the infinitude of primes?, the classical proof of the infinitude of primes is nc if it only reaches a contradiction, but as pointed out in the answers it can easily be modified so it defines an algorithm which comes up with the (n+1)th prime. If proofs by contradiction are nc, what is the nc principle that they use?

  • 0
    Also, working in a constructive system does not prevent you from using LEM or double negation. You just need to state those as assumptions.2014-08-13

2 Answers 2

7

I apologize if this answer ends up a little vague.

There is no one definition of what "constructive" or "non-constructive" means. Even in the community of mathematical constructivism, there are many disagreements. Just the title of one classic book, "Varieties of constructive analysis", already suggests this.

I can point out two common issues with constructive or non-constructive proofs.

  • Constructiveness depends on proof methods. For example, the classical inference rule of double negation elimination ("From $\lnot \lnot P$ derive $P$") is usually viewed as nonconstructive. But a somewhat similar rule of ex falso quodlibet ("From $P$ and $\lnot P$ derive any sentence $Q$") was viewed as acceptable to proponents of intuitionism. The status of the axiom of choice varies greatly from one program of constructive mathematics to another.

  • Constructiveness depends on representations. The things that can be done constructively with a mathematical object depend on how the object is represented. For example, in general one cannot prove constructively that for any real number $a$ either $a < 0$, $a = 0$, or $a > 0$. This is because the usual system for representing real numbers does not allow this question to be answered in constructive manner just given a representation for $a$. On the other hand, it is possible in many constructive systems to prove that any integer is "negative, 0, or positive", because the representation of an integer used in such systems is sufficiently nice to allow the answer to be constructively determined from the representation. Note that for some constructivists the "representation" that matters is the mental representation they have.

These two items are related because the constructively permissible proof methods depend greatly on the representations being used. For example, the appropriate forms of the axiom of choice are non-constructive relative to CZF set theory but are constructive relative to Martin-Löf type theory.

Back to the original question. There are many constructive proofs that do not use any methods that imply the entire law of the excluded middle. For example the proof might just use the so-called "lesser limited principle of omniscience" which does not imply excluded middle. In fact I do not know whether there is any one sentence in the language of Heyting arithmetic that implies the entire law of the excluded middle over the rest of HA.

  • 0
    Thank you for your answer. I guess I knew there wasn't a strightforward definition of constructiveness before I posted the question, still I hear the word a lot and I sometimes think it is misused. I will read up on the principles of omnicence, it looks very interesting.2011-11-13
4

Two good online resources to start learning about constructive mathematics are Wikipedia and SEP. There are also several nice books and surveys on constructive mathematics and its varieties. Here are some I like more:

Survey:

Books:

  • A. Heyting, "Intuitionism — An Introduction", 1971

  • M. Beeson, "Foundations of Constructive Mathematics", 1985

  • D. van Dalen and A.S. Troelstra, "Constructivism in Mathematics: An Introduction", two volumes, 1988

  • D. Bridges, F. Richman, "Varieties of Constructive Mathematics", 1987

  • Per Martin-Löf "Intuitionistic Type Theory", 1984 (note: this is quite old and Martin-Löf has made several significant changes to this views over time which are to best of my knowledge are not published in a nice form unfortunately.)

For most constructive mathematicians, the essence of mathematics is not formal proofs but constructions. What they mean by construction varies, e.g. for Brouwer these are mental constructions, mathematical objects (particularly infinite mathematical objects) do not have a mind independent existence. So to prove some object exists you should construct it. How can be construct a mental mathematical objects? According to some intuitionist, a mathematician can directly understand what a construction by his/her intuition. There are methods for construction that has been accepted but there is not an a priori bound possible methods, some mathematician can come up with a new method of construction tomorrow. With this in mind it becomes more clear why they expect the justification for nonexistence of an object to be a construction converting a hypothetical construction for it to a construction for contradiction. A good starting point to understand these is the BHK interpretation. As Carl has pointed out there are subtle points about how these constructions are represented, in particular what is the representations for the inputs and the outputs of a functional construction. Many classically identical concepts are not constructively identical, for example there are differences between a function and an operation (see Beeson 1985 for more details). So in constructive mathematics we have more fundamental concepts than we have in classical mathematics where many of these concepts can be reduced to definitions based on other ones and one should be careful about the meaning of statements. When one writes $\forall f \ldots$ is $f$ an operation or a function? and so on.

Other than variations of Bouwer's intuitionism, there are three other active versions of constructivism: 1. Recursive/Computable Mathematics interprets construction as computable function (related to Russian school of constructivism and Markov), 2. Bishop style constructivism which is consistent with classical mathematics and also with intuitionism and computable mathematics, and 3. Martin-Löf's type theory which is more delicate than others (at least IMHO).

So it is not easy how you can rule out that a theorem does not have a constructive proof in the sense of intuitionism (unless one has a constructive proof that would convert such hypothetical proofs to constructive proofs of contradiction) since the possible constructions are not limited to those we have currently, and checking if a given proof is a constructive proof is an intuitive concept which is not defined formally and cannot be checked based on a fixed set of rules (e.g. by a computer program). So in theory, every classical theorem that is not ruled out by a constructive proof can potentially have a constructive proof and it is difficult to give counterexamples to classical reasoning. On the other hand Brouwer developed what is called weak-counter examples, statements that their correctness would imply that we know something at this moment which we don't, e.g. convergence of all Cauchy sequences of rational numbers implies that either we know that GC (Goldbach's Conjecture) is true or that we know GC is false, and right now we don't know either. (GC is not essential for the argument, we can replace it with any $\Pi_1$ formula that we don't know it is true and we don't know it is false).

  • 0
    If we take an intuitionistic theory, e.g. HA (the intuitionistic version of PA) then PEM for HA's Godel sentence is not provable in HA because HA has the [disjunction property](http://en.wikipedia.org/wiki/Disjunction_and_existence_properties).2011-11-22