- (Mathematical Realism or Platonist) There IS a model of the reals that is the RIGHT one.In that model CH is either true of false. ZFC just isn't up to the task of figuring it out.Paul Cohen thought that there were an INFINITE number of cardinalities between N and R.I've heard rumors that Kurt Godel thought there was exactly ONE cardinality between N and R.Hugh Woodin has some mathematical reasons to think there is exactly ONE:CHone CHtwo. Many people prefer the simplicity of having NONE---the infinity after N is R. Some people think that we need to add new axioms to ZFC such as Large Cardinals or the Axiom of Determinacy to settle the question. Are these really candidates for axioms?That may be a later post.
- (Not sure what these people are called.) Since ZFC settles virtually everything else in mathbut not this question, CH has no answer. There is No `correct' copy of the reals.The weakness in this response may be the virtually. Are there questions in math that need it? Are there such questions outside of Set Theory? That may be a later post.
Monday, April 02, 2007
What to make of the Ind of CH ?
Dave Barrington suggested I blog about Paul Cohen since he just died.
Scotts Blog already reported on Paul Cohen's
death, and there were many comments on C* algebras and PAC learning
(none of which Paul Cohen worked on).
Paul Cohen's most important result was that CH is independent of ZFC.
What does this mean and what do we make of it?
CH is the statement there is no cardinality strictly between N and R
ZFC is Zermelo-Frankl Set Theory (with the Axiom of Choice).
Virtually all of Math can be derived from these axioms.
(There are quibbles about this which might be a latter blog.)
Kurt Godel showed that there is a model of ZFC where CH is TRUE.
Paul Cohen showed that there is a model of ZFC where CH is FALSE.
Together we have that CH is INDEPENDENT OF ZFC.
What to make of this? Here are opinions I have heard over the years:
Subscribe to:
Post Comments (Atom)
For people already familiar with ZFC and Choice, the absolute best introduction to "What additional axioms should we use?" and "What's at Stake?" is Shelah's "Logical Dreams" paper. Spoiler: he disagrees strongly with Woodin.
ReplyDeleteIt should be noted that Both Godel's and Cohen's results are relative consistency results.
ReplyDeleteGodel prove that if ZF has a model than ZFC + CH has a model.
Cohen proved that if ZF has a model that ZFC + not CH has a model. (He also proved ZF + not choice has a model).
Godel's Second Incompleteness Theorem says that this is the best you can get unless ZF is actually inconsistent.
I think two camps in phil of math would accept (2), or at least a variation of it: fictionalists and intuitionists. Fictionalists think that asking these questions (or any mathematical questions) about the reals is like asking questions about a fictional story. Some have a "real" answer, e.g. was Huck Finn male or female (it is *true* that he
ReplyDeleteis a male, according to the story) but others are simply beyond the scope of the story ("what did Huck Finn have for breakfast the day before he met Tom?"). In my opinion, the debate is pretty boring if we consider mathematical statements
like CH. It's much more interesting when the statements are used as part of a mathematical theory about empirical phenomena in the world (like physics)... Hartry Field does a lot with this.
A fun quote from Michael Dummett:
"We are, after all, being asked to choose between two metaphors, two pictures. The platonist metaphor assimilates mathematical enquiry to the investigations of the astronomer: mathematical structures, like galaxies, exists, independently of us, in a realm of reality which do not inhabit but which those of us who have the skill are capable of observing and reporting on. The constructivist metaphor assimilates mathematical activity to that of the artificer fashioning objects in accordance with the creative power of his imagination. ...the activities if the mathematician seem strinkingly unlike those either of the astronomer or of the artist. What basis can exist for deciding which metaphor is to be preferred?...We have first to decide on the correct model of meaning - either an intuitionistic one...or a platonistic one...and then one or other picture of the metaphysical character of mathematical reality will force itself on us."
Harvey Friedman showed that there are fairly basic mathematical statements that are not decided in ZFC.
ReplyDeleteWell, if no one else is going to state the obvious, I guess I will: some people have suggested that P vs. NP is independent of ZFC. A couple of them have evidently even gone so far as to prove it.
ReplyDeleteMy advisor, Carl Jockusch Jr., told me that Paul Cohen himself believed that the CH fails badly--that there are unimaginably many infinities between aleph_0 and 2^{aleph_0}.
ReplyDeleteFor what it's worth, I believe this too.
Zermelo "observed" his axioms of Set Theory as properties of his mental model of the cumulative hierarchy of sets. It turns out that these axioms are pretty much what you need to prove the validity of definition by transfinite induction, and I don't believe this is an accident. [The exceptional axiom, as usual, is foundation, but this easy to observe -- the witness for a given non-empty set is just an element of minimal rank, and therefore foundation is essentially the hypothesis with the Zermelo model that the ordinals are well ordered.]
Frankel's axiom of regularity came afterwards, and it was clearly informed by the notion that setness vs. proper classness is a matter of size -- i.e., if a class can be put into 1-1 correspondence with a set, then it is "small," and therefore gets to be a set too. This, too, is observable in Zermelo's model, as long as you assume that the ordinals don't have a small (set-like) cofinality.
Note that Frankel's intuition is radically different here that Zermelo's -- you get to be a Frankel set by being "small," whereas you get to be a Zermelo set by being "finished." It is more startling that people seem to realize that such different views about "what makes a set" seem to be consistent with one another.
From a Continuum Hypothesis point of view, ZF says less than it should about the power set operator. Remember, each successor level of the Cumulative Hierarchy consists of the power set of the preceding level, and therefore the power set operator is absolutely central to mental construction, so this is essentially an incompleteness of the model as well as the theory. The CH is merely the assumption that power sets are small, and the standard (V=L) proof of relative consistency proof for ZF+GCH over ZF is little more than a working out of the consequences of having the smallest possible power sets.
So why do I stand with Cohen on the CH? The power set is a representation-free version of the exponential function, which enables its extension to the infinite. My experience (based admittedly on the finite) is that the exponential function grows very quickly, and there is a lot of room between successive iterates of the exponential function. I carry this intuition to the infinite, and conclude that the Continuum Hypothesis is false, and badly so.
Like all statements of finite combinatorics, P<>NP is a property of the set of integers which can be written down as a first-order formula in the language of rings (+,*,=).
ReplyDeleteWe have to figure out whether this formula is satisfied by the set of "true" integers.
If one would like to prove an independence result, it seems reasonable to start not with the all-powerful ZFC system but with some weaker system for proving properties of the integers, such as e.g. Peano arithmetic (or perhaps some even weaker system). Is there any result along those lines?
Is there any result along those lines?
ReplyDeleteYes, I think there are some results showing the independence of P != NP from considerably weak arithmetic.
I think that results of A. Razborov and Ran Raz show that "SAT has no poly-size circuits" has no small resolution proofs, which then implies an independent result on a very weak arithmetic formal system of the P!=NP problem.
Razborov has some more results on this I think. If I'm not wrong, he showed that if a plausible cryptographic assumption holds then P!=NP is independent of some weak subsystem of Peano Arithmetic (relativized S^2_2 and relativized S^1_2).
Gaisi Takeuti had also some papers from the '90s about forcing and P!=NP.
A propos of Kurt and anonymous' comments on the potential independence of P vs NP:
ReplyDeleteMiki Ajtai, who has a record on these kinds of complexity questions that is nonpareil, is among those who think it will be independent. At a DIMACS workshop in 2000 in which a number of leaders in the field gave their opinions about the resolution of open complexity questions, he conjectured that P vs NP was independent. When asked to clarify whether he meant independent of Peano arithmetic, to the surprise of many in the room he clarified that he meant independent of ZFC.
Miki Ajtai ... thinks it will be independent of ... ZFC
ReplyDeleteThat's quite amazing.
Maybe a more `feasible' question is:
Assuming P!=NP (or other computational hardness conjecture of the kind), is it true that there are no short (ZFC/PA) proofs of P!=NP?
Is a blog post on S^_2 or S^1_2 on the menu?
ReplyDeleteWell, we do have all kinds of weird crap going on... for example, the partial consistency stuff of Krajicek and Pudlak shows that if NEXP \neq coNEXP, then there are propositional tautologies that require superpolynomially large proofs in ZFC, but would have polysize proofs in some other system.
ReplyDeleteWhat that other system is not entirely clear- the natural thing to guess is that it would be ZFC + some large cardinal or determinacy stuff and that somehow yields a proof of soundness for some slick method of proving certain propositional statements. But there's no reason to suspect that, it may be that the extra-ZFC principles that help map out the subsets of the reals are totally different from ones that help us succinctly validate tautologies.
Perfesser Nine Toes
Is a blog post on S^_2 or S^1_2 on the menu?
ReplyDeleteWhat?
To #12:
ReplyDeletewhat do you mean by
propositional tautologies that require superpolynomially large proofs in ZFC?
That is, what do you mean by a proof in ZFC (or any other first order system) of a propositional tautology?
In a formalization of ZFC you can define the concepts of "propositional formula" and "propositional tautology" in a straightforward manner.
ReplyDeleteSo, I mean proof system in the Cook-Reckhow sense where you take the input formula \tau, and then convert into its encoding in your formalized ZFC. Then, using some standard first-order proof system with the axioms of set theory, you prove the sentence stating that this particular propositional formula is a tautology.
This is proof system in the Cook-Reckhow sense, provided you choose a natural polytime encoding of formulas and tautologies.
It's all in the red book.
--- Perfesser Nines Toes
What's the red book ?
ReplyDeleteI think that the main problem here is that people assume that there is a "correct" choice of axioms. People used to think the same thing about the parallel postulate, but nowadays we know that this is actually an axiom and that there are essentially different, but equally useful, kinds of geometry depending on which type of parallel axiom one chooses.
ReplyDeleteI can't see why we should treat set theory differently. Just as we have several different geometries to study we have several different kinds of set theory. All of them equally correct.
I know almost nothing about set theory, but that doesn't prevent me from having an opinion about the issue raised by klas m.
ReplyDeleteWhen we're talking about "exotic" stuff like large cardinals or CH, I would tend to agree that all set theories should be treated on an equal footing (provided that they're not downright inconsistent).
However, set theory can in principle have an impact on such "concrete" questions as the satisfiability of diophantine equations:
By Matyasevitch, we know that there must exist diophantine equations whose satisfiability is independent of ZFC (or o f your favorite alternative system).
I would argue that one set theory is better than another set theory if it proves more true statements about the satisfiability of diophantine equations (and of course does not prove any wrong statement!)
This makes sense only if you believe that that there is a "true" set of the integers, but who doesn't?
It's all in the red book
ReplyDeleteI guess you mean:
http://www.amazon.com/Arithmetic-Propositional-Encyclopedia-Mathematics-Applications/dp/0521452058/ref=sr_1_1/002-5707863-3608822?ie=UTF8&s=books&qid=1175679430&sr=1-1
I'll look it up then.
Thanks
Pascal: I am not a set theorist either, I'm in combinatorics, so I shouldn't stick my neck out too far here.
ReplyDeleteMy impression is that the integers and set theory in general are slightly different. For the integers there is at least some way of making sense of a "smallest" model for them, in terms of which objects are included in the model, and I guess that would be what most people would call the "real integers".
However for set theoretic axioms like the Axiom of Choice or CH there only seems to different models rather than some which are smaller and some which are larger. For example, if we remove AC then we can add the axiom that all sets are measurable, and we suddenly get many new theorems which are not true with AC, like all linear functions being continuous, and if we add AC we get more objects, like non-measurable sets, and fewer theorems about them.
Klas: I guess the issue is, whether by adding "exotic" set-theoretic axioms (such as e.g. CH or large cardinals axioms) you can prove more "combinatorial" results (about e.g. the satisfiability of diophantine equations) ?
ReplyDeletePascal: Do we have any concrete examples of this kind where we can say that one choice of "exotic" axiom let us gain more than another choice?
ReplyDeleteKlas: I certainly do not have such an example, but perhaps the more knwoledgeable readers of this blog can answer your question?
ReplyDeleteActually, I can cook up a stupid example: take a diophantine equation which is not satisfiable, and whose unsatisfiability is not provable in ZFC. Add its unsatisfiability as a new axiom.
The problem is that this is not a "natural" set-theoretic axiom such as CH, and moreover I can't actually show you the equation (it wouldn't fit on this blog).
Pascal: This kind of example is what I have mind when I talk about the integers having some kind of minimal model.
ReplyDeleteFor a statement of the type "these equations in k variables have no integer solutions" we can for each k-tuple of integers prove that it is not a solution, but the original statement is itself unprovable. So if we add the statement as an axiom we still have the same integers and a new axiom to prove theorems with.
However if we, for the same equations, add the axiom "these equations in k variables have an integer solution", then we have a new axiom, and since no k-tuple of ordinary integers satisfy the equations we have also stated that there exists some additional objects which we include among the integers, and they do satisfy the equations.
But for the set theoretic axioms it seems harder to talk about smaller and larger models in this way.
Here is a related question that puzzles me.
ReplyDeleteWe do not know whether ZFC is consistent, but if it is, does that imply that ZFC can only prove statements about the integers that are satisfied by the true integers?
One could imagine that ZFC is consistent, but that each model has a set of integers which, in addition to the true integers, contains "pathological" objects which make it satisfy equations that are not satisfied in the true integers.
Can that possibility be ruled out?
The most plausible candidate for settling the Continuum Hypothesis (Freiling's symmetry axiom) has the disadvantage that, when combined with the plausible assumption that any subset of the reals of cardinal less than c will have measure zero, it will imply that the continuum cannot be well ordered.
ReplyDeleteOn the other hand, why should we simultaneously believe both the Power Set Axiom and the Axiom of Choice?