322,840 research outputs found
Some remarks on completion of numberings
No full textWe present some examples and constructions in the theory of complete numberings and completions of numberings that partially answer a few questions of a paper of Badaev, Goncharov and Sorb
Isomorphism types and theories of Rogers semilattices of arithmetical numberings
No full textWe investigate differences in isomorphism types and elementary
theories of Rogers semilattices of arithmetical numberings,
depending on different levels of the arithmetical hierarchy. It is
proved that new types of isomorphism appear as the arithmetical
level increases. It is also proved the incompleteness of the
theory of the class of all Rogers semilattices of any fixed level.
Finally, no Rogers semilattice of any infinite family at
arithmetical level is weakly distributive, whereas
Rogers semilattices of finite families are always distributive
Elementary theories for Rogers semilattices
No full textIt is proved that for every level of the arithmetic hierarchy, there exist infinitely many families of sets with pairwise non-elementarily equivalent Rogers semilattices
Isomorphism types of Rogers semilattices for families from different levels of the arithmetical hierarchy
No full textWe investigate differences in isomorphism types for Rogers semilattices of computable numberings of families of sets lying in different levels of the arithmetical hierarchy
Rogers semilattices of families of two embedded sets in the Ershov hierarchy
No full textLet be a Kleene's ordinal notation of a nonzero computable ordinal. We give a sufficient condition on , so that for every --computable family of two embedded sets, i.e. two sets , with properly contained in , the Rogers semilattice of the family is infinite. This condition is
satisfied by every notation of ; moreover every nonzero computable ordinal that is not sum of any two smaller ordinals has a notation that satisfies this condition. On the other hand, we also give a sufficient condition on , that yields that there is a --computable family of two embedded sets, whose Rogers semilattice consists of exactly one
element; this condition is satisfied by all notations of every successor ordinal bigger than , and by all notations of the ordinal ; moreover every computable ordinal that is sum of two smaller ordinals has a notation that satisfies this condition. We also show that for every nonzero
, or , and every notation of a nonzero ordinal there exists a --computable family of cardinality , whose Rogers semilattice consists of exactly one element
On elementary theories and isomorphism types of Rogers semilattices
No full textWe investigate differences in the elementary theories and
isomorphism types of Rogers semilattices of computable numberings
of families of sets lying in different levels of the arithmetical
hierarchy
Algebraic properties of Rogers semilattices of arithmetical numberings
No full textWe investigate initial segments and intervals of Rogers semilattices of arithmetical families. We prove that there exist intervals with different algebraic properties; the elementary theory of any Rogers semilattice at arithmetical level n ≥ 2 is hereditarily undecidable; the class of all Rogers semilattices of a fixed level n ≥ 2 has an incomplete theory
Completeness and universality of arithmetical numberings
No full textAbstract We investigate completeness and universality notions, relative to differ-ent oracles, and the interconnection between these notions, with applica-tions to arithmetical numberings. We prove that principal numberings are complete; completeness is independent of the oracle; the degree of any incomplete numbering is meet-reducible, uniformly complete num-berings exist. We completely characterize which finite arithmetical fam-ilies have a universal numbering
Friedberg numberings in the Ershov hierarchy
No full textWe show that for every n 1, there exists a 1n -computable family which up to equivalence has exactly one Friedberg numbering which does not induce the least element of the corresponding Rogers semilattice
Elementary properties of Rogers semilattices of arithmetical numberings
No full textWe investigate differences in the elementary theories
of Rogers semilattices of arithmetical numberings, depending on
structural invariants of the given families of arithmetical sets.
It is shown that at any fixed level of the arithmetical hierarchy
there exist infinitely many families with pairwise elementary
different Rogers semilattices
- …
