arithmetic in ZF
in [Logic]
|
Prev: What is wrong with this argument?
Next: Courage?
From: Bhupinder Singh Anand on 10 Apr 2005 17:29 On Apr 10, 12:18 pm, George wrote: G>> ... The class of sentences provable in FOL from a recursive axiom-set IS NECESSARILY, PROVABLY, ALWAYS, recursively enumerable. It may even be recursive as well (although in the cause of PA and ZF, it is not; that, again, is the whole content of Godel's 1st incompleteness theorem). <<G George ===== Sorry, I don't quite follow this. My understanding of a recursively enumerable set is that it is the range (assumed to be a consistently well-defined set of a set theory such as, say, ZF) of a recursive function. Now, Goedel's relation Bew(x), defined as: (Ey)(y is the Goedel-number of a PA-proof of the PA-formula whose Goedel-number is x) is not recursive. It follows that the set of Goedel-numbers of the provable formulas of PA is not recursively enumerable. So, in what sense are we to treat the set of provable arithmetical sentences of PA, or of ZF, as recursively enumerable? Regards, Bhup
From: Barb Knox on 10 Apr 2005 23:04 In article <1113168563.406607.197610(a)o13g2000cwo.googlegroups.com>, "Bhupinder Singh Anand" <re(a)alixcomsi.com> wrote: >On Apr 10, 12:18 pm, George wrote: > >G>> ... The class of sentences provable in FOL from a recursive >axiom-set IS NECESSARILY, PROVABLY, ALWAYS, recursively enumerable. It >may even be recursive as well (although in the cause of PA and ZF, it >is not; that, again, is the whole content of Godel's 1st incompleteness >theorem). <<G > >George >===== >Sorry, I don't quite follow this. > >My understanding of a recursively enumerable set is that it is the >range (assumed to be a consistently well-defined set of a set theory >such as, say, ZF) of a recursive function. > >Now, Goedel's relation Bew(x), defined as: > >(Ey)(y is the Goedel-number of a PA-proof of the PA-formula whose >Goedel-number is x) > >is not recursive. > >It follows that the set of Goedel-numbers of the provable formulas of >PA is not recursively enumerable. No, it doesn't follow. Just because a particular set happens to be the range of SOME non-recursive function does not imply that ALL functions with that set as their range are non-recursive. For a simpler example, the non-recursive boolean function IndexedTuringMachineHaltsOnBlankTape(i) has the recursive range {true,false}. >So, in what sense are we to treat the set of provable arithmetical >sentences of PA, or of ZF, as recursively enumerable? > >Regards, > >Bhup -- --------------------------- | BBB b \ Barbara at LivingHistory stop co stop uk | B B aa rrr b | | BBB a a r bbb | Quidquid latine dictum sit, | B B a a r b b | altum viditur. | BBB aa a r bbb | -----------------------------
From: Bhupinder Singh Anand on 11 Apr 2005 08:01 On Apr 10, 8:04 pm, Barb Knox wrote: BSA>> It follows that the set of Goedel-numbers of the provable formulas of PA is not recursively enumerable. <<BSA BK>> No, it doesn't follow. <<BK Barb/George =========== You're right. That was silly of me - sorry. The set of provable formulas of PA is, indeed, recursively enumerable if we assume Church's Thesis. The point I intended to raise was that the standard interpretation of this - namely, that there is always a uniform mechanical procedure (algorithm) for generating a r.e. set - may not be definitive. Thanks, and regards, Bhup
From: Daryl McCullough on 11 Apr 2005 11:05 Bhupinder Singh Anand says... >My understanding of a recursively enumerable set is that it is the >range (assumed to be a consistently well-defined set of a set theory >such as, say, ZF) of a recursive function. > >Now, Goedel's relation Bew(x), defined as: > >(Ey)(y is the Goedel-number of a PA-proof of the PA-formula whose >Goedel-number is x) > >is not recursive. > >It follows that the set of Goedel-numbers of the provable formulas of >PA is not recursively enumerable. Introduce a new recursive function F(x,y) as follows: If y is the Goedel-number of a PA-proof of the PA-formula whose Goedel-number is x, then return x. Otherwise, return the Goedel-number of the formula "0=0". Then the range of F will be the set of all Goedel numbers of provable formulas of PA. -- Daryl McCullough Ithaca, NY
From: Bhupinder Singh Anand on 11 Apr 2005 11:43
On Apr 9, 8:06 pm, Bhupinder Singh Anand wrote: BSA>> ... the set of arithmetical sentences provable in ZF need not be r.e. ... <<BSA This, of course, is wrong. Sorry. What I meant was that, even assuming Church's Thesis, the arithmetical sentences provable in ZF need not be algorithmically enumerable, although they are, of course, recursively enumerable. The issue that I sought to highlight was that, though the standard interpretation of the term 'computable' in Church's thesis implicitly implies algorithmic computability, i.e., a uniform, mechanical process of computation, this need not be so. Thus a computable number-theoretic function may be provable as individually 'computable' for any set of natural number values given to its free variables (as Goedel has shown); however, there may be no algorithm, or uniform mechanical procedure, for the computation. Further, although the set of true arithmetical sentences is not arithmetical, the assertion that the set is also not r.e. seems based on implicitly treating recursive enumerability as equivalent to algorithmic enumerability. Such, implicitly assumed, equivalence may not be definitive. Regards, Bhup |