A Borel reductibility theory for classes of countable structures

E-ISSN： 1943-5886|54|3|894-914

ISSN： 0022-4812

Source： The Journal of Symbolic Logic, Vol.54, Iss.3, 1989-09, pp. : 894-914

Disclaimer: Any content in publications that violate the sovereignty, the constitution or regulations of the PRC is not accepted or approved by CNPIEC.

Previous Menu Next

Abstract

We introduce a reducibility preordering between classes of countable structures, each class containing only structures of a given similarity type (which is allowed to vary from class to class). Though we sometimes work in a slightly larger context, we are principally concerned with the case where each class is an invariant Borel class (i.e. the class of all models, with underlying set = ω, of an L_ω1ω sentence; from this point of view, the reducibility can be thought of as a (rather weak) sort of L_ω1ω -interpretability notion). We prove a number of general results about this notion, but our main thrust is to situate various mathematically natural classes with respect to the preordering, most notably classes of algebraic structures such as groups and fields.