tag:blogger.com,1999:blog-3722233.post5234566692235534665..comments2024-03-04T02:59:26.350-06:00Comments on Computational Complexity: A students unusual proof might be a better proofLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger14125tag:blogger.com,1999:blog-3722233.post-40575417373679481912016-12-06T15:44:31.832-06:002016-12-06T15:44:31.832-06:00I realize the remarks above may seem to contradict...I realize the remarks above may seem to contradict themselves. Let me clarify. I can construct the midpoint z of (x,y) with compass and straightedge. I can construct the midpoint w of (x,z) with compass and straightedge. I can argue that one of z or w must be irrational (given that x and y are), but I can't (constructively) tell you which. <br /><br />The student's proof doesn't have this nonconstructivity. She constructs the sequence 1/2, 1/3, etc., until she finds an n such that 1/n < y-x. Then she claims x + 1/n as a witness.stuhttps://www.blogger.com/profile/05190631846507740664noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-13536204753106133702016-12-06T15:38:17.844-06:002016-12-06T15:38:17.844-06:00Aaah I misread and believed you asked to find an i...Aaah I misread and believed you asked to find an irrational between to rationals, my bad... Then right, the proof is different (and mine is then wrong as the hypothesis I had in mind are not the right ones). So OK, the only missing thing is a formal definition of <<. Taking delta = 1/n does the trick as you say below. holfnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-5488203477550666282016-12-06T15:11:38.441-06:002016-12-06T15:11:38.441-06:00What I like about both my proof and the student...What I like about both my proof and the student's is that they are constructive in the rather extreme sense of relying on algebraic properties of reals that can be demonstrated by classical compass and straightedge constructions (cf., Galois theory). <br /><br />There's an interesting difference between them, which may well be sharp. The student gives a fully constructive proof, beginning with the lengths [1,x,y]. I give a nonconstructive proof beginning with just [x,y]. Is it possible to give construct a number z from lengths x, y such that z will be irrational whenever x and y are? [I.e., without a unit reference]. I doubt it.<br />stuhttps://www.blogger.com/profile/05190631846507740664noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-52085478671783122362016-12-06T15:10:15.678-06:002016-12-06T15:10:15.678-06:00Today I learned about Hilbert's 24. problem (h...Today I learned about Hilbert's 24. problem (https://en.wikipedia.org/wiki/Hilbert's_twenty-fourth_problem) and today I read Bill's question.<br />Sounds a little bit related. Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-31957393959166452972016-12-06T14:52:36.439-06:002016-12-06T14:52:36.439-06:00Yes- I meant to say `there are an uncountable numb...Yes- I meant to say `there are an uncountable number of REALS'<br />and have made that correction.<br /><br />I like your midpoint/midpoint proof!GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-29092911100108982222016-12-06T14:10:27.435-06:002016-12-06T14:10:27.435-06:00Knowing that the reciprocals of the integers are d...Knowing that the reciprocals of the integers are dense near zero is enough. I don't buy your proof of the irrational theorem, which (it seems to me) begins by assuming what it is supposed to prove.<br /><br />I think what you wanted to say is that there are uncountably many numbers between x and y (consider the natural linear surjection between [0,1] and [x,y]), only countably many of which are rational, ergo, uncountably many irrationals.<br /><br />Here's an alternative :-). Consider the midpoint z of (x,y). If z is irrational, we're done. Otherwise the midpoint of (x,z) must be irrational (as it is the average of a rational and an irrational).stuhttps://www.blogger.com/profile/05190631846507740664noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-62930951273820005142016-12-06T14:03:05.045-06:002016-12-06T14:03:05.045-06:00Saying it another way, the quantity
x + 1/ceil(1/(...Saying it another way, the quantity<br />x + 1/ceil(1/(y-x))<br />is no more than y, since<br />1/ceil(1/(y-x)) <= 1/(1/(y-x)) = y-x,<br />and since the rationals are closed under addition, the quantity is rational when x is.<br /><br />The closure of the rationals under addition implies that the sum of a rational and an irrational is irrational, so the same quantity is irrational when x is irrational.<br /><br />Using (x+y)/2 instead is just as easy for the rational x,y case, but not for irrational x,y.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-2829450975643317152016-12-06T13:56:38.611-06:002016-12-06T13:56:38.611-06:00A proof is a proof ...A proof is a proof ...Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-58075250168294717852016-12-06T12:30:48.466-06:002016-12-06T12:30:48.466-06:00AH- for one thing I should define << more ca...AH- for one thing I should define << more carefully.<br />We need to find a rational delta such that<br /><br />x+ delta < y<br /><br />OH- all I need is delta < y-x.<br /><br />Okay then. For all n, 1/n is rational and the sequence<br />cvg to 0. Hence there is an n such that 1/n < y-x<br /><br />bill g.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-33815158611829390882016-12-06T11:52:30.212-06:002016-12-06T11:52:30.212-06:00How can you just assume there is a small and ratio...How can you just assume there is a small and rational delta between x and y? I'd want that proven to me otherwise the "proof" is just hand waving.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-21619302214234509132016-12-06T11:44:49.697-06:002016-12-06T11:44:49.697-06:00Bill: the student's proof about existence of i...Bill: the student's proof about existence of irrational number between two irrationals is very nice! But the first one is incomplete: Why can you assume there is 0 < δ << y - x that is rational?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-43279859195094750062016-12-06T10:11:51.990-06:002016-12-06T10:11:51.990-06:00holf: given that x,y are irrational taking delta s...holf: given that x,y are irrational taking delta small and rational, clearly x+delta is irrational. So I begin with two irrationals. Hence I see the proofs as diffeent.<br /><br />Anon- not sure whose proof you are commenting on, mine or Holfs. In my proof we take irrational + ratiaonal which is clearly irrational.<br /><br />GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-20056016013890107902016-12-06T10:04:12.107-06:002016-12-06T10:04:12.107-06:00The sum of two irrational numbers is not necessari...The sum of two irrational numbers is not necessarily irrational, right? e.g. sqrt{2} and (2 - sqrt{2}). So it is not clear to me that the second proof is complete. Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-11717092484770364832016-12-06T09:18:57.820-06:002016-12-06T09:18:57.820-06:00Formally, you still need to show the existence of ...Formally, you still need to show the existence of an irrational number between 0 and y-x. So for me, both proofs are the same. <br /><br />You however do not need to use any counting argument for this: observe u(n) = sqrt(2)^{-2n+1} is irrational for all n and -> 0. Then with your proof or your student's proof, take n such that u(n) < y-x and choose x+u(n).holfnoreply@blogger.com