Issue Theoret. Informatics Appl. Volume 37, Number 1, January-March 2003 Page(s) 1 - 15 DOI 10.1051/ita:2003011

Theoret. Informatics Appl. 37, 1-15 (2003)
DOI: 10.1051/ita:2003011

Fixpoints, games and the difference hierarchy

Julian C. Bradfield

LFCS, School of Informatics, University of Edinburgh, Edinburgh, EH9 3JZ, UK; jcb@inf.ed.ac.uk.

Abstract
Drawing on an analogy with temporal fixpoint logic, we relate the arithmetic fixpoint definable sets to the winning positions of certain games, namely games whose winning conditions lie in the difference hierarchy over . This both provides a simple characterization of the fixpoint hierarchy, and refines existing results on the power of the game quantifier in descriptive set theory. We raise the problem of transfinite fixpoint hierarchies.

Mathematics Subject Classification. 03E15, 68Q45.

Key words: Descriptive set theory -- fixpoint -- game quantifier -- induction.

The main part of this paper was first presented at CSL'99 in Madrid [3]; the final part is based on a talk given at FICS 2001 in Florence, published in RAIRO: Theoret. Informatics Appl., volume 36, No. 2 (2002).

© EDP Sciences 2003

What is OpenURL?