## Floating in Platonic heaven

In the comments section of my last post, Jack in Danville writes:

I may have misunderstood [an offhand comment about the “irrelevance” of the Continuum Hypothesis] … Intuitively I’ve thought the Continuum Hypothesis describes an aspect of the real world.

I know we’ve touched on similar topics before, but something tells me many of you are hungerin’ for a metamathematical foodfight, and Jack’s perplexity seemed as good a pretext as any for starting a new thread.

So, Jack: this is a Deep Question, but let me try to summarize my view in a few paragraphs.

It’s easy to imagine a “physical process” whose outcome could depend on whether Goldbach’s Conjecture is true or false. (For example, a computer program that tests even numbers successively and halts if it finds one that’s not a sum of two primes.) Likewise for P versus NP, the Riemann Hypothesis, and even considerably more abstract questions.

But can you imagine a “physical process” whose outcome could depend on whether there’s a set larger than the set of integers but smaller than the set of real numbers? If so, what would it look like?

I submit that the key distinction is between

1. questions that are ultimately about Turing machines and finite sets of integers (even if they’re not phrased that way), and
2. questions that aren’t.

We need to assume that we have a “direct intuition” about integers and finite processes, which precedes formal reasoning — since without such an intuition, we couldn’t even do formal reasoning in the first place. By contrast, for me the great lesson of Gödel and Cohen’s independence results is that we don’t have a similar intuition about transfinite sets, even if we sometimes fool ourselves into thinking we do. Sure, we might say we’re talking about arbitrary subsets of real numbers, but on closer inspection, it turns out we’re just talking about consequences of the ZFC axioms, and those axioms will happily admit models with intermediate cardinalities and other models without them, the same way the axioms of group theory admit both abelian and non-abelian groups. (Incidentally, Gödel’s models of ZFC+CH and Cohen’s models of ZFC+not(CH) both involve only countably many elements, which makes the notion that they’re telling us about some external reality even harder to understand.)

Of course, everything I’ve said is consistent with the possibility that there’s a “truth” about CH floating in Platonic heaven, or even that a plausible axiom system other than ZFC could prove or disprove CH (which was Gödel’s hope). But the “truth” of CH is not going to have consequences for human beings or the physical universe independent of its provability, in the same way that the truth of P=NP could conceivably have consequences for us even if we weren’t able to prove or disprove it.

For mathematicians, this distinction between “CH-like questions” and “Goldbach/Riemann/Pvs.NP-like questions” is a cringingly obvious one, probably even too obvious to point out. But I’ve seen so many people argue about Platonism versus formalism as if this distinction didn’t exist — as if one can’t be a Platonist about integers but a formalist about transfinite sets — that I think it’s worth hammering home.

To summarize, Kronecker had it backwards. Man and Woman deal with the integers; all else is the province of God.

### 91 Responses to “Floating in Platonic heaven”

1. Luca Says:

Amen!

2. Moodworves Says:

I’m having trouble imagining a process who’s outcome is dependent on the P vs. NP question. Certainly if P=NP, and the proof/algorithm is easy enough to find, that could influence a process, but is there a process that gives the answer to the P vs. NP question? In other words, is the P vs. NP question reducible a halting problem?

3. komponisto Says:

Let Man and Woman deal with the integers; all else is the province of God.

This sounds dangerously close to a quote of Errett Bishop:

“Classical mathematics concerns itself with operations that can be carried out by God.. Mathematics belongs to man, not to God… When a man proves a positive integer to exist, he should show how to find it. If God has mathematics of his own that needs to be done, let him do it himself”.

Such a view is of course Wrong with a capital W, for several reasons:

1. God doesn’t exist, so if we don’t do it, no one will.
2. It implicitly assumes Platonism: that when mathematicians talk about transfinite sets, they aren’t just talking about consequences of the ZFC axioms in the first place.
3. We don’t know enough about physics to know whether transfinite sets “correspond to reality” even in the naive sense that everyone always assumes in these discussions.
4. Assuming we did have this kind of knowledge, we would need to express it in the form of a formal physical theory, which would then necessarily make use of these mathematical concepts.

4. Scott Says:

Moodworves, P=NP is reducible to the halting problem with an oracle for the halting problem. To put it differently, P=NP means that there exists a Turing machine M and integers c,k such that for all SAT instances φ of size n, M decides φ after at most cnk steps. Ignoring the details, this is tantamount to saying that there exists an integer x such that for integers y, some computable predicate A(x,y) is true. Which is still a statement about integers (just like Goldbach’s Conjecture), the only difference being that now there are two quantifiers instead of one.

5. Scott Says:

komponisto, two quick responses:

1. My view is very different from the view of Bishop you quoted. Unlike him, I have no problem at all accepting nonconstructive existence proofs. (Of course constructive proofs often yield deeper insights, better algorithms, etc., but those are added bonuses.) More generally, I’d never, ever advocate throwing away interesting math to uphold a philosophical principle. I’m not talking about discarding anything we can prove; I’m talking about how to deal with statements we know we can’t prove.

2. If you think a saying like “all else is the province of God” presupposes God’s existence, you’re reading way too much into it! Think of the legal concept “act of God” (meaning “not an act of anyone you can sue”).

6. Moodworves Says:

Ah, thanks Scott!

Correct me if I’m wrong, but it seems that the second quantifier makes the P vs. NP question fundamentally different from Goldbach’s Conjecture, in that it is possible that it doesn’t affect the behavior of any computable process. Since our universe (as far as we understand it) doesn’t have any halting oracles, it could some day be relegated to Plato’s Math Heaven (where it can sit around with the Continuum Hypothesis). …That’s a strange thought considering the importance a positive or negative result would have.

7. Liron Says:

Thanks Scott, I was really wondering about what’s real and what isn’t, but now it’s obvious in retrospect.

8. csrster Says:

Scott, shh! You were on your way to a Templeton Prize nomination there for a couple of hours.

9. asdf Says:

Scott, I saw your paper about whether P=NP might be independent of ZFC. ZFC seems pretty artificial and bogus to me (powerset function, ok; iterating it through the entire transfinite list of ordinals: wtf?). And maybe that independence is unlikely.

But I wonder if anyone has considered whether P=NP might be independent of first order Peano arithmetic. I’m thinking of the graph minor theorem (a generalization of Kruskal’s tree theorem) as an example of that sort of thing. It doesn’t seem so outrageous (at least to a neophyte like me) that a theorem about an infinite set of graphs is independent of PA, since the obvious well-orderings on these graphs have order type larger than epsilon-0 which is the largest ordinal that “fits” in PA, so some inductions over those graphs may not fit in PA. And the graph minor theorem proves nonconstructively(!!) that certain problems are solvable in polynomial time.

Anyway in an earlier comment thread someone suggested it would be amusing if P=NP but the fastest algorithm for SAT was O(n^10000) or something like that. If P vs NP is independent of PA, it might be natural for the situation to be a lot worse, e.g. P=NP (provable in 2nd order arithmetic) but the fastest algorithm for SAT is O(n^B(B(k+7))) where k is the number of states of the smallest TM that solves an np-complete problem (in exponential time) and B is the (uncomputably fast-growing) busy beaver function.

Anyway the above is just raving bogosity, no real mathematical thought behind it, but if it turns out to be true, there’s probably someone out there in Platonic heaven laughing at us….

10. asdf Says:

Also I wonder if you know of Woodin’s argument that CH is false, based on infinitary logic. And Paul Cohen was not a platonist but nonetheless once said he thought CH was obviously false, because the powerset operation was so much more powerful than diagonalization.

I’ve been trying to make up a joke but all I have is the beginning, so sorry if that gets you ready to hear something funny, but the funny part doesn’t come. It begins: Kurt Godel died in 1978 and went immediately to heaven, where like all new arrivals, he was given wings and a harp and asked if he had any questions. The first thing he wanted to know was whether the continuum hypothesis is true. …

I’m not sure where to go from there. I’ve thought of a couple directions. Maybe someone can think of a suitable conclusion. I realized after a while that it’s sort of similar to a very famous joke about Wolfgang Pauli and the fine structure constant, that you all probably know.

11. asdf Says:

Darn, I wish there was a way to edit these comments. Anyway I had forgotten to ask in the first one, whether anyone had thought of what natural well-orderings there might be on P-time Turing machines and that sort of thing, and what the corresponding ordinals would be. Is that a completely bogus thing to want to know?

12. Pascal Koiran Says:

Maybe one reason why no “natural” example has been found yet is that one would have to reason outside of ZFC to obtain such an example.
Consider for instance diophantine equations. Since their solvability is Turing-undecidable (Matiyasevich) there must exist specific equations whose solvability is undecidable in ZFC (assuming of course that ZFC is consistent, or you can prove anything and its negation).
But the moment you exhibit such an equation (call it E) you know that E is, in fact, unsolvable! Indeed, simple proofs of solvability (namely, an integral solution) exist for all solvable equations.
We therefore have a proof (in ZFC) of non-solvability for E.
So the original proof that E is ZFC-undecidable must have been obtained outside of ZFC. QED

Possibly, this argument breaks down if one looks for a “natural example” which is higher up in the arithmetic hierarchy.

13. Job Says:

If P=NP, then i find it unintuitive that NPC problems would require n^c where c is very large. Why would it be n^10000 for example? All the relevant data can be scanned in n^2, so it would either be of the form 2^f(n) due to some requirement that a portion of the 2^n subsets be analyzed, or of the form n^c where c

14. Job Says:

…where c is small (~3).

15. asdf Says:

Job, if c were small it would be computable and someone would have solved the problem by now ;-). That’s what makes me chuckle over the idea that it’s enormous, uncomputably large in some parameter having to do with the problem class.

Pascal, where would something like the twin primes conjecture come in? It might be independent but the independence doesn’t imply either its truth or its falsity.

16. Andy Says:

I agree with Scott’s general message, although I think as we go higher in the arithmetic hierarchy we should be correspondingly less confident about our intuitions.

The one point I would emphasize is that in asking how ‘concrete’ or ‘physically meaningful’ a statement S is, we should look, not at its syntactic, ‘apparent’ content (cardinalities of the sets it concerns, level of existential-universal alternation, etc.), but at its ‘essential’ content: the syntactic content of the least-complex statement S’ provably equivalent to S under ZFC (though we have latitude to decide what syntactic resources count as ‘complex’), or at least the least-complex known equivalent.

Scott already affirmed this, when he described P vs NP as being reducible to a halting problem relative to a HALT oracle. A naive translation would’ve placed P vs NP one level higher in the arithmetic hierarchy (corresponding to an attempt to ‘guess’ which NP machine accepted a hard language), but Cook’s theorem allows us to remove that quantifier–we know a SAT checker is the best guess.

Similarly, research in set theory has shown that CH is provably equivalent to lower-complexity statements (i.e. ones with fewer alternations). Bill G. discussed one example: CH is equivalent to

‘there exists a coloring of the reals with countably many colors, without a monochromatic solution to x + y = w + z in distinct w, x, y, z.’

Can we even rule out that CH might be provably equivalent to a statement involving only natural numbers, albeit high in the arithmetic hierarchy?

17. Andy Says:

Bill’s discussion:

http://weblog.fortnow.com/2007/11/it-was-stupid-question-or.html

18. Scott Says:

asdf, a few responses:

1. If you go further into my survey, you’ll see that there’s a whole subfield (which Razborov, Krajicek, Pudlak, and others have been involved in) which tries to prove P=NP independent of weak fragments of PA. For example, it’s now known that Resolution and various other proof systems too weak to prove things like the Pigeonhole Principle can’t prove circuit lower bounds. Alas, these techniques are nowhere near being able to handle anything as rich as PA — and the great irony is that if they were, then we’d probably understand enough about proof complexity to be able to prove NP≠coNP (which implies P≠NP)!

2. I don’t understand Woodin’s argument for 2Aleph0=Aleph2, though I know he has such an argument. My own favorite argument for not(CH) is Freiling’s: in ZFC+CH, it’s possible to assign a countable subset S(x)⊂[0,1] to every real number x∈[0,1], so that for every (x,y) pair, either y∈S(x) or x∈S(y). That seems incredibly counterintuitive: how could a set that’s countable for every x possibly be “dense” enough that the union of it with its flipped version would cover the entire unit square? Whereas in ZFC+not(CH) this isn’t possible. (See Lecture 2 of the Democritus series.)

3. Like ZFC, your joke about Gödel has multiple consistent extensions. Maybe he ends up starving himself because he thinks God is going to poison him?

19. david Says:

Pascal, how do you draw the conclusion that “there must exist specific equations whose solvability is undecidable in ZFC” from “solving diophantine equations is undecidable”? This only means that there is no general algorithm to solve the question, but any specific equation may be proven not to have any solutions in ZFC, only that the same proof method won’t work for all of them.

20. david Says:

Ok I get it, we can enumarate all statements provable in ZFC and see if one of these says that equation has no solution.

21. Scott Says:

I removed the word “Let” from the sentence “Let Man and Woman deal with the integers…”, just to eliminate a whiff of prescriptive dogmatism.

22. Pascal Koiran Says:

>Ok I get it, we can enumarate all statements provable
>in ZFC and see if one of these says that equation
> has no solution.

That’s correct.

23. david Says:

Anyway it is true that we can exhibit specific equations whose solvability is unprovable in ZFC, once we fix encodings.

We can write a program P which, given a diophantine equation E, enumerates all proofs in ZFC and checks if one of them gives a solution of E, or proves there is none, and if so, outputs the answer.
We want to find an E such that P(E) never halts (which implies E is unsolvable). But the proof of non-computability of the halting problem tells us just how to do this.

Given an integer i, we can write a program Q(i) that does the following:
1. Write a diophantine equation E(i) such that E(i) has a zero if and only if the I-th Turing machine halts on input i.
2. Compute P(E(i)); if it halts, we know i does not halt on input i (this is where we use that ZFC is consistent).

Now if we let i = code of program Q, it follows that P(E(Q)) does not halt, so e(Q) is unprovable in ZFC.

So, it seems there is an algorithm to explicitly find an expression (namely E(Q)) such that E is undecidable in ZFC, and hence unsolvable.
We can also prove in ZFC that if E is solvable, there is a proof for this (compute the value of E on the purported solution).
I guess (I’m not entirely sure) inside ZFC we can carry out all these steps, but we have to assume ZFC is consistent in order to draw the conclusion that P(E(i)) halts implies Mi(i) doesn’t. Am I right?

24. Pascal Koiran Says:

David, at first glance I am happy with your argument; the only thing that worries me is that the conclusion that you reach is in contradiction with mine…
I am afraid that I don’t know enough set theory to be sure who’s right.
We need a wise, fair and knowledgable referee in this case:

25. Scott Says:

Pascal: Yes, I believe it’s possible to write down an explicit Diophantine equation that has a solution iff ZFC is inconsistent (and hence, whose solvability is independent of ZFC). This is non-obvious but should follow from the Matiyasevich/MRDP Theorem. I don’t know if that Diophantine equation will need variables in the exponents or not. Does anyone who actually knows want to enlighten us?

26. Pascal Koiran Says:

Scott, I am beginning to believe it too. The equation E would “simulate” a Turing machine that enumerates all proofs in ZFC and halts when it finds a contradiction.
So indeed, Solvable(E) is independent of ZFC (assuming that ZFC is consistent).
However, the statement E’:
Solvable(E) “ZFC inconsistent”
would presumably be provable in ZFC (because the Matiyasevich-based argument can presumably be formalized within ZFC).
So the next challenge would be to exhibit a diophantine equation E such that the associated statement E’ is independent of ZFC!

27. zzz Says:

CH just says sets are either computably enumerable |Z|, or uncomputable |R|. Never really understood what the fuss is.

28. Pascal Koiran Says:

Also I think you would not need variables in the exponents of E: Matiyasevich showed that those don’t buy you any additional power (and the conversion from these “exponential diophantine equations” to ordinary diophantine equations is effective!)

29. Pascal Koiran Says:

One last comment for tonight: in my definition of E’ an equivalence sign got eaten by wordpress.

Solvable(E) equivalent to “ZFC inconsistent”.

I have a question which I hope belongs in this thread: Suppose that T is a Turing machine and N is an input. It is possible that there is a proof that T(N) halts and perhaps there is a proof that T(N) does not halt. Of course, a formal proof assumes some collection of axioms. So, can there be a pair (T, N) which provably halts if we assume ZFC and provably does not halt if we assume ZF+notC?

Can the workings of a Turing machine depend on the axioms we assume? And if so, what could this possibly mean?

31. Joseph Hertzlinger Says:

I’ve been trying to make up a joke but all I have is the beginning, so sorry if that gets you ready to hear something funny, but the funny part doesn’t come. It begins: Kurt Godel died in 1978 and went immediately to heaven, where like all new arrivals, he was given wings and a harp and asked if he had any questions. The first thing he wanted to know was whether the continuum hypothesis is true. …

By analogy with the Pauli joke, God would hand Godel a paper with an elegant philosophical argument answering the Continuum Question. Godel would leaf through it, point to page epsilon 0, and say “There’s a mistake right over here…”

32. asdf Says:

Sam Nead, I think there is a TM like you are asking for. Someone more knowledgeable should confirm/unconfirm this, but I believe that the MRDP theorem implies that one can construct a diophantine equation system that has a solution (set of integers) iff AC is true. So the TM would just start enumerating sets of integers and checking whether they were a solution to that diophantine system, halting if a solution is fonud.

33. Scott Says:

Sam and asdf: No, a given Turing machine either halts or doesn’t halt; it makes no difference what axioms you assume! This is an absolutely crucial point, and is a huge part of what I was trying to get across in this post.

You might ask, what makes me so sure? Well, suppose you want to believe that a given Turing machine M has “indeterminate” behavior — i.e., that there’s no objective fact about whether M halts or not, separate from what can be proved about the question in various formal systems like ZFC. Then why on earth would you suppose there’s an objective fact about whether ZFC proves M halts? After all, the existence of a proof just corresponds to the halting of another Turing machine. So you see that there’s an infinite regress: if the question “does M halt?” is meaningless in the absence of a proof one way or the other, then question “is there a proof?” is equally meaningless.

Let’s consider two concrete examples:

1. A Turing machine that searches for inconsistencies in ZFC will run forever, assuming ZFC is consistent. Of course ZFC can’t prove it runs forever, but that’s just because ZFC is consistent (i.e., because it does run forever)!

2. On the other hand, I now claim that assuming ZF+Con(ZF) is consistent, there’s no Turing machine that can be proved in ZF to halt iff AC is true.

Proof: Suppose such a machine M existed. Then

ZF |= “If M halts, then AC is true.”

This implies that if M halts, then ZF proves AC. But we know from Cohen that if ZF is consistent then ZF doesn’t prove AC. Hence M doesn’t halt.

Now, the whole argument above can be formalized in the system ZF+Con(ZF). Hence ZF+Con(ZF) proves that M doesn’t halt. This means that ZF+Con(ZF) proves not(AC). But we know that ZF+Con(ZF) doesn’t prove not(AC), assuming ZF+Con(ZF) is consistent. (I can’t remember who showed this, but it follows from the fact that large cardinal axioms don’t decide AC.) So M can’t exist, QED.

(Question for experts: can one weaken the assumption in the above result, from ZF+Con(ZF) is consistent to ZF is consistent?)

So asdf: no, the MRDP theorem can’t possibly yield a diophantine system that has a solution iff AC is true. What you might have been thinking is this: the MRDP theorem does yield a diophantine system that has a solution iff ZF proves AC. But that’s a different question, and assuming ZF is consistent we know the answer to it (no) — hence the diophantine system in question simply won’t have a solution.

34. asdf Says:

Scott, doh, thanks, that was a good explanation of my silly error. What I was actually thinking may have been somewhat different:

Is there a Turing machine T such that

1) T halts on every input
2) That T halts on every input is provable in ZFC, but it is not provable in ZF in the absence of AC.

I believe the answer to the above is yes.

35. wolfgang Says:

> So, can there be a pair (T, N) which provably halts if we assume ZFC and provably does not halt if we assume ZF+notC?

Now this is a really stupid question:
What if N (the input) is simply “we assume ZFC” or “we assume ZF+notC” in whatever encoding and T (the Turing machine) simply checks if it is one or the other?

36. wolfgang Says:

Sorry, please disregard my previous comment, it makes no sense.

37. Jack in Danville Says:

I get it! There are only enumerably transfinite quantities in the physical world. That’s a profound statement. It follows there are ultimate Planckian units of time and volume, the points of the physical world; and geodesics have a dimension orthogonal to the dimension of direction.

38. Gil Kalai Says:

“For mathematicians, this distinction between “CH-like questions” and “Goldbach/Riemann/Pvs.NP-like questions” is a cringingly obvious one, probably even too obvious to point out. But I’ve seen so many people argue about Platonism versus formalism as if this distinction didn’t exist — as if one can’t be a Platonist about integers but a formalist about transfinite sets — that I think it’s worth hammering home.”

I must admit that I do not see this distinction as obvious or clear, in fact, I do not see it. I am not sure it is meaningful for practicing mathematics. For both kinds of questions some intuition emerges and occasionally the intuition is incorrect.

39. Scott Says:

It follows there are ultimate Planckian units of time and volume, the points of the physical world; and geodesics have a dimension orthogonal to the dimension of direction.

Huh? I don’t understand what you’re talking about (what’s the “dimension of direction”?). I was only arguing for an implication in the other direction: it follows from the fact that we’re finite creatures who can only ever engage in finite chains of reasoning (and in particular, from the Church-Turing Thesis), that CH can have no effect on us separate from its provability.

40. Scott Says:

Is there a Turing machine T such that

1) T halts on every input
2) That T halts on every input is provable in ZFC, but it is not provable in ZF in the absence of AC.

Interesting question! I’m pretty sure a generalization of the argument from my previous comment would rule this out. I just landed in Seattle and am way too tired to think, but let me get back to you about it later (unless someone wants to beat me to the punch).

41. asdf Says:

Joseph Hetzinger, I like your conclusion of the joke. Maybe Woodin’s argument could even be incorporated into it somehow.

Gil and Scott, I thought the difference between a Goldbach-type question and a CH type question was the number of alternating quantifiers. That would make the twin prime conjecture (that there are infinitely many p such that p and p+2 are both prime) a CH-type question: it doesn’t involve any uncountable sets, but it is not necessarily decidable by a Turing machine as either true or false.

Re being a platonist about the integers but a formalist about transfinite sets: well, what are the integers anyway? They are described (up to isomorphism) by the Peano axioms in second-order logic, but believing those axioms would impute some kind of existence to every subset of the integers, and there are uncountably many such subsets…

42. Scott Says:

asdf: No, the difference between “Goldbach-type questions” and “CH-type questions” has nothing to do with the number of quantifiers. The difference is that in the one case the quantifiers range over integers, while in the other they range over transfinite sets.

And no, I don’t agree that the Peano axioms “impute some kind of existence” to every subset of integers. After all, the key point about PA is that it only involves quantification over integers, and not over sets of integers.

43. asdf Says:

Arggh, I misspelled Joseph Hertzlinger’s name above, I was thinking of someone else after scrolling down. My apologies.

Scott, I don’t see how to convert your argument about ZF vs ZFC into one where we’re only discussing provability of whether the machine halts. But, I’m not very good at this subject, as you can surely tell.

BTW, here is an interesting article by Doron Zeilberger, who doesn’t believe in any infinite sets of any kind, i.e. he thinks there are really only finitely many integers and there is a largest one, and shows how to develop calculus from there: pdf link.

44. asdf Says:

PA (first order Peano arithmetic) quantifies only over integers, but because of that, it has nonstandard models. Goodstein’s theorem is a fairly straightforward theorem about integers that is unprovable in PA (but provable in PA+CON(PA) if I understand it right). The classical Peano axioms contain an induction axiom which says (from Wikipedia “Peano axioms”): If K is a set such that:
* 0 is in K, and
* for every natural number n, if n is in K, then S(n) is in K,
then K contains every natural number. This is where second-order logic comes in: that axiom quantifies over all sets of integers. The result is that the Peano axioms have only one model. However, since it’s second-order logic, the completeness and compactness theorems of first-order logic don’t hold, so there are sentences about the unique model of the Peano axioms that are true but are not theorems. I don’t think we can say first-order PA describes the platonic integers, since PA has (as you put it) multiple consistent extensions.

45. cody Says:

asdf, havent you read Scott’s biggest number essay?
…Doren must have discovered that 83 is the largest integer.

46. cody Says:

i am not intimate enough with ZFC to know why we all have such confidence (faith?) in its consistency. so, as a physicist, id like to admit that lack of simultaneity is still a very non-intuitive result for me to cope with… and so my question is, why are Gödel’s incompleteness theorems so well accepted when ZFC is not provably consistent?

also, in regards to the last post, mathematicians seem to be (on average), the most demanding, least accepting of conjecture, group of individuals so far established, (if not possible, thanks Cauchy), so its hard to imagine you guys biting bullets at all. which is intended as a compliment, not criticism.

47. John Sidles Says:

I’d like to thank asdf for providing the link to Doron Zeilberger’s ultrafinitist manifesto … this essay was a lot of fun to read!

Zeilberger’s observation that “There are many ways to divide mathematics into two-culture dichotomies” was for me an especially enjoyable starting point.

Zeilberger’s essay divides mathematics into an (old-fashioned) culture of the continuous versus a (new-fangled) culture of the discrete. The essay then argues that the discrete side of the dichotomy contains all of the truth of the continuous side, with none of the bedeviling transfinite conundrums.

But is this really the case? Zeilberger’s essay notes the ubiquity of interval arithmetic in theorem-proving on the discrete side. He asserts that this arithmetic is governed by “obvious rules” … leaving the reader to assume that these rules have no philosophical depth.

But are all the implications of interval arithmetic’s seeming simple rules really obvious? Definitely not! Until quite recently, for example, it definitely was *not* obvious that computing the cube of an interval matrix is NP-hard.

Zeilberger’s essay thus confronts us with an unexpectedly difficult dichotomous choice between two mathematical paradises: Cantor’s transfinite paradise—which has the flaw that seeming truths in set-theory are undecidable—versus Zeilberger’s “ultrafinite paradise”—which the flaw that even the simplest mathematical questions have answers that are NP-hard to compute.

Since my own mathematical philosophy is unitarian, it is for me an article of faith that all mathematical paradises are fundamentally the same paradise.

It follows, therefore, that the transfinite obstruction to uniquely choosing set-theory axioms must be identical to the ultrafinite obstruction of proving P≠NP.

Having demonstrated philosophically that this transfinite / ultrafinite equivalence must exist, I will leave the details of actually proving it to mathematicians who are wiser than myself! 🙂

48. Jack in Danville Says:

Huh?

Doh! Well I thought (and bought) you were arguing there are physically no transfinite sets of cardinality greater than Aleph-null.

That would apply to points in physical space. If the collection of points in a line segment, or any finite path, cannot have a higher cardinality, I cannot see how the set can have a cardinality of merely Aleph-null, so the points in a finite path, or a finite volume of space, must be finite.

(If I haven’t already gotten into trouble, surely this is where I do.)

Finite points in finite space requires a smallest unit of space (a Planck volume?). Any path in spacetime, for instance a geodesic, would consist of a series of these teeny-tiny volumes strung together. Hence as well as having length the path would have a circumference (an additional dimension perpendicular to the dimension of length).

49. Pascal Koiran Says:

Even if there is a smallest unit of length, quantum mechanics could provide the continuous with a victory over the discrete: amplitudes are complex numbers, and I’ve never heard of a “smallest amplitude.”
Have the physicists ever proposed such a thing ?

50. Bram Cohen Says:

Scott, given that ZFC is consistent, doesn’t that mean that every diophantine equations with no solutions qualifies as one having solutions iff ZFC is inconsistent?

51. Scott Says:

Bram: What you want, and what Matiyasevich/MDRP gives you, is a Diophantine equation that can be proved in ZFC to have solutions iff ZFC is inconsistent.

52. Scott Says:

Pascal: Plenty of people have speculated about “QM with discrete amplitudes,” but no one has proposed such a theory that makes any sense. The fundamental problem is that the discrete subgroups of the unitary group all seem to be “trivial” (e.g., they don’t allow entanglement) or “unphysical” (e.g. the Clifford group).

53. Scott Says:

Well I thought (and bought) you were arguing there are physically no transfinite sets of cardinality greater than Aleph-null.

Jack: Sets are mathematical objects; I’m not even sure what it would mean for them to “physically exist.” For me the question is not what exists; it what we ever need to invoke to explain our experiences. Because we’re finite beings, who live for finite amounts of time and discriminate between observations with finite precision, all our knowledge and reasoning can be expressed as finite strings of bits. Goldbach’s Conjecture and the Riemann Hypothesis both make predictions about what the outcomes of certain operations on finite strings of bits are going to be, whereas CH makes no such prediction. That’s the key difference between them as I see it.

54. Scott Says:

my question is, why are Gödel’s incompleteness theorems so well accepted when ZFC is not provably consistent?

Cody: I wouldn’t say Gödel’s theorems require us to “assume” ZFC is consistent. They say either there are such-and-such limits on what ZFC can prove, or else ZFC is inconsistent — in which case it can prove anything, but who cares?

55. John Sidles Says:

Pascal: lattice gauge theory has all the ingredients you require — space is discrete, the values of the gauge fields are (or can be chosen to be) discrete too, and the resulting theory is well-posed mathematically, efficient algorithmically, and can be directly linked to experiment.

This article by Kenneth Wilson is a wonderful account of how all these ideas were worked-out.

From a fundamental physics point of view, however, this discretizing leads nowhere — by design! — because the whole point is to devise a lattice theory such that the discreteness parameter disappears from the final predictions.

This is yet another example of the ubiquity of “duality” in physics and mathematics … in which the main point of Discipline “A” commonly appears as a small parameter or unwanted side-effect of Discipline “B”.

My own interest in the Continuum Hypothesis chiefly resides in trying to guess what other problems it might be dual to. I am a little bit surprised that no one else is posting about this point of view!

56. komponisto Says:

Scott:

Goldbach’s Conjecture and the Riemann Hypothesis both make predictions about what the outcomes of certain operations on finite strings of bits are going to be, whereas CH makes no such prediction. That’s the key difference between them as I see it.

But if you’re a formalist, to ask about CH is just to ask whether there is a proof of CH in ZFC — and then we’re right back in Turing Machine Land.

So my question for you, Scott, is: why aren’t you a formalist?

57. asdf Says:

A formalist might believe that ZFC is not the best formalization of set theory for doing math in. They might prefer some other axioms instead. And then the question of whether CH is a theorem is back in play.

58. Scott Says:

komponisto: I’m reluctant to buy into any sort of -ism without being sure of what I’m getting. So for example, could a formalist believe P≠NP, even supposing the question were proved independent of ZFC? If not, then I am not a formalist.

59. komponisto Says:

Along the lines of asdf’s comment, I suspect that if the P vs. NP question were to be proved independent of ZFC, there would be a movement to revisit ZFC’s status as the “official” axiom system of mathematics. (Indeed, there was/is such a movement with CH, but it hasn’t really taken off, I suppose because CH is not seen as a particularly urgent question by the larger mathematical community.)

Like Platonists, formalists can have preferences among axiom systems; the difference is that formalists don’t attribute “incorrectness” to the systems they’re less interested in.

60. John Sidles Says:

Komponisto, please correct me if I’m wrong, but if the P vs. NP question were proved to be independent of ZFC, wouldn’t that immediately imply P≠NP?

On the following grounds. One proof that P = NP would be a concrete algorithm in P that solved NP-complete problems. So if P≠NP is independent of ZFC, then no such proof exists, and hence, no such algorithm exists.

Probably this point is already clear to most people … or else my own understanding of this implication is simply wrong.

61. komponisto Says:

John: My understanding from reading Scott’s paper on this topic is that there might be such an algorithm, but it might be impossible to prove that it works.

By the way, I thought your earlier comment was right on the mark.

62. komponisto Says:

Let’s try that second link again.

63. asdf Says:

CH used to be an urgent issue. It stopped being urgent when Cohen proved its independence.

I don’t think it’s possible to prove P!=NP is independent of ZFC. I.e. it might be independent, but (within ZFC) there can be no proof of this. The reason is that P!=NP is a statement about the standard integers, and these are the same in every model of ZFC, unlike the situation with CH. Maybe Scott’s article says more about this. I should re-read it now that I know a little bit more logic than I did the last time.

64. asdf Says:

No wait, what I said above makes no sense. If the standard integers are the same in every model of ZFC, then obviously a first-order statement about them can’t be independent. Can somebody straighten me out?

65. Scott Says:

Live from STOC 2008:

asdf: It’s perfectly conceivable (even if astronomically unlikely) that P≠NP could be proved independent of ZFC, despite being about standard integers. Consis(ZFC) is also about standard integers, but we know it’s independent of ZFC.

John: If Goldbach’s Conjecture were proved independent of ZFC, that would immediately imply Goldbach’s Conjecture. However, the same is not true for P≠NP. The difference is that if Goldbach is false, then there’s necessarily a proof it’s false; but if P=NP, then there’s not necessarily a proof (as komponisto says, there could be a polytime algorithm for SAT, but no way to prove its efficiency or correctness).

66. Job Says:

If “is P!=NP?” is a particular instance of a problem L and “is P=NP?” is an instance of a problem L’, then would L be in NP? What about L’?

Formally i don’t know what L’s input is, but it seems plausible that given a proof that P!=NP, it can be quickly verified. Is that probably the case?

67. Job Says:

In more detail, to avoid asking a blurry question, suppose L is the problem:
Given two complexity classes A and B, are they different?

And L’ would be the complement.

68. Scott Says:

Job, “complexity class” is itself a blurry notion.

69. John Sidles Says:

Konponisto and Scott, thank you both for your clarifying replies, which helped my understanding a lot … Scott’s survey article was a very great help too. Tricky stuff, this set theory!

70. mitchell porter Says:

Scott: can you imagine a “physical process” whose outcome could depend on whether there’s a set larger than the set of integers but smaller than the set of real numbers?

Naively it seems possible that the subset structure of the continuum might have ‘detectable’ implications for real analysis, and hence for continuum-based physics. I’d ask the gurus of FOM, such as Harvey Friedman, some of whom have worked on the practical implications of large cardinal axioms.

71. Walt Says:

As far as I understand your argument, Scott, it advances two basic claims. The first claim is that there exist statements whose truth has no impact on what theorems are true about integers and Turing machines. It’s not obvious that this is true. Fortunately, it really is true, and the Continuum Hypothesis is an example. Forcing cannot change the truth of any statement about the integers, so any statement proven independent by forcing cannot have any consequences for the integers. But this is only one of the two main ways to prove statements independent of ZFC. The other main way is to prove that the statement implies the consistency of ZFC, which means such a statement makes predictions about integers as well as the reals. The types of things Woodin talks about are of this type.

The other claim is that there are no physical processes that can’t be modelled as Turing machines. I have to admit everything I know about this claim I learned from your blog, but my sense is that has the statement of a plausible conjecture, rather than an established fact.

72. JerboaKolinowski Says:

Hi Scott,

I think I can imagine a physical process whose outcome depended on the existence of a set larger than the integers but smaller than the reals. However, my admitted lack of mathematical sophistication may make this easier for me than for some!

In my limited understanding, the independence of CH from ZFC means that in speaking of the “existence” such a set we must be using the word “existence” as a gloss for “existence under some set of axioms which is not ZFC”, and so my imagined physical process depends on there being some interesting set of axioms under which we are prepared to say that there either is or is not a set greater than the integers and less than the reals.

The physical process I imagine, then, is just some mathematician writing down a proof under this as-yet-undreamed-of axiom set, where the (non)existence of the set in question is a result or dependency of the proof (or, if you like, a machine check of this proof). Because I am a mathematical unsophisticate, I don’t have to try very hard to imagine this. In particular, I don’t feel the need to specify the axiom set – I just imagine the mathematician in the act of writing and leave the details to her 😉

In this respect, the “existence” of the set seems in a position no different from the “existence” of other mathematical objects: it “exists” in the same way we would say that the solution to a problem “exists”. Naturally some problems (or axiom sets) seem more important or fundamental to us than others, and in those cases we’re more tempted towards a platonic viewpoint, perhaps.

73. david Says:

Sidles: Even if a proof that P=NP gives a concrete algorithm in P to solve SAT, this doesn’t mean that it is provable in ZFC that it runs in polynomial time.
So the question may be independent of ZFC and still this need not imply that P=NP.

74. John Sidles Says:

Thank you David .. and more generally, many thanks to *everyone* who is contributing to this very enjoyable topic … I’ve learned a lot, and I’m sure many other folks have too. Again, I especially commend Scott’s survey Is P Versus NP Formally Independent? as a starting point for further reading.

75. John Sidles Says:

Folks following this thread might enjoy reading the numerous good research ideas on the wiki Vision Nuggets for Theoretical Computer Science.

Included on the wiki are Scott’s nugget entitled Efficient computation in the physical world (?) and Avi Wigderson’s nugget entitled P != NP as a law of nature.

76. Raoul Ohio Says:

There are about 37k Google hits for “joke about Wolfgang Pauli and the fine structure constant” (Turns out I remember it). Is this a great universe, or what?

77. RM Says:

But can you imagine a “physical process” whose outcome could depend on whether there’s a set larger than the set of integers but smaller than the set of real numbers? If so, what would it look like?

Well, venturing into wild speculation here, such a process might look something like the Casimir Effect. Imagine a similar phenomenon (which I’ll call the Rimisac Effect just to make it clear that I am not claiming that the Casimir Effect forces us to believe the continuum exists, and to allow me to bend to physics a bit) in which two plates in empty space are drawn together by something akin to vacuum modes. There are an infinite number of such modes both between the plates and outside them, but the infinity within is countable while the infinity without is uncountable.

Now suppose we know from experiments with exciting modes that these modes are energetically degenerate: the energy density of a cavity doesn’t depend on which modes are excitied, only on the number of excitations, and our theory says that this fact should carry over to the vacuum limit (no excitations). Thus we find that the energy density in any countably infinite set of vacuum modes is the same, but less than it would be for an uncountable set. Add in some theorem that no discrete model of the universe (satisfying some reasonable constraints) can give rise to uncountably infite modes outside the plates, and the Rimisac experiment may well give an empirical measurement of whether the continuum “exists” in this universe.

As for the Continuum Hypothesis, let us imagine that we can modify the Rimisac experiment with some sort of metacavity structure that sets the countable and uncountable vacua in a carefully balanced tension such that theorists predict will either result in erratic jumps between the two types or else equilibrate to an intermediate infinity if such a thing “exists”. Thus in this hypothetical scenario the Continuum Hypothesis could be equivalent to the claim that there can exist cavities with Rimisic energy densities greater than that of countable-mode cavities and less than that of the continuuous vacuum. I make no claims about the relevance to actual physics, only that this seems to be a conceptual cartoon of what it might “look like” for the CH to be relevant to the physical world.

78. Job Says:

I suppose complexity classes like P, NP, etc are undecidable languages. We can’t have a TM decide the elements of P or NP.

In addition P_k and NP_k also seem to be undecidable. P_k being the class containing languages whose TMs complete in n^k time, similarly for NP_k.

If P and NP are “probably” different, where would they start diverging at the beginning? Or maybe would P_1 = NP_1, P_2 = NP_2 but then P_3 != NP_3 and so on?

The complexity classes P_(ksb) and NP_(ksb) would be decidable. These being the classes containing languages whose TMs complete in n^k time on inputs less than s in length and where the TM definition takes no more than b bits. If P_(ksb) is not equal to NP_(ksb) for some given values of k, s and b, then does this imply that P != NP?

If P != NP, then must there be values of k, s and b such that P_(ksb) and NP_(ksb) are different? In other words, can a brute force attempt at settling P vs NP succeed?

79. Job Says:

I apologize in advance if the above makes no sense, sometimes i write things without thinking them through and usually regret it.

80. Jonathan Vos Post Says:

RM’s “Rimisac Effect” is clever but does not, I think, answer the question.

Because of particle-wave duality and Bohr’s principle of complementarity, the wave description of Casimir effect is dual to a photon description. I have not seen a good theoretical nor experimental description of photons with infinitesimal energy, for either of several definitions of infinitesimal.

Note that Cantor did believe that his hierarchy of infinity applied to an atomistic model of physical reality, and he said that the mind (or soul) was made of infinitesimal particles of a higher order of infinity than the particles of matter. But he never said how this could be tested, and nobody believed him.

81. Walt Says:

I just read Scott’s survey, and it is good. It also makes me realize 80 percent of my comment was superfluous…

82. Yury Says:

can one weaken the assumption in the above result, from ZF+Con(ZF) is consistent to ZF is consistent?

Yes, it suffices to assume that ZF is consistent.

The truth value of the formula “M halts” depends only on the set of natural numbers, \omega, in the model. If two models have the same natural numbers then either M halts in both models, or M halts in neither of them (that is, “M halts” is an absolute formula). In particular, “M halts” relativized to the constructible universe L is true if and only if “M halts” is true in V.

Now we choose a model T of ZF in which AC is false, we get that
T |= AC is false, T |= AC^L is true
If ZF implied that “AC holds iff M halts”, then we would get that
T |= M doesn’t halt
T |= (M halts)^L

In general, when we prove independence results by forcing or by considering L, we don’t change truth values of arithmetic formulas.

83. Darran Says:

This is the first time I’ve heard somebody else say this, but it’s kind of what I’ve always thought as well. That is to say I think questions like P=NP and the Riemann hypothesis have real answers “out there in the heavens above”. However I’m a formalist about stuff like the Continuum hypothesis.

Things like the Continuum hypothesis have always struck me as artefacts of the language of set theory. Sets are such a basic concept that they’re approaching the point of concepts left undefined and can easily lead to self-contradiction if they aren’t limited in their scope. However if you limited them too much they don’t really correspond to our intuitive understanding of a set. Hence we end up with axioms like ZFC which are purposefully vague about exactly when something is a set. Which leads to a question like CH having no answer since it asks how many subsets of the Naturals there are. Definitely something you can’t answer if you haven’t said exactly what a set is.
Hence CH seems to be a language thing.

Constrast this with P=NP or Cauchy’s integral theorem, very definite statements about well defined objects.

84. Job Says:

Scott, if i’m getting annoying let me know and i’ll stop spamming but i have a question on a variant of P vs NP, namely:

Is P “exactly” equal to NP?
In other words, given that a solution to problem P can be verified in exactly n^k time and g(n) space, can it also be solved in exactly n^k time and g(n) space?

Do we know the answer to this already? I was thinking about that question and the following problem doesn’t seem to be verifiable as quickly as it is solvable:

Given an array of n numbers, identify a sequence of n or less steps that can sort the array.

It requires at least nlogn operations to solve but can be verified in linear time, isn’t that right? But this isn’t a yes/no problem anyway. Do we know that P isn’t “exactly” equal to NP?

85. Scott Says:

Job, that’s actually an excellent question, and it turns out that we do know the answer to it. Paul, Pippenger, Szemeredi and Trotter showed in 1983 that DTIME(n)≠NTIME(n); that is, there are problems solvable in nondeterministic linear time but not deterministic linear time, on reasonable models such as multi-tape Turing machines. (Their lower bound on the deterministic time needed to solve these problems is n times an extremely slow-growing function of n, basically iterated log.)

However, with all such results you need to be careful in defining the model. Regarding your sorting example, there are several issues:

(1) Even verifying a sort will require n*log(n) time, if we measure time by the number of bit operations. This is because, if each number in the array has at least n possible values (as is needed for the n*log(n) lower bound to hold), then the numbers will take log(n) bits each to specify, hence even reading them all will take n*log(n) time.

(2) If we instead adopt the comparison model (where the only allowed operation is to compare two numbers, but each comparison takes unit time), then if we’re going to be consistent and apply the same rules to the witness, it again will take n*log(n) time to verify a sort (by a generalization of the standard proof that sorting takes n*log(n) time in the comparison model).

(3) If we consider more powerful models — which involve “unit-cost comparisons” but also bit operations — then the n*log(n) lower bound for sorting breaks down (in many such models it’s actually known to be false).

So, I don’t know whether there’s any reasonable model for which sorting yields a separation between DTIME(n) and NTIME(n).

86. Job Says:

How cool, that’s really interesting.

87. sirix Says:

Scott, I generally agree with your article. However, today I’ve learned about Whitehead Problem (see wikipedia). I am stunned that it is undecidable.

I’m not saying that it contradicts your logic or anything, but still, I’m stunned, and it does change my thinking about set theory and stuff a bit.

88. Joe Shipman Says:

No arithmetical statement can depend on CH, but the ontology of fundamental physical theories involves sets that are not only uncountable, but several levels of infinity up from the integers. Itamar Pitowsky showed that the EPR paradox could be resolved if a certain kind of nonmeasurable set exists, which allows the physical weirdness to be explained by a Banach-Tarski-like mathematical weirdness; his model (later elaborated by Stanley Gudder) involved iterated integrals of (necessarily nonmeasurable) functions giving different answers with the order of integration corresponding to the order noncommuting observables were measured. Pitowsky and Gudder USED CH to build their models.

In my thesis (“Cardinal Conditions for Strong Fubini Theorems”, October 1990 Transactions of the AMS) I showed that some such trans-ZFC assumption was necessary, because it is consistent with ZFC that iterated integrals (for non-negative functions to avoid trivial counterexamples) always match when they exist.

My favorite candidate for an axiom that settles CH is the existence of a countably additive measure on ALL (not just the measurable) subsets of the reals. This axiom (known as RVM for “real-valued measurable cardinal”) is equiconsistent with a measurable cardinal, entails the continuum being very large (having many “weakly inaccessible cardinals” below it), and has a certain intuitive plausibility. (It also implies the strong Fubini theorems I alluded to above — iterated integrals must agree when they exist.)

The Banach-Tarski phenomenon shows that such a measure could not be rotationally invariant. But a possible alternative history for physics could have had Riemann not die young and discover General Relativity quite early, before the quantum theory destroyed the intuition of continuous space.

In this alternate timeline, Banach-Tarski might been discovered shortly thereafter and the assumption that was sacrificed as unphysical could have been the isotropy of space rather than its continuity, since General Relativity already requires anisotropy and assumes continuity, and so RVM could have come to be accepted as an axiom. By the time quantum mechanics had been discovered, RVM would have been shown so fruitful (it proves Con(ZFC) for example!) that it would be retained as a mathematical axiom and CH would be considered settled.

89. Scott Says:

Yury #82: Thanks very much for sharing! If I’m not mistaken, your argument should also answer in the negative the question from comment #40 (which I just realized I never answered).

90. John Sidles Says:

Joe Shipman sez: “The Banach-Tarski phenomenon shows …”

Joe, have you ever read White Light? It’s one of the very few quasi-comedic novels ever written about the CF … which is what earned it a place in our UW QSE Group’s library of subversive literature.

Perhaps I’ll transcribe some excerpts from White Light in the next few days … it includes quite a few quotations from Cantor’s own writings on the physical and meta-physical implications of CH.

91. Yury Says:

Scott, yes, the argument also gives a negative answer to the question in post #40.