Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userClassifying equivalence relations in the Ershov hierarchy
105
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Computably enumerable equivalence relations (ceers) received a lot of attention in the literature. The standard tool to classify ceers is provided by the computable reducibility $leq_c$. This gives rise to a rich degree-structure. In this paper, we lift the study of $c$-degrees to the $Delta^0_2$ case. In doing so, we rely on the Ershov hierarchy. For any notation $a$ for a non-zero computable ordinal, we prove several algebraic properties of the degree-structure induced by $leq_c$ on the $Sigma^{-1}_{a}smallsetminus Pi^{-1}_a$ equivalence relations. A special focus of our work is on the (non)existence of infima and suprema of $c$-degrees.
rate research
Read More
Computability theorists have introduced multiple hierarchies to measure the complexity of sets of natural numbers. The Kleene Hierarchy classifies sets according to the first-order complexity of their defining formulas. The Ershov Hierarchy classifies $Delta^0_2$ sets with respect to the number of mistakes that are needed to approximate them. Biacino and Gerla extended the Kleene Hierarchy to the realm of fuzzy sets, whose membership functions range in a complete lattice $L$ (e.g., the real interval $[0; 1]_mathbb{R}$). In this paper, we combine the Ershov Hierarchy and fuzzy set theory, by introducing and investigating the Fuzzy Ershov Hierarchy. In particular, we focus on the fuzzy $n$-c.e. sets which form the finite levels of this hierarchy. Intuitively, a fuzzy set is $n$-c.e. if its membership function can be approximated by changing monotonicity at most $n-1$ times. We prove that the Fuzzy Ershov Hierarchy does not collapse; that, in analogy with the classical case, each fuzzy $n$-c.e. set can be represented as a Boolean combination of fuzzy c.e. sets; but that, contrary to the classical case, the Fuzzy Ershov Hierarchy does not exhaust the class of all $Delta^0_2$ fuzzy sets.
We study strong types and Galois groups in model theory from a topological and descriptive-set-theoretical point of view, leaning heavily on topological dynamical tools. More precisely, we give an abstract (not model theoretic) treatment of problems related to cardinality and Borel cardinality of strong types, quotients of definable groups and related objecets, generalising (and often improving) essentially all hitherto known results in this area. In particular, we show that under reasonable assumptions, strong type spaces are locally quotients of compact Polish groups. It follows that they are smooth if and only if they are type-definable, and that a quotient of a type-definable group by an analytic subgroup is either finite or of cardinality at least continuum.
We extend some recent results about bounded invariant equivalence relations and invariant subgroups of definable groups: we show that type-definability and smoothness are equivalent conditions in a wider class of relations than heretofore considered, which includes all the cases for which the equivalence was proved before. As a by-product, we show some analogous results in purely topological context (without direct use of model theory).
We generalise the main theorems from the paper The Borel cardinality of Lascar strong types by I. Kaplan, B. Miller and P. Simon to a wider class of bounded invariant equivalence relations. We apply them to describe relationships between fundamental properties of bounded invariant equivalence relations (such as smoothness or type-definability) which also requires finding a series of counterexamples. Finally, we apply the generalisation mentioned above to prove a conjecture from a paper by the first author and J. Gismatullin, showing that the key technical assumption of the main theorem (concerning connected components in definable group extensions) from that paper is not only sufficient but also necessary to get the conclusion.
A standard tool for classifying the complexity of equivalence relations on $omega$ is provided by computable reducibility. This reducibility gives rise to a rich degree structure. The paper studies equivalence relations, which induce minimal degrees with respect to computable reducibility. Let $Gamma$ be one of the following classes: $Sigma^0_{alpha}$, $Pi^0_{alpha}$, $Sigma^1_n$, or $Pi^1_n$, where $alpha geq 2$ is a computable ordinal and $n$ is a non-zero natural number. We prove that there are infinitely many pairwise incomparable minimal equivalence relations that are properly in $Gamma$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
