[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.)



Panu Raatikainen

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

E-mail: panu.raatikainen at helsinki.fi

More information about the FOM mailing list