Hi,
Here is a little test, just for singling out a typical non
intuitionistic (non constructive) argument.
Such kind of argument makes me recall the tale: "The Little Prince"
written by the French pilot and novelist St-Exupery, where the Little
Prince asked the narrator (a pilot) to draw a sheep. But he can't draw
at all and fails badly in all his attempt to draw a sheep, so that
after a while, and because the Little Prince insisted so much,
eventually he decided to draw just a box, and told the little Prince
that the sheep was in the box.
Well, classical mathematicians does that all the time: actually they do
it each time they prove the existence of some object without exhibiting
precisely that object. Constructivist and engineers can be
disappointed, but platonist or classical mathematicians are quite cool
with such non-constructive proof.
I know by experience that even if I give the solution of the *puzzle*,
many people does not really see the non constructive step. So let me
first illustrate such a non-constructive reasoning on a very cute
example.
It is a "well known" proof that there exist irrational numbers x, y,
such that x^y is rational. We don't ask that x should be different of
y. The question is really (in english): is it possible that a
irrational number exponentiated by an irrational number gives a
rational number?
(I recall that a positive real number r is rational iff there exist
natural numbers n and m such that r is equal to m/n. r will be said
to be irrational if r is not rational. A typical irrational number is
the square root of 2, written sqrt(2)).
Here is the delightful proof by Jarden.
First note that a real number is either rational or ... irrational.
Right?
Well, if you say "yes" to this, you have already leave the constructive
area!!!! You have accepted the principle of excluded middle saying that
for any well-defined proposition p, either p is true, or p is false. In
this case p is, for some real number r, the proposition "r is
rational". The excluded middle principle gives then: "r is rational or
r is not rational", or "r is rational or is irrational".
Good ... So you agree that the real number sqrt(2) ^ sqrt(2), that is:
the (square root of two) exponentiated up to the (square root of two)
is rational or irrational. Right?
So we have just two cases to consider:
1) sqrt(2) ^ sqrt(2) is rational. Well, in that case we have a
solution: x = y = sqrt(2).
2) sqrt(2) ^ sqrt(2) is irrational. In that case just take x =
(sqrt(2) ^ sqrt(2)), and y = sqrt(2). Then, if you remember elementary
algebra, i.e. that ((a^b)^c) = a^(bc), then you see that x^y = 2 which
is rational of course.
So in all cases we have end up with an irrational which exponentiated
up to some irrational gives a rational, and we have solve the existence
problem. If you ask me a precise (constructive) solution, this
reasoning is not satisfactory. But the reasoning is far from hopeless:
the solution is given to you in a box, the box (set) containing the
couple (sqrt(2) , sqrt(2)) and the couple (sqrt(2) ^ sqrt(2) ;
sqrt(2)). I can, like St-Exupery, tell you that the solution is in the
two-elements box:
{ (x = sqrt(2) ; y = sqrt(2)) (x = sqrt(2) ^ sqrt(2) ; y =
sqrt(2)) }
But I cannot tell you which one, among the two solutions, is the
correct one.
Put in a different way I did prove a non-constructive OR proposition. I
have proved that
["x = sqrt(2) , y = sqrt(2)" is the solution] OR ["x= sqrt(2) ^
sqrt(2) ; y = sqrt(2)" is the solution].
And the or is non constructive because my reasoning does not allow us
to choose between the solution proposed on the left of the "or" or if
it is the one on the right of the "or".
In this present case, highly complex number theory (including elliptic
function theory, modular form, etc.) can settle the disjunction
constructively, but in theoretical computer science, on the contrary,
we will met many non-constructive "or" which can be proved being
necessarily non constructive. That means the non constructive solution
is the best we can ever hope for.
And that will be the case for the solution of the *puzzle*.
I don't want to jeopardize the pleasure of searching that solution, and
so I let you think a little bit more. Normally, with what Jesse and
Hall (notably) told, and what you have already seen, + the present
post, you have all the tools in the hands to explain exactly and
precisely how we can generate all computable functions in a way
vaccinated from the diagonalization procedure.
Of course, the "or" of the first person talk about its future personal
memory in the Washington Moscow duplication is also a special sort of
non constructive OR. Also, in the field of theoretical artificial
intelligence (or computational learning theory), it can be shown that
almost all "OR" are necessarily non constructive, making almost the
entire field completely empty from an intuitionist perspective.
Another example: I insist all the time that the correct part of the
Penrose-Lucas use of Godel's theorem is that it does not show that we
are not machine, but only that if we are machines then we cannot know
which one we are, and this means that the proposition "I am a machine"
*does* necessarily leave the constructive area. The proposition "I am a
machine" is equivalent (with Church thesis) with the proposition "I am
M1 OR I am M2 OR I am M3 OR I am M4 OR ...", with Mi giving an
enumeration of all machine (exist by CT). Given that I cannot know
which machine I am, all those "OR" are non constructive. Of course I
anticipate here.
OK so far? Do you want to know the solution? Do you prefer to think
about all this a couple of days?
You = Tom, or George, or others ...
Be sure to understand the problem before I give the solution. We really
are at the heart of the matter, not just of Smullyan's FU, but of all
my own work and what I am trying to say. All the nuances between the
arithmetical plotinian hypostases will emerge thanks to all those
nuances between computations, proofs, constructive, not constructive,
etc.
Bruno
http://iridia.ulb.ac.be/~marchal/
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups "Everything List" group.
To post to this group, send email to everything-list.domain.name.hidden
To unsubscribe from this group, send email to everything-list-unsubscribe.domain.name.hidden
For more options, visit this group at
http://groups.google.com/group/everything-list
-~----------~----~----~----~------~----~------~--~---
Received on Tue Jun 06 2006 - 10:39:38 PDT