[FOM] Intuitionists and excluded-middle
Dana Scott
dana.scott at cs.cmu.edu
Sun Oct 16 14:42:15 EDT 2005
"Lew Gordeew" <legor at gmx.de> wrote:
> But this is very important for most mathematicians. Most students of
> mathematics immediately ask "hey, but which x is the solution - sqrt
> (2) or
> sqrt(2)^sqrt(2)?" Now Analysis says it is sqrt(2)^sqrt(2), but
> clearly the
> LEM proof does no good to this end. I must confess though that our
> comp sci
> students are less concerned with the answer because they don't know
> much
> about irrational numbers. :-) :-(
The sqrt(2) argument is fun to consider, especially as the proof of the
irrationality of sqrt(2)^sqrt(2) is hard. But there are many ways to
give explicitly irrationals a and b so that a^b is rational, where the
proof is fairly elementary. (I think this has been posted before.)
Consider e, the basis for natural logarithms. From the power-series
expansion of e^x, it is not hard to argue that each integral power
e^n is irrational. (Hint: consider all those fractions with large
factorials in the denominators.)
Next, consider the natural logarithm, ln(2). If this were a rational
p/q, then we could conclude that 2^q = e^p, which is impossible. So,
one solution to the puzzle is to take a = e and b = ln(2). (Other
examples, perhaps more elementary, can be found by using logs to bases
such as sqrt(3).)
Here is another puzzle asking for a very quick proof using LEM (first
pointed out to me by Paul Halmos): From the construction of the reals
we know that between any two irrationals there is a rational. Show that
there is also an irrational. (Hint: If the irrationals are a < b, then
the average (a+b)/2 is a bad answer because it might be rational.)
Second question: What is a more constructive proof?
More information about the FOM
mailing list