9,290 research outputs found
The enumeration degrees of the Sigma_2^0 sets
No full textWe give a survey of some recent results on the enumeration degrees of the Sigma_2^0 set
Effective inseparability, lattices, and preordering relations
No full textWe study effectively inseparable (abbreviated as e.i.) prelattices. Solving a problem raised by Montagna and Sorbi (1985) we show that if L is an e.i. prelattice then the preordering relation of L is universal with respect to all c.e. pre-ordering relations. In fact it is locally universal, i.e. in any nonempty interval one can computably embed every c.e. pre-ordering relation. Also the preordering relation of L is uniformly dense. Some consequences and applications of these results are discussed, in particular to derive uniform density and local universality for certain prelattices of sentences arising in logic
Comparing Pi^0_2 of the Baire space by means of general recursive operators
No full textBy applying a notion of reducibility suggested by DiPaola and Heller to the domains of a recursion category previously introduced by ourselves, we get many-one reducibility between PI-2(0) sets of the arithmetical hierarchy of sets of functions by means of general recursive operators. We give a characterization of the complete domains in this reducibility. We also introduce an upper semilattice B to which this reducibility gives rise in a standard way. Several facts about B are proved: we characterize the finite ideals of B; the first order theory of B is shown to be undecidable
Self-full ceers and the uniform join operator
No full textA computably enumerable equivalence relation (ceer) is called self-full if whenever is a reduction of to then the range of intersects all -equivalence classes. It is known that the infinite self-full ceers properly contain the dark ceers, i.e. the infinite ceers which do not admit an infinite computably enumerable transversal. Unlike the collection of dark ceers, which are closed under the operation of uniform join, we answer a question raised by Andrews and Sorbi by showing that there are self-full ceers and so that their uniform join is non-self-full. We then define and examine the hereditarily self-full ceers, which are the self-full ceers so that for any self-full , is also self-full: we show that they are closed under uniform join, and that every non-universal degree in have infinitely many incomparable hereditarily self-full strong minimal covers. In particular, every non-universal ceer is bounded by a hereditarily self-full ceer. Thus the hereditarily self-full ceers form a properly intermediate class in between the dark ceers and the infinite self-full ceers which is closed under
Some remarks on the algebraic structure of the Medvedev Lattice
No full textThis paper investigates the algebraic structure of the Medvedev lattice M. We prove that M is not a Heyting algebra. We point out some relations between M and the Dyment lattice and the Mucnik lattice. Some properties of the degrees of enumerability are considered. We give also a result on embedding countable distributive lattices in the Medvedev lattice
Reducibility in some categories of partial recursive operators
No full textWe consider two categories with one object, namely the set of all partial functions of one variable from the set of natural numbers into itself; the morphisms are the partial recursive operators in one case, and certain continuous partial mappings in the other case. We show that these categories are recursion categories and we characterize the domains and the complete domains. Some observations are made on a notion of reducibility obtained by using the total morphisms of these categories, and, subsequently, the general recursive operators. MSC: 03D65, 03D45, 18B2
Numerazioni positive, r.e. classi e formule
No full textIn this paper we investigate some recursion-theoretic properties of the positive numerations induced by certain remarkable formulas of any theory T as strong as Peano Arithmetic: in particular we prove that any Sigma_n-truth predicate (in an appropriate sense) induces a precomplete positive numeration and that the formulas which preserve the provable equivalence induce u-m-v equivalence relations (and there exist formulas which induce u-m-c but not precomplete numerations). By means of theory of numerations, a classical result due to Putnam and Smullyan (1960) and redemonstrated by Smorynski (1978) is generalized
Jumps of computably enumerable equivalence relations
No full textWe study computably enumerable equivalence relations (or, ceers), under computable reducibility ≤, and the halting jump operation on ceers. We show that every jump is uniform join-irreducible, and thus join-irreducible. Therefore, the uniform join of two incomparable ceers is not equivalent to any jump. On the other hand there exist ceers that are not equivalent to jumps, but are uniform join-irreducible: in fact above any non-universal ceer there is a ceer which is not equivalent to a jump, and is uniform join-irreducible. We also study transfinite iterations of the jump operation. If a is an ordinal notation, and E is a ceer, then let E(a) denote the ceer obtained by transfinitely iterating the jump on E along the path of ordinal notations up to a. In contrast with what happens for the Turing jump and Turing reducibility, where if a set X is an upper bound for the A-arithmetical sets then X(2) computes A(ω), we show that there is a ceer R such that R≥Id(n), for every finite ordinal n, but, for all k, R(k)≱Id(ω) (here Id is the identity equivalence relation). We show that if a,b are notations of the same ordinal less than ω2, then E(a)≡E(b), but there are notations a,b of ω2 such that Id(a) and Id(b) are incomparable. Moreover, there is no non-universal ceer which is an upper bound for all the ceers of the form Id(a) where a is a notation for ω2
Universal recursion theoretic properties of r.e. preordered structures
No full textThe paper studies the natural version of m-reducibility between recursively enumerable preordered structures, and shows that many recursively enumerable preordered structures arising from logic are universal with respect to this reducibility
Classifying positive equivalence relations
No full textGiven two (positive) equivalence relations R,S on the set omega of natural
numbers, we say that R is m-reducible to S if there exists a total recursive function
h such that for every x, y in omega, we have x R y if hx S hy. We prove that the equivalence
relation induced in omega by a positive precomplete numeration is complete with
respect to this reducibility (and, moreover, a "uniformity property" holds). This result
allows us to state a classification theorem for positive equivalence relations. We show that there exist nonisomorphic positive equivalence relations which are
complete with respect to the above reducibility; in particular, we discuss the provable
equivalence of a strong enough theory: this relation is complete with respect to reducibility
but it does not correspond to a precomplete numeration.
From this fact we deduce that an equivalence relation on co can be strongly represented
by a formula if it is positive. At last, we interpret the situation
from a topological point of view. Among other things, we generalize a result of Visser
by showing that the topological space corresponding to a partition in e.i. sets is irreducible
and we prove that the set of equivalence classes of true sentences is dense
in the Lindenbaum algebra of the theory
- …
