[math-fun] Request for example elementary non-constructive proofs with "witnesses"
Could anyone supply me with elementary examples that illustrate the idea of a non-constructive proof, for those with a "Martin Gardner reader" level of mathematical sophistication that also has a not-too-trivial but reasonably easily-verified case? For example a non-constructive proof that some set of numbers is non-empty, along with an example of such a number that can be fairly easily checked? Thanks!
Theorem: There exist irrationals x, y such that x^y is rational. Proof: Suppose that we already know that sqrt(2) is irrational. If sqrt(2)^sqrt(2) is rational, then the proof is done. If not (i.e. sqrt(2)^sqrt(2) is irrational), then (sqrt(2)^sqrt(2))^sqrt(2) = 2, a rational. Hope this helps. Warut On Mon, Nov 14, 2011 at 3:04 AM, Marc LeBrun <mlb@well.com> wrote:
Could anyone supply me with elementary examples that illustrate the idea of a non-constructive proof, for those with a "Martin Gardner reader" level of mathematical sophistication that also has a not-too-trivial but reasonably easily-verified case? For example a non-constructive proof that some set of numbers is non-empty, along with an example of such a number that can be fairly easily checked? Thanks!
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
On 13 Nov 2011 at 12:04, Marc LeBrun wrote:
Could anyone supply me with elementary examples that illustrate the idea of a non-constructive proof, for those with a "Martin Gardner reader" level of mathematical sophistication that also has a not-too-trivial but reasonably easily-verified case?
How about the existence of irrational numbers? The classic proof that sqrt(2) cannot be rational shows the existence of such numbers, but says essentially nothing about how to find more or how many of them there are, etc. /Bernie\ -- Bernie Cosell Fantasy Farm Fibers mailto:bernie@fantasyfarm.com Pearisburg, VA --> Too many people, too few sheep <--
From: Bernie Cosell <bernie@fantasyfarm.com> To: math-fun <math-fun@mailman.xmission.com> Sent: Sunday, November 13, 2011 12:27 PM Subject: Re: [math-fun] Request for example elementary non-constructive proofs with "witnesses"
On 13 Nov 2011 at 12:04, Marc LeBrun wrote:
Could anyone supply me with elementary examples that illustrate the idea of a non-constructive proof, for those with a "Martin Gardner reader" level of mathematical sophistication that also has a not-too-trivial but reasonably easily-verified case?
How about the existence of irrational numbers? The classic proof that sqrt(2) cannot be rational shows the existence of such numbers, but says essentially nothing about how to find more or how many of them there are, etc.
/Bernie\
--
Another nice example is Cantor's diagonalization proof that there are uncountably many real numbers. Since it is easy to see that there are only countably many rational or algebraic numbers, it follows that there exist (uncountably many) irrationals and transcendentals, but Cantor's proof does not exhibit any example of such. An actual transcendental number was first discovered by Liouville in 1851, predating Cantor. -- Gene
On Sun, Nov 13, 2011 at 12:04 PM, Marc LeBrun <mlb@well.com> wrote:
Could anyone supply me with elementary examples that illustrate the idea of a non-constructive proof, for those with a "Martin Gardner reader" level of mathematical sophistication that also has a not-too-trivial but reasonably easily-verified case? For example a non-constructive proof that some set of numbers is non-empty, along with an example of such a number that can be fairly easily checked? Thanks!
This too is in a slightly different direction than the other examples given, but I think it might prove useful to you: Demonstrate that the game of Chomp <http://en.wikipedia.org/wiki/Chomp> has a winning strategy for the first player while making the point that finding an actual strategy is much more difficult and in most cases remains a mystery. Once the (fairly simple) rules of the game are laid down, it's pretty easy to convince the audience that either the first player has an opening move that stumps the opponent, or they don't; in the latter case, the opponent has a winning response to anything the first player throws at them. But this latter case is seen to be impossible by "strategy stealing": if that were the case, the second player could respond to a "nip the corner" first move, and that response might well have been played by the first player to begin with. Thus, there is a strategy, but we don't know what it is. A simple case where it *is* known is the square board, and you can probably show one also for some small board like the 2x3, but it shouldn't fail to impress your audience that we have just logically shown that there must be a winning play for the 17x29 board but we have no idea what it is - and probably nobody else does either.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
This is the one I've been trying to remember. Thank you, Alon. This also reminds me of the proof that the Game of Life has a finite Garden of Eden pattern. (Since the original proof, many explicit predecessorless patterns have been found.) It depends on counting possible predecessors and shows that for a certain class of patterns, the number of candidate predecessors is smaller than the number of patterns, so one of that class must lack a predecessor. The class is astronomically large, though, and the counting argument gives no hints about how to find an example. On Sun, Nov 13, 2011 at 5:29 PM, Alon Amit <alon.amit@gmail.com> wrote:
On Sun, Nov 13, 2011 at 12:04 PM, Marc LeBrun <mlb@well.com> wrote:
Could anyone supply me with elementary examples that illustrate the idea of a non-constructive proof, for those with a "Martin Gardner reader" level of mathematical sophistication that also has a not-too-trivial but reasonably easily-verified case? For example a non-constructive proof that some set of numbers is non-empty, along with an example of such a number that can be fairly easily checked? Thanks!
This too is in a slightly different direction than the other examples given, but I think it might prove useful to you: Demonstrate that the game of Chomp <http://en.wikipedia.org/wiki/Chomp> has a winning strategy for the first player while making the point that finding an actual strategy is much more difficult and in most cases remains a mystery.
Once the (fairly simple) rules of the game are laid down, it's pretty easy to convince the audience that either the first player has an opening move that stumps the opponent, or they don't; in the latter case, the opponent has a winning response to anything the first player throws at them. But this latter case is seen to be impossible by "strategy stealing": if that were the case, the second player could respond to a "nip the corner" first move, and that response might well have been played by the first player to begin with.
Thus, there is a strategy, but we don't know what it is. A simple case where it *is* known is the square board, and you can probably show one also for some small board like the 2x3, but it shouldn't fail to impress your audience that we have just logically shown that there must be a winning play for the 17x29 board but we have no idea what it is - and probably nobody else does either.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
I think the original counting argument was Moore's, and it easily applied directly to Life. However, there's an easy example of a GOE from the counting argument: The argument shows that there's some GOE pattern, of size < a computable number N. To make the argument constructive, just make up a supersize pattern, with all possible patterns of size N. Wrt showing Louiville numbers are transcendental: Use the example L = sum 10 ^ (- N!). In this special case, it's not too hard to check that L defeats any prospective polynomial. Rich --- Quoting Allan Wechsler <acwacw@gmail.com>:
This is the one I've been trying to remember. Thank you, Alon.
This also reminds me of the proof that the Game of Life has a finite Garden of Eden pattern. (Since the original proof, many explicit predecessorless patterns have been found.) It depends on counting possible predecessors and shows that for a certain class of patterns, the number of candidate predecessors is smaller than the number of patterns, so one of that class must lack a predecessor. The class is astronomically large, though, and the counting argument gives no hints about how to find an example. <...>
Thanks for the many excellent suggestions to think about! Some of them might work; I'll have to ponder further. Just to be clear, I'm asking for a bit MORE than just an existence proof that gives no hint of how to find an example. There are indeed a number of notorious cases of those (I appreciate the reminders). However what I want is one of those, PLUS an actual non-trivial example case that's reasonably easily verifiable. The example shouldn't be immediately obvious, and would probably be obtained using either more advanced methods, or else just brute force. As an illustrative analogy: an elementary non-constructive proof that there are integers that are sums of two cubes in two different ways, PLUS a statement like, "oh, and by the way, 1729 is the smallest such, which you can easily verify by 12^3+1^3=10^3+9^3" or the like would hit the spot. (The second "1729" part of this fills the bill, but the first part is either obvious, or else could entail showing that some generating function wasn't identically zero, which isn't exactly "elementary"). Perhaps Gene's suggestion can be made to work. Certainly the wonderful Cantor diagonal proof is easy enough. But traditionally we'd show the transcendence of some particular example Liouville number X in two stages, by first proving that ALL Liouville numbers are transcendental, and then showing that X is Liouville. Can we keep this argument sufficiently elementary yet make it more direct? Thanks!
From: Marc LeBrun <mlb@well.com> To: math-fun <math-fun@mailman.xmission.com> Sent: Sunday, November 13, 2011 3:39 PM Subject: Re: [math-fun] Request for example elementary non-constructive proofs with "witnesses"
Thanks for the many excellent suggestions to think about! Some of them might work; I'll have to ponder further.
Just to be clear, I'm asking for a bit MORE than just an existence proof that gives no hint of how to find an example.
There are indeed a number of notorious cases of those (I appreciate the reminders).
However what I want is one of those, PLUS an actual non-trivial example case that's reasonably easily verifiable.
The example shouldn't be immediately obvious, and would probably be obtained using either more advanced methods, or else just brute force. ... Perhaps Gene's suggestion can be made to work. Certainly the wonderful Cantor diagonal proof is easy enough. But traditionally we'd show the transcendence of some particular example Liouville number X in two stages, by first proving that ALL Liouville numbers are transcendental, and then showing that X is Liouville. Can we keep this argument sufficiently elementary yet make it more direct?
Thanks! _______________________________________________
Mark, Check it out to your own satisfaction. The proof that Liouville numbers are transcendental, and examples of actual Liouville numbers can be found in elementary number theory books, and is surely available on-line somewhere. The proof of the transcendence of e and π can be found in Niven's Carus Monograph, "Irrational Numbers". -- Gene
Aren't most proofs of the "intermediate value theorem" essentially non-constructive? http://en.wikipedia.org/wiki/Intermediate_value_theorem It's fairly easy to search for zeros of continuous functions if you have additional constraints, but for a general continuous function, you're almost forced to do an exhaustive search, which for an infinite set isn't particularly productive. At 12:04 PM 11/13/2011, Marc LeBrun wrote:
Could anyone supply me with elementary examples that illustrate the idea of a non-constructive proof, for those with a "Martin Gardner reader" level of mathematical sophistication that also has a not-too-trivial but reasonably easily-verified case? For example a non-constructive proof that some set of numbers is non-empty, along with an example of such a number that can be fairly easily checked? Thanks!
="Henry Baker" <hbaker1@pipeline.com> Aren't most proofs of the "intermediate value theorem" essentially non-constructive?
I again apologize for not being clear what I was asking for--I buried the second half of the conjunction too deeply in the prose:
=Marc LeBrun ... a non-constructive proof... that ALSO has an easily-verified case?
Come to think of it factoring provides an example: you can easily and non-constructively show that some big N is composite, AND you can easily verify that some X divides N, BUT finding X is hard. Thanks for all the suggestions!
Well, if someone shows you an x0 such that f(x0)=0, then the verification is trivial; finding that x0 might have taken eons, but once it has been found, it is easily verified. So the intermediate value theorem is still an example for you. At 08:55 AM 11/15/2011, Marc LeBrun wrote:
="Henry Baker" <hbaker1@pipeline.com> Aren't most proofs of the "intermediate value theorem" essentially non-constructive?
I again apologize for not being clear what I was asking for--I buried the second half of the conjunction too deeply in the prose:
=Marc LeBrun ... a non-constructive proof... that ALSO has an easily-verified case?
Come to think of it factoring provides an example: you can easily and non-constructively show that some big N is composite, AND you can easily verify that some X divides N, BUT finding X is hard.
Thanks for all the suggestions!
I apologize for my bad example. The following Lisp program (domain binary search) produces an approximation to a zero of f(x) at 1 bit per iteration: (defun intval (f lb ub n) ;;; Produce n'th approx to zero of f(x) in interval lb<x<ub. ;;; f(lb)<0<f(ub). (assert (minusp (funcall f lb))) (assert (minusp (- (funcall f ub)))) (cond ((minusp n) `(,lb ,ub)) ((< lb ub) (let* ((ib (/ (+ lb ub) 2)) (fib (funcall f ib))) (cond ((zerop fib) `(,ib ,ib)) ((minusp fib) (intval f ib ub (1- n))) (t (intval f lb ib (1- n)))))) (t `(,lb ,ub)))) At 09:04 AM 11/15/2011, Henry Baker wrote:
Well, if someone shows you an x0 such that f(x0)=0, then the verification is trivial; finding that x0 might have taken eons, but once it has been found, it is easily verified.
So the intermediate value theorem is still an example for you.
At 08:55 AM 11/15/2011, Marc LeBrun wrote:
="Henry Baker" <hbaker1@pipeline.com> Aren't most proofs of the "intermediate value theorem" essentially non-constructive?
I again apologize for not being clear what I was asking for--I buried the second half of the conjunction too deeply in the prose:
=Marc LeBrun ... a non-constructive proof... that ALSO has an easily-verified case?
Come to think of it factoring provides an example: you can easily and non-constructively show that some big N is composite, AND you can easily verify that some X divides N, BUT finding X is hard.
Thanks for all the suggestions!
participants (8)
-
Allan Wechsler -
Alon Amit -
Bernie Cosell -
Eugene Salamin -
Henry Baker -
Marc LeBrun -
rcs＠xmission.com -
Warut Roonguthai