A characterization of determinacy for Turing degree games
A Characterization of the Veblen-Schütte Functions by Means of Functionals
A classification of the ordinal recursive functions.
A conjecture of Ershov for a relative hierarchy fails near .
A generalized Feiner hierarchy.
A Hierarchy of Automatic ω-Words having a Decidable MSO Theory
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...
A hierarchy of primitive recursive sequence functions
A Turing machine oracle hierarchy. I.
A Turing machine oracle hierarchy. II.
Analytic determinacy and 0# A forcing-free proof of Harrington’s theorem
We prove the following theorem: Given a⊆ω and , if for some and all u ∈ WO of length η, a is , then a is . We use this result to give a new, forcing-free, proof of Leo Harrington’s theorem: -Turing-determinacy implies the existence of .
Arithmetical classification of the set of all provably recursive functions
The set of all indices of all functions provably recursive in any reasonable theory is shown to be recursively isomorphic to , where is -complete set.
Automatic listing of important observational statements. I
Automatic listing of important observational statements. II
Automatic listing of important observational statements. III
Bad Wadge-like reducibilities on the Baire space
We consider various collections of functions from the Baire space 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 (compatible with its standard topology). We analyze the degree-structures induced by such sets of functions when used as reducibility notions between subsets of...
Beweistheoretische Charakterisierung einer Erweiterung der Grzegorczyk-Hierarchie.
Binumerability in a sequence of theories
Built-up systems of fundamental sequences and hierarchies of number-theoretic functions.
Complete index sets of recursively enumerable families
Complexity of the axioms of the alternative set theory
If T is a complete theory stronger than ZF such that axiom of extensionality for classes + T + is consistent for 1 (each alone), where are normal formulae then we show AST + + scheme of choice is consistent. As a consequence we get: there is no proper -formula in AST + scheme of choice. Moreover the complexity of the axioms of AST is studied, e.gẇe show axiom of extensionality is -formula, but not -formula and furthermore prolongation axiom, axioms of choice and cardinalities are -formulae,...