Premium
On Σ 1 1 equivalence relations over the natural numbers
Author(s) -
Fokina Ekaterina B.,
Friedman SyDavid
Publication year - 2012
Publication title -
mathematical logic quarterly
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.473
H-Index - 28
eISSN - 1521-3870
pISSN - 0942-5616
DOI - 10.1002/malq.201020063
Subject(s) - equivalence relation , mathematics , equivalence (formal languages) , combinatorics , natural number , sigma , discrete mathematics , physics , quantum mechanics
We study the structure of Σ 1 1 equivalence relations on hyperarithmetical subsets of ω under reducibilities given by hyperarithmetical or computable functions, called h‐reducibility and FF‐reducibility, respectively. We show that the structure is rich even when one fixes the number of properly \documentclass{article}\usepackage{amssymb}\begin{document}\pagestyle{empty}$\Sigma ^1_1\ \big ($\end{document} i.e., Σ 1 1 but not \documentclass{article}\usepackage{amssymb}\begin{document}\pagestyle{empty}$\Delta ^1_1\big )$\end{document} equivalence classes. We also show the existence of incomparable Σ 1 1 equivalence relations that are complete as subsets of ω × ω with respect to the corresponding reducibility on sets. We study complete Σ 1 1 equivalence relations (under both reducibilities) and show that existence of infinitely many properly Σ 1 1 equivalence classes that are complete as Σ 1 1 sets (under the corresponding reducibility on sets) is necessary but not sufficient for a relation to be complete in the context of Σ 1 1 equivalence relations.