[FOM] Non-constructiveness.
Lucas Wiman
wiman at uiuc.edu
Thu Jul 3 16:53:54 EDT 2003
> I can't see anything wrong with this. (The constructive part of) PA
> obviously decides any such statement correctly. Furthermore we have a
> constructive proof that PA is consistent (Goedel/Genzen 1933) and thus
> the whole of PA only decides it one way. Thus we have a constructive
> proof that there is a constructive proof of the result, which of course
> is a constructive proof of the result. This is really just the basic
> idea of the Hilbert programme, only substituting 'constructive' for
> 'finitary'.
I think you're missing his point. The point is that mathematicians
would be very reluctant to call these "constructive proofs," though
they're generally labeled as such. There is an area of combinatorics
called Ramsey theory which (often) deals solely with finite numbers.
Here is a big open problem in Ramsey theory:
For each number n, find the smallest number R(n) such that each
2-coloring of the edges of the complete graph on n vertices, there is a
monochromatic complete graph on n vertices.
The existence of this number for every n is pretty easy to show, but say
we want to know that R(6)=178 (which is one possible value for it, as
far as we know). Then we much show that every graph of order 178 has a
complete subgraph of order 6, and that there is some graph of order 177
that has no complete subgraph of order 6. Any such graph must be really
weird, and is hence rather hard to find by looking for it
intelligently. We can't do a brute search because there are a whole lot
of graphs of order 177!
The methods of modern combinatorics give no aid in finding the exact
value, so we have to accept it on what's been called "religious faith"
on this list. This is the sense in which it is non-constructive: an
existence theorem, even in the "large finite" arena can fail to really
give you the object of which it speaks.
- Lucas Wiman
More information about the FOM
mailing list