A cute math puzzle that I saw twice in the past week.
There are three parts. The first two are supposed to be very easy.
- Are there two irrational numbers a and b such that a+b is rational?
- Are there two irrational numbers a and b such that ab is rational?
- Are there two irrational numbers a and b such that ab is rational?
Sources: The Princeton Companion and Richard Lipton's blog, quoting a talk by Manny Blum.
8 comments:
1. Let a = sqrt(2) and b = -sqrt(2)
2. Let a = b = sqrt(2)
3. If sqrt(2)^sqrt(2) is rational, let a = b = sqrt(2). Otherwise, let a = sqrt(2)^sqrt(2) and let b = sqrt(2). a^b = (sqrt(2)^sqrt(2))^sqrt(2) = sqrt(2)^(sqrt(2)*sqrt(2)) = sqrt(2)^2 = 2.
That's exactly the proof in The Companion!
#3 is the simplest non-constructive proof I know, other than the various ways of saying LEM.
other than the various ways of saying LEM.
Are you saying that the proof of, say, x=~~x starting from x\/~x is non-constructive? I remember writing down natural deduction style proofs for various equivalent formulations of the excluded middle, but I find the constructive / non-constructive distinction to be rather meaningless for such proofs.
Perhaps I'm misunderstanding.
I realized I misread the puzzle in Lipton's post: It wants a=b, so the proof above doesn't work. The answer is supposedly still `yes'.
If we replace sqrt(2) by q in the argument above and force a=b then we get: "either (1) q^q is rational or (2) q^(q^(q+1)) is". So it is sufficient to find an irrational number q such that q^(q^(q+1)) is rational. If we set q=sqrt(p) where p is some prime then we see that it's sufficient to find some prime number such that sqrt(p)^(sqrt(p)+1) is even. But none of these two tasks seems easier to me :(
Perhaps a different approach is needed?
Oops. For sqrt(p)^(sqrt(p)+1) to be even we need sqrt(p) to be odd, which is clearly not possible.
Oops. I think I'll better wait until I wake up today.
re:LEM:
I guess it depends on which proof one thinks one is doing. Certainly, proofs of (forall a . a \/ ~ a) -> (forall a . ~~a -> a) are constructive. But proofs of (forall a . ~~a -> a) are (always?) non-constructive.
Post a Comment
Note: (1) You need to have third-party cookies enabled in order to comment on Blogger. (2) Better to copy your comment before hitting publish/preview. Blogger sometimes eats comments on the first try, but the second works. Crazy Blogger.