“Is There Something Mysterious About Math?”
When it rains, it pours: after not blogging for a month, I now have a second thing to blog about in as many days. Aeon, an online magazine, asked me to write a short essay responding to the question above, so I did. My essay is here. Spoiler alert: my thesis is that yes, there’s something “mysterious” about math, but the main mystery is why there isn’t even more mystery than there is. Also—shameless attempt to get you to click—the essay discusses the “discrete math is just a disorganized mess of random statements” view of Luboš Motl, who’s useful for putting flesh on what might otherwise be a strawman position. Comments welcome (when aren’t they?). You should also read other interesting responses to the same question by Penelope Maddy, James Franklin, and Neil Levy. Thanks very much to Ed Lake at Aeon for commissioning these pieces.
Update (4/22): On rereading my piece, I felt bad that it didn’t make a clear enough distinction between two separate questions:
- Are there humanly-comprehensible explanations for why the mathematical statements that we care about are true or false—thereby rendering their truth or falsity “non-mysterious” to us?
- Are there formal proofs or disproofs of the statements?
Interestingly, neither of the above implies the other. Thus, to take an example from the essay, no one has any idea how to prove that the digits 0 through 9 occur with equal frequency in the decimal expansion of π, and yet it’s utterly non-mysterious (at a “physics level of rigor”) why that particular statement should be true. Conversely, there are many examples of statements for which we do have proofs, but which experts in the relevant fields still see as “mysterious,” because the proofs aren’t illuminating or explanatory enough. Any proofs that require gigantic manipulations of formulas, “magically” terminating in the desired outcome, probably fall into that class, as do proofs that require computer enumeration of cases (like that of the Four-Color Theorem).
But it’s not just that proof and explanation are incomparable; sometimes they might even be at odds. In this MathOverflow post, Timothy Gowers relates an interesting speculation of Don Zagier, that statements like the equidistribution of the digits of π might be unprovable from the usual axioms of set theory, precisely because they’re so “obviously” true—and for that very reason, there need not be anything deeper underlying their truth. As Gowers points out, we shouldn’t go overboard with this speculation, because there are plenty of other examples of mathematical statements (the Green-Tao theorem, Vinogradov’s theorem, etc.) that also seem like they might be true “just because”—true only because their falsehood would require a statistical miracle—but for which mathematicians nevertheless managed to give fully rigorous proofs, in effect formalizing the intuition that it would take a miracle to make them false.
Zagier’s speculation is related to another objection one could raise against my essay: while I said that the “Gödelian gremlin” has remained surprisingly dormant in the 85 years since its discovery (and that this is a fascinating fact crying out for explanation), who’s to say that it’s not lurking in some of the very open problems that I mentioned, like π’s equidistribution, the Riemann Hypothesis, the Goldbach Conjecture, or P≠NP? Conceivably, not only are all those conjectures unprovable from the usual axioms of set theory, but their unprovability is itself unprovable, and so on, so that we could never even have the satisfaction of knowing why we’ll never know.
My response to these objections is basically just to appeal yet again to the empirical record. First, while proof and explanation need not go together and sometimes don’t, by and large they do go together: over thousands over years, mathematicians learned to seek formal proofs largely because they discovered that without them, their understanding constantly went awry. Also, while no one can rule out that P vs. NP, the Riemann Hypothesis, etc., might be independent of set theory, there’s very little in the history of math—including in the recent history, which saw spectacular proofs of (e.g.) Fermat’s Last Theorem and the Poincaré Conjecture—that lends concrete support to such fatalism.
So in summary, I’d say that history does present us with “two mysteries of the mathematical supercontinent”—namely, why do so many of the mathematical statements that humans care about turn out to be tightly linked in webs of explanation, and also in webs of proof, rather than occupying separate islands?—and that these two mysteries are very closely related, if not quite the same.
Follow
Comment #1 April 22nd, 2015 at 6:46 am
From the article: “A second possible answer is that even the parts of math that look far removed from physics, are indirectly inspired by our experience with the physical world—and that they’re coherent because the physical world is.”
Wild speculation: sometimes I think “if physicalism is true, you can learn something about matter just by thinking”. Usually I’m pondering the mysteries of induction and inductive bias, and wondering whether having a mind made from matter gives us enough of an inductive bias to be getting on with. But here; maybe our thoughts are coherent because they’re thought by physical systems.
Comment #2 April 22nd, 2015 at 9:04 am
So, lack of mystery is mysterious, but isn’t that just a different form of the “interesting number paradox”? 😛
Comment #3 April 22nd, 2015 at 9:19 am
Ever since I read “the unreasonable effectiveness of mathematics”, this has been bugging me. The mutual-consistency of disparate mathematical systems, and their effectiveness at modeling the physical world is “the water this fish swims in” – I usually don’t notice it, but when I think about it, it seems like there is something strange about the fact that it works at all.
It inspires a sort of mathematical-platonist Tegmarkian sort of idea about the universe: We use math to make models of the universe, and the things that happen in the models correspond to things that happen in the universe. (I suppose if it were the case that the universe *couldn’t* be modeled in this way, we would never have developed brains as we know them, since whatever goes on in the brains couldn’t correspond to what happens in reality, and couldn’t provide any sort of survival advantage)
If the universe were to have the same math-ontological status as any of our models of the universe (ie, it’s a state machine of some sort with (partially known/unknown) laws that propagate the state, just as our models of it are), then it wouldn’t be a huge mystery that we could hit upon models that mimic the behavior of the universe. This is sort of the default assumption necessary to do physics at all! (Or, if you want to adopt a time-independent perspective, the universes space-time state history is an allowed state when evaluated by some timeless functional which corresponds to the laws)
As for the self-consistency of math though:
I’m vaguely (on a total layman’s level) aware of Steven Wolfram’s program to automate mathematics: To automatically generate proofs of desired statements from a set of axioms, when stated in a formal computer-crunchable language of some sort. The article I was reading on the subject said something to the effect that many proofs were found using the system, but they were all convoluted and far from obvious – they weren’t the sort of proofs that a human mathematician would have come up with when trying to solve the same problem at all.
(I imagine there is some combinatorial explosion property inherent in this that makes “test everything” a bad algorithm for more than toy problems with a very small set of axioms. Other than that, I’m unfamiliar with the territory.)
Comment #4 April 22nd, 2015 at 9:23 am
It seems that when a mathematician can’t come with a proof directly, then he/she can try to focus on proving whether a proof can even exist or not, and possibly take it one step higher (proof of a existence of a proof of existence of a proof) in a sort of recursion?
Is there a formal name for such mechanism? How many levels can this go in practice?
Does this relate to mapping theorems into computable and un-computable functions? (like the busy beaver).
Comment #5 April 22nd, 2015 at 9:38 am
Stephen Wolfram, sorry.
Aside:
I may be deficient in the sense of what people regard as mathematical beauty. I suppose this might be part of why physically disconnected math, like completely abstract discreet math looks like an arbitrary jumble to some people (probably myself included, unless I am able to conjure a “picture” of the problem domain and of what certain operations “do” or “mean”), while making sense to mathematicians that have this mathematical beauty sense.
I was talking with another student one day, and he was rhapsodizing about the mathematical beauty of Maxwell’s equations. I’ve never really understood what people meant when saying things like that.
I said “well … it’s a PDE system. Like other PDE systems. It’s linear, I guess, which gives you a lot of tools to attack it. Would you say the same thing about the Navier Stokes equations?”
“Ugh, no! The Navier Stokes equations are ugly!”
“Why?”
He said something about it being an aesthetic judgement, but it’s one that I never really understood. If you start with some assumptions about what a continuum fluid is, you can do some derivations and arrive at the NS equations, just like if you make some assumptions about what the forces between two charged particles are (ie, the field responds linearly to the presence and motion of charges, the laws are invariant under Lorenz transformations, etc) you can do some derivations and end up with Maxwell’s equations. One being linear and easy to solve (and susceptible to all the nice linear-system tools (Galerkin’s method, Green’s functions, etc)), and the other being nonlinear and a pain to solve doesn’t translate into “beauty” in my mind – just ease of solution.
I don’t really understand why someone would think either of these are a-priori “beautiful” or “likely to be correct/interesting” independent of the underlying physical assumptions that give rise (eventually, after a lot of crunching/derivation) to the equations. In fact, I actually have a bit of an aversion to things ‘coming out of nowhere’ like that.
Comment #6 April 22nd, 2015 at 9:41 am
As you say it’s possible that the mathematical questions accessible to humans are by definitions the ones that can be mapped into the structures of the human brain.
Just like the Mandelbrot set has seemingly disconnected “islands” when viewed at a certain scale but once you look closely you see they’re all really connected by some generating formula. And for math the underlying generator is the structure of the human brain. Maybe one day we’ll be able to look into the brain of a mathematician and see what happens when two separated mathematical questions become connected/understood.
Things like Godel’s theorems are maybe a glimpse of what lies beyond our own capabilities.
Comment #7 April 22nd, 2015 at 10:15 am
MathRocketSci #3
Reality is “only” the patterns in our sensory data streams that can be extracted and mapped into symbols in the brain.
Math itself, as symbol manipulation, happens in the human brain.
Math is also as much about the scientific method, the “process”, than the results themselves (the theorems and all that). Mathematics/science is a way for the brain to “condition” itself to be more efficient at mapping reality. And not just as an internal process in the individual brain, but also as a meta process at the level of society, through teaching, books, engineering, etc.
So it’s really no surprise that our reality is so mathematical.
The question maybe should be about how mathematics gets realized in the structures of the brain.
The brain itself has also plenty of potential for over-interpreting the sensory data and seeing patterns and connections where there are none (superstitions, religions, etc).
We hear a lot that it’s amazing that math is such a powerful tool to understand reality, but there are obvious limitations. Things like quantum mechanics seem to be at the fringe and you hear scientists say “no-one can truly understand QM”. Or take the struggle to unite QM and gravity, etc.
Scientists start to rely on machines to go beyond the limits of the human brain to come up with proofs and find patterns. But can machines designed by the human brain transcend it one day?
Comment #8 April 22nd, 2015 at 10:51 am
MadRocketSci #3:
I’m vaguely (on a total layman’s level) aware of Steven Wolfram’s program to automate mathematics: To automatically generate proofs of desired statements from a set of axioms, when stated in a formal computer-crunchable language of some sort.
Actually, the program of automated theorem-proving has essentially nothing to do with Wolfram. It predates him by decades—going back to the very beginning of the computer age, or even to people like Leibniz, Frege, and Russell. Furthermore, Wolfram is well-known as an extreme skeptic of the value of formal proofs (whether human- or machine-generated): with a few isolated exceptions, his preferred method in A New Kind of Science is to eyeball pictures of cellular automata and “just see” what they do, rather than trying to prove anything about them.
Comment #9 April 22nd, 2015 at 11:02 am
Scott, #8
Whoops. Well, that’s what I get for posting from vague memories of pop-sci articles. Maybe I had the wrong mathematician’s name, or maybe I misunderstood what Wolfram’s position on the matter was.
fred #7
Reality is “only” the patterns in our sensory data streams that can be extracted and mapped into symbols in the brain.
Why, a-priori, should we expect the “range of pattern-finding” ability of our brains, and our mathematics to be much greater than the bare minimum of our ancestral environment that is useful to parse?
You could argue that this *is* the case for most animals: A small radius and very short timescale of predictive ability that touches on a few spare aspects of the world. “There are things out in the Savannah grass moving around, and some of them want to eat you”. Everything beyond that – the stuff in the sky, the things on the other side of the world, might as well be white noise – sensory junk – the pattern doesn’t cohere in the brains of these animals. (Though I have an amusing secondhand anecdote about an OCD Border Collie who was clearly forming some kind of hypothesis about the shadows cast by birds, and the birds in the air. She kept looking excitedly from one to the other.)
If you have something differentially smarter than an ape though: all of a sudden the range of stuff that makes sense shoots clear across the observable universe to the beginning of time and includes things that have absolutely nothing to do with our ancestral environment, like quantum physics that you mentioned, or the star-quakes on neutron stars.
Comment #10 April 22nd, 2015 at 2:22 pm
On a related note, I wonder if the amount of “interesting math” is finite. Of course there are an infinite number of theorems to prove, but is it possible that we could ever get to a point (in the far-distant future) where all of the problems we care about have been solved, all branches of math that can be discovered have been, and there’s nothing deep left for mathematicians to do?
Comment #11 April 22nd, 2015 at 2:58 pm
Vadim #10: Yes, it’s possible that someday we could run out of interesting math. But I’m not too worried about that, since given the combinatorial explosion of interesting math problems one can pose, compared with the finiteness of the physical world, it seems to me that we could only run out of interesting math long, long after we had run out of interesting physics and astronomy and chemistry and biology and every other natural science. Except, that is, insofar as the natural sciences reorient themselves—as indeed many have been doing—to be less about “what is” (e.g., what are the fundamental laws of physics? what are the chemical elements?) than about “what can be” (e.g., what new states of matter or molecules or organisms could we synthesize?). But the limit of reorienting yourself around “what can be” (or: “given these building blocks and rules, what is the complete space of possibilities?”) is that your science basically becomes a branch of math. In other words, I predict that if scientific inquiry continues for long enough, then math (in all its many manifestations, including theoretical computer science, theoretical biology, etc.) will be the last thing standing—which is good enough for me. 🙂
Comment #12 April 22nd, 2015 at 3:05 pm
I don’t really understand Wigner’s “unreasonable effectiveness” of math.
Is English, or binary code, also unreasonably effective at describing the world?
In my opinion, the only mystery is that the Universe is describable rather than completely random.
Coincidentally, there was a recent Nova documentary on PBS titled The Great Math Mystery.
Why is there such little Computer Science/Complexity Theory in these documentaries?
Comment #13 April 22nd, 2015 at 3:06 pm
congrats on the aeon article & its always great to see “scientific outreach” which is not always so common. youre turning into a CS carl sagan dont you think?
as for the topic, lets face it, math evolves! it is quite like all other scientific disciplines in this sense. it is said by some that kuhnian shifts dont seem to apply to math, but that sounds incorrect & near lame to me, to me math is just as full of them as the other sciences, and they are simply breakthroughs that show up intermittently/ randomly like earthquakes among the perpetual force of plate shearing. (this analogy was used by the director of the Clay institute in an excellent book about Perelman “perfect rigor” by Gessen, just finished, highly recommend it).
as for the Big Questions, the very hard conjectures, the question is how much further can math evolve? yes the dragon of undecidability seems to mock some of our efforts (going back to the thwarting of hilberts agenda) and its still not fully appreciated what the exact boundaries are, they are being poked at as we speak. some questions are so deep they cannot even be solved in a few generations, or even several… yet our understanding progresses…
but 1½ centuries of NON solution to the riemann problem (and other key hard problems long unsolved) does indeed suggest a pessimistic although not fatalistic outlook.
Comment #14 April 22nd, 2015 at 3:22 pm
@Job: The impression I got from Wigner’s article is that the focus of his surprise was really the unreasonable effectiveness of the relatively simple math needed to describe the world, not so much at the language of math itself. In the piece, he expresses surprise at Newton’s gravity law and Heisenberg’s matrix mechanics turning out surprisingly accurate but for ex. doesn’t mention plutarch’s epicycles in the same vein.
Comment #15 April 22nd, 2015 at 3:23 pm
Actually, i would go further and say that the only mystery is that the Universe is consistent, thus allowing us to use past events to predict future events and establish abstractions such as Math.
Comment #16 April 22nd, 2015 at 3:25 pm
Job #12: If someone waxed philosophical about “the unreasonable effectiveness of LaTeX in describing the world,” or “the unreasonable effectiveness of mathematical notation,” that would indeed be about as silly as “the unreasonable effectiveness of English.” But math is not just a language or notation. It’s also the actual structures that mathematicians found—complex numbers, finite simple groups, Lie algebras, etc.—and the theorems that characterize and relate those structures. Wigner was asking why the structures that mathematicians found to be important for their own internal reasons, so often turn out to be the same structures that are important for physics.
I haven’t watched that PBS math show yet—should I?
Complexity theory seems really, really hard to do on TV, one reason being the lack of obvious and arresting visuals analogous to the wormholes, vibrating strings, etc. that the physicists can show. After you’ve shown a traveling salesman and a 3-colorable map, then what: an inclusion diagram of complexity classes? a graph of the exponential function? Arthur and Merlin? a Bombe churning through possibilities at Bletchley Park? (OK, the last one actually worked pretty well in The Imitation Game.) But I do hope it’s tried someday, and that when it is, they don’t make a complete “hash” of it (har, har).
Comment #17 April 22nd, 2015 at 3:37 pm
I haven’t watched that PBS math show yet—should I?
Stephen Wolfram shows up at the end. 🙂
Comment #18 April 22nd, 2015 at 3:42 pm
dhaus #14, thanks for clarifying, in that context i have to say i agree with Wigner’s statement.
Comment #19 April 22nd, 2015 at 3:51 pm
@Scott: I’d partly attribute that to a lot of the math used in physics being relatively simple (and thus likely to be generally applicable piece of math) by the standards of mathematicians? String theory is of course a big gaping exception to this.
Comment #20 April 22nd, 2015 at 4:23 pm
This piece is very well done. I’d be very interested in seeing Lubos write a response.
Comment #21 April 22nd, 2015 at 4:24 pm
Scott,
I would not recommend the PBS show unless you want to get annoyed. The signal to fluff ratio was terrible.
Comment #22 April 22nd, 2015 at 6:00 pm
the essay writes “And yet, 85 years after Gödel uncovered this gremlin in the center of mathematics, the fact is that it’s remained mostly dormant…”
think this should be qualified. undecidability is rampant in mathematics and computer science. even basic math questions studied since the time of antiquity like solving diophantine equations turn out to be undecidable, in the general sense. am planning to blog on undecidability myself at some pt, but heres a pov inspired by your article. it seems human thinking is very likely “nearly” algorithmic and must inherently focus on decidable aspects of reality so to speak, and math is a subarea of that. this is a concept explored by penrose somewhat, on the relationship between undecidability & human consciousness…. what really seems to be going on is that the map boundary between decidable and undecidable is endlessly varied & human consciousness is traversing/ exploring this terrain in mathematics scientific evolution.
Comment #23 April 22nd, 2015 at 6:54 pm
vzn #22: I completely agree with you that undecidable computational problems abound in math and CS (e.g., given as input a Diophantine equation, decide whether it’s solvable). But in the passage you quoted, I was talking about something different: specific, individual propositions for which people care whether they’re true or false, like the Riemann Hypothesis or P≠NP or the consistency of ZFC. The two things are clearly related: for example, the general undecidability of Diophantine equations implies you can construct a specific (but enormous, like 200-page!) Diophantine equation such that ZFC can’t prove that it’s unsolvable. But Turing-undecidability and Gödel-undecidability are not at all the same thing: mathematicians would gladly accept that there’s no general procedure to determine the solvability of arbitrary Diophantine equations, as long as they could resolve all the specific equations they cared about! And the examples of specific yes-or-no questions, whose answers are known today to be independent of strong formal systems, are more-or-less the ones that I listed.
Comment #24 April 22nd, 2015 at 9:26 pm
What kind of argument is this “empirical” one?
Here’s the situation since Godel demonstrated his remarkable result. Among the prominent outstanding problems we have tried to prove since that time, there are basically two kinds: those we have resolved, one way or the other, and those we have not. No, we have not actually proved that any of them is independent of ZF — but how surprising would that be, given the extraordinary complexity of such proofs? Consider what a great mathematical achievement it was to show that such simple statements as the Continuum Hypothesis and the Axiom of Choice were independent. What hope might there be that we’d be able to show the independence of P=NP or the Riemann hypothesis, or any other well known outstanding problem?
From an “empirical” point of view, all we really have are any number of problems that remain unresolved; any number of them, for all we know, might be in fact independent of ZF or ZFC.
Comment #25 April 23rd, 2015 at 2:06 am
There were a couple of related posts on my blog under the title “why is mathematics possible” also referring to a 1999 essay by David Kazhdan “Reflection on the development of mathematics in the twentieth century.” (Ad to an argument I had with Boaz Barak.)
The “mystery” is the following: We know that mathematical statements can, in general, be undecidable. We also know that a proof for a short mathematical statement can be extremely long. And we also know that even if a mathematical statement admits a short proof, finding such a proof can be computationally intractable. Given all that, what are the reasons that mathematics is at all possible?
There were several interesting comments and one by Gowers was outlined in a separate post.
Here are the links: Kazhdan 1999 paper http://link.springer.com/content/pdf/10.1007%2F978-3-0346-0425-3_13.pdf , My post https://gilkalai.wordpress.com/2013/05/23/why-is-mathematics-possible/; Gowers’s take on it: https://gilkalai.wordpress.com/2013/06/19/why-is-mathematics-possible-tim-gowerss-take-on-the-matter/
The exchange with Boaz http://windowsontheory.org/2013/05/06/reasons-to-care-in-honor-of-scott-aaronson/ .
Comment #26 April 23rd, 2015 at 2:24 am
I agree with candid_observer, the hard problems might be hard precisely because they are independent of our axioms, and it shouldn’t surprise us that it’s also hard to prove this independence. What would be mysterious is if we could show something very concrete is independent, because that would mean we understood it impressively well enough to show independence results in both directions, while not yet well enough to actually decide which way it really went.
(The famous independence results of Godel and Cohen and similar ones fail at this, either because (Godel) they are so concrete that we understand them perfectly and simply recognize that the consistency of a schema is stronger than the schema itself, or because (Cohen) they are so abstract that there is an inherent vagueness about their meaning, so it’s also not surprising that they are independent).
Harvey Friedman has spent nearly 50 years getting independence results of greater and greater concreteness, and they are finally close to perfectly (that is, minimally) simple. However, they still strike mathematicians as strange for the totally predictable reason that they are the kind of mathematics which previous generations of mathematicians would never have made good proofs about, precisely because of the independence phenomena, so that intuition about such objects is lacking.
Comment #27 April 23rd, 2015 at 7:38 am
“Fermat’s Last Theorem, […] could have been neither provable nor disprovable”
Is this true? If the theorem were undecidable then, given a candidate sum of two nth powers, one could be sure that it was *not* a counterexample to Fermat, as that would constitute a disproof. Would this not make the theorem true?
Comment #28 April 23rd, 2015 at 7:52 am
One should keep in mind that the “the unreasonable effectiveness of math” is possible because the weirdness (e.g. Banach-Tarski paradox) can be contained and e.g. Goedel’s result does not show up (but it could have, e.g. sums over all possible manifold in 4d quantum gravity).
But one should also keep in mind that large parts of e.g. the standard model are not even based on well-defined (axiomatic) math, rather a patchwork of “physicist’s math” and the real mystery is why this works 😎
Comment #29 April 23rd, 2015 at 8:46 am
Gil 25. What is a short proof? (I mean, if it’s short, couldn’t we find it out of enumerating all possible proofs?)
Comment #30 April 23rd, 2015 at 9:11 am
James #27: What you say is absolutely correct, if you had a proof that Fermat’s Last Theorem was neither provable nor disprovable in some reasonable axiom system—that proof would also necessarily show that FLT was true! (And the same goes for any other “Π1-sentence,” like Goldbach’s Conjecture or the Riemann Hypothesis.)
On the other hand, if the independence of FLT were itself unprovable, then no such conclusion would follow.
And actually, there’s yet another possibility: it’s conceivable that you could have a proof that (say) Goldbach’s Conjecture is unprovable in ZFC if true, but that said nothing about the possibility of Goldbach’s Conjecture being provably false. That would be the case if, for example, you could somehow show Goldbach’s Conjecture equivalent to the consistency of ZFC.
Comment #31 April 23rd, 2015 at 9:49 am
A beautiful piece, but I understand too little about mathematical proof, mathematical explanation and the difference between the two to make a qualified comment.
My entirely fanciful suspicion would be that the reasoning process (that runs inside the mathematically trained brain as well as across groups of them) has its own location inside the supercontinent of things in mathspace, i.e. is itself “mathematical”, meaning it can be connected to other places in the supercontinent just like they’re connected to each other. This begs the questions of:
1. why our particular mathematical reasoning process should happen to be on the supercontinent and
2. why there should be a supercontinent at all.
But reasoning processes located on smaller, apparently unconnected islands would lack access to the physical applications that the supercontinent happens to include, so the brains they run on would never get anywhere.
I hesitate to go fully anthropic and say Math has little mystery because if it had more we’d never notice that it does. Because that doesn’t explain how after we realized the Unreasonable Effectiveness, it kept growing. But at least it is a fourth kind of answer to add to the three better ones you came up with.
Comment #32 April 23rd, 2015 at 12:10 pm
Since “surprise” itself is a construct within the mind, could evolution have conditioned us to a proclivity to discover the sort of mathematical relationships that are less likely to surprise us?
I’m struggling to describe what I want to say, but it is brain circuitry after all that lets us discover a deep mathematical truth. It is also brain circuitry that decides what surprises us. What if those different tasks are correlated in some way?
In other words, is it just harder to discover surprising things and easier to discover less surprising things? If so, then the rarity of surprises wouldn’t be so surprising any more since it would be now more a statement about what our brain can or cannot discover than the lack of surprises in math itself.
Not sure if I am making sense. 🙂
Comment #33 April 23rd, 2015 at 12:36 pm
While the success of mathematics is mysterious we can speculate about regimes where mathematics’ luck will run out.
Here is a very bold conjecture in this direction
Conjecture:
Any version of the prime number theorem (and perhaps even just the infinitude of primes) for an explicit deterministic set $A$ of integers containing less than $n^o(1)$ integers smaller than $n$ is intractable to prove!
We can even try to replace $n^o(1)$ by $n^{1/2-epsilon}$ for every $\epsillon >0$.
By explicit I mean that $A$ is the image of a function $f(k)$ defined on the set of integers by a polynomial time algorithm in the digits of $k$.
We do not allow randomization for the construction. (However, the conjecture may imply that certain very strong, yet, very plausible, versions of derandomization conjectures are also intractable to prove.)
“Intractable to prove” refers to one of various possibilities and being independence from ZFC is one of these possibilities (but not the only one). An informal way to think about “intractable to prove” is :
“mankind will never be able to prove it.” (There is a famous claim that the value of the Ramsey number R(6,6) is intractable to prove. This also relates to Jay’s question. A task being finite does not make it tractable.)
Of course, the main reason for making such a bold conjecture is to try to attract counter-examples and perhaps also to find reductions between instances of the conjecture.
The issue is: will it make it easier to prove that there are infinitely many primes for a set with less than $n^{1/3}$ integers among {1,2,…,n} (say) (for every $n$) if *you* can devise the set as you wish!
(Yet another version of the conjecture will deal with sets where membership can be decided very efficiently, where “very efficiently” refers to computational complexity class not strong enough for primality.)
Comment #34 April 23rd, 2015 at 1:36 pm
Gil Kalai #25
“We know that mathematical statements can, in general, be undecidable. ”
But if the universe is mathematical in nature, what is the consequence of this?
Is there a physical equivalent to undecidability?
Like the apparent break in causality with randomness as a irreducible source of events without an apparent cause?
Or things like “on its way to the screen, did this electron go through the left slit or the right slit?”
Or the role of consciousness in the selection of coherent realities?
Comment #35 April 23rd, 2015 at 1:51 pm
Gil, that’s an interesting conjecture. Note that Iwaniec and Friedlander’s theorem http://arxiv.org/abs/math/9811185 is almost but not quite a counterexample They prove that there are infinitely many primes which are of the form m^4+n^2. The set of k which are at most x and are of this form has O(x^(3/4)) .
Comment #36 April 23rd, 2015 at 3:43 pm
@Gil Kalai:
That’s not really speculation, though. We already know that most questions in number theory are hard to solve.
Comment #37 April 24th, 2015 at 9:49 am
MadRocketSci #9
“If you have something differentially smarter than an ape though: all of a sudden the range of stuff that makes sense shoots clear across the observable universe to the beginning of time and includes things that have absolutely nothing to do with our ancestral environment, like quantum physics that you mentioned, or the star-quakes on neutron stars.”
Once we had the tools to do in-depth analysis of things that were in our ancestral environment, like microscopes to understand microbes and fight diseases, or the math tools necessary to build bridges and do finance, or electricity to do long range communication, the rest just snowballs and it’s only a matter of time before we very quickly hit the potential limits of our knowledge (QM, energy barrier of super colliders).
What’s interesting to me is whether there is something beyond human mathematics, i.e. whether all the physical mechanisms of the universe can be mapped onto the structures of the human brain. If machines are the next step in evolution we may be able to get an answer (the day they come up with predictions that we won’t understand).
Comment #38 April 24th, 2015 at 5:00 pm
Scott #30:
Can you explain this in some other way? It seems “obvious” to me that if someone had claimed that FLT were undecidable, then I should not have believed them. This is because we could compute a counter example to FLT if one existed. So if FLT were undecidable, then no counter example could ever be found. But, surely, this would mean that FLT has to be true… Same applies to RH… Perhaps I am misunderstanding something… (In any case, this type of thinking seems too twisted for my taste!!)
Comment #39 April 24th, 2015 at 5:39 pm
gh #38: Again, if you knew FLT or RH were undecidable in some reasonable formal system, then you would also know they were true. I’m not disputing that!
But, again, it’s logically possible for RH to be undecidable, and for its undecidability to itself be unprovable, and so on forever. In that case, RH would indeed be “Platonically true,” but we would never get any formal indication of it. I.e., we would remain forever in exactly the same epistemic state that we’re in now.
Comment #40 April 25th, 2015 at 4:20 am
How does the mathematical community come up with good problems? I mean what is the general process? There has to be something common in the history of good problem definitions.
Comment #41 April 25th, 2015 at 7:16 am
Ashley #40: That’s sort of like asking, “how does the Internet community come up with good memes?” Someone suggests something; then if other people like it they repeat it (in talks, papers, conversations, open problem lists, etc). Maybe the problem gets quickly solved, or shown to be equivalent to some previously-known problem, but maybe subsequent study shows the problem is even richer and more interesting than originally thought. If the original proposer is famous, it might increase the chance of the problem being noticed, but that’s by no means necessary (e.g., Riemann was a mathematical giant independently of his Hypothesis, and Poincaré independently of his Conjecture, but Goldbach and Collatz were not).
Comment #42 April 25th, 2015 at 9:15 am
Scott #39:
Thank you for the clarification. But I am still not convinced! Even if the hierarchy of undecidability that you described were to exist, then this, in itself, would imply that no counter example to RH (or FLT) could ever be computed or found! This, to me, would be proof that the RH is true.
Comment #43 April 25th, 2015 at 10:11 am
Scott,
I was more asking about the sequence of things before the event ‘Someone suggests something’ (I should have asked how a mathematician comes up with good problems – my bad. I used the word ‘community’ because I thought in general this event could be a culmination of decisive contributions from various individuals).
Mathematicians don’t randomly generate problems and then select the good ones, so what is it that they do? Of course we definitely do not understand this process well enough to write computer programs, but we may be able to say things like they try to generalize known facts, or they modify ‘existing’ problems etc. (It could be that there are multiple such ‘ways’ mathematicians generally come up with problems, but not numerous ones).
(Do they have good books on this kind of thing, somewhat analogous to ‘How to solve’ kind of books on the problem solving thought process?)
Comment #44 April 25th, 2015 at 10:19 am
gh #42: Once again you’re failing to distinguish between the hierarchy of undecidability existing, and our knowing that it exists. Maybe there’s this hierarchy for the Riemann Hypothesis right now, but we don’t know it! But you wouldn’t say on that basis that we already have a proof of RH, would you? I don’t know how else to explain it to you.
Comment #45 April 25th, 2015 at 10:26 am
Ashley #43: Rather than asking about these things in the abstract, it would probably be better if you dipped into some particular area of math (maybe one requiring little background, like elementary number theory?) so you could get a sense for mathematicians’ thought processes. For example, you could try the book Unsolved Problems in Number Theory by Richard Guy. Briefly, though, the usual ways to come up with new problems include these:
– You play around with things, notice a pattern, and wonder whether always holds or whether there’s a deeper explanation for it
– You’re trying to do something very concrete (say, solve an equation), notice a difficulty, and wonder whether the difficulty represents an inherent limitation of the tools you’re using
– Someone else proves something, and you wonder whether it can be generalized, or whether the converse is also true (“but is it an if and only if?”), or whether it’s still true if you drop an assumption, or whether an analogous result holds for something you personally care about
– You’re trying to compute something, and you wonder whether there’s a faster way to do it
– You know from experience or history that asking a certain kind of question tends to be fruitful—so when a new mathematical object is proposed, you immediately ask that question about it
– (My personal favorite 🙂 ) Someone else says something you think is wrong, and you wonder how to prove it’s wrong
Comment #46 April 25th, 2015 at 2:14 pm
gh #42,
There a few issues here going on, and Scott has touched on most of them, but I’d like to make one of them more explicit: if I prove in some broad sense that say RH is undecidable in some axiomatic system (say ZFC), then I haven’t proven in ZFC that RH is true, but I’ve only proven it true in some larger metamathetical sense.
Comment #47 April 25th, 2015 at 6:13 pm
Maths is just a consequence of some rules. In tic-tac-toe (or “noughts and crosses” where I live) you can show that the 2nd player must place a cross/zero on a diagonal to avoid defeat (assuming the first player played the centre square). As the domain and rules get bigger there are far more complex possibilities,
There shouldn’t be any puzzlement that complex stuff arises, but also we wouldn’t expect a HUGE number of surprises – we are aren’t performing magic by creating a few rules/axioms in the first place
Nature, also, surely has a ruleset – and discovering that is a much bigger deal.
Unfortunately us dumb humans find approximations to nature’s rules and then extrapolate this in fantasy worlds that are much more complex than anything in nature.
There’s mystery in mathematics, because it’s unnatural, if we ever meet an alien species I’m sure they will have discovered weird mathematics beyond number theory etc that will astound us, just as they may be astounded by inter universal teichmuller theory and other weird stuff that we’ve managed to create.
But nature has only one possible correct interpretation, and it surely won’t involve a lot of the more esoteric areas of mathematics.
Comment #48 April 25th, 2015 at 8:11 pm
You’re conflation (in the article) of the issue of propositions being independent of the axioms of a system and Godel undecidability is unhelpful here; what Godel proved was that there must be propositions where only one answer is consistent with the axioms of a system but nonetheless can’t be proven from those axioms.
I think the possibility of the undecidability of open problems should be considered a serious possibility precisely because, for many of the problems you mention, unprovability of undecidability is or is nearly a logical consequence of undecidability. So I’m uncomfortable saying the Godelian gremlin hasn’t reared its head when there are plenty of problems where a) it could have and b) if so we’ll almost certainly never know that it has.
To make my point more concrete let’s consider the possible universes for P vs NP:
1. P = NP and this can be proven.
2. P = NP and this is impossible to prove.
3. P != NP and this can be proven.
4. P != NP and this is impossible to prove.
P = NP seems less likely precisely because most of the proof for it has been written — all we need is a polynomial time algorithm for an NP-complete problem, and if P = NP then such an algorithm certainly exists. That makes #2 almost impossible. I say almost, because there is a remote possibility that algorithms exist that have a polynomial runtime bound, but it is impossible to prove that their runtime is polynomially bounded. So to prove the undecidability of P vs NP you would need to show that either P != NP or that it will be impossible to prove that the runtime bound of any polynomial algorithm to an NP-complete problem is actually polynomially bounded. That would be a truly miraculous proof; I would be quite surprised to discover that it is possible to prove that and not possible to establish P vs NP. I am not holding my breath for that proof. But the remaining possibilities are, we will either some discover a proof one way or the other, or we will beat our heads endlessly against this problem never knowing that it is impossible and we should just add P != NP as an axiom. I see no reason to doubt that last possibility; it seems quite likely. It is even more likely that, among the various open questions you mentioned, there is at least one problem like that. We’ll never know that to be true; we’ll only maybe see a few of them knocked off the open questions list and figure the problems we can’t solve seem no different from the problems we had a lot of difficulty solving but ultimately did.
Comment #49 April 26th, 2015 at 1:28 am
@Eric http://en.wikipedia.org/wiki/P_versus_NP_problem#Polynomial-time_algorithms
Comment #50 April 26th, 2015 at 2:10 am
Much of this discussion of the mystery of math is about the foundations of math. When physicists like Wigner talk about the mystery of math, I don’t think that they care about these foundational issues at all.
Comment #51 April 26th, 2015 at 9:06 am
Partial answers to the questions asked by several commenters (e.g., Kalai #25 and #33; Ashley #40 and #43; Eric L #48, etc.) are supplied by mathematical luminaries — that include Fields Medalists Noam Elkies and Terry Tao — in comments-and-answers to the MathOverflow question “For which Millennium Problems does undecidable -> true?”.
In particular, it is natural to sharpen the question to
There are two classes of answers.
The first class of answers accepts the problem statements in their present form: then if we further assume P≠NP, then the Riemann Hypothesis is the sole Millennium Prize problem that can be falsified by an $\Pi^0_1$ counterexample whose form can presently be envisioned.
The second class notes that Millennium Prize problem statements can be amended (at the discretion of the Scientific Advisory Board (SAB) of the Clay Mathematics Institute (CMI)).
Then the following question is (seemingly) entirely open
Opinions vary widely in regard to the second question … this variation signifies a healthy and vigorous mathematical community (needless to say).
Conclusion It is reasonable to consider whether amended postulates associated to the Millennium Prize statement of the PvsNP problem might simultaneously evade proof obstructions and still address practical questions like “do there exist dynamical systems — including both physical systems and ciphers — that provably cannot be simulated/solved in with resources in P?”
Comment #52 April 26th, 2015 at 10:50 am
Why should we be surprised that ZFC resolves a lot of classical mathematical statements- it didn’t “come out of nowhere”; it was designed for that purpose. Indeed, suppose a sudden spate of inconsistency results presented themselves: I mean, really classical questions like Goldbach’s Conjecture, Riemann Hypothesis, etc. were shown to be independent of ZFC. Then wouldn’t we look at the axioms again?
Comment #53 April 26th, 2015 at 2:02 pm
Sam #52
Good point, in fact it’s not clear (afaik) whether Mochizuki’s recent claimed proof of the abc conjecture satisfies ZFC – but suppose his argument turns out to be quite persuasive, but requiring an addition axiom(s) – how would the mathematics community respond?
I was fascinated by the Goodstein Theorem as a student, since it was a very concrete example of a sequence of numbers which converge to zero (incredibly after massive explosive growth) – but the convergence can not be proved in Peano arithmetic. There are no infinities involved, the sequence just grows very large but finite and always descends back to zero. However, you just need to add an axiom to allow transfinite ordinals, then the proof is simple!
So I lost my fascination, as it seemed just a clever game where you can find “mysteries” but you solve them by additional rules to cover the “mystery”
side note: I attended a public lecture at the Cambridge Newton Institute shortly after Andrew WIles had claimed a proof of FLT, the proof was still not verified. John Coates gave the lecture and at the end Stephen Hawking asked a question – “Does the proof use the axiom of choice?” – Poor John Coates was very uncomfortable giving an answer, he said no, it was all very straightforward constructions that didn’t employ AC. To be fair to professor Coates, the proof was not fully understood at the time, and Wiles had yet to provide the crucial Euler system to fix a big error. As it turns out, it is now accepted that the axiom of choice IS required in Wiles’ proof.
So how do people feel about a proof of FLT requiring a slightly “dodgy” (“unnatural”?) axiom – is that satisfactory? Should we require a proof in ZF alone (not ZFC)?
Comment #54 April 26th, 2015 at 5:56 pm
James, FLT does not require AC. Wiles’s proof does not use AC, and even if it did, Shoenfield says that it can be removed.
Comment #55 April 26th, 2015 at 6:27 pm
Douglas
Ok, it seems tricky point, in fact Wiles’ proof may involve even worse stuff like Grothendieck Universes
If “Shoenfield” has a paper can you link ?
Comment #56 April 26th, 2015 at 7:06 pm
James #55: Wiles’s original proof did indeed use Grothendieck universes, which go outside ZF, but it’s now known that that was just a convenience, and that the proof can be reformulated within ZF. (On the other hand, it’s still open how to do the proof in PA; almost all experts think it’s possible, but it seems to require genuinely new ideas.) See here for more.
Also, Douglas was referring to Schoenfeld’s absoluteness theorem, which tells us that all the purely arithmetical consequences of ZFC can be proved in ZF alone. That implies that the proof of FLT can’t possibly need the axiom of choice.
Comment #57 April 26th, 2015 at 8:10 pm
Sctoo @ 56,
That actually brings up a question: given a proof S in ZFC of an arithmetic statement T, how tightly can we bound the size of the proof of the smallest proof in ZF of T in terms of the length of S? It isn’t immediately obvious to me even that there’s any such bound that is a computable function. So it may be that although the proof of FLT doesn’t require choice, the length of any such proof will be much too long for a human to ever work out. (This issue obviously goes away if there’s a way to make absoluteness constructive. I don’t know of any but I’m not a model theory person.)
Comment #58 April 26th, 2015 at 9:49 pm
“Jshoua” 🙂 #47: Maybe I’m missing something, but why wouldn’t a proof of FLT that used choice, together with the proof of Schoenfeld’s absoluteness theorem, just constitute the desired proof (when suitably expressed in the language of ZF)?
Comment #59 April 26th, 2015 at 11:22 pm
No, it was always 100% completely clear that Wiles’s use of universes was pure convenience.
Comment #60 April 26th, 2015 at 11:47 pm
The parts compose the whole.
The whole comprises the parts.
Comment #61 April 27th, 2015 at 7:54 am
Douglas #60: OK, thanks, fixed.
Comment #62 April 27th, 2015 at 7:55 am
Oof, I saw that typo right as the comment was submitting.
That pushes the limits of how much I know about ZFC, but I’m not sure you if you can phrase that in ZF itself. Again, I’m not a model theory person but can ZF talk about itself that way?
Comment #63 April 27th, 2015 at 9:14 am
Scott, do you know whether anyone has proved the existence of sentences with the property you mentioned — that they should be independent of ZFC, and such that the fact that they are independent is again independent of ZFC, and so on?
Comment #64 April 27th, 2015 at 9:27 am
Ashley #43
I’m pretty sure that career prospects also play a big role in selecting what problems are worth pursuing.
If the community thinks something is a long shot, or very complicated, it’s only natural that ppl will be more reluctant spending precious years of their limited life on it.
Comment #65 April 27th, 2015 at 1:37 pm
There is nothing mysterious about math, because it is a dedcutive science. No mystery in 2+3=5. However, as soon as mathematicians add imaginary concepts like infinity, it becomes mysterious.
Comment #66 April 27th, 2015 at 3:08 pm
Joshua #62: I’m not a model theorist either, but if we don’t get a short proof in ZF, shouldn’t we at least get a short proof in ZF+Con(ZF) or something like that? The point here strikes me as a big one, not just a matter of detail: namely, if you prove that a proof of X has to exist, then we might as well say that you thereby have proved X!
Comment #67 April 27th, 2015 at 3:12 pm
Eyvind #63: Formally, the Gödel sentence G(F), or the consistency statement Con(F), are already examples of what you’re asking for. We know that if F is sound, then it can neither prove nor disprove Con(F). But even if F could prove that Con(F) was independent, or that the question of Con(F)’s independence was independent, etc., etc., any of those statements would amount to proving Con(F) itself (since if Con(F) had been false, none of these questions would’ve been independent).
Comment #68 April 27th, 2015 at 5:11 pm
Scott #66,
Yes, you should get a short proof in ZFC+ Con(ZFC), but there can be as I understand it very big reductions in proof size between proofs in ZFC and proofs in Con(ZFC).
On the gripping hand, if we believe that ZFC is consistent we should be just as ok using ZFC+Con(ZFC) anyways.
Comment #69 April 28th, 2015 at 7:42 am
Scott #67: Right, those are examples of what I asked for, but on the face of it they don’t really open up the epistemic abyss of “never even […] knowing why we’ll never know” in a satisfactory way 🙂
Hmm, so perhaps I should rather have asked something along these lines: Is it known whether there are sentences A such that not only is A independent from (the suitable formal system) F, but so is
Con(F) \to Ind_F(A) (=”A is independent from F”),
and in general Con(F) \to Ind_F^n(A), where
Ind_F^1(A) \equiv Ind_F(A)
and
Ind_F^{n+1}(A) \equiv Ind_F(Con(F) \to Ind_F^n(A))?
(One could also replace Con(F) with something stronger, like Con(F+Con(F)), and so on, but then I guess we land squarely in the subject of autonomous progressions of theories…)
Comment #70 April 28th, 2015 at 9:16 am
Eyvind #69: Once again, I think I can give you what you’re asking for but in a way you won’t like. Namely, you could take an iterated consistency statement, where the number of iterations is some infinite countable ordinal!
Now, the question of whether there are arithmetical questions whose answers are independent of PA or ZFC plus all iterated consistency statements—involving all possible computable ordinals, all the way up to the Church-Kleene ordinal—is an extremely interesting one. But my understanding is that, alas, it doesn’t have a well-defined answer, because it can depend on how we choose to encode computable ordinals as Turing machines. In fact, given any Π1-sentence A, there’s some (“cheating”) way of encoding ω+1 by a Turing machine, in such a way that PA plus its (ω+1)st iterated consistency statement decides A. Indeed, this was one of the main observations in Alan Turing’s 1939 PhD thesis. For more, see my blog post What Alan T. Did for His PhD.
Comment #71 April 29th, 2015 at 8:31 am
Scott #70: Right now I don’t see why you shouldn’t be able to prove Con(F) \(\to\) Ind\(_{F}\) (Con(F) \(\to\) Ind\(_{F}\)(A)) in F, if A is such an iterated consistency statement for F. But for the time being my head is completely taken up with grading student papers, so perhaps I’ll better get back to that later 🙂
I agree that the work of Turing, Feferman and Spector on progressions of theories is extremely interesting, and it is interesting that whether a statement A is independent of PA or ZFC plus all (or a lot of) iterated consistency statements seems not too closely connected to how simple it is in terms of how many of the statements Ind\(_{F}^n\)(A) hold: For a statement like CH, which isn’t even arithmetical, we can still prove Con(ZFC) \(\to\) Ind\(_{ZFC}\)(CH), so that it is “simple” in the sense that we know “why we’ll never know”. (Or at least, why we’ll need some completely new insight to settle it…)
Comment #72 April 29th, 2015 at 5:31 pm
There is nothing mysterious about math at all. In particular, the most important benefit of math is not that it allows us to “understand things in a deeper way”, but rather that it allows us to derive correct conclusions even when we are unable to comprehend something holistically.
The human brain features a very powerful inference engine, but our ability for hostical comprehension is seriously bottlenecked by the limitations of our memory subsystem. Math just helps us to work around these limitations. That’s all.
Comment #73 April 29th, 2015 at 7:11 pm
The following quote seems to be relevant. 🙂
“The Axiom of Choice is obviously true, the well-ordering principle obviously false, and who can tell about Zorn’s lemma?” — Jerry Bona
Comment #74 April 30th, 2015 at 2:32 am
Michael #73:
Which equivalent statement maximizes your confidence that the axiom of choice is reasonable? I find the following one quite intuitive: “Every (infinite) connected graph has a spanning tree.”
A world where (infinite) graphs do not have this property, would be a very strange world from my point of view. Thus, it makes sense to add this as an axiom for me.
Comment #75 April 30th, 2015 at 4:34 am
One other remark with respect to the axiom of choice:
Why is there so much more controversy about the axiom of choice than about the axioms of traditional ZF? What makes the foundation axiom or the axiom of infinity more natural than the axiom of choice? After all, non-well-founded set theory is possible, but I never heard that a proof was questioned, because it requires the foundation axiom.
You could argue that the foundation axiom seems natural, because we identify sets with collections of physical objects, and it resembles our real world experience that collections of physical objects cannot be recursive. But then again, all the collections of physical objects that we deal with in the real world are finite. Thus, following the same argument, the axiom of infinity seems not natural at all. And if we exclude the axiom of infinity, then the axiom of choice becomes very natural.
As far as I can see, there is only so much controversy about the axiom of choice, because it is often possible to find proofs that work without this axiom. I am pretty sure that virtually no one would question the axiom of choice if the vast majority of proofs simply required it to work.
So apparently, whether an axiom is accepted or not says more about how much we need it than about how natural it is.
Comment #76 April 30th, 2015 at 10:24 am
For students especially, it may be more productive to wonder
The nLab web page The Axiom of Choice provides a succinct overview, with references to a large literature. In a nutshell, category theorists embrace the broader view that
For the particular category Set, the usual ZFC/Axiom of Choice is recovered.
Note that for the mathematical citizens of nLab‘s categorical universe, the properties of Set are not foundational, such that the role of the Axiom of Choice is not fundamental.
For some practicing mathematicians (not all), this framework is an example of — in Wittgenstein’s phrase — a mathematical problem solved by its being dissolved.
Conclusion Opinions in regard to categorical frameworks differ widely and are evolving rapidly … and that is why it is well for young researchers to at least be aware of this burgeoning literature.
Comment #77 April 30th, 2015 at 12:49 pm
Alexander #75: My post with a quote was a jest comment on the viewpoint inferred from Scott’s article that mathematical truth often seem natural; the business around axiom of choice seems to indicate that sometimes seemingly obvious assertion may contradict each other.
As for importance of the axiom of choice and in all its guises, it prevents numerous pathological oddities.
Comment #78 May 1st, 2015 at 10:44 am
You write,
“Conceivably, not only are all those conjectures unprovable from the usual axioms of set theory, but their unprovability is itself unprovable, and so on, so that we could never even have the satisfaction of knowing why we’ll never know.”
With this wording, I’m not sure if you’re aware — and probably a number of readers aren’t — of how very terrible of a problem this is! Indeed, it is easily shown that many (most?) of these problems (Goldbach conjecture, Riemann hypothesis, P v. NP) would be unprovably unprovable if they were in fact unprovable.
Suppose that the Goldbach conjecture were unprovable. Certainly then it can’t be false, because a sufficiently long search through the natural numbers would find the counterexample and thus prove it false. So if it were known to be unprovable, we could immediately see it to be true, so that any proof of unprovability would itself be a proof (of truth), a contradiction. So if Goldbach’s conjecture is independent of the normal axioms, we’re never to know.
Similar arguments hold of the Riemann hypothesis (where a counterexample would be a zero off the critical line; something we can find with a search), P v. NP (if they are equal, there is an algorithm to transform 3SAT into Horn-Sat, and this can be found by a search), Birch and Swinnerton-Dyer (this is equivalent to a statement about integer solutions to polynomial equations, where a counterexample could easily be verified), the existence of odd perfect numbers, Euler bricks, Lehmer’s totient problem, and many others.
It’s worrisome, I think. :/
Comment #79 May 1st, 2015 at 4:00 pm
Alex #78: First of all, P vs. NP is genuinely different from the other questions you mention. If P=NP, it’s not clear that we can verify it finitely, since there’s an algorithm that you need to verify is correct and halts in polynomial time on every input. (Technically, P≠NP is a Π2 rather than Π1-sentence.)
More importantly: yes, it’s true that if a Π1-sentence like Goldbach were independent of ZF, then its independence would also need to be independent and so on forever.
But as I said in one of the comments above, there’s also another possibility: that we could prove that Goldbach is unprovable in ZFC if true, via a proof that did nothing to address the possibility of its being false. That would be the case, for example, if we could somehow prove Goldbach equivalent to Con(ZFC).
Comment #80 May 2nd, 2015 at 4:12 pm
Scott #78 “Technically, P≠NP is a Π2 rather than Π1-sentence”
Let’s suppose that there is a proof that P≠NP. Would that turn this question into a Π1-sentence? I mean, instead of looking for Levin’s algorithm on every input, couldn’t we enumerate all possible proofs that P≠NP, and if there is one then this procedure will halt after a finite number of steps?
Also, if someone find that “either P≠NP or ZF is false”, would that makes P≠NP or would that make the question independant of ZF?
Finally, how would you handle a crazy result such as: “P≠NP implicates ZF+not(con(ZF))”? (not because that’s likely, but to help me understand “ZF plus ZF not consistent” -you mentionned in your writings that, as crazy as it sounds, this strange creature is as consistent as ZF itself)
Comment #81 May 2nd, 2015 at 11:27 pm
Is this question related to the question of why giant components form in things represented as graphs? I imagine mathematical discovery linked together like the famous graph of everyone related to Erdos.
In semantic networks, this giant component thing happens, in social networks, biological transcription networks. There are more commonalities than that: a radical fat-tailed inequality in degree, if you represent all these natural phenomena with graphs. Them looking suspiciously like plaid if you look at the adjacency matrices. Then the explanation could be the fairly easy heuristic one: imagine there were two big components which are left unconnected, and you were sampling from the graph space: the chance that there are _no_ edges between the two big components decreases really quickly
Comment #82 May 3rd, 2015 at 11:47 am
Questions like “Is there something mysterious about math?” are motivated (in part) by the Hogwarts-style practical objective “Help students learn to apply the mysterious powers of math.” Students bring three expectations to this learning process:
We know of course that rigor+universality is unachievable, and so the most that students can expect from their choice of mathematical foundations is a reasonable accommodation of rigor+naturality.
What options does present mathematical research offer for foundations that unite rigor with naturality? An explicit roadmap — as envisioned by a group of mathematical luminaries — is “Homotopy Type Theory: Unified Foundations of Mathematics and Computation/MURI Proposal” (2014) and its accompanying textbook Homotopy Type Theory: Univalent Foundations of Mathematics (2014).
Many of the key ideas and motivations of this roadmap are set forth informally and accessibly in a two-part “Interview with F. William Lawvere” (Bulletin of the International Center for Mathematics, 2007). In a nutshell, category theory seeks to provide foundations that ensure rigor and foster natural human understanding.
Conclusion In some mathematical circles (not all) the reputation of ZFC is fading: it’s superstrong on rigor, not so helpful on naturality. Concomitantly, the reputation of category theory is rising: it purports to subsume ZFC (thereby subsuming ZFC’s rigor) while affording greater practical/personal access to “the mysterious power of mathematics” than ZFC.
At least, that’s what some (not all) mathematicians are asserting nowadays … young researchers (especially) have to assess for themselves the viability of these ideas.
Questions Would the full embrace of these ideas entail radical revisions in STEAM pedagogy … including revisions of textbooks, syllabi and degree requirements? And can be consequences of such an attempted revision be fully and reliably foreseen?
Answers Yes to the first question; no to the second. That’s why these ideas are contentious.
Comment #83 May 3rd, 2015 at 12:58 pm
Jay #80: In some sense, a proof of P≠NP would make it equivalent to a Π0-sentence—namely, 1=1, or some other tautologically-true sentence!
If you had a proof of P≠NP assuming Con(ZFC), and that proof was itself formalizable (in principle) in some reasonable system, I’m pretty sure the Clay foundation would give you the million dollars, and virtually all mathematicians would consider the problem solved. After all, as we discussed above, Wiles’s original proof of FLT used principles beyond ZFC (Grothendieck universes), but most mathematicians in fields other than logic don’t really care about such things.
If you had a proof that P≠NP implied ZFC’s inconsistency, then I suppose I’d have to bite the bullet, and say you’d given massive evidence for P=NP. But at this point we’re deep into the realm of Alice-in-Wonderland hypotheticals: e.g., “would you still believe the Big Bang theory, if someone proved it implied ghosts were real?”
Comment #84 May 3rd, 2015 at 1:12 pm
Howon #81: Yes, I suppose you could mount an argument that that’s all that’s going on with the interconnectedness of the mathematical world. But the counterargument would be that in other fields, you would think the same argument would apply, yet we almost never see the same degree of crazy interconnectedness. E.g. it’s a safe bet that the explanation for some geological formation on Earth doesn’t involve Saturn, yet it’s not a safe bet that the explanation for the behavior of a random walk doesn’t involve modular functions. So we simply can’t think of the edges in an explanation graph as being sampled anywhere close to randomly, without some further argument for why we should expect that in particular cases (like math?).
Comment #85 May 3rd, 2015 at 1:13 pm
“But Turing-undecidability and Gödel-undecidability are not all the same thing” what does this mean?
Comment #86 May 3rd, 2015 at 1:48 pm
you have mentioned before it is not proven quantum computers are not proven to have exponential improvement over classical computers. I heard a lecture by Yao who states a certain Simon’s problem is exponentially faster on QC provably http://courses.cs.washington.edu/courses/cse599d/06wi/lecturenotes8.pdf
So quantum computers are provably better?
Comment #87 May 3rd, 2015 at 2:20 pm
There is an interesting quote from Amos Funkenstein’s book “Theology and the scientific imagination”
“The history of mathematics may be read as a running commentary on the incompleteness theorem. Time and again the inability to solve problems within one field led to the constructions of new fields, since ‘no antecedent limits can be placed on the inventiveness of mathematicians in devising new rules of proofs.'”
I saw it in an exciting essay on language and geometry by Ehud Hrushovsky (in Hebrew)http://www.academy.ac.il/data/egeret/90/EgeretArticles/4_Ehud_Hrushovski_31.pdf
Comment #88 May 3rd, 2015 at 3:26 pm
a #85: It means that they are not the same thing. (If they were, Turing wouldn’t have needed to prove a new result in his paper; he could’ve just noted that Godel already did it!) Turing-undecidability is a concept that applies to languages, like the set of all solvable Diophantine equations, while Godel-undecidability is a concept that applies to individual propositions, like the consistency of ZF or the Axiom of Choice. (Also, Godel-undecidability is always relative to your choice of formal system, whereas Turing-undecidability is an absolute concept, not dependent on the formal system at all.)
a #86: An exponential quantum speedup is provable today for black-box problems (i.e., problems involving an oracle), such as Simon’s problem. It is not provable today for non-black-box problems (which don’t involve an oracle), such as factoring integers. That is the resolution.
Comment #89 May 3rd, 2015 at 3:50 pm
Scot 83, Thx, that answers my two first questions. But my last question was even weirder than how you read it.
It’s not a “what if P!=NP implicates ZFC’s inconsistency”. It’s about the consistency of the (unsound) system of axiom ZF+(ZF not consistent).
Correct me if I don’t get this straight, but assuming ZF consistent, then it’s true that ZF+(ZF not consistent) is itself consistent. But how would you interpret that the latter, the latter only, was proven true iff P!=NP ?
My thought now is we shouldn’t interpret this as evidence for ZF inconsistency at all. To the contrary, if ZF was not consistent, then also ZF+(ZF not consistent), then P!=NP would be wrong. Certainly we could say that P!=NP is independent of both ZF and ZF+(ZF not consistent), or we could prove ZF+(ZF not consistent) within itself -and then it would not be consistent. But I also think I may be doing a bad mix between theories and models, so your input would be welcome.
Comment #90 May 3rd, 2015 at 4:37 pm
Jay #89: Sorry if I didn’t and don’t understand your third question. ZF and ZF+(ZF not consistent) have the same consistency strength; that the latter is consistent if ZF is, is best seen as just an inevitable consequence of the Second Incompleteness Theorem. Now, I would bet quite a bit of money (if Dana still let me bet on such things!) that the consistency of ZF is TRUE, so much so that if the inconsistency of ZF were shown equivalent to something I believe (like P≠NP), then I would believe that other thing dramatically less. At the same time, even an inconsistency in ZF wouldn’t be the end of mathematics (or imply that 1+1=3, etc.); it would “merely” mean that we had to rebuild the foundations (as already happened before, e.g. with Russell’s paradox, and note that that rebuilding happened with very little disruption to the upper floors). Sorry if this still isn’t the answer you were looking for; as I said, I might not fully understand what you’re asking (and my flight to Phoenix is about to take off).
Comment #91 May 3rd, 2015 at 4:58 pm
I think everyone agrees that physics is mysterious.
The mystery arises from a seemingly arbitrary choice of rules leading to something that we, as humans, can interpret, recognize, and relate to.
One example of this is the Game of Life. It is very mysterious that such a small set of rules can lead to emergent behaviors and patterns which are very familiar to us.
Another example is the way humans resonate with the seemingly simply physics of parabolic ballistics – hence the pleasure of throwing baseballs or the massive and broad success of the video game Angry Birds.
With mathematics in general (disconnected from physics) the connections with humans are more abstract, but many mathematicians talk about finding beauty in equations, and beauty is always mysterious.
Comment #92 May 3rd, 2015 at 6:20 pm
>ZF and ZF+(ZF not consistent) have the same consistency strength
Do you mean that both con(ZF) => con(ZF+(ZF not consistent)) and con(ZF+(ZF not consistent)) => con(ZF)? If yes, then ok that answers my question! (I thought only the former was known)
Comment #93 May 3rd, 2015 at 7:10 pm
>con(ZF+(ZF not consistent)) => con(ZF)?
Silly me, of course if there is no inconsistency within ZF + whatever, then there is no inconsistency within ZF. Question solved, sorry!
Comment #94 May 4th, 2015 at 2:45 am
Comment #88 What is the best book/notes to understand the undecidability context w.r.t turing/Godel you are explaining?
So if one proves that there is no other way to solve factoring efficiently without using black box models, you would have shown quantum better than classical query complexity? Do you think this could be proven?
Comment #95 May 4th, 2015 at 9:48 am
a #94: I really love the book Gödel’s Theorem: An Incomplete Guide to its Use and Abuse, by Torkel Franzen. (Plus, it’s short and cheap.) Or you could try Chapter 3 of my own Quantum Computing Since Democritus.
Again, for query complexity (the measure relevant for period-finding), we already know an unconditional exponential separation between quantum and classical. For circuit and time complexities (the measures relevant for factoring itself), we can only conjecture such a separation at present; proving it would require solving an even harder problem than P≠NP.
And yes, if one could prove that “there’s no other way to solve factoring than to reduce it to the black-box period-finding problem,” then one would be done. The problem (or one problem, anyway) is that that statement is false!! We already know classical factoring algorithms—notably, the quadratic field sieve and the number field sieve—that run in subexponential time (like ~2√n or ~2n^{1/3}), which is faster than one could possibly achieve from the usual reduction to period-finding.
Comment #96 May 5th, 2015 at 7:48 pm
Hamming’s thoughts are interesting too:
The Unreasonable Effectiveness of Mathematics
by R. W. HAMMING
https://www.dartmouth.edu/~matc/MathDrama/reading/Hamming.html
Comment #97 May 7th, 2015 at 9:32 am
Tony #96
Can we flip this around and try to imagine examples of realities/worlds/systems where mathematics wouldn’t be effective?
Comment #98 May 7th, 2015 at 10:17 am
Besides, what does “effective” even mean?
There’s a big difference between “elegant” theoretical equations/models and making actual accurate predictions/computations.
In many cases, we fall back to “simulations”, which try to mimic the bottom-up way of how nature works (even for something as seemingly simple as the three-body problem).
Pure analytical solutions are also rare, and we fall back to basic numerical approximations.
It all boils down to systems where there are “things” that have stable identities/properties and some stable order between them. That’s by definition what mathematics is and what a reality with human brains needs to be.
It then falls back to a sort of anthropic principle – mathematics works because we’re here to ask the question.
Comment #99 May 7th, 2015 at 10:44 am
Michael Harris’ recent weblog essay “My last word (for now) on HOTT” (May 2, 2015) articulates a point-of-view in regard to mathematical foundations that has not yet been heard here on Shtetl Optimized
The comments associated to Harris’ essay are lively and well-reasoned too (as they seem to me) … not all of them agree with Harris, needless to say!
Conclusion The ongoing “Moore’s Law” progress in large-scale quantum dynamical simulation capabilities presents us with a transformational heuristic advance that is only slowly being distilled to rigorous mathematical proofs, universal mathematical properties, and natural mathematical understandings … its good news for the entire STEAM community (young researchers especially) that the opportunities for participating in this distillation are wide open.
Comment #100 May 8th, 2015 at 6:10 pm
Here’s news of broad interest to readers of weblogs like Shtetl Optimized, Gödel’s Lost Letter, and Quantum Frontiers:
There’s plenty more material on the LogiQ Program Proposer’s Day announcement page.
Readers of Michael Harris’ book and/or weblog Mathematics Without Apologies (as they are both titled) will appreciate that IARPA is designating stable logical qubits as an avatar (in Harris’ phrase) for catalyzing advances in our general understanding of noise, decoherence, and entropy.
Conclusion The physical process of removing von Neumann entropy from systems of qubits/qudits can be appreciated as a mathematical avatar — in Michael Harris’ phrase — for the computational algorithms that (heuristically) are so marvelously effective in removing Boltzmann entropy from atoms/molecules in large-scale quantum simulation software … sufficient to compose (F)foundations for the $120M/5yr investment by the Swiss-based pharmaceutical corporation Sanofi in the Portland-based quantum simulation corporation Schrödinger.
Hopefully at least some East Coast quantum cognoscenti will attempt/report on this fine workshop!
Comment #101 May 10th, 2015 at 12:43 am
I will try to find some time to flesh out my reasoning, but for now I will just put my two cents in the fray:
I consider the mystery aspect of math to be pretty low. You come to understand new areas of math by working lots of problems, and once you grok it, it is obvious.
I also don’t find the effectiveness of math to be unreasonable. My view is that some problems are amenable to a math treatment, and we say “wow, that was effective”. Other problems are not amenable to math, so nobody knows anything about them but guesses and hunches. But we don’t say “this shows that math is not effective”.
There are also weird areas like applied statistics. Statistics can be very effective if you really understand it, but most people don’t. I have degrees in math and physics, but tend to be very unsure when using statistics in real world situations. However, it is not uncommon to see social scientists (likely with little math skill) announcing far fetched conclusions on the basis of some stat test. Sometimes these are decisive in court cases.
Two main branches of math are continuous and discrete. Continuous math is explored in advanced calculus, then real analysis and complex analysis.
In real analysis you learn that no matter how ugly the landscape, soldier on, figure out what an integral should be, and the basic tools usually almost work. No mystery here, just drudgery.
In complex analysis you learn that beautiful stuff is lying about, waiting to be discovered and put to use in physics problems. I see this as more wonderful than mysterious. Power series, the Cauchy integral formula, and classifying singularities are such powerful tools that everything has to work.
A tip for math students: Play around with the geometric series (finite and infinite) until you grok it. Pretty easy. Everything in power series and convergence tests boils down to comparing things to the series for (1 – z)^{-1}. It is also central in matrix theory and functional analysis.
Many math text books do a lousy job of showing how easy stuff really is. For example, it is insane that in the 21’st century anyone presents multivariable differential calculus with out using matrices. The usual lame excuse is that “this way, students don’t have to learn matrix multiplication”. But matrix mult is 100 times easier that MV calc, and a central tool useful for everything! Totally lame.
There are also lots of wonderful math books: check out Terrance Tao’s nonlinear dispersive waves book. I wish that had been around when I was studying that stuff 30 odd years ago.
Comment #102 May 12th, 2015 at 12:57 am
Know anything about this?
http://www.wired.com/2015/05/spooky-quantum-action-might-hold-universe-together
It claims gravity emerges from quantum entanglement, through an argument sort of reminiscent of statistical mechanics.
Comment #103 May 12th, 2015 at 11:00 pm
The reason undecidability (in the Turing sense) doesn’t bother ordinary mathematicians is because problems known to be undecidable tend to be artificial and “meta,” never straying far from circular questions about computation itself. Mathematicians genuinely investigating space and number (i.e., the natural universe) wouldn’t think to ask these sociological, human questions. Sure there are exceptions like Diophantine equations, but notice that undecidability only comes up for nasty equations with a much higher degree or number of variables than plane algebraic curves, which have been sufficiently rich to captivate number theorists for centuries. Imagine a number theory grad student putting the universal Diophantine equation on a Powerpoint slide for his qualifying exam. His professors would react as I’m sure you would to a student seeking to separate P and NP.
With the possible exception of the mortal matrix problem, I’ve yet to see an undecidable problem for which I could fool an unsuspecting mathematician into wagering “Sure, I bet I could come up with an algorithm for that.”
Comment #104 May 14th, 2015 at 1:30 pm
Here’s a candidate for undecidable-yet-natural: pick the fastest algorithm from a set of candidate algorithms.
More formally, given a finite set of algorithms — with each algorithm presented as a concretely specified Turing Machine [TM] — order the set of algorithms by runtime exponent.
This natural-yet-undecidable problem is the gist of the (well-rated) TCS StackExchange question “Are runtime bounds in P decidable? (answer: no)”:
Grappling with this particular class of undecidable complexity-theoretic properties extends to questions that are deep, open … and fun.
A deep/open extension When we consider the restriction of P to languages recognized by TM’s whose runtime exponents are bounded by computable limits, we are led to the considerations of the (well-rated) TCS StackExchange community wiki “Does P contain incomprehensible languages?”.
A recreational extension Further deep/open/fun undecidability considerations whenever TMs play William Newcomb’s Box-Game on Terry Tao’s Island of the Blue-Eyed People’
Conclusion The Complexity Zoo’s ecology of languages and the TM’s that accept them has sufficiently many undecidable / deep / open / fun attributes that present-day complexity-theorists appeal to oracles even to state problems of fundamental interest (like PvsNP).
Bottom line Mathematics may or may not be mysterious … but complexity theory definitely is!
Comment #105 May 16th, 2015 at 7:57 pm
Slides #104,
Don’t you asked about the behavior of a TM promised to halt? If it’s promised to halt, how could one reduce the halting problem to it?
I’m afraid Viola and Rafael answered what was in the title, not the question you’re reproducing here.
Comment #106 May 17th, 2015 at 5:32 pm
[…] once handled, enable the rest of the proof to be executed with a broad brush. As linked from an essay post by Scott Aaronson, Tim Gowers relates an opinion by Don Zaiger that we morph into saying that we […]
Comment #107 November 27th, 2015 at 8:54 pm
In your article you say that “A priori, Fermat’s Last Theorem, the Poincaré Conjecture, and pretty much every other statement of mathematical interest could have been neither provable nor disprovable…” However, it would not be possible to prove that independence for these statements. For instance,
– Assume that the Fermat Theorem’s is consistent
– Assume that integers a, b, c, violate the Fermat Theorem
– Then, the Fermat Theorem is inconsistent.
Therefore, proving that the Fermat Theorem is consistent would immediately prove the Fermat Theorem.
In the same way, many mathematical statements are proven immediately as soon as a consistency proof is given. I.e., an independence proof is impossible for these statements and that’s why there aren’t independence proofs. Perhaps many of the unproven statements are actually independent but we can’t prove that.
Also, I personally find it striking that the Continuum Hypothesis is independent. If that is not disconcerting, I don’t know what would be.