tag:blogger.com,1999:blog-3722233.post6029863789037200040..comments2019-12-15T21:55:18.569-05:00Comments on Computational Complexity: Fermat's Last Theorem and Large Cardinals. Really!Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger13125tag:blogger.com,1999:blog-3722233.post-25767701705798139072015-03-06T15:56:56.379-05:002015-03-06T15:56:56.379-05:00My interest in the Fermat Conjecture, (FC,) began ...My interest in the Fermat Conjecture, (FC,) began as an interest in the Pythagorean theorem. I wasn't looking for other integral solutions to the n greater than 2 problem. I was more interested in the fact that odd integral values of 'a' resulted in 'b' being equal to (c-1.) Then, I began looking at the FC, and his statement, in the margin, that he had a solution, but it was too big to fit in the margin. I realized that with the mathematical tools in existence at that time, it was probably algebraic or geometric in expression. The solution proposed in 1995 that exceeded 120 pages, and used mathematics far in excess of what was available to Fermat was probably much more complex that needed. I began by using simple substitution to eliminate variables. It was determined that b= [(a to the 2)-1]/2, and c=[(a to the 2)+1]/2. Using an integral 'n', the problem became, "Is there a positive integer 'n', such that the equation: [(a to the n)-1]/n is an integer?" Although (a to the n) / n would result in an integral solution, because 1 is subtracted from the numerator prior to the division, there are NO positive integers for 'a' and 'n' greater than 2 that would result in b being positively non-fractional. COMMENTS? A.Conti, Allen@TheWalnutGrove.com or OWInc@att.netReal Alhttps://www.blogger.com/profile/08405619805485846755noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1626385987562742182014-02-12T00:15:57.278-05:002014-02-12T00:15:57.278-05:00http://en.wikipedia.org/wiki/Zermelo%E2%80%93Fraen...http://en.wikipedia.org/wiki/Zermelo%E2%80%93Fraenkel_set_theory#Criticisms<br /><br />You might be interested to know that there is a set theoretic principle in set theory such that if you assume it you will end up with theorems that are counter-intuitive and if you assume their negation you end up with some other counter-intuitive theorem. There is a false sense of security in some mathematicians for being inside set theory like ZFC. The most one can say is that ZFC doesn't seem to be an inconsistent system but formal consistency is far from being sound and corresponding to the reality.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-9530466743679898632014-02-11T03:52:07.780-05:002014-02-11T03:52:07.780-05:00Number theorists and others have stopped caring ab...Number theorists and others have stopped caring about set theory long time ago. People insisting on turning these categorical perspectives to set theoretical perspectives are doing a translation for the older generation of mathematicians who have not got used to the categorical foundation. You cannot teach algebraic topology worrying all the time how to translate it back to set theory and with this attitude the students also learn not to care about set theory. However older mathematicians who are not brought up in this fashion and don't use category theory have hard time adopting to the new reality and feel insecure in using these tools. This is despite the fact that categorical perspective are often more concrete that their set theoretical counterpart. Expecting people to worry about how the set theoretical foundations of their proofs in this age is like expecting Python programmers to worry about how their code would like in assembly or even worth Turing machines!Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-75800193686531103242014-01-29T15:59:15.845-05:002014-01-29T15:59:15.845-05:00Note that it is trivial there are finite statement...Note that it is trivial there are finite statements about numbers that can only be proven assuming the consistency of large cardinals. Proofs are finite objects, and as Gödel first noted, can be encoded using Peano Arithmetic. Because ZFC is recursive, the existence of a proof that ZFC+"there exists a measurable cardinal" implies 0=1 is ultimately a statement about the existence of an integer with certain elementary properties. In other words, the assertion that no such integer exists is exactly the assertion that measurable cardinals are consistent.<br /><br />Because of Matiyasevich's theorem (and its fully constructive proof), this can actually be expressed in terms of an explicit Diaphontine equation whose solutions encode proofs of inconsistency. Simpler would be to evoke the Davis-Putnam-Robinson theorem regarding exponential equations (like Fermat!).<br /><br />(william e emba)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-32974259701097594332014-01-29T15:20:05.865-05:002014-01-29T15:20:05.865-05:00Something similar was done by Solomon Feferman in ...Something similar was done by Solomon Feferman in the 1960s. See his "Set-theoretical foundations of category theory", in Reports of the Midwest Category Seminar, III, Lecture Notes in Mathematics, vol. 106, pp. 201-247, Springer-Verlag, Berlin, 1969.<br /><br />In brief, lots of freewheeling uses of proper classes of proper classes, etc, in the style of category theory fit inside ZFC using reflection. The main application was to localization of categories, something the Grothendieck school treated using universes. J. Frank Adams in his book on Stable Homotopy went so far as to describe the written proof of the main result was really a "research program". later officially solved by Bousfield, who essentially kept track of the reflection invocations to provide cardinality bounds.<br /><br />(william e emba)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-10995396295600064322014-01-29T03:23:26.095-05:002014-01-29T03:23:26.095-05:00I remember seeing a talk by A. Macintyre outlining...I remember seeing a talk by A. Macintyre outlining possible avenues to showing that FLT can be proved in Peano arithmetic (this is discussed in §2 of McLarty's paper). He seemed pretty convinced that it is possible, though I don't know what concrete progress has been made so far.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-37361750085202771572014-01-28T20:35:48.857-05:002014-01-28T20:35:48.857-05:00have long wondered if large cardinals relate someh...have long wondered if large cardinals relate somehow to high space-complexity functions in TCS or some other structure. it would seem there would have to be a connection somewhere. maybe a big bridge thm lurking here....vznhttp://vzn1.wordpress.comnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-70663161960467981842014-01-28T07:57:57.125-05:002014-01-28T07:57:57.125-05:00Getting the universe axiom out and just using ZFC ...Getting the universe axiom out and just using ZFC is routine but no one does it. It would have some some cost in terms of the conceptual order. It has no real profit from a logical point of view since ZFC is also vastly disproportionate to the arithmetic core of the proofs. When Grothendieck and Dieudonne came up with the methods using universes they knew it was a convenience and could be avoided. The best example would be Deligne's chapter of SGA 4.5 where he gently words most results to avoid universes, although he specifies in that work that he is not giving complete proofs, and he refers to complete proofs he wrote elsewhere that do use universes.<br /><br />Nothing I have written changes the real arithmetic of the existing proofs. My goal is to preserve that arithmetic while lightening the logical apparatus around it. I have shown that ZFC+U can be very far weakened to a logic at the strength of finite order arithmetic (dealing with numbers, sets of numbers, and so on to any finite level, but only to finite levels and with all sets defined by arithmetic conditions). Some of the most general lemmas have to be treated carefully here but the parts of the proofs that number theorists care about are unchanged. This is on the Math arXiv as "<br />A finite order arithmetic foundation for cohomology".<br /><br />As a lot of logicians have said, large parts of the proof that are not overtly in Peano Arithmetic can be put there with no real change. But not all. There is no reason to doubt it can all get into PA somehow, but there is no articulate proof yet that it can, let alone a known proof in PA. I am a great optimist and believe that someday someone will find an overtly elementary argument for FLT, likely using the concrete arithmetic that goes into Wiles's and later known proofs, but that will depend on genius. At the same time we can analyze the conceptual tools currently used to show how far PA can handle them. Colin McLartyhttps://www.blogger.com/profile/12518163963160591824noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-6623657270450911792014-01-28T07:37:28.996-05:002014-01-28T07:37:28.996-05:00To Sidles: yes, exactly. I will write a fuller co...To Sidles: yes, exactly. I will write a fuller comment. But real the point is just as Sidles puts it.Colin McLartyhttps://www.blogger.com/profile/12518163963160591824noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-66325657819081504682014-01-28T05:43:22.897-05:002014-01-28T05:43:22.897-05:00Grothendieck himself speaks to these issues in a l...Grothendieck himself speaks to these issues in <b><a href="http://mathoverflow.net/questions/7155/famous-mathematical-quotes#comment190676_7157" rel="nofollow">a letter to Ronnie Brown</a>:</b><br /><br />--------<br />"The question you raise, 'how can such a formulation [as post-ZFC "universes"] lead to computations?' doesn't bother me in the least! Throughout my whole life as a mathematician, the possibility of making explicit, elegant computations has always come out by itself, as a byproduct of a thorough conceptual understanding of what was going on. Thus I never bothered about whether what would come out would be suitable for this or that, but just tried to understand - and it always turned out that understanding was all that mattered."<br />--------<br /><br />Why would/should practical engineers/simulationists care? For the eminently practical reason that Grothendieck's world-view is invariant under the duality <b>"<a href="http://www.scottaaronson.com/blog/?p=1643#comment-99703" rel="nofollow">formulation ⇆ computation</a>."</b> That is, the path between a "thorough conceptual understanding" of practical computations and a Grothendieck-style "childishly simple" formalization of that understanding comprises a <i>single</i> mathematical path … that can be creatively traversed in either of <i>two</i> directions.<br /><br />Concretely, engineers are motivated to traverse this two-way path, in both directions, by the (seeming) obstructions to our geometric/dynamical understanding that are associated to the singularities of varietal state-spaces, and by the (seeming) obstructions to our algebraic/informatic understanding that are associated to the finite-field discretization of varietal state-spaces. <br /><br />Both practical computations and Grothendieck-style abstract formulations show us that these obstructions are illusory, such tat the practical and abstract approaches <i>together</i> provide us with a "thorough conceptual understanding" (in Grothendieck's phrase) of why the past generation's <b><a href="http://www.scottaaronson.com/blog/?p=1643#comment-99436" rel="nofollow">thousand-fold capability increases and thousand-fold cost decreases in simulation capability</a></b> can plausibly continue for another generation. Which would be GOOD, needless to say!<br /><br /><b>Conclusion</b> The unbounded quest to understand mathematics “in width, in depth, and in context” requires our collective embrace of <i>both</i> the Grothendieck-style "childish simplicity" of post-ZFC universes <i>and</i> their un-simple PA foundations … even if as individuals we may strongly prefer one style of mathematics over the other. John Sidleshttps://www.blogger.com/profile/16286860374431298556noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-8210569962243808132014-01-27T17:09:29.799-05:002014-01-27T17:09:29.799-05:00Is this a meta-mathematical result? In many cases,...Is this a meta-mathematical result? In many cases, the advanced set theory axioms don't change the arithmetical structure. Hence if an arithmetical statement (FLT is a $\Pi_1$ arithmetical sentence) is provable using arcane set-theory axioms it is provable without them. Davidhttps://www.blogger.com/profile/13818371550669837787noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-34323867258153425232014-01-27T15:24:42.672-05:002014-01-27T15:24:42.672-05:00Is there a new proof of FLT? Or does McLarty now ...Is there a new proof of FLT? Or does McLarty now show that the original proof of Wiles can be interpreted/modified (albeit, not in any significant way) to do away with the LC assumption? Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-53898843557104907432014-01-27T14:43:13.716-05:002014-01-27T14:43:13.716-05:00Is there any publications of this recent result by...Is there any publications of this recent result by McLarty? I have not been able to find any paper.Anonymousnoreply@blogger.com