tag:blogger.com,1999:blog-3722233.post4416053002201539396..comments2024-05-20T10:34:03.365-05:00Comments on Computational Complexity: Conventions in Math- just to make the rules work or more?Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger10125tag:blogger.com,1999:blog-3722233.post-79059402354538137582011-10-04T13:30:13.208-05:002011-10-04T13:30:13.208-05:001)
a^1/2 = sqrt{a} isn’t made true in order to mak...1)<br />a^1/2 = sqrt{a} isn’t made true in order to make a^(x+y) = a^x*a^y true.<br />a^1/2 = sqrt{a} is a consequence of the rule a^(x+y) = a^x*a^y <br />Proof:<br />Every positive real number has tow roots b and –b, let’s assume sqrt{} returns the positive root.<br />Then by the definition of the sqrt{} function sqrt{a} is the positive number b such that b*b = a (b is unique, this can bebproven easily)<br />but the number a^1/2 is just like sqrt{a} because a^1/2*a^1/2 = a^(1/2 + 1/2) = a^1 = a (this step is justified by the rule a^(x+y) = a^x*a^y) <br />since b is unique it follows that sqrt{a} = a^1/2 if a^1/2 > 0<br />else sqrt{a} = -a^1/2<br />A comprehensive Abstract algebra text should contain proofs that show that these rules are consequences of the definition of exponentiation. <br />Here is a good one that contains the proofs: Abstract Algebra: A Comprehensive Treatment (Chapman & Hall/CRC Pure and Applied Mathematics) by Claudia Menini and Freddy Van Oystaeyen<br /><br />2)<br />(∀ x ∈ ∅)[P(x)] is true because it can’t be false, remember that a true statement in logic is nothing other than a statement that can’t be false.<br /><br />Proof: if (∀ x ∈ ∅)[P(x)] is false <br />then there must exist at least one x ∈ ∅ such that P(x) is false<br />but it is absurd to say that the empty set contains an element<br />hence the statement (∀ x ∈ ∅)[P(x)] can’t be false so it must be true<br />3)<br />In my opinion the assigning of 0 and 1 to the summation over an empty set and the product over an empty set respectively is natural choice that makes summations and products convenient. With these rules on can express the sum or products of elements in a set as the sum or products of the elements in its disjoint subsets without worrying about empty subsets.<br />For example: A = {1,2} = {} U {1,2}<br />Sum(A) = Sum({} U {1,2}) = sum({}) + sum{{1,2}} = 0 + 3 = 3.<br />Product(A) = Product({} U {1,2}) = Product({} *Product( {1,2}) = 1 * 2 = 2Ecksnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-49599171161473344382011-09-15T14:13:20.000-05:002011-09-15T14:13:20.000-05:00Daina Taimina's book Crocheting Adventures wit...Daina Taimina's book <i>Crocheting Adventures with Hyperbolic Planes</i>, which won last year's coveted Diagram Prize, includes a Foreword by Bill Thurston that expounds upon the theme of Terry Tao's post (above) as follows:<br /><br />-----------------------<br />Mathematics is an art of <i>human</i> understanding … Our brains are complicated devices, with many specialized modules working behind the scenes to give us an integrated understanding of the world. Mathematical concepts are abstract, so it ends up that there are many different ways that they can sit in our brains. <br /><br />A given mathematical concept might be primarily a symbolic equation, a picture, a rhythmic pattern, a short movie---or best of all, an integrated combination of several different representations. These non-symbolic mental models for mathematical concepts are extremely important, but unfortunately, many of them are hard to share.<br /><br />Mathematics sings when we feel it in our whole brain. People are generally inhibited about even trying to share their personal mental models. People like music, but they are afraid to sing. You only learn to sing by singing.<br />-----------------------<br /><br />I would like to share one idiom that engineers commonly employ in choosing among mathematical conventions. The idiom draws upon ideas that are presented in three highly-rate <i>MathOverflow</i> (MOF) posts: (1) Gil Kalai's MOF Wiki <a href="http://mathoverflow.net/questions/4994/fundamental-examples" rel="nofollow"><i>Fundamental examples</i></a>, (2) Tao's comment upon the MOF Wiki <a href="http://mathoverflow.net/questions/27943/in-what-ways-is-physical-intuition-about-mathematical-objects-non-rigorous/27953#27953" rel="nofollow"><i>In what ways is physical intuition about mathematical objects non-rigorous?</i></a>, and (3) Terry Tao's comment upon the MOF Wiki <a href="http://mathoverflow.net/questions/44593/still-difficult-after-all-these-years/44622#44622" rel="nofollow"><i>Still difficult after all these years</i></a>.<br /><br />The basic idiom is to take any fundamental example (per Kalai) that is associated to a set of mathematical conventions (per Gasarch) and <i>run that example backwards</i>. If something physically or informatically useful happens (per Tao's first MOF post), good! Otherwise, adjust the conventions/definitions (per Tao's second MOF post) until something good <i>does</i> happen.<br /><br />The practical point of this engineering idiom is summarized in an old joke: "<b>Q:</b> What happens when you play a country-and-western song backwards? <b>A:</b> You get out of jail, sober up, find a job, fix your truck, then your spouse comes back to you and your dog does too." <br /><br />For example, the strategy "Play it again, … this time backwards" is very natural in complexity theory, in which algorithms "played backwards" lead naturally to the study of trapdoor functions. But obstructions are encountered too. In particular, generic examples of algorithms in <i>P</i> are infeasible to construct, because so many of their key properties are undecidable (per Hartmanis). That is why we engineers would be happy to see the conventional definitions of <i>P</i> adjusted to remove this obstruction.<br /><br />Quantum computers too (error-correcting ones especially) perform a natural and useful function when they are "played backwards", namely they operate as engines for quantum separative transport. And the low-entropy quantity they distill, namely quantum coherence, is transformationally valuable for purposes of both sensing and computation. <br /><br />That bottom line is that (for engineers) good mathematical definitions and conventions help us create novel systems, take them apart, and run them backwards, all to useful purpose.John Sidleshttps://www.blogger.com/profile/16286860374431298556noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-14474573977135160362011-09-14T23:04:33.178-05:002011-09-14T23:04:33.178-05:00I agree with what previous commenters have said: a...I agree with what previous commenters have said: a^{1/2} is *** by definition *** the number that when squared gives a. So it's not "to make the rules work out", it's just a definition (that, fortunately, happens to be consistent with the rules).Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-17193146462002322312011-09-14T13:06:27.007-05:002011-09-14T13:06:27.007-05:00As pointed out by Thurston, any fundamental mathem...As pointed out by Thurston, any fundamental mathematical concept worth its salt (and exponentiation is certainly one of these) should have a number of different interpretations, and the one that one is first exposed to (in this case, iterated multiplication) is not necessarily the "best" one for generalisation. One already sees this with, say, multiplication; how does one justify (-2)*(-3) = 6 using the iterated addition interpretation of multiplication?<br /><br />I discuss different interpretations of exponentiation, by the way, at <br /><br />http://www.google.com/buzz/114134834346472219368/hTVJiP5LoPb<br /><br />Iterated multiplication is interpretation 4. While this interpretation does not cover a^{1/2}, other interpretations (in my list, 5, 6, 7, and 9) do. ("Making the rules work" is interpretation 6.)Terryhttps://www.blogger.com/profile/10186436058521523236noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-18477058511279824622011-09-14T12:37:14.841-05:002011-09-14T12:37:14.841-05:00In third grade I was taught the following regretta...In third grade I was taught the following regrettable yet unforgettable mnemonic: <br /><br />--------------<br />"Minus times minus equals plus; <br />the reason for this, we will not discuss."<br />-------------- <br /><br />A graduate-level echo of this is found in William L. Burke's <i>samizdat</i> masterpiece <i>Div, Grad, Curl are Dead</i>:<br /><br />-----------------<br /><b>Mathematician:</b> When do you guys treat dual spaces?<br /><br /><b>Scientist/Engineer:</b> We don't.<br /><br /><b>Mathematician:</b> What! How can that be?<br />-----------------<br /><br />Burke goes on to say: <br /><br />-----------------<br />"You may have taken a course on linear algebra. The purpose of this book is to repair the omissions of such a course, which now is typically only a course on matrix manipulation."<br />-----------------<br /><br />Here Burke's point is that mathematical ideals of naturality and universality (which nowadays are ubiquitous in the mathematics curriculum and which I take to be the broad theme of GASARCH's post) are making their way only slowly and painfully into the science-and-engineering curriculum.<br /><br />It is not at all clear (to me) how to recognize "naturality and universality" in complexity theory, and yet definitely I wish for this ability; remarks (from anyone) in this regard would be very welcome. And if someone (not me!) has the requisite chutzpah to post it as a question/community wiki on <i>TCS StackExchange</i>, that might be fun too.John Sidleshttps://www.blogger.com/profile/16286860374431298556noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-24414691049441083992011-09-14T11:53:34.156-05:002011-09-14T11:53:34.156-05:00I would say that for n a natural number \ge 1
a^n...I would say that for n a natural number \ge 1<br /><br />a^n = a * a * ... * a (n times)<br />is the DEFINITION of a-to-a-power.<br /><br />All the rest of the rules (e.g., a^{-1} = 1/a<br />and a^{1/2}=sqrt(a), etc) are made up in order to make<br />the addition rule WORK. So I think that a*a=a^2 is<br />quite diff from a^{1/2} = sqrt(a).<br /><br />Again- I AGREE with the definitions but wonder if there<br />is an alternative explanation of them.<br />I was thinking of a SIMPLE explanation, so<br />Richard Elwes comment, while very interesting, is not<br />quite what I am looking for.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-15043535713738731322011-09-14T11:51:06.525-05:002011-09-14T11:51:06.525-05:00(1) holds because sqrt{a} is a shortcut for a^{1/2...(1) holds because sqrt{a} is a shortcut for a^{1/2}.<br /><br />(2) holds because "(∀ x ∈ ∅)[P(x)]" is a shortcut for "∀ x ((x ∈ ∅) => P(x))". Since "(x ∈ ∅)" is always false, "((x ∈ ∅) => P(x))" is always true.<br /><br />(3) In any group, the product of elements in the empty set equals the identity element of the group. Now 0 is the identity element of the additive group, and 1 is the identity element of the multiplicative group.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-56028275984119848742011-09-14T11:11:50.024-05:002011-09-14T11:11:50.024-05:00Why is a^2 = a*a? Is this equivalent to square-roo...Why is a^2 = a*a? Is this equivalent to square-root question or more fundamental?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-82321759283538535802011-09-14T10:50:17.590-05:002011-09-14T10:50:17.590-05:00My favorite of these is 0^0, which is defined to b...My favorite of these is 0^0, which is defined to be 1, but there are some semi-plausible sounding reasons you might be compelled to define it to be 0, or even leave it undefined. (Of course, if you actually did something rash like that, then it would no longer be true that for every real x, e^x = sum_{i=0}^{infty} x^i/i!)Sam Alexanderhttp://www.xamuel.comnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-42907207874335312712011-09-14T09:42:13.545-05:002011-09-14T09:42:13.545-05:00Because a^{1/2} = exp( {1/2} ln a)
One could argu...Because a^{1/2} = exp( {1/2} ln a)<br /><br />One could argue that this is also 'just making a rule work out', but I'd say that the theory of the complex exponential and natural logarithm is natural and rich enough to give serious weight to the argument that it 'makes sense'.Richard Elweshttp://www.richardelwes.co.uknoreply@blogger.com