Title:  AN UNDECIDABLE LINEAR ORDER THAT IS n-DECIDABLE FOR ALL n    

Authors:
JOHN CHISHOLM, Department of Mathematics, Western Illinois University, Macomb, Illinois 61455
MICHAEL MOSES, Department of Mathematics, The George Washington University Washington, D.C. 20052

Preprint: GWUM-1999-03

Abstract: A linear order is n-decidable if its universe is N and the relations determined by S_n formulae are uniformly computable. This means that there is a computable procedure which, when applied to a S_n formula f([`x]) and a sequence [`a] of elements of the linear order, will determine whether or not f([`a]) is true in the structure. A linear order is decidable if the relations determined by all formulae are uniformly computable.

These definitions suggest two questions: Are there, for each n, n-decidable linear orders that are not (n+1)-decidable? Are there linear orders that are n-decidable for all n but not decidable? The former was answered, in the positive, in Moses (1993). Here we answer the latter, also positively.
 
 File translated from T_EX by T_TH, version 1.57.