Re: Primitive recursive vs recursive at the base of the arithmetical hierarchy.
From: Mike Oliver (mike_lists_at_verizon.net)
Date: 10/09/04
- Next message: Henry Fool: "Cheney was right to oppose Mandela's release"
- Previous message: Barb Knox: "Re: Deep Thoughts # 17: Liar Paradox is a Formal Metamathematical Theorem"
- In reply to: H. Enderton: "Re: Primitive recursive vs recursive at the base of the arithmetical hierarchy."
- Messages sorted by: [ date ] [ thread ]
Date: Fri, 08 Oct 2004 21:48:18 -0500
H. Enderton wrote:
> Rex Butler <RexButler@hotmail.com> wrote:
>
>>With regards to the theory of computability, I've noticed two
>>alternate definitions for the base class of the arithmetical
>>hierarchy. One defines the base class Delta_0 as the set of
>>*primitive recursive* relations,
>
>
> I can't see why anyone would do that. The class of primitive
> recursive relations is not a particularly natural class.
Well, it's the set of all relations definable over
<N,0,1,+,*> using only bounded quantifiers, isn't it?
That seems like a pretty natural thing to call Delta_0.
>>and the other defines the base class
>>Delta_0 as the set of (total) *recursive* relations.
>
>
> Good choice. Perfectly natural. As you pointed out, we get
> the same class for Sigma_1 in both cases.
But then you get Delta_1 == Delta_0 -- why would you
want that?
- Next message: Henry Fool: "Cheney was right to oppose Mandela's release"
- Previous message: Barb Knox: "Re: Deep Thoughts # 17: Liar Paradox is a Formal Metamathematical Theorem"
- In reply to: H. Enderton: "Re: Primitive recursive vs recursive at the base of the arithmetical hierarchy."
- Messages sorted by: [ date ] [ thread ]
Relevant Pages
|
