1,721,025 research outputs found
On some filters and ideals of the Medvedev lattice
No full textLet M be the Medvedev lattice: this paper investigates some filters
and ideals (most of them already introduced by Dyment). If X is any
of the filters or ideals considered, the questions concerning which we try to
answer are: (1) is X prime? What is the cardinality of M/X ? Occasionally, we
point out some general facts on the T-degrees or the partial degrees, by which
these questions can be answered
∑0n-equivalence relations
No full textThe paper investigates arithmetical equivalence relations. In particular it introduces the Sigma_0^n-precomplete equivalence relations, with n>0, and shows that they are universal with respect to the computable reducibility of equivalence relations on the natural numbers
Sets of generators and automorphism bases for the enumeration degrees
No full textWe exhibit some automorphism bases for the enumeration degrees, and we derive some consequences relative to the automorphisms of the enumeration degrees. (C) 1998 Elsevier Science B.V. All rights reserved
Embedding Brouwer algebras in the Medvedev lattice
No full textWe prove various results on embedding Brouwer algebras in the
Medvedev lattice. In particular, we characterize the finite Brouwer algebras
that are embeddable in the Medvedev lattice
On Quasi-Minimal E-Degrees And Total e-Degrees
No full textThe paper show that there exist sets A such that the e-degree of A isquasi-minimal and the e-degree of the complement of A is total
Embeddings into the enumeration degrees
No full textWe give a proof of the fact that in every nonempty interval of enumeration degrees one can embed every countable partial order
Some Quotient Lattices of the Medvedev Lattice
No full textThe paper investigates some quotient lattices of the Medeved lattice and of the Muchnik lattice. Typical questions are: Is the quotient a Brouwer algebra? If so, which Brower algebras can be embedded in it, and what are the propositional identities
A note on closed degrees of difficulty of the Medvedev lattice
No full textWe consider some nonprincipal filters of the Medvedev lattice. We prove that the filter generated by the nonzero closed degrees of difficulty is not principal and we compare this filter, with respect to inclusion, with some other filters of the lattice. All the filters considered in this paper are disjoint from the prime ideal generated by the dense degrees of difficulty
Bounded enumeration reducibility and its degree structure
No full textWe study a strong enumeration reducibility, called bounded enumeration reducibility and denoted by , which is a natural extension of -reducibility . We show that , , and enumeration reducibility do not coincide on the -sets, and the structure
of the \be-degrees is not elementarily
equivalent to the structure of the --degrees. We show also that the first order theory of is computably
isomorphic to true second order arithmetic: this answers an open question raised by Cooper
Branching in the enumeration degrees of the Σ02sets
No full textWe show that every incomplete Sigma_0^2 enumeration degree is meet-reducible in the structure of the enumeration degrees of the Sigma(2)(0) sets
- …
