Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userResults in descriptive set theory on some represented spaces
99
0
0.0
(
0
)
Added by
Mathieu Hoyrup
Publication date
2017
fields
Informatics Engineering
and research's language is
English
Authors
Mathieu Hoyrup
Ask ChatGPT about the research
No Arabic abstract
Descriptive set theory was originally developed on Polish spaces. It was later extended to $omega$-continuous domains [Selivanov 2004] and recently to quasi-Polish spaces [de Brecht 2013]. All these spaces are countably-based. Extending descriptive set theory and its effective counterpart to general represented spaces, including non-countably-based spaces has been started in [Pauly, de Brecht 2015]. We study the spaces $mathcal{O}(mathbb{N}^mathbb{N})$, $mathcal{C}(mathbb{N}^mathbb{N},2)$ and the Kleene-Kreisel spaces $mathbb{N}langlealpharangle$. We show that there is a $Sigma^0_2$-subset of $mathcal{O}(mathbb{N}^mathbb{N})$ which is not Borel. We show that the open subsets of $mathbb{N}^{mathbb{N}^mathbb{N}}$ cannot be continuously indexed by elements of $mathbb{N}^mathbb{N}$ or even $mathbb{N}^{mathbb{N}^mathbb{N}}$, and more generally that the open subsets of $mathbb{N}langlealpharangle$ cannot be continuously indexed by elements of $mathbb{N}langlealpharangle$. We also derive effecti
rate research
Read More
These are lecture notes from a course I gave at the University of Wisconsin during the Spring semester of 1993. Part 1 is concerned with Borel hierarchies. Section 13 contains an unpublished theorem of Fremlin concerning Borel hierarchies and MA. Section 14 and 15 contain new results concerning the lengths of Borel hierarchies in the Cohen and random real model. Part 2 contains standard results on the theory of Analytic sets. Section 25 contains Harringtons Theorem that it is consistent to have $Pi^1_2$ sets of arbitrary cardinality. Part 3 has the usual separation theorems. Part 4 gives some applications of Gandy forcing. We reverse the usual trend and use forcing arguments instead of Baire category. In particular, Louveaus Theorem on $Pi^0_alpha$ hyp-sets has a simpler proof using forcing.
This survey paper examines the effective model theory obtained with the BSS model of real number computation. It treats the following topics: computable ordinals, satisfaction of computable infinitary formulas, forcing as a construction technique, effective categoricity, effective topology, and relations with other models for the effective theory of uncountable structures.
We begin to study classical dimension theory from the computable analysis (TTE) point of view. For computable metric spaces, several effectivisations of zero-dimensionality are shown to be equivalent. The part of this characterisation that concerns covering dimension extends to higher dimensions and to closed shrinkings of finite open covers. To deal with zero-dimensional subspaces uniformly, four operations (relative to the space and a class of subspaces) are defined; these correspond to definitions of inductive and covering dimensions and a countable basis condition. Finally, an effective retract characterisation of zero-dimensionality is proven under an effective compactness condition. In one direction this uses a version of the construction of bilocated sets.
We investigate language interpretations of two extensions of the Lambek calculus: with additive conjunction and disjunction and with additive conjunction and the unit constant. For extensions with additive connectives, we show that conjunction and disjunction behave differently. Adding both of them leads to incompleteness due to the distributivity law. We show that with conjunction only no issues with distributivity arise. In contrast, there exists a corollary of the distributivity law in the language with disjunction only which is not derivable in the non-distributive system. Moreover, this difference keeps valid for systems with permutation and/or weakening structural rules, that is, intuitionistic linear and affine logics and affine multiplicative-additive Lambek calculus. For the extension of the Lambek with the unit constant, we present a calculus which reflects natural algebraic properties of the empty word. We do not claim completeness for this calculus, but we prove undecidability for the whole range of systems extending this minimal calculus and sound w.r.t. language models. As a corollary, we show that in the language with the unit there exissts a sequent that is true if all variables are interpreted by regular language, but not true in language models in general.
The $omega$-power of a finitary language L over a finite alphabet $Sigma$ is the language of infinite words over $Sigma$ defined by L $infty$ := {w 0 w 1. .. $in$ $Sigma$ $omega$ | $forall$i $in$ $omega$ w i $in$ L}. The $omega$-powers appear very naturally in Theoretical Computer Science in the characterization of several classes of languages of infinite words accepted by various kinds of automata, like B{u}chi automata or B{u}chi pushdown automata. We survey some recent results about the links relating Descriptive Set Theory and $omega$-powers.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
