O-PA, CON(ZF) and non-standard models of ZF.
in [Logic]
|
Prev: OPERATIONS AND SUPPLY MANAGEMENT 12-E JACOBS Test Bank and solution manual is available. Email me at allsolutionmanuals11[at]gmail.com if you need to buy this. All emails will be answered as soon as possible.
Next: Hemant Pandey from India Solves P vs. NP
From: Marina Gotovchits on 28 Oct 2009 09:34 On 28 Okt, 12:19, Marina Gotovchits <renessa...(a)gmail.com> wrote: > On 28 Okt, 12:09, Marina Gotovchits <renessa...(a)gmail.com> wrote: > > > Let O-PA be Peano Arithmetic extended with the omega.rule. As is well > > known, O-PA is complete, and for any aithmetically true sentence A, O- > > PA "proves" A. (Or so we think, unless we suffer from certain highly > > finitist, or ultra-predicativist, qualms, e.g. à la Leonard Nelson.) > > Sorry, I meant Edward Nelson, of course.
From: Marina Gotovchits on 29 Oct 2009 19:09 On 29 Okt, 21:40, Rupert <rupertmccal...(a)yahoo.com> wrote: > On Oct 29, 7:19 pm, Marina Gotovchits <renessa...(a)gmail.com> wrote: > > > > > > > On 29 Okt, 05:34, Rupert <rupertmccal...(a)yahoo.com> wrote: > > > > On Oct 28, 10:09 pm, Marina Gotovchits <renessa...(a)gmail.com> wrote: > > > > > Let O-PA be Peano Arithmetic extended with the omega.rule. As is well > > > > known, O-PA is complete, and for any aithmetically true sentence A, O- > > > > PA "proves" A. (Or so we think, unless we suffer from certain highly > > > > finitist, or ultra-predicativist, qualms, e.g. à la Leonard Nelson.) > > > > > Suppose ZF is consistent. It then seems that an arithmetical sentence > > > > to the effect CON(ZF) is true. So CON(ZF) should hold in O-PA. > > > > > Now, does this not mean that if ZF is consistent then there is a non- > > > > standard model of ZF in O-PA? > > > > I don't understand this. How can you do model theory in the first- > > > order language of arithmetic? > > > Is your problem that the theory is first-order? I should think not. By > > the Skolem-Löwenhem Theorem, if ZF has a model, it has a countable > > model. Now CON(ZF) should be ezpressible in arithmetic. Hence the > > question. > > > > > If right, how is the situation with regard to the 1-consistency of > > > > certain extensions of ZF. Let e.g. G be the theory ZFC + LCA, where > > > > LCA is some large cardinal axiom. If G is 1-consistent, it again seems > > > > that this can be expressed in an arithmetical sentence 1-CON(G), and > > > > since true, 1-CON(G) will hold in O-PA. Does this mean that there is a > > > > non-standard 1-consistent model of G in O-PA?- Hide quoted text - > > > - Show quoted text - > > Con(ZF) is an arithmetical sentence, yes. What you are calling O-PA is > basically true arithmetic, the set of arithmetical sentences which are > true in the standard model. And this will include Con(ZF) on the > assumption that ZF is consistent. > > But I don't understand what it means to say "there is a nonstandard > model of ZF in O-PA". That seems to mean something like "O-PA proves > that there is a nonstandard model of ZF", but the problem is that I > cannot talk about arbitrary countable models of ZF in the first-order > language of arithmetic. I can do so in the second-order language of > arithmetic. Thanks Rupert, I have, after having posed the question, come to see that it was ill posed. These matters of couse all depend upon what we mean by a "model". But it seems, and I believe uncontroverially, that this should mean something like "there is a pair <V,e> so that V contain the "sets" in the theory and e is a sub"set" of V2 so that ...... blah, blah". So I agree that we need to move somewhat upwards in the hierarcy of subsystems of second-order arithmetic to have such a countable model for ZF. My question should have been posed as folllows, perhaps: If we have the omega-rula along the climb up the hierarchy of subsystems os SOA, how far do we need to go in order to have a model of ZF if ZF is consistent? Perhaps only ACA(0)? ATR(0)? PI-1-1? Higher? I don't see any need for talking about "arbitrary" countable models of ZF here.
From: Aatu Koskensilta on 29 Oct 2009 19:28 Marina Gotovchits <renessanse(a)gmail.com> writes: > My question should have been posed as folllows, perhaps: If we have > the omega-rula along the climb up the hierarchy of subsystems os SOA, > how far do we need to go in order to have a model of ZF if ZF is > consistent? WKL-0 proves the completeness theorem, and thus in particular that if ZF is consistent it has a model. -- Aatu Koskensilta (aatu.koskensilta(a)uta.fi) "Wovon mann nicht sprechen kann, dar�ber muss man schweigen" - Ludwig Wittgenstein, Tractatus Logico-Philosophicus
From: Marina Gotovchits on 30 Oct 2009 06:41 On 30 Okt, 00:28, Aatu Koskensilta <aatu.koskensi...(a)uta.fi> wrote: > Marina Gotovchits <renessa...(a)gmail.com> writes: > > My question should have been posed as folllows, perhaps: If we have > > the omega-rula along the climb up the hierarchy of subsystems os SOA, > > how far do we need to go in order to have a model of ZF if ZF is > > consistent? > > WKL-0 proves the completeness theorem, and thus in particular that if ZF > is consistent it has a model. Aha! Thank you very much Aatu!! I recall Simpson's Theorem I.10.3.8 (page 36 of his Book), which states that WKL(0) is equivalent, over RCA (0), to "Gödel's completeness theorem: every (consistent) finite, or countable, set of sentences in the predicate calculus has a countable model. Does this mean that if ZF is consistent, then a countable model "lives in" WKL(0)+the omega rule. Or do we need to go slightly higher for the model to be representable by a "set" in a subsystem of SOA. I ask this because Gödel's completeness theorem here may be interpreted existentially relative to WKL(0). I.e.. GCT and WKL(0) are equivalent, over RCA(0), so maybe WKL(0)+ the omega rule only asserts that there IS a countable model of ZF (if ZF is consistent), without itself exhibiting such a model. If so, when does the model itself become a "set"?
From: Rupert on 30 Oct 2009 12:56
On Oct 30, 9:41 pm, Marina Gotovchits <renessa...(a)gmail.com> wrote: > On 30 Okt, 00:28, Aatu Koskensilta <aatu.koskensi...(a)uta.fi> wrote: > > > Marina Gotovchits <renessa...(a)gmail.com> writes: > > > My question should have been posed as folllows, perhaps: If we have > > > the omega-rula along the climb up the hierarchy of subsystems os SOA, > > > how far do we need to go in order to have a model of ZF if ZF is > > > consistent? > > > WKL-0 proves the completeness theorem, and thus in particular that if ZF > > is consistent it has a model. > > Aha! Thank you very much Aatu!! I recall Simpson's Theorem I.10.3.8 > (page 36 of his Book), which states that WKL(0) is equivalent, over RCA > (0), to "Gödel's completeness theorem: every (consistent) finite, or > countable, set of sentences in the predicate calculus has a countable > model. > > Does this mean that if ZF is consistent, then a countable model "lives > in" WKL(0)+the omega rule. Or do we need to go slightly higher for the > model to be representable by a "set" in a subsystem of SOA. I ask this > because Gödel's completeness theorem here may be interpreted > existentially relative to WKL(0). I.e.. GCT and WKL(0) are equivalent, > over RCA(0), so maybe WKL(0)+ the omega rule only asserts that there > IS a countable model of ZF (if ZF is consistent), without itself > exhibiting such a model. If so, when does the model itself become a > "set"? Assuming that ZF is consistent, in WKL_0+the omega rule we can prove that there exists a model of ZF. We probably can't prove that the natural numbers are standard in this model. Was that your question? |