How Can ZFC/PA do much of Math - it Can't Even Prove PA is Consistent (EASY PROOF)
in [Logic]
|
Prev: equivalence
Next: How Can ZFC/PA do much of Math - it Can't Even Prove PA is Consistent (EASY PROOF)
From: MoeBlee on 29 Jun 2010 10:55 On Jun 28, 9:07 pm, Charlie-Boo <shymath...(a)gmail.com> wrote: > On Jun 28, 12:24 pm, MoeBlee <jazzm...(a)hotmail.com> wrote: > > And it's easy enough to see that if a theory has a model then that > > theory is consistent. > > Is that an axiomatic proof in ZFC? Plain Z-regularity proves that if a theory has a model then the theory is consistent. It's quite simple; you would come up with it yourself on just a moment's reflection. > 3. If a theory has a model then that theory is consistent. > Rule of Inference: It's easy enough to see. > Ha! Don't be a jerk (especially since I'm doing you the favor of providing information you've requested). I didn't say that just saying "it's easy to see" constitutes a proof. Of course, it should be formally proven, and saying "it's easy to see" is not a proof. But, my posts are not themselves a textbook of listed proofs one after another. Just think about the matter for a moment, and indeed you should see how a formal proof would be quite simple here. MoeBlee
From: MoeBlee on 29 Jun 2010 11:02 On Jun 28, 11:18 pm, Chris Menzel <cmen...(a)remove-this.tamu.edu> wrote: > On Mon, 28 Jun 2010 15:46:25 -0700 (PDT), MoeBlee <jazzm...(a)hotmail.com> > said: > > > One thing I don't know how to do is show the mutual-interpretability > > of PA and Y=ZF-"ax inf"+"~ax inf" > > > One direction seems not too difficult: interpreting PA in Y. > > > But how do we interpret Y in PA? Specifically, how do we define 'e' in > > PA and then prove, in PA, all the axioms of Y as interpreted in the > > language of PA? > > The best known approach uses a mapping that Ackermann defined from the > hereditarily finite sets into N that takes the empty set to 0 and, > recursively, {s_1,...s_i} to 2^(n_1) + ... + 2^(n_i), where n_i codes > s_i. For numbers n and m, let nEm iff the quotient of m/2^n is odd. > The relation E is obviously definable in PA. Ackermann showed that, by > defining the membership predicate as E, the axioms of Y are all theorems > of PA. Thanks. Would you recommend a book (or site) where I can read it in all details? (Also, it occurred to me that I shouldn't have been so overconfident about the other direction (interpreting PA in Y). Does Ackermann do it also?) MoeBlee
From: Chris Menzel on 29 Jun 2010 11:10 On Tue, 29 Jun 2010 03:16:07 -0700 (PDT), Charlie-Boo <shymathguy(a)gmail.com> said: > On Jun 28, 10:17 pm, Chris Menzel <cmen...(a)remove-this.tamu.edu> > wrote: >> On Mon, 28 Jun 2010 04:56:30 -0700 (PDT), Charlie-Boo >> <shymath...(a)gmail.com> said: >> >> > On Jun 27, 6:31 pm, Chris Menzel <cmen...(a)remove-this.tamu.edu> wrote: >> >> On Sun, 27 Jun 2010 10:50:16 -0700 (PDT), Charlie-Boo >> >> <shymath...(a)gmail.com> said: >> >> >> > ... ZFC declares that there is a set that satisfies Peano's >> >> > Axioms and defines N to be that set. >> >> >> You have it completely backwards. The set is defined first, >> >> independent of any mention of PA. >> >> > So? >> >> So what you said was false. You said that ZFC defines N to be a set >> that satisfies the Peano Axioms. False. > > > So, to complete the answer to your question: N is never *defined* to > > be a set -- or, more exactly, the domain of a model -- in which the > > Peano axioms are true. That *turns out* to be the case after the > > set and corresponding model are defined. > > N is defined to be a set that meets the Peano Axioms whether they > mention PA or not. You seem to use the word "define" in a way that no one else does. > You say it "turns out" to be the case. It turns out because of the > answer to my question that you steadfastly refuse to mention: It is > done with the ZFC Axiom of Infinity, which merely says that there is a > set that models Peano's Axioms. It simply says no such thing. > ZFC Axiom of Infinty = PA Induction > > ZFC: Ex (0 e x ^ Ay e x (Y' e x) ) I guess you mean Ex ({} e x ^ Ay e x (yU{y} e x) ) You use the constant '0' and a successor symbol but they are not part of the language of ZF. Nor are the empty set and the operation yU{y} just magically identical to the number zero and the successor function, respectively. Among the things that are proved when one builds the usual model of PA, in fact, are that the empty set and the operation in question can serve in these roles. It's part of what makes the matter interesting. Note more generally that there is no mention of Peano's axioms in the axiom of infinity nor is there any reference to the *true-in* relation between sentences and models. There would have to be if the axiom actually said "that there is a set that models Peano's axioms". Why you think otherwise is curious. > PA: 0 e N > PA: Ay e N (Y' e N) So that's what you think induction is, huh? That explains a lot. > Change x in ZFC to N and you get PA. That's just how the "proof" > works. Well, you've been pointed to many references that would be very helpful to you.
From: Charlie-Boo on 29 Jun 2010 11:25 On Jun 29, 10:55 am, MoeBlee <jazzm...(a)hotmail.com> wrote: > On Jun 28, 9:07 pm, Charlie-Boo <shymath...(a)gmail.com> wrote: > > > On Jun 28, 12:24 pm, MoeBlee <jazzm...(a)hotmail.com> wrote: > > > And it's easy enough to see that if a theory has a model then that > > > theory is consistent. > > > Is that an axiomatic proof in ZFC? > > Plain Z-regularity proves that if a theory has a model then the theory > is consistent. It's quite simple; you would come up with it yourself > on just a moment's reflection. Sorry, but I don't know what proof you have in mind, so I can't determine how the Axiom of Regularity would play a role. What is the proof and how is Regularity essential? > > 3. If a theory has a model then that theory is consistent. > > Rule of Inference: It's easy enough to see. > > Ha! > > Don't be a jerk (especially since I'm doing you the favor of providing > information you've requested) Have you? C-B > > MoeBlee
From: MoeBlee on 29 Jun 2010 11:33
On Jun 29, 2:09 am, "R. Srinivasan" <sradh...(a)in.ibm.com> wrote: > On Jun 29, 3:48 am, Transfer Principle <lwal...(a)lausd.net> wrote:> On Jun 28, 9:14 am, MoeBlee <jazzm...(a)hotmail.com> wrote: > > > > On Jun 27, 10:49 pm, "R. Srinivasan" <sradh...(a)in.ibm.com> wrote: > > > > Here is one possible approach. Consider the theory F that I had > > > > defined in another post, where > > > > F = ZF - Inf + D=0, > > > > Where 0 is the null set and D is defined as > > > > D = {x: An(x not in P_n(0))} > > > I wonder why Srinivasan can't simply use the nth level of the > > cumulative hierarchy, V_n, so that we don't have to worry > > about whether P_n(0) is welldefined or not. > > Being a finitist, I do not accept that there is any such thing as a > cumulative hierarchy in the first place. There can be a doubt about > whether P_n(0) is well defined only if you admit to having a doubt > about what "finite" means in "n is finite". I do not have any such > doubts. > > > > Prove (and please state the formal language, logic, and axioms in > > > which you conduct this proof) that there exists a D such that for all > > > x, we have x in D iff An x not in P_n(0). > > > Unless you can do that, then your 'D' is not well defined. > > > OK, I see the problem here. In standard ZF, the object that Srinivasan > > calls "D" would be too large to be a set. Thus, it's not evident that > > the set D exists. > > Here you are *assuming* that D=0 is not provable in the theory ZF-Inf. > If that is the case, then indeed D can only exist as a proper class if > we add the axiom Inf to ZF-Inf. I contend that if you go ahead and add > D to the language of ZF-Inf, we have no option but to accept that D=0 > is provable in ZF-Inf. YOU'RE NOT LISTENING. Not listening to me or to Transfer Principle. We PROVE from ZF-Inf that there IS NO SUCH object that you are calling 'D'. (or at least we have not before us a proof that there IS such an object). Just adding a constant symbol 'D' and saying whategver you want about it does not override. And I SHOWED you how to accomplish your axiom without resorting to D. > But this would be controversial and there would > still be some ambiguity on whether the existence of infinite sets is > ruled out despite our forcing D=0. > > Instead, what I have done in my work is to define D as a class and > allow the proposition D=0 in a theory of finite sets F where F allows > classes in its language. So according to the classical way of > thinking, D would be a set (null set) if infinite sets do not exist > and a proper class otherwise. But "THERE ARE NO proper classes" is a theorem of Y. (Why don't you understand this?) Therefore, talk of proper classes in context of Y is merely figurative, a figure of speech, for some other actual statement in the meta-language. And in this case, you don't even NEED D. I showed you how. > But in my logic NAFL, the undecidability > of the proposition D=0 in the theory F is a contradiction, and so the > conclusion is that D=0 must be provable in F. This would genuinely > rule out the existence of infinite sets in the NAFL theory F. Whatever about "NAFL". > I do not want to allow any explicit references to infinite objects in > the language of the theory ZF-Inf. What does that MEAN? What is your technical definition of "explict reference to infinite sets in the language"? > We can and should deny the > existence of infinite sets without explicitly defining any infinite > object. Yes you can! You ALREADY did it with theory Y: ZF-"Inf'+"~Inf" That theory entails that every object is finite. And there is no definition of any infinite object possible in that theory. > Of course if we admit classes we may allow V_n as a class > without committing that it is a set. You CAN'T do that with ZF-Inf or ZF-Inf+"~Inf" or with ZF-Inf+"every set is hereditarily finite" (i.e., your "D=0") and still have a CONSISTENT theory. You have to maks some OTHER MODIFICATIONS. > > > > Here P_n(0) is power set operation iterated n times on 0, and P_0(0) = > > > > P(0), P_1(0)=P(P(0)), etc. Clearly only hereditarily finite sets can > > > > exist in models of F. > > > Prove it. > > > OK, I see the problem here. Even if F has a model in which every set > > is > > HF, there might be non-isomorphic models of F with sets which aren't > > HF at all. > > Again this is subject to the assumption that such models are > permitted. > > > Still, I believe that Srinivasan is on his way to giving a theory that > > will satisfy most finitists. > > I believe that the logic NAFL is the ideal platform for launching such > a theory F and not classical logic. In NAFL, we accept a meta-proof > that the theory F proves 'D=0' and since F admits the notion of proper > classes, this forces the non-existence of infinite sets in any model > of F. > > Let me now address the huge disconnect between me and someone like > MoeBlee, who accepts classical logic. What does "accepts classical logic" mean? I am happy to work in classical logic. And I am happy to investigate and work in other (COHERENTLY STATED) logics. I don't claim that all mathematics MUST be based in classical logic. > This is well illustrated in this > discussion of the theory Y=ZF-Inf+~Inf (or the equivalent that rules > out the existence of any sets other than the hereditarily finite > ones). > > It is very clear to me that MoeBlee would only accept an argument for > the inconsistency of PA that first *presumes* the existence of > infinite sets, PA is an infinite set. If there are no infinite sets, then there is no object as we describe 'PA' to denote. That is hardly a strict adherence only to classical logic. Moreover, YOU were the one who said you were going to demonstrate something in theory Y. And theory Y happens to be in classical logic. So YOU chose classical logic as the context. If you wish to have another theory with the axioms of Y but in another logic, then just specify that logic (and please do so in a manner that there it is an algorithm to determine whether a given object is or is not a proof). > defines the theory "PA" as an infinite object in terms > of infinite sets and then attempts to prove "PA is inconsistent" by > ruling out the existence of models for PA. What? WHO is supposed to be doing such a proof? > But this is hopelessly > circular, and any such "proof" is meaningless, for it would > immediately be declared as a proof of a "false" statement in view of > our having accepted the "true" existence of infinite sets in the first > place. If this is "rigor", I do not want any part of it. This is where > I get off the bus, and this is where someone like MoeBlee gets in. I never got on any such "bus". I never gave nor implied the argument you gave above. > Instead, take a look at the theory Y. It does NOT define any explicit > infinite object. Indeed, I would restrict the language of Y to ban > *any* explicit reference to infinite sets, What does that MEAN? Please provide your exact technical definition of "ban explicit reference to infinite sets". Then please show such a language in which there is an algorithm to determine that an object is or is not well formed formula in your language. > even for the purpose of > denying their existence. So the theory Y cannot prove that "The theory > PA does not exist" because such a proposition is not even legitimate > in the language of Y. YOU'RE NOT LISTENING. Y proves that there is no such object as is desribed in the definiens of 'PA' as that definiens is LEGITIMATELY given in Z. If Y is extended by definitions with a constant symbol 'PA' then that definition is NOT have the same definiens as the definiens of 'PA' in Z. That is because Y PROVES that there IS NO OBJECT that satifisfies that definiens. I've explained this over a dozen times. > What Y does is to effectively define the theory PA *constructively* by > displaying all its axioms and theorems in the language of Y (via a > suitable interpretation of the theory PA in Y) and with no reference No, Y HAS as theorems all the translations of the PA axioms. But that is not a "DEFINITION" of PA in Y. > Having done that, we also observe > that Y admits Con(PA) as a legitimate proposition in its language. What we have is EXACTLY as I stated in previous posts. > Thus Y does not commit itself to any notion of the theory PA as having > been defined in terms of infinite sets but nevertheless is able to > formalize "There exists a model of PA" (which is just Con(PA)). See my previous posts. You're just skipping the EXACT situation in favor of a woozily described one. > Lastly, observe that Y proves that "Infinite sets do not exist". Which > means that, according to Y, there is no object corresponding to any > model of PA in the universe of sets. Y does not mention "models" or "PA" AT ALL. > Therefore I assert that Y proves > ~Con(PA). WRONG. WRONG. WRONG. I've explained already how you are mixed up about this. You are now arguing just by RECLAIMING what you have not proven. Y proves "no x is infinite". In the language of Y there is a sentence S such that when S is translated into the language of PA (under an interpretation of Y into PA) as sentence S*, we have that S* is true in the standard model of PA iff PA is inconsistent. But you have NOT shown that S is a THEOREM of Y. Just because there is a sentence in the language of Y doesn't entail that sentence is a THEOREM of Y. MoeBlee |