共查询到20条相似文献,搜索用时 15 毫秒
1.
We show that each computably enumerable Turing degree is a degree of autostability relative to strong constructivizations for a decidable directed graph. We construct a decidable undirected graph whose autostability spectrum relative to strong constructivizations is equal to the set of all PA-degrees. 相似文献
2.
S. Barry Cooper 《Mathematical Logic Quarterly》1996,42(1):191-196
We prove that there exists a nonzero recursively enumerable Turing degree possessing a strong minimal cover. Mathematics Subject Classification: 03D30. 相似文献
3.
Cupping the Recursively Enumerable Degrees by D.R.E. Degrees 总被引:2,自引:0,他引:2
We prove that there are two incomplete d.r.e. degrees (the Turingdegrees of differences of two recursively enumerable sets) suchthat every non-zero recursively enumerable degree cups at leastone of them to 0', the greatest recursively enumerable (Turing)degree. 1991 Mathematics Subject Classification: primary 03D25,03D30; secondary 03D35. 相似文献
4.
O. V. Kudinov 《Algebra and Logic》1996,35(6):384-391
Established are (1) a nonuniform criterion for the stability of models in terms of enumeration reducibility of constructivizations;
(2) a criterion for the autostability of certain particular classes of models close to algebraic number fields; (3) a uniform
autostability of each 1-constructive model that is autostable.
Supported by RFFR grant No. 096-01-01525 and by ISF grant NQ 6000.
Translated fromAlgebra i Logika, Vol. 35, No. 6, pp. 685–698, November–December, 1996. 相似文献
5.
We establish that for every computably enumerable (c.e.) Turing degree b the upper cone of c.e. Turing degrees determined by b is the degree spectrum of the successor relation of some computable linear ordering. This follows from our main result, that
for a large class of linear orderings the degree spectrum of the successor relation is closed upward in the c.e. Turing degrees.
The authors acknowledge partial support by the NSF binational grant DMS-0554841, and Harizanov by the NSF grant DMS-0704256,
and Chubb by the Sigma Xi Grant in Aid of Research. 相似文献
6.
S. S. Goncharov 《Algebra and Logic》2009,48(6):410-417
We furnish an example of an Ehrenfeucht theory whose prime model is autostable under strong constructivizations and there
exists a prime model in a finite expansion by constants that is nonautostable under strong constructivizations of the theory
constructed. 相似文献
7.
Consider the Turing degrees of differences of recursively enumerable sets (the d-r.e. degrees). We show that there is a properly
d-r.e. degree (a d-r.e. degree that is not r.e.) between any two comparable r.e. degrees, and that given a high r.e. degreeh, every nonrecursive d-r.e. degree ≦h cups toh by a low d-r.e. degree.
The second author was partially supported by NSF grant DMS-8701891. 相似文献
8.
We give a proof of a theorem of Harrington that there is no orbit of the lattice of recursively enumerable sets containing elements of each nonzero recursively enumerable degree. We also establish some degree theoretical extensions. 相似文献
9.
10.
Stephan Wehner 《Proceedings of the American Mathematical Society》1998,126(7):2131-2139
It is proven that there is a family of sets of natural numbers which has enumerations in every Turing degree except for the recursive degree. This implies that there is a countable structure which has representations in all but the recursive degree. Moreover, it is shown that there is such a structure which has a recursively represented elementary extension.
11.
We characterize the recursively enumerable first order Gödel logics with △ with respect to validity and non-satisfiability. The finitely valued and four infinitely valued Gödel logics with △ are recursively enumerable, not-satisfiability is recursively enumerable if validity is recursively enumerable. This is in contrast to first order Gödel logics without △, where validity is recursively enumerable for finitely valued and two infinitely valued Gödel logics, not-satisfiability is recursively enumerable if validity is recursively enumerable or 0 isolated in the truth value set. 相似文献
12.
Every Set has a Least Jump Enumeration 总被引:1,自引:0,他引:1
Coles Richard J.; Downey Rod G.; Slaman Theodore A. 《Journal London Mathematical Society》2000,62(3):641-649
Given a computably enumerable set W, there is a Turing degreewhich is the least jump of any set in which W is computablyenumerable, namely 0'. Remarkably, this is not a phenomenonof computably enumerable sets. It is shown that for every subsetA of N, there is a Turing degree, c'µ(A), which is theleast degree of the jumps of all sets X for which A is . In addition this result providesan isomorphism invariant method for assigning Turing degreesto certain torsion-free abelian groups. 相似文献
13.
S. N. Manukian 《Journal of Mathematical Sciences》2005,130(2):4598-4606
Algebras of operations defined on recursively enumerable sets of different kinds are considered. Every such algebra is specified by a list of operations involved and a list of basic elements. An element of an algebra is said to be representable in this algebra if it can be obtained from given basic elements by operations of the algebra. Two kinds of recursively enumerable sets are considered: recursively enumerable sets in the usual sense and fuzzy recursively enumerable sets. On binary, i.e., two-dimensional recursively enumerable sets of these kinds, algebras of operations are introduced. An algebra θ is constructed in which all binary recursively enumerable sets are representable. A subalgebra θ0 of θ is constructed in which all binary recursively enumerable sets are representable if and only if they are described by formulas of Presburger’s arithmetic system. An algebra Ω is constructed in which all binary recursively enumerable fuzzy sets are representable. A subalgebra Ω0 of the algebra Ω is constructed such that fuzzy recursively enumerable sets representable in Ω0 can be treated as fuzzy counterparts of sets representable by formulas of Presburger’s system. Bibliography: 16 titles.__________Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 304, 2003, pp. 75–98. 相似文献
14.
Cupping partners of an element in an upper semilattice with a greatest element 1 are those joining the element to 1. We define a congruence relation on such an upper semilattice by considering the elements having the same cupping partners as equivalent. It is interesting that this congruence relation induces a non-dense quotient structure of computably enumerable Turing degrees. Another main interesting phenomenon in this article is that on the computably enumerable degrees, this relation is different from that modulo the noncuppable ideal, though they define a same equivalent class for the computable Turing degree. 相似文献
15.
Shamil Ishmukhametov 《Archive for Mathematical Logic》2000,39(3):145-154
Let d be a Turing degree, R[d] and Q[d] denote respectively classes of recursively enumerable (r.e.) and all degrees in which d is relatively enumerable. We proved in Ishmukhametov [1999] that there is a degree d containing differences of r.e.sets (briefly, d.r.e.degree) such that R[d] possess a least elementm
0. Now we show the existence of a d.r.e. d such that R[d] has no a least element. We prove also that for any REA-degree d below 0
the class Q[d] cannot have a least element and more generally is not bounded below by a non-zero degree, except in the trivial cases.
Received: 17 January 1996 相似文献
16.
Valeriy K. Bulitko 《Mathematical Logic Quarterly》2002,48(3):367-373
In this paper we consider the we known method by E. Post of solving the problem of construction of recursively enumerable sets that have a degree intermediate between the degrees of recursive and complete sets with respect to a given reducibility. Post considered reducibilities ≤m, ≤btt, ≤tt and ≤T and solved the problem for al of them except ≤T. Here we extend Post's original method of construction of incomplete sets onto two wide classes of sub‐Turing reducibilities what were studying in [1, 2]. 相似文献
17.
A suitable measure for the similarity of shapes represented by parameterized curves or surfaces is the Fréchet distance. Whereas
efficient algorithms are known for computing the Fréchet distance of polygonal curves, the same problem for triangulated surfaces
is NP-hard. Furthermore, it remained open whether it is computable at all.
Using a discrete approximation, we show that it is upper semi-computable, i.e., there is a non-halting Turing machine which produces a decreasing sequence of rationals converging to the Fréchet
distance. It follows that the decision problem, whether the Fréchet distance of two given surfaces lies below a specified
value, is recursively enumerable. 相似文献
18.
The terms of the upper and lower central series of a nilpotent computable group have computably enumerable Turing degree. We show that the Turing degrees of these terms are independent even when restricted to groups which admit computable orders. 相似文献
19.
Andr Nies 《Mathematical Logic Quarterly》1994,40(4):490-518
We investigate the upper semilattice Eq* of recursively enumerable equivalence relations modulo finite differences. Several natural subclasses are shown to be first-order definable in Eq*. Building on this we define a copy of the structure of recursively enumerable many-one degrees in Eq*, thereby showing that Th(Eq*) has the same computational complexity as the true first-order arithmetic. Mathematics Subject Classification: 03D25, 03D15, 03D35. 相似文献
20.
We introduce techniques that allow us to embed below an arbitary nonlow2 recursively enumerable degree any lattice currently known to be embeddable into the recursively enumerable degrees.
Research partially supported by NSF Grants DMS-9204308, DMS-93-44740, a US-NZ binational grant NSF 90-20558, the U.S. ARO
through ACSyAM at the Mathematical Sciences Institute of Cornell Univrsity Contract DAAL03-91-C-0027 and the IGC of Victoria
University. 相似文献