[FOM] cofinite quantifier

praatika@mappi.helsinki.fi praatika at mappi.helsinki.fi
Sun Feb 29 07:38:43 EST 2004


Thomas Forster <T.Forster at dpmms.cam.ac.uk> wrote:

> How undecidable is the theory of natural numbers with 
> the cofinite quantifier?  Does anyone know about this?


The following seems to be at least related:

{x : W_x is co-finite} is Sigma_3 -complete.

(ref.: H. Rogers: Theory of Recursive Functions and Effective 
Computability, p. 328.)

Best

Panu


Panu Raatikainen

PhD., Docent in Theoretical Philosophy
Fellow, Helsinki Collegium for Advanced Studies
University of Helsinki
 
Address: 
Helsinki Collegium for Advanced Studies
P.O. Box 4
FIN-00014 University of Helsinki
Finland

E-mail: panu.raatikainen at helsinki.fi
 
http://www.helsinki.fi/collegium/eng/Raatikainen/raatikainen.htm 



More information about the FOM mailing list