From: "Jeffrey Ketland" Subject: Re: CH and second order set theory Date: Tue, 24 Jul 2001 18:35:42 +0100 Newsgroups: sci.math,sci.logic Summary: Do axioms of second-order set theory decide the Continuum Hypothesis? I don't have my copy of Hintikka's 1969 edited volume handy, but the short answer is no. I have not gone through the precise proofs of the following two statements, but my understanding is this: (1) CH is either *true* in all full models (of second-order Z2) or *false* in all full models. That does *not* imply there is a proof--the semantic consequence relation w.r.t. full models is not complete. (2) Forcing methods a la Cohen (but using non-full Henkin models) can be used to show that CH is independent of Z2. I.e., there is no proof of either CH or ~CH from the axioms of Z2. (I seem to recall that there's a paper by Thomas Weston on this, in 1976 or so?). Truth and proof (in a fixed formal system) are provably different concepts. -- Jeff Peter Percival wrote in message <3B5DAB70.22C652FA@cwcom.net>... >This discussion was called "Abject Surrender--Death of a Thread" and has >been renamed for the convenience of David Ullrich and myself and also >with the thought that others may wish to join it; for which reason it >has also been cross-posted to sci.logic. The question is: is there >either a proof in second order Zermelo set theory of the continuum >hypothesis (CH), or a proof in second order Zermelo set theory of >not-CH? It is my belief that Georg Kreisel claimed that there was one >or the other, though of course it is not known which. I believe that ============================================================================== From: "Jeffrey Ketland" Subject: Re: CH and second order set theory Date: Wed, 25 Jul 2001 21:28:08 +0100 Newsgroups: sci.math,sci.logic David C. Ullrich wrote in message <3b5ed61b.3106513@nntp.sprynet.com>... >On Tue, 24 Jul 2001 18:35:42 +0100, "Jeffrey Ketland" >Huh. Not knowing exactly what _that_ means I have to ask: Can it >be that whether it's true in all "full models" or false in all >of them still depends on what we're assuming about set theory? I agree that whether it's *provable* or not will depend upon the background assumptions (i.e., in the meta-theory) about sets. But I'd want to reject the idea that proof and truth are identical. >I'm almost certain I'm confused about this: In second-order >logic we quantify over sets, right? Now it seems like the sets >we quantify over must be "real sets", not just the sets in some >model of set theory. But for those of us who don't believe >that it makes any sense to talk about those real sets this is >a problem... That's exactly where the debate between realism/anti-realism about sets sets in (excuse the pun!). >I've always assumed that second-order logic was sort of embedded >in set theory; so it could be that CH is either true in all full >models or false in all full models, while it could still be that >it's true in all full models for one person and false in all >full models for another person, because the two individuals >have different universes of sets. It's all very controversial. I confess to realism---I don't see how the properties of sets depend upon us (or depend upon the theories we invent to represent them). I think of sets as rather like olives, and I think of undecided problems about sets as akin to: did Aristotle eat 13 olives on his 13th birthday? There is a fact of the matter, but it is possible we shall never determine what this fact is--or have convincing evidence one way or another. >That's what I was getting at when I suggested that CH being >determined in some semantic 2nd-order sense would still sound >to me like whether it's true or false depends on our assumptions >about set theory. It seems very likely that I'm confusing >something here - if you could locate the misconception that >would be great. I think you've located the real problem, which is non-trivial. It's the central question about the interpretation of mathematics.......I've just re-read Kreisel's paper "Informal Rigour & Completeness proofs", and his discussion of Zermelo's 1930 paper on second-order set theory, and his defence of higher-order logic. Let (K) be Kreisel's statement: (K) Either Z2 |=* CH or Z2 |=* ~CH (where Z2 is the second-order set theory Kreisel discusses and |=* is: semantic consequence relation for SOL--i.e., Tarskian semantic consequence but *restricted* to full models). If your inclination is towards formalism, then I think you should say roughly, "We can prove (K) in some suitable formal theory T. That is, we can give a formal proof of (K) from the set-theoretic axioms of T. But that does not mean that (K) is true in some further, external, ontological sense." The exact set-theoretic assumptions T needed to prove (K) are probably spelt out somewhere, maybe in Shapiro's book. -- Shapiro, S 1991: _Foundations without foundationalism: a case for SOL_ (Oxford). A realist will say (Smullyan says something like the first-part too, and I suppose set-theoretic realists, like Steel and others): "I think that CH has an objective truth value--there is a fact of the matter about the size of |R. Indeed, Kreisel's (K) is nice because it shows that this objective fact is semantically determined by Z2. We do not (yet) know what the truth value of CH is, and we cannot even use Z2 to determine the truth value (by a proof, say) because CH is independent of Z2. This latter assumes that Z2 is consistent--but it is consistent, since it is true." -- Jeff ============================================================================== From: "Jeffrey Ketland" Subject: Re: CH and second order set theory Date: Tue, 24 Jul 2001 18:44:33 +0100 Newsgroups: sci.math,sci.logic I've found the book. Peter Percival wrote... >Now I'll quote Kreisel: "... [snip] Consequently >we have (Zer |- CH) v (Zer |- not-CH)." >Actually, Kreisel uses a script Z where I have written Zer. The >turnstile has a subscript "2" and Kreisel defines "A >turnstile-with-a-subscript-2 B" to mean "B is a consequence of the >second order formula A". Could that be _semantic_ consequence, usually >symbolized |= ? If yes then I withdraw my claim. Claro!!!! Kreisel's subscripted turnstile |- _{2} means second-order consequence (as Kreisel himself says in the very next two paragraphs!). -- Jeff ============================================================================== From: "Jeffrey Ketland" Subject: Re: CH and second order set theory Date: Tue, 24 Jul 2001 19:44:45 +0100 Newsgroups: sci.math,sci.logic I found the references for what Weston wrote too. --Weston, Thomas 1976: "Kreisel, the Continuum Hypothesis and Second-Order Set Theory", J. Phil Logic 5, 281-298. --Weston, Thomas 1977: "The Continuum Hypothesis is Independent of Second-Order Set Theory", Notre Dame J. of Formal Logic 18, 499-503. The forcing methods were first applied in, --Chuaqui, R. 1972: "Forcing for the Impredicative Theory of Classes", J. Symb. Logic 37, 1-18. See brief discussion: --Shapiro, S. 1991: _Foundations w/o foundationalism_ (paperback edition 2000), p. 105. Best -- Jeff