Page 1 Next

Displaying 1 – 20 of 110

Showing per page

A Hierarchy of Automatic ω-Words having a Decidable MSO Theory

Vince Bárány (2008)

RAIRO - Theoretical Informatics and Applications

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...

Analytic determinacy and 0# A forcing-free proof of Harrington’s theorem

Ramez Sami (1999)

Fundamenta Mathematicae

We prove the following theorem: Given a⊆ω and 1 α < ω 1 C K , if for some η < 1 and all u ∈ WO of length η, a is Σ α 0 ( u ) , then a is Σ α 0 . We use this result to give a new, forcing-free, proof of Leo Harrington’s theorem: Σ 1 1 -Turing-determinacy implies the existence of 0 .

Bad Wadge-like reducibilities on the Baire space

Luca Motto Ros (2014)

Fundamenta Mathematicae

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...

Complexity of the axioms of the alternative set theory

Antonín Sochor (1993)

Commentationes Mathematicae Universitatis Carolinae

If T is a complete theory stronger than ZF Fin such that axiom of extensionality for classes + T + ( X ) Φ i is consistent for 1 i k (each alone), where Φ i are normal formulae then we show AST + ( X ) Φ 1 + + ( X ) Φ k + scheme of choice is consistent. As a consequence we get: there is no proper Δ 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 Π 1 -formula, but not Σ 1 -formula and furthermore prolongation axiom, axioms of choice and cardinalities are Π 2 -formulae,...

Currently displaying 1 – 20 of 110

Page 1 Next