Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userRogers semilattices in the analytical hierarchy: The case of finite families
70
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$. 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.
rate research
Read More
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.
In previous work, we have combined computable structure theory and algorithmic learning theory to study which families of algebraic structures are learnable in the limit (up to isomorphism). In this paper, we measure the computational power that is needed to learn finite families of structures. In particular, we prove that, if a family of structures is both finite and learnable, then any oracle which computes the Halting set is able to achieve such a learning. On the other hand, we construct a pair of structures which is learnable but no computable learner can learn it.
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.
We continue the study of the virtual large cardinal hierarchy, initiated in Gitman and Schindler (2018), by analysing virtu
Given a semilattice $X$ we study the algebraic properties of the semigroup $upsilon(X)$ of upfamilies on $X$. The semigroup $upsilon(X)$ contains the Stone-Cech extension $beta(X)$, the superextension $lambda(X)$, and the space of filters $phi(X)$ on $X$ as closed subsemigroups. We prove that $upsilon(X)$ is a semilattice iff $lambda(X)$ is a semilattice iff $phi(X)$ is a semilattice iff the semilattice $X$ is finite and linearly ordered. We prove that the semigroup $beta(X)$ is a band if and only if $X$ has no infinite antichains, and the semigroup $lambda(X)$ is commutative if and only if $X$ is a bush with finite branches.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
