Torkel Franzen on truth
in [Logic]
|
From: Newberry on 19 Nov 2007 23:11 On Nov 19, 11:38 am, stevendaryl3...(a)yahoo.com (Daryl McCullough) wrote: > Newberry says... > > > > >On Nov 17, 4:47 pm, stevendaryl3...(a)yahoo.com (Daryl McCullough) > >wrote: > >> The problem here is that you haven't defined what > >> the heck you are talking about. What is T(F)? > >> How about defining your terms before using them? > > >> T(F) --> F > > >> isn't compelling to me, because I don't even > >> know what it means. > >P(x,y) is a provability predicate > > For what theory? Say PA. > >F is any wff > >T(F) is true > > How are you defining T(F)? Tarski showed that no consistent > language can have a truth predicate for that very language. I am not defining it. You defined it in your previous posts. I did not say that it was in the language of PA. I said that T(F) --> F is just as compelling as any other axiom. What I mean is that by puting T(F) on another level you did avoid a contradiction, nevertheless intuitively T(F) --> F. ("F" means any wff not "false."}
From: Newberry on 20 Nov 2007 00:55 On Nov 19, 11:34 am, stevendaryl3...(a)yahoo.com (Daryl McCullough) wrote: > Newberry says... > > > > > > > > >On Nov 17, 5:01 pm, stevendaryl3...(a)yahoo.com (Daryl McCullough) > >wrote: > >> Now, if you want to go for the whole ball of wax and > >> come up with a theory T_ultimate with the following > >> property: > > >> T_ultimate proves > >> Ex (P_ultimate(x,#F)) -> F > > >> There is no such theory T_ultimate except for an > >> inconsistent theory. > > >Do you mean that there is no such extension of PA (classical logic > >with Peano axioms) or do you mean there is no such extension of ANY > >theory capable of arithmetic. > > I mean the latter, but I'm not sure about the distinction you > are making. It's hard to see how something could be "capable > of arithmetic" without being an extension of PA (or at least > an extension of Robinson arithmetic). When you say "arithmetic" what do you mean by that? And what do you mean by "PA"? "Peano arithmetic" or a specific formal system = classical logic + Peano axioms"? What if we do not use classical logic? Is it still Peano arithmetic? Is it still "arithmetic"? > >If you mean the later then I think it is > >not true. > > Yes, it is. That's what Godel's second incompleteness theorem > proves: If T_ultimate is consistent, then it cannot prove its > own consistency. Even Aatu Koskensilta posted a contribution not to long ago where he concedes that the 2-nd theorem depends on the particulars of the formal system. I have never seen a proof of "Any conceivable formal system capable of arithmetic (representing all p.r. functions) cannot prove its own consistency."
From: Newberry on 20 Nov 2007 00:57 On Nov 17, 5:01 pm, stevendaryl3...(a)yahoo.com (Daryl McCullough) wrote: > Newberry says... > > > > >On Nov 17, 10:26 am, stevendaryl3...(a)yahoo.com (Daryl McCullough) > >wrote: > >> >What I meant is that we can say > >> >(Ex)(Px, #(F)) --> F > >> >leaving the T out. > >> >Yes, it is inconsistent. > > >> No, it's not inconsistent, if you are careful about it. > > >Please explain. You were the one who claimed it was inconsistent in an > >earlier post. > > We talked about a bunch of different things. I don't know > what P is supposed to mean here. Is it the provability predicate? > If so, the provability predicate for what theory? What is F? > Is it just any contradiction? I'll assume it is. > > If you have a theory T1, then you can define a provability > predicate for T1, call it P1(x,y) (meaning "x is a code > for a proof in T1 of a formula whose code is y"). If T1 > is a sound theory (anything it says about arithmetic is > true in the usual interpretation), then the statement > > Ex (P1(x,#F)) -> F > > is a perfectly true sentence. So you can add that as > an axiom to T1 to get a new theory T2. There is no > problem with consistency. T2 can prove G1, the Godel > sentence for T1. But T2 cannot prove G2, the Godel > sentence for T2. You can define a provability predicate > for T2, call it P2, and you can formulate a perfectly > good statement of arithmetic: > > Ex (P2(x,#F)) -> F > > You can add this as an axiom to T2 to get a new theory T3. > And so on. > > This process gives you a way to go from axiomatizable > true theories to more complete axiomatizable true theories. > > Now, if you want to go for the whole ball of wax and > come up with a theory T_ultimate with the following > property: > > T_ultimate proves > Ex (P_ultimate(x,#F)) -> F > > There is no such theory T_ultimate except for an > inconsistent theory. > > -- > Daryl McCullough > Ithaca, NY This is interesting stuff. Where can I read about it? How do you construct P_ultimate(x,y)?
From: Daryl McCullough on 20 Nov 2007 09:16 Newberry says... >> Now, if you want to go for the whole ball of wax and >> come up with a theory T_ultimate with the following >> property: >> >> T_ultimate proves >> Ex (P_ultimate(x,#F)) -> F >> >> There is no such theory T_ultimate except for an >> inconsistent theory. >This is interesting stuff. Where can I read about it? How do you >construct P_ultimate(x,y)? Well, as I said, it's inconsistent, so it's not really that interesting. But you can do this: Let Pr(x,y,z) be defined so that it holds if and only if x is a code for an r.e. theory T, and y is a code for a proof p, and z is a code for a formula S, and p is a proof of S from the axioms of T. If #T0 is the code for an r.e. set of axioms in the language of PA, then let f(#T0) be the code for the theory T1 where the axioms of T1 consists of the axioms of T0 plus the "soundness" schema for T0, which is, for every formula S in the language of PA, Ex Pr(#T0,x,#S) -> S Now we just use the fixed point theorem for r.e. sets to come up with a theory T extending PA such that #T and f(#T) code the same r.e. set of axioms. Here's what the fixed point theorem for r.e. sets says: If x is any natural number, then let W_x be the r.e. set coded by x (or the empty set, if x doesn't code anything). Then if f is any recursive function from naturals to naturals, then there is a natural number n such that W_n = W_{f(n)} -- Daryl McCullough Ithaca, NY
From: Daryl McCullough on 20 Nov 2007 09:30
Newberry says... > >On Nov 19, 11:34 am, stevendaryl3...(a)yahoo.com (Daryl McCullough) >wrote: >> >Do you mean that there is no such extension of PA (classical logic >> >with Peano axioms) or do you mean there is no such extension of ANY >> >theory capable of arithmetic. >> >> I mean the latter, but I'm not sure about the distinction you >> are making. It's hard to see how something could be "capable >> of arithmetic" without being an extension of PA (or at least >> an extension of Robinson arithmetic). > >When you say "arithmetic" what do you mean by that? For me, to say that a theory is capable of arithmetic means that it can prove the following theorems: 1. Ax x+0 = x 2. Ax Ay x+(y+1) = (x+y) + 1 3. Ax x * 0 = 0 4. Ax x * (y+1) = (x*y) + x 5. Ax ~ ((x+1)=0) 6. Ax Ay ((x+1) = (y+1) -> x=y) >And what do you mean by "PA"? Basically, axioms 1-6 together with the induction schema: Phi(0) & (Ax (Phi(x) -> Phi(x+1))) -> Ax (Phi(x)) >"Peano arithmetic" or a specific formal system = >classical logic + Peano axioms"? What if we do not use classical >logic? Is it still Peano arithmetic? Is it still "arithmetic"? You can use the same axioms for intuitionistic arithmetic. The distinction is not really important for discussing Godel's theorem. >> >If you mean the later then I think it is >> >not true. >> >> Yes, it is. That's what Godel's second incompleteness theorem >> proves: If T_ultimate is consistent, then it cannot prove its >> own consistency. > >Even Aatu Koskensilta posted a contribution not to long ago where he >concedes that the 2-nd theorem depends on the particulars of the >formal system. >I have never seen a proof of "Any conceivable formal >system capable of arithmetic (representing all p.r. functions) >cannot prove its own consistency." I'm not sure what Aatu meant, but if you define consistency of a theory T via the provability predicate, Con(#T) == Ax ~Pr(#T,x,#0=1) "there does not exist a proof of 0=1 from the axioms of T", then if T is capable of proving some routine facts about arithmetic (I'm not sure whether induction is needed or not) then it follows that if T proves Con(#T), then T is inconsistent. -- Daryl McCullough Ithaca, NY |