### A characterization of determinacy for Turing degree games

Skip to main content (access key 's'),
Skip to navigation (access key 'n'),
Accessibility information (access key '0')

We investigate automatic presentations of ω-words. Starting points of our study are the works of Rigo and Maes, Caucal, and Carton and Thomas concerning lexicographic presentation, MSO-interpretability in algebraic trees, and the decidability of the MSO theory of morphic words. Refining their techniques we observe that the lexicographic presentation of a (morphic) word is in a certain sense canonical. We then generalize our techniques to a hierarchy of classes of ω-words enjoying the above...

We prove the following theorem: Given a⊆ω and $1\le \alpha <{\omega}_{1}^{CK}$, if for some $\eta <{\aleph}_{1}$ and all u ∈ WO of length η, a is ${\Sigma}_{\alpha}^{0}\left(u\right)$, then a is ${\Sigma}_{\alpha}^{0}$. We use this result to give a new, forcing-free, proof of Leo Harrington’s theorem: ${\Sigma}_{1}^{1}$-Turing-determinacy implies the existence of $0$.

The set of all indices of all functions provably recursive in any reasonable theory $T$ is shown to be recursively isomorphic to $U\times \overline{U}$, where $U$ is ${\Pi}_{2}$-complete set.

We consider various collections of functions from the Baire space ${}^{\omega}\omega $ into itself naturally arising in (effective) descriptive set theory and general topology, including computable (equivalently, recursive) functions, contraction mappings, and functions which are nonexpansive or Lipschitz with respect to suitable complete ultrametrics on ${}^{\omega}\omega $ (compatible with its standard topology). We analyze the degree-structures induced by such sets of functions when used as reducibility notions between subsets of...

If T is a complete theory stronger than ZF${}_{\text{Fin}}$ such that axiom of extensionality for classes + T + $(\exists X){\Phi}_{i}$ is consistent for 1$\le i\le k$ (each alone), where ${\Phi}_{i}$ are normal formulae then we show AST + $(\exists X){\Phi}_{1}+\cdots +(\exists X){\Phi}_{k}$ + scheme of choice is consistent. As a consequence we get: there is no proper ${\Delta}_{1}$-formula in AST + scheme of choice. Moreover the complexity of the axioms of AST is studied, e.gẇe show axiom of extensionality is ${\Pi}_{1}$-formula, but not ${\Sigma}_{1}$-formula and furthermore prolongation axiom, axioms of choice and cardinalities are ${\Pi}_{2}$-formulae,...