TY - GEN

T1 - Boole vs Wadge: Comparing Two Basic Tools of Descriptive Set Theory

AU - Selivanov, Victor

PY - 2022/1/1

Y1 - 2022/1/1

N2 - We systematically compare ω -Boolean classes and Wadge classes, e.g. we complement the result of W. Wadge that the collection of non-self-dual levels of his hierarchy coincides with the collection of classes generated by Borel ω -ary Boolean operations from the open sets in the Baire space. Namely, we characterize the operations, which generate any given level in this way, in terms of the Wadge hierarchy in the Scott domain. As a corollary we deduce the non-collapse of the latter hierarchy. Also, the effective version of this topic is developed.

AB - We systematically compare ω -Boolean classes and Wadge classes, e.g. we complement the result of W. Wadge that the collection of non-self-dual levels of his hierarchy coincides with the collection of classes generated by Borel ω -ary Boolean operations from the open sets in the Baire space. Namely, we characterize the operations, which generate any given level in this way, in terms of the Wadge hierarchy in the Scott domain. As a corollary we deduce the non-collapse of the latter hierarchy. Also, the effective version of this topic is developed.

KW - Baire space

KW - Cantor space

KW - quasi-Polish space

KW - Scott domain

KW - Wadge hierarchy

KW - ω -ary Boolean operation

UR - http://www.scopus.com/inward/record.url?scp=85134169270&partnerID=8YFLogxK

U2 - 10.1007/978-3-031-08740-0_24

DO - 10.1007/978-3-031-08740-0_24

M3 - Conference contribution

AN - SCOPUS:85134169270

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 287

EP - 298

BT - Revolutions and Revelations in Computability

T2 - computability in europe-2022

Y2 - 11 July 2022

ER -