Abstract
The usual setting for recursion theory is the standard model for second order arithmetic; i.e., the structure (N, P(w)), where N is the standard model for first order arithmetic, and P(w) is the family of all subsets of w--the set of natural numbers. In recent years people (M.J. GROSZEK, P. HAJEK, K. KONTOSTATHIS, A. KUCERA, M. E. MYTILINAIOS, P. PUDLAK, T. A. SLAMAN, W. H. WOODIN, Y. YANG--see references) have considered recursion theory in other second order structures of the form (M, S), where M is a nonstandard model of Peano Arithmetic (PA) or some fragment of PA, and S is a family of subsets of M. The purpose of these investigations in general has been to develop a better understanding of the properties actually needed in proving various results from recursion theory.
In the present paper, we consider the following elementary result:
PROPOSITION 1. For any sets X and Y, the following are equivalent
(1) X is r.e. relative to Y
(2) X is definable by a formula which is Xi (Y); i.e., X1 with a predicate for Y.
In structures of the form (M, S) where M is a model of (a sufficient fragment of) PA, (1) implies (2), and if S consists of amenable sets, then (2) implies (1). Here we show that without amenability, (2) need not imply (1). More precisely, we prove that for any countable model AM of PA, there is a conservative extension M, with a subset Y such that a certain Σ1 (Y)-formula defines a set which is not r.e. relative to Y. The model M is produced using methods of Specker-MacDowell and Gaifman, and the set Y is produced by forcing, using N-finite forcing conditions.
Original language | American English |
---|---|
State | Published - Jan 6 1995 |
Event | Association for Symbolic Logic Winter Meeting (ASL) - San Francisco, CA Duration: Jan 6 1995 → … |
Conference
Conference | Association for Symbolic Logic Winter Meeting (ASL) |
---|---|
Period | 01/6/95 → … |
Disciplines
- Mathematics
Keywords
- Forcing
- Models of Peano Arithmetic
- Recursively enumerable
- Σ1 definable