Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userIsomorphism types of Rogers semilattices in the analytical hierarchy
69
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
A numbering of a countable family $S$ is a surjective map from the set of natural numbers $omega$ onto $S$. A numbering $ u$ is reducible to a numbering $mu$ if there is an effective procedure which given a $ u$-index of an object from $S$, computes a $mu$-index for the same object. The reducibility between numberings gives rise to a class of upper semilattices, which are usually called Rogers semilattices. The paper studies Rogers semilattices for families $S subset P(omega)$ belonging to various levels of the analytical hierarchy. We prove that for any non-zero natural numbers $m eq n$, any non-trivial Rogers semilattice of a $Pi^1_m$-computable family cannot be isomorphic to a Rogers semilattice of a $Pi^1_n$-computable family. One of the key ingredients of the proof is an application of the result by Downey and Knight on degree spectra of linear orders.
rate research
Read More
A numbering of a countable family $S$ is a surjective map from the set of natural numbers $omega$ onto $S$. The paper studies Rogers semilattices, i.e. upper semilattices induced by the reducibility between numberings, for families $Ssubset P(omega)$. Working in set theory ZF+DC+PD, we obtain the following results on families from various levels of the analytical hierarchy. For a non-zero number $n$, by $E^1_n$ we denote $Pi^1_n$ if $n$ is odd, and $Sigma^1_n$ if $n$ is even. We show that for a finite family $S$ of $E^1_n$ sets, its Rogers $E^1_n$-semilattice has the greatest element if and only if $S$ contains the least element under set-theoretic inclusion. Furthermore, if $S$ does not have the $subseteq$-least element, then the corresponding Rogers $E^1_n$-semilattice is upwards dense.
A general theme of computable structure theory is to investigate when structures have copies of a given complexity $Gamma$. We discuss such problem for the case of equivalence structures and preorders. We show that there is a $Pi^0_1$ equivalence structure with no $Sigma^0_1$ copy, and in fact that the isomorphism types realized by the $Pi^0_1$ equivalence structures coincide with those realized by the $Delta^0_2$ equivalence structures. We also construct a $Sigma^0_1$ preorder with no $Pi^0_1$ copy.
An $omega$-tree-automatic structure is a relational structure whose domain and relations are accepted by Muller or Rabin tree automata. We investigate in this paper the isomorphism problem for $omega$-tree-automatic structures. We prove first that the isomorphism relation for $omega$-tree-automatic boolean algebras (respectively, partial orders, rings, commutative rings, non commutative rings, non commutative groups, nilpotent groups of class n >1) is not determined by the axiomatic system ZFC. Then we prove that the isomorphism problem for $omega$-tree-automatic boolean algebras (respectively, partial orders, rings, commutative rings, non commutative rings, non commutative groups, nilpotent groups of class n >1) is neither a $Sigma_2^1$-set nor a $Pi_2^1$-set.
This paper investigates type isomorphism in a lambda-calculus with intersection and union types. It is known that in lambda-calculus, the isomorphism between two types is realised by a pair of terms inverse one each other. Notably, invertible terms are linear terms of a particular shape, called finite hereditary permutators. Typing properties of finite hereditary permutators are then studied in a relevant type inference system with intersection and union types for linear terms. In particular, an isomorphism preserving reduction between types is defined. Type reduction is confluent and terminating, and induces a notion of normal form of types. The properties of normal types are a crucial step toward the complete characterisation of type isomorphism. The main results of this paper are, on one hand, the fact that two types with the same normal form are isomorphic, on the other hand, the characterisation of the isomorphism between types in normal form, modulo isomorphism of arrow types.
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.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
