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: William Hale on 27 Jun 2010 05:18 In article <ff54cc7d-b23f-4a45-9040-0459145ff6fc(a)j8g2000yqd.googlegroups.com>, Charlie-Boo <shymathguy(a)gmail.com> wrote: [cut] > If ZFC can't calculate what PA can, how can anyone say that ZFC is a > good basis for doing mathematics - PA is used by lots of > mathematicians. PA is not used by any mathematicians to do algebra, number theory, real analysis, complex analysis, topology, or differential geometry. These mathematicians represent most mathematicians. They use ZFC as their axiomatic system.
From: R. Srinivasan on 27 Jun 2010 05:44 On Jun 27, 11:24 am, Transfer Principle <lwal...(a)lausd.net> wrote: > On Jun 26, 7:51 pm, Tim Little <t...(a)little-possums.net> wrote: > > > On 2010-06-26, R. Srinivasan <sradh...(a)in.ibm.com> wrote: > > > The theory ZF-Inf+~Inf clearly proves ~Inf ("Infinite sets do not > > > exist"). > > Actually ~Inf does not assert "Infinite sets do not exist". It only > > asserts "there does not exist a successor-closed set containing the > > empty set". > > This has come up time and time again. I myself have claimed that > the theory ZF-Infinity+~Infinity proves that every set is finite, > and someone (usually MoeBlee or Rupert) points out that this > theory only proves that there's no _successor-inductive_ set > containing 0, not that there is no infinite set. > > There is a simple way to sidestep this controversy. Suitably extend the language of ZF-Inf to admit the set D, where D = {x: An (x not in P_n(0))} Here 0 is the null set, n ranges over the non-negative integers and P_n(0) is the power set operation iterated n times on 0 with P_0(0) = P(0). Note that by definition, D does not include any hereditarily finite set, but it will contain every other set. Consider the theory F = ZF-Inf+{D=0} It is clear that F will only admit models with hereditarily finite sets. Use the theory F instead of ZF-Inf+~Inf in my post. > > > And every time this comes up, I want to say _fine_ -- so if > ZF-Inf+~Inf _doesn't_ prove that every set is finite, then there > should exist a model M of ZF-Inf+~Inf in which "there is an > infinite set" is true, even though "there exists a set containing > 0 that is successor-inductive" is clearly false (assuming, of > course, that ZF is itself consistent), just as the fact that ZFC > doesn't prove CH implies that there is a model of ZFC in which > CH is false (once again, assuming that ZF is itself consistent). > > Yet no one seems to accept the existence of this model M. > > Either this model M exists, or ZF-Inf+~Inf really does prove that > every set is finite. There are no other possibilities. > > So let's settle this once and for all. Assuming that ZF is > consistent, I ask: > > 1. Is there a proof in ZF-Inf+~Inf that every set is finite? > 2. Does there exist a model M of ZF-Inf+~Inf in which "there > is an infinite set" is true? > > Notice that exactly one of these questions has a "yes" answer > and exactly one has a "no" answer. (Actually, come to think > of it, since the base theory is ZF and not ZFC, it's possible > that the answer to 1. is "yes" if by "finite" we mean one > type of finite, say Dedekind finite, and "no" if we mean some > other type of finite. In this case, I'd like to know which > types of finite produce a "yes" answer.) > > If 1. is "yes," then I hope that I will never again see a post > claiming that ZF-Inf+~Inf doesn't prove that every set is in > fact finite. In fact, I'll go as far as to suggest that if 1. > is "yes," then those who claim that ZF-Inf+~Inf doesn't prove > that every set is finite deserve to be called five-letter > insults -- if posters are going to call those who deny the > proof of Cantor's Theorem by five-letter insults, then those > who deny the proof of "every set is finite" in ZF-Inf+~Inf > also ought to be called the same. > > If 2. is "yes," then what I'd like to know is how can I take > _advantage_ of this fact? Suppose I want to consider a theory, > based on ZF-Inf, which actually proves that an infinite set > exists, yet also proves that no successor-inductive set > containing 0 exists. > > I am also very much interested in knowing the outcome of this controversy. A quick look at Wikipedia, http://en.wikipedia.org/wiki/Axiom_of_infinity , throws up the following; \begin{quote} Indeed, using the Von Neumann universe, we can make a model of the axioms [of ZF] where the axiom of infinity is replaced by its negation. It is V_\omega \!, the class of hereditarily finite sets, with the inherited element relation. \end{quote} > > > In the current Tony Orlow thread, there is a discussion about > whether TO is defining N+ to be a successor-inductive set. It > is possible that the theory that I mentioned above might be > useful to discussing TO's ideas. > > But of course, we can't proceed until we know, once and for > all, whether ZF-Inf+~Inf proves every set to be finite or not.
From: R. Srinivasan on 27 Jun 2010 06:50 On Jun 27, 7:51 am, Tim Little <t...(a)little-possums.net> wrote: > On 2010-06-26, R. Srinivasan <sradh...(a)in.ibm.com> wrote: > > > The theory ZF-Inf+~Inf clearly proves ~Inf ("Infinite sets do not > > exist"). > > Actually ~Inf does not assert "Infinite sets do not exist". It only > asserts "there does not exist a successor-closed set containing the > empty set". It may turn out to prove an equivalent statement under > the rest of the axioms, but ~Inf does not actually mean "infinite sets > do not exist". > > Please see my reply to Transfer Principle. We may sidestep this issue by replacing ZF-Inf+~Inf in my post with a theory F which will only admit models with hereditarily finite sets. > > > > This proof obviously implies that "There does not exist a model for > > PA", for a model of PA must have an infinite set as its universe > > Even if your intepretation of ~Inf were correct, all it would prove is > that ZF-Inf+~Inf does not model PA. > Sure. But the point is that ZF-Inf+~Inf is *the* chosen metatheory (or model theory) of PA, in which models of PA, if they exist, can be constructed. I happen to have chosen a metatheory which will not admit any models of PA. In such a metatheory, PA is provably inconsistent because we have a proof that models of PA cannot exist. > > > > Now I am sure a lot of people are going to jump up and down and > > protest at this interpretation. But it is logical. > > No, it is not. It exhibits a fairly elementary failure of logic. The > statement "X models PA" implies "PA has a model". However, "X does > not model PA" does *not* imply "PA has no model". > > What you are effectively saying is that ZF-Inf+~Inf is the "wrong" metatheory because there *are* models of PA "out there" , meaning outside of our chosen model theory. This is just an assertion of Platonic existence. There is no particular reason for preferring ZF to ZF-Inf+~Inf as a model theory for PA. The fact that the latter theory yields an unpleasant result does not make it "wrong". RS
From: R. Srinivasan on 27 Jun 2010 08:17 On Jun 27, 2:42 am, Nam Nguyen <namducngu...(a)shaw.ca> wrote: > R. Srinivasan wrote: > > On Jun 26, 7:42 pm, Nam Nguyen <namducngu...(a)shaw.ca> wrote: > >> R. Srinivasan wrote: > >>> There are two notions of consistency, namely the syntactic and model- > >>> theoretic notions, which are supposed to be equivalent. > >>> Syntactically the consistency of PA is expressed by the sentence > >>> Con(PA) which can be encoded in ZF and proven. > >> What does it mean for a formula A of L(T) to _syntactically signify_ the > >> (possible) consistency of T? > > > By the way I do not agree that a formula of L(T) can express the > > consistency of T. > > So why did you use the phrases "syntactically" and "consistency of PA" > in your "Syntactically the consistency of PA is expressed by the sentence > Con(PA)"? > > As I said, I was expressing the conventional wisdom when I said that. I was arguing from the point of view of accepted classical logic. Basically I was playing along with the status quo to make a point later on. > > > > As I have stated in my post later on, I strongly > > believe that the consistency of T is a metamathematical (or in this > > case metatheoretical) notion that cannot be expressed in the language > > of T. > > So, again, why did you say "the consistency of PA is expressed by ... > Con(PA)", as below? > That is an accepted result of Godel from classical logic. Later on, when I was talking about NAFL, I disagreed with the classical result. NAFL is what I really believe in. RS > > >>> Syntactically the consistency of PA is expressed by the sentence > >>> Con(PA) which can be encoded in ZF and proven. > > > > > However, according the conventional wisdom, which is what I was > > stating above, a formula A of L(T) can represent the (code of the) > > assertion that "There does not exist a proof of '0=1' in the theory > > T", for theories T that can encode a certain amount of arithmetic. At > > least this is what Godel claimed. > > But all this is still syntactical, which you said above that "I do not > agree that a formula of L(T) can express the consistency of T". No?
From: Frederick Williams on 27 Jun 2010 08:21
Charlie-Boo wrote: > > On Jun 25, 4:58 pm, Frederick Williams <frederick.willia...(a)tesco.net> > wrote: > > Charlie-Boo wrote: > > > point. Who has proved PA consistent using ZFC? > > > Also, see Gentzen > > and Ackermann. Gentzen's proof used far less than full ZFC. > > References please. On-line?? Thanks! Gentzen: Mathematische Annalen, vol. 112, pp 493-565 and Forschungen zur Logik und zur Grundlegung der exakten Wissenschaften no. 4, pp 19-44. Ackermann: Mathematische Annalen, vol 117, pp 162-194. For Gentzen in English see his collected papers edited by Szabo. For an account of Ackermann's proof see Wang, Logic, Computers and Sets, Ch XIV. > > You may wish to know that ZFC with the axiom of infinity replaced > by > > its negation is a model of PA and vice versa. > > Wow, that sounds cool. I'll have to think anout that one. Where can > I read about it? I wish I could remember. Chris Menzel will tell us shortly. -- I can't go on, I'll go on. |