arithmetic in ZF
in [Logic]
|
Prev: What is wrong with this argument?
Next: Courage?
From: Daryl McCullough on 11 Apr 2005 12:27 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. Instead of Bew(x), define a function f(x,y) as follows: f(x,y): 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. -- Daryl McCullough Ithaca, NY
From: Bhupinder Singh Anand on 11 Apr 2005 16:18 On Apr 11, 9:27 am, Daryl McCullough wrote: DM>> Then the range of f will be the set of all Goedel-numbers of provable formulas. <<DM You're right. This function does enumerate the provable formulas algorithmically. Thanks, and regards, Bhup
From: george on 12 Apr 2005 20:33 Bhupinder Singh Anand wrote: > 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. Sorry, wrong again. That "algorithmically"=df="recursively" IS Church's Thesis. Church's Thesis is that "algorithm" MEANS "algorithm implementable on a Turing Machine". EVERY set for which there exists a TM that accepts all&only-the- elements-of-that-set is recursively enumerable BY DEFINITION (THAT IS the definition of "recursively enumerable").
From: Torkel Franzen on 12 Apr 2005 21:48 "george" <greeneg(a)cs.unc.edu> writes: > Church's Thesis is that > "algorithm" MEANS "algorithm implementable on a Turing Machine". No it isn't. Church's thesis states that every function computable by an algorithm is computable by a Turing machine. The thesis that "algorithm" means "algorithm implementable on a Turing machine" is trivially false.
From: george on 14 Apr 2005 08:57
TF> Church's thesis states that every function computable TF> by an algorithm is computable by a Turing machine. TF> The thesis that "algorithm" means "algorithm implementable TF> on a Turing machine" is trivially false. That statement is trvially contradictory, unless there are algorithms out there that are good for doing things more important than merely computing functions. What sorts of things can those algorithms do? In the context of the argument that is ACTUALLY GOING ON, however, which is between me and Bhup about ENUMERATING A CLASS OF SENTENCES OF ZF, since EVERY SUCH ENUMERATION *IS* A FUNCTION, his claim of the existence of a difference between "algorithmically enumerable" and "recursively enumerable" EVEN given Church's Thesis is what is trivially false. In other words, it would've helped, since the question was about picking a side, for you to pick the side you knew to be right, instead of just trying to embarrass me. And actually failing. |