2014/01/09 by Samuel Allen Alexander, Samuel Alexander
Computer Science · Mathematics · Psychology · #Advanced Topology and Set Theory #Arithmetic #Artificial intelligence #Axiom of choice #Baire measure #Baire space #Class (philosophy) #Computability, Logic, AI Algorithms #Computer science #Discrete mathematics #Equivalence relation #Hausdorff space #Hierarchy #Limit (mathematics) #Mathematics #Philosophy and Theoretical Science #Remainder #Set (abstract data type) #Set theory #Successor cardinal #math.LO #msc:03E15
paper · pdf · doi:10.1215/00294527-3443549
published as Notre Dame J. Formal Logic 57, no. 2 (2016), 209-220 · 12 pages, accepted to the NDJFL
arxiv created 2014/01/09 · openalex publication_date 2016/01/01 · arxiv updated 2016/06/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
In his dissertation, Wadge defined a notion of guessability on subsets of the Baire space and gave two characterizations of guessable sets. A set is guessable if and only if it is in the second ambiguous class (Δ20), if and only if it is eventually annihilated by a certain remainder. We simplify this remainder and give a new proof of the latter equivalence. We then introduce a notion of guessing with an ordinal limit on how often one can change one’s mind. We show that for every ordinal α, a guessable set is annihilated by α applications of the simplified remainder if and only if it is guessable with fewer than α mind changes. We use guessability with fewer than α mind changes to give a semi-characterization of the Hausdorff difference hierarchy, and indicate how Wadge’s notion of guessability can be generalized to higher-order guessability, providing characterizations of Δα0 for all successor ordinals α>1.