Hostname: page-component-7b7567c8c-z4zkx Total loading time: 0 Render date: 2026-11-17T15:28:28.495Z Has data issue: false hasContentIssue false

Selection in the monadic theory of a countable ordinal

Published online by Cambridge University Press:  12 March 2014

Alexander Rabinovich
Affiliation:
Tel-Aviv University, Sackler Faculty of Exact Sciences, Tel-Aviv 69978, Israel, E-mail: rabinoa@post.tau.ac.il
Amit Shomrat
Affiliation:
Tel-Aviv University, Sackler Faculty of Exact Sciences, Tel-Aviv 69978, Israel, E-mail: shomrata@post.tau.ac.il

Abstract

A monadic formula ψ(Y) is a selector for a formula φ(Y) in a structure if there exists a unique subset P of which satisfies ψ and this P also satisfies φ. We show that for every ordinal α ≥ ωω there are formulas having no selector in the structure (α, <). For α ≤ ω1, we decide which formulas have a selector in (α, <) , and construct selectors for them. We deduce the impossibility of a full generalization of the Büchi-Landweber solvability theorem from (ω, <) to (ωω, <). We state a partial extension of that theorem to all countable ordinals. To each formula we assign a selection degree which measures “how difficult it is to select”. We show that in a countable ordinal all non-selectable formulas share the same degree.

Information

Type
Research Article
Copyright
Copyright © Association for Symbolic Logic 2008

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable