How Can ZFC/PA do much of Math - it Can't Even Prove PA is Consistent (EASY PROOF)
in [Math]
|
Prev: ? theoretically solved
Next: How Can ZFC/PA do much of Math - it Can't Even Prove PA is Consistent (EASY PROOF)
From: Transfer Principle on 5 Jul 2010 18:35 On Jul 3, 5:45 pm, "K_h" <KHol...(a)SX729.com> wrote: > "R. Srinivasan" <sradh...(a)in.ibm.com> wrote in message > > In NAFL, N is a proper class and there is no > > such thing as P(N). You cannot quantify over all > > the infinite sub-classes of N to get P(N), > > because quantification over proper classes is not > > permitted. > Why is N a proper class in NAFL and what is the basis to even have proper classes > in NAFL? The whole reason to bifurcate collections into sets and proper classes > is so that mathematics is self-consistent. That is, the problems presented by > Cantor's theorem (for example the Cantor and Burali-Forti paradoxes) can only be > solved by dividing collections into two types: sets and proper classes. (The > problems presented by Russell's paradox are solved by the axiom of foundation, no > collection can be a member of itself.) So it's because of Cantor's theorem that > such a bifurcation is necessary. If Cantor's theorem is false in NALF then on > what basis does NALF bifurcate collections into the two types? As far as I can > tell, NAFL has no basis to do so and so N should be a set. As a set, it is easy > to show that |N|<|P(N)|. So K_h acknowledges that because of two paradoxes, Cantor and Burali-Forti, we have theories with proper classes -- in particular, we have the proper classes V and On, respectively. But now let's take a look at N. We know that by the von Neumann definition of natural number, a natural number is a finite ordinal. So now we ask, how do we know that N isn't equal to the class On of all ordinals? In standard theory, the Axiom of Infinity proves that omega is a set, and an ordinal, but an infinite ordinal. Thus we have (omega)eOn and yet ~(omega)eN. Therefore ~N=On. But without the Axiom of Infinity, we can't prove that omega is a set. And according to Srinivasan, the theory NBG-Infinity, with NAFL as the underlying logic, proves that N=On and so N is a proper class, indeed the proper class of all ordinals. If we use FOL instead of NAFL, we can't prove that N=On unless we add the additional axiom D=0 (since On intersect D is exactly N). This raises another question. I believe in the following analogy: ZF-Infinity(+~Infinity) is to ZF as ZF(+~Inaccessible) is to ZF +Inaccessible Indeed, it is often stated that in a way, Infinity is the first large cardinal axiom. We can replace all references to ZF in the above with NBG so that we can discuss proper classes (or we can adopt MoeBlee's trick and treat class symbols as syntactic sugar for expressions that omit references to classes). And so now let's define a class M to be the class of all "accessible" ordinals (i.e., less than the first inaccessible ordinal). We note that in NBG+~Inaccessible, all ordinals are accessible and so M is exactly the class On of all ordinals, hence M is a proper class. But in NBG+Inaccessible, M is exactly the first of the inaccessible ordinals, and so M is actually a _set_. So, when K_h writes: > As far as I can > tell, NAFL has no basis to do so and so N should be a set. As a set, it is easy > to show that |N|<|P(N)|. I can just as easily write: "As far as I can tell, NAFL (or even FOL) has no basis to do so and so M should be a set. As a set, it is easy to show that |M|<|P(M)|." thus forcing K_h to accept inaccessibles! In other words, for me to require K_h to accept inaccessibles is analogous to requiring a finitist like Srivinasan to accept infinite sets. > We must show that |N|<|P(N)|. For this it must demonstrated that |N|<=|P(N)| and > |N|=/=|P(N)| are both true. To establish |N|<=|P(N)|, note that for all n in N > the function f(n)={n} does the job. To establish |N|=/=|P(N)|, a proof by > contradiction is needed. Subsets of N, like {2,5} and {1,3,5,7,9,...}, can be > written like {_,_,2,_,_,5,_,_,_,...} and {_,1,_,3,_,5,_,7,_,9,_,...} where the > underscore denotes the natural numbers that are missing from the subset. Since > one subset of N is N itself, N={0,1,2,3,4,5,6,7,8,9,...} is the only subset > without underscore characters and the empty set will have nothing but underscore > characters. Assume there is a bijection, f, between N and P(N) as follows: Does this proof work if N=On? I doubt it. Otherwise, why can't we substitute M for N above in the proof? Sure, K_h (assuming that he's working in a consistent ZF/NBG) can't refute that M=On, but neither does Srinivasan refute that N=On. > It is clear that the subset S of N is not in the list because it is different > from every set in the list according to the axiom of extensionality. Recall that > the axiom of extensionality says that two sets are equal iff they contain the > same elements. The set S={0,3,4,...} is clearly a subset of N S is clearly a sub_class_ of N. If N is a proper class, then it's possible for S to be a proper class as well, but only _sets_ can be elements of other sets. Therefore, the proof appears to be invalid unless we can prove that N is a set -- and in Srinivasan's theory, N isn't a set. Although the following isn't directly related to Srinivasan's theory, the following might be relevant in other threads, including Herc's: K_h states that the main reason to make a distinction between sets and proper classes is Cantor's Theorem. Thus, in a theory which refutes Cantor's Theorem, such as NFU, we expect there to be no distinction between sets and proper classes. Indeed, we see that this is exactly the case -- NFU proves that even V is a set. Notice that Infinity isn't an axiom of NFU (but in practice, set theorists work in NFU+Infinity or even NFU+Infinity+AC). But suppose we had the theory NFU+"N is a set" (with "N is a set" being syntactic sugar for a valid formula in NFU). Is K_h's proof now a valid proof that card(N) < card(P(N)), and thus, N must be a Cantorian set? I suspect that the answer might be "yes" -- which is why even though NFU proves the existence of non-Cantorian sets, the set N must still be Cantorian no matter what. This is why, in the Herc threads, I'm trying to find out whether Herc opposes Cantor's Theorem per se (so that NFU satisfies his desiderata) or the idea of cardinals larger than card(N) (so that NFU still won't satisfy Herc)? If the latter, then we'd need a theory other than NFU, one which proves N to be non-Cantorian, in other to meet Herc's desiderata. > > Again, you are arguing backwards. In NAFL, > > truth as provability is a fundamental logical > > requirement (as I have illustrated above while > > discussing the law of non-contradiction). > > Therefore the incompleteness theorems do not > > hold for NAFL theories (e.g. F, the theory of > > finite sets). > > You haven't demonstrated what you say you have. All formal systems are limited > in what they can mechanically prove but those limitations are not limitations on > existence. > > _- Hide quoted text - > > - Show quoted text -
From: Transfer Principle on 5 Jul 2010 18:54 On Jul 5, 3:35 pm, Transfer Principle <lwal...(a)lausd.net> wrote: > axiom D=0 (since On intersect D is exactly N). Correction: On\D = N -- that is, On set-subtraction D equals N.
From: MoeBlee on 6 Jul 2010 13:34 On Jul 5, 5:08 pm, Aatu Koskensilta <aatu.koskensi...(a)uta.fi> wrote: > MoeBlee <jazzm...(a)hotmail.com> writes: > > And, in that regard, I have said all along that there is no finitistic > > proof of the consistency of PA. I base that on the second > > incompleteness theorem. > > The first incompleteness theorem already suffices. This elementary point > is often overlooked, and has recently been stressed by Richard Zach. I > said a bit about this in an earlier post, not that it matters much in > the grand scheme of things. I'm sorry I overlooked that post. I always welcome these kinds of sharpenings. I'll try to go back to your post and I'll keep an eye out for Zach's remarks too (would you suggest where I can find them?). > > (I haven't personally verified every detail in a proof of the second > > incompleteness theorem, so my remarks are to the extent we can be > > confident that the second incompleteness theorem does indeed withstand > > complete scrutiny, as it is reported in the literature that it does.) > > Come now, you're surely not hedging your bets and saying you're not > absolutely certain the second incompleteness theorem, I'm on some tough deadlines right now, so I can only give a short answer that deserves some later elaboration. For me, it's not a matter of 'absoluteness' or 'certainty' per se, except as I would need to describe the sense in which I would mean them. My remarks do not at all reflect any special, significant, or important doubts that such and such a formal proof (such as of second incompleteness) does indeed exist. Perhaps later I'll explain later more specifically what I have in mind and why I gave such a disclaimer as above. Anyway, the purpose of my remarks above, the reason for the disclaimer I gave, is not to raise any real question as to to whether second incompleteness is indeed a theorem. > which has > withstood the most exacting and extreme scrutiny humanly possible, far, > far beyond what any run of the mill result in mathematics -- the > classification of finite groups, the Heine-Borel theorem, most of stuff > in analysis, Wiles's proof of Fermat's last theorem, the fundamental > theorem of arithmetic ... -- usually has to endure to prove its good > name, holds. I make the following comment NOT toward any purpose (which I do not have) of claiming need for skepticism regarding second incompleteness. That said, as far as I can tell, the literature on second incompleteness does not seem to me to be as thorough in proof details as you seem to convey. Most textbooks admit to providing only an outline and to omit certain "tedious" sections. As far as I know, there are not many full expositions other than Hilbert & Bernays, which still awaits translation into English. Even a tome such as Hinman's (which tends toward fussy details) provides only such an outline. Pace, again, my point is not to say that this requires important doubts as to theoremhood, but rather just to say that I don't think that, as a matter of literary fact, second incompleteness is accessible to a student's verification as are many other resuts in mathematics. (That there are results that may be even LESS accessible I do not contest.) > (I apologise for the clumsiness in the construction of the > previous sentence. My only excuse is that I'm again suffering of severe > lack of sleep. Aatu, I really hope you can find an ongoing solution for your insomnia. I know what suffering it can be. Maybe exercise? I don't know. But I hope the best for you. P.S. I've been reading over your other post in which you proposed an exercise, though I haven't written a post in response. MoeBlee
From: MoeBlee on 6 Jul 2010 16:47 On Jul 5, 6:46 pm, Nam Nguyen <namducngu...(a)shaw.ca> wrote: > Aatu Koskensilta wrote: > > It seems your posts have nevertheless led Nam [...] to incorrect > > ideas about my views. This is not any fault of yours. > > Huh? You didn't say anything in that conversation and silently > let him "represent" your views and if his "representing" goes > wrong that would be my fault, no explanation needed? > > Where are your (and his) sense of credibility and responsibility? vomitous: see above. MoeBlee
From: K_h on 6 Jul 2010 18:29
"Transfer Principle" <lwalke3(a)lausd.net> wrote in message news:e272b12a-3214-487c-beef-ebe1ac54dc74(a)y4g2000yqy.googlegroups.com... > On Jul 3, 5:45 pm, "K_h" <KHol...(a)SX729.com> wrote: >> "R. Srinivasan" <sradh...(a)in.ibm.com> wrote in message >> > In NAFL, N is a proper class and there is no >> > such thing as P(N). You cannot quantify over all >> > the infinite sub-classes of N to get P(N), >> > because quantification over proper classes is not >> > permitted. >> Why is N a proper class in NAFL and what is the basis to even have >> proper classes >> in NAFL? The whole reason to bifurcate collections into sets and >> proper classes >> is so that mathematics is self-consistent. That is, the problems >> presented by >> Cantor's theorem (for example the Cantor and Burali-Forti paradoxes) >> can only be >> solved by dividing collections into two types: sets and proper >> classes. (The >> problems presented by Russell's paradox are solved by the axiom of >> foundation, no >> collection can be a member of itself.) So it's because of Cantor's >> theorem that >> such a bifurcation is necessary. If Cantor's theorem is false in >> NALF then on >> what basis does NALF bifurcate collections into the two types? As >> far as I can >> tell, NAFL has no basis to do so and so N should be a set. As a set, >> it is easy >> to show that |N|<|P(N)|. > > But now let's take a look at N. We know that by the von Neumann > definition of natural number, a natural number is a finite ordinal. So > now we ask, how do we know that N isn't equal to the class On of > all ordinals? Yo, transfer dude. If I may kindly ask, why would it be? > And according to Srinivasan, the theory NBG-Infinity, with NAFL as > the underlying logic, proves that N=On and so N is a proper class, How so? Why wouldn't NBG-infinity be agnostic on this issue? > thus forcing K_h to accept inaccessibles! In other words, for me to > require K_h to accept inaccessibles is analogous to requiring a > finitist like Srivinasan to accept infinite sets. Okay. I accept inaccessibles; Srivinason is free to reject infinite sets if he likes. >> It is clear that the subset S of N is not in the list because it is >> different >> from every set in the list according to the axiom of extensionality. >> Recall that >> the axiom of extensionality says that two sets are equal iff they >> contain the >> same elements. The set S={0,3,4,...} is clearly a subset of N > > S is clearly a sub_class_ of N. If N is a proper class, then it's > possible for S to be a proper class as well, but only _sets_ can > be elements of other sets. Therefore, the proof appears to be > invalid unless we can prove that N is a set -- and in Srinivasan's > theory, N isn't a set. Let's review some basics about proper classes. Logically, a proper class has a "cardinal" or "ordinal" size of absolute infinity. (I use the equivocal quotes there because it's technically an abuse of those terms.) So the idea is that a proper class has the largest size possible and so there cannot be another class with an "ordinal" or "cardinal" size bigger than that. But you CAN get a bigger "ordinal" object than N. For instance, consider the sum of (1/2)^n for all n in {0,1,2,3,...}. Each natural number n provides one term in the sum: 1 + 1/2 + 1/4 + 1/8 + 1/16 + ... When this is summed for all naturals we get 2. Can we now add more? Yes we can: we can add the number 3 to 2 to get 5 and then we can add the number 4 to 5 to get 9. So it makes sense to say that the number 3 is the w term in the sum and the number 4 is the w+1 term in the sum. Ordinals simply mean do this first, do that second, etc, in a given order -- e.g. addition. That's the motivation underlying the ordinals. If N were a proper class then its "ordinal" size would have to be absolute infinite and, in this example, the number 4 would correspond to an "ordinal" term greater than absolute infinite! That is plainly a contradiction and this simple fact is one reason why N really must be a set. > K_h states that the main reason to make a distinction between > sets and proper classes is Cantor's Theorem. Thus, in a theory > which refutes Cantor's Theorem, such as NFU, we expect there > to be no distinction between sets and proper classes. Indeed, > we see that this is exactly the case -- NFU proves that even V > is a set. Why do you think NFU refutes Cantor's theorem instead of being agnostic on it? I am just curious -- whatever you believe is your own business. _ |