共查询到20条相似文献,搜索用时 203 毫秒
1.
S. Yu. Podzorov 《Algebra and Logic》2007,46(3):163-187
We deal with some upper semilattices of m-degrees and of numberings of finite families. It is proved that the semilattice
of all c.e. m-degrees, from which the greatest element is removed, is isomorphic to the semilattice of simple m-degrees, the
semilattice of hypersimple m-degrees, and the semilattice of Σ
2
0
-computable numberings of a finite family of Σ
2
0
-sets, which contains more than one element and does not contain elements that are comparable w.r.t. inclusion.
Supported by the Grant Council (under RF President) for Young Russian Scientists via project MK-1820.2005.1.
__________
Translated from Algebra i Logika, Vol. 46, No. 3, pp. 299–345, May–June, 2007. 相似文献
2.
Dieter Spreen 《Archive for Mathematical Logic》2005,44(2):209-217
A strong reducibility relation between partial numberings is introduced which is such that the reduction function transfers exactly the numbers which are indices under the numbering to be reduced into corresponding indices of the other numbering. The degrees of partial numberings of a given set with respect to this relation form an upper semilattice.In addition, Ershovs completion construction for total numberings is extended to the partial case: every partially numbered set can be embedded in a set which results from the given set by adding one point and which is enumerated by a total and complete numbering. As is shown, the degrees of complete numberings of the extended set also form an upper semilattice. Moreover, both semilattices are isomorphic.This is not so in the case of the usual, weaker reducibility relation for partial numberings which allows the reduction function to transfer arbitrary numbers into indices.This research has partially been supported by INTAS under grant 00-499 Computability in Hierarchies and Topological Spaces.Mathematics Subject Classification (2000): 03D45 相似文献
3.
Z. G. Khisamiev 《Algebra and Logic》2006,45(6):431-434
Any subfamily of a given at most countable non-empty family can be converted into a set of all special elements of a suitable
numbering.
__________
Translated from Algebra i Logika, Vol. 45, No. 6, pp. 758–764, November–December, 2006. 相似文献
4.
We establish a number of results on numberings, in particular, on Friedberg numberings, of families of d.c.e. sets. First, it is proved that there exists a Friedberg numbering of the family of all d.c.e. sets. We also show that this result, patterned on Friedberg's famous theorem for the family of all c.e. sets, holds for the family of all n-c.e. sets for any n>2. Second, it is stated that there exists an infinite family of d.c.e. sets without a Friedberg numbering. Third, it is shown that there exists an infinite family of c.e. sets (treated as a family of d.c.e. sets) with a numbering which is unique up to equivalence. Fourth, it is proved that there exists a family of d.c.e. sets with a least numbering (under reducibility) which is Friedberg but is not the only numbering (modulo reducibility). 相似文献
5.
We investigate differences in isomorphism types for Rogers semilattices of computable numberings of families of sets lying
in different levels of the arithmetical hierarchy.
Supported by RFBR grant No. 05-01-00819 and by INTAS grant No. 00-499.
Supported by NSFC grant No. 60310213.
__________
Translated from Algebra i Logika, Vol. 45, No. 6, pp. 637–654, November–December, 2006. 相似文献
6.
7.
D. A. Tusupov 《Algebra and Logic》2007,46(4):281-286
The paper deals in questions on the complexity of isomorphisms and relations on universes of structures, on the number and
properties of numberings in various hierarchies of sets, and on the existence of connections between semantic and syntactic
properties of the structures and relations for the class of nilpotent groups of class two.
Supported by the Council for Grants (under RF President) and State Aid of Fundamental Science Schools via project NSh-4413.2006.1.
__________
Translated from Algebra i Logika, Vol. 46, No. 4, pp. 514–524, July–August, 2007. 相似文献
8.
The different behaviour of total and partial numberings with respect to the reducibility preorder is investigated. Partial numberings appear quite naturally in computability studies for topological spaces. The degrees of partial numberings form a distributive lattice which in the case of an infinite numbered set is neither complete nor contains a least element. Friedberg numberings are no longer minimal in this situation. Indeed, there is an infinite descending chain of non‐equivalent Friedberg numberings below every given numbering, as well as an uncountable antichain. (© 2005 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim) 相似文献
9.
We introduce a new upper bound for the maximum-entropy sampling problem. Our bound is described as the solution of a linear
integer program. The bound depends on a partition of the underlying set of random variables. For the case in which each block
of the partition has bounded cardinality, we describe an efficient dynamic-programming algorithm to calculate the bound. For
the very special case in which the blocks have no more than two elements, we describe an efficient algorithm for calculating
the bound based on maximum-weight matching. This latter formulation has particular value for local-search procedures that
seek to find a good partition. We relate our bound to recent bounds of Hoffman, Lee and Williams. Finally, we report on the
results of some computational experiments.
Received: September 27, 2000 / Accepted: July 26, 2001 Published online: September 5, 2002
Key words. experimental design – design of experiments – entropy – maximum-entropy sampling – matching – integer program – spectral
bound – Fischer's inequality – branch-and-bound – dynamic programming
Mathematics Subject Classification (2000): 52B12, 90C10
Send offprint requests to: Jon Lee
Correspondence to: Jon Lee 相似文献
10.
We determine upper bounds for the least radius of a ball in which a given set is a Pompeiu set (the set considered is a half
right circular cone). The obtained estimates significantly improve known results.
Translated from Ukrains’kyi Matematychnyi Zhurnal, Vol. 61, No. 1, pp. 61–72, January, 2009. 相似文献
11.
We prove that a broad class of systems of equations have endomorphisms of negative numberings as solutions. Moreover, we prove that if the endomorphisms of a numbering uniformly solve this class of systems of equations and have the separability property then the numbering is negative. 相似文献
12.
V. G. Puzarenko 《Algebra and Logic》2002,41(5):314-322
The article deals in the numbering theory for admissible sets, brought in sight in [1]. For models of two special classes, we resolve the problem of there being 1-1 computable numberings of the families of all computable sets and of all computable functions. In proofs, for the former case the role of finite objects is played by syntactic constructions, and for the latter — by finite subsets on hereditarily finite superstructures. 相似文献
13.
An effectively closed set, or class, may viewed as the set of infinite paths through a computable tree. A numbering, or enumeration, is a map from ω onto a countable collection of objects. One numbering is reducible to another if equality holds after the
second is composed with a computable function. Many commonly used numberings of classes are shown to be mutually reducible via a computable permutation. Computable injective numberings are given for the
family of classes and for the subclasses of decidable and of homogeneous classes. However no computable numberings exist for small or thin classes. No computable numbering of trees exists that includes
all computable trees without dead ends.
Research partially supported by National Science Foundation grants DMS 0554841, 0532644 and 0652732. 相似文献
14.
A sufficient condition is given under which an infinite computable family of Σ-1
a
-sets has computable positive but undecidable numberings, where a is a notation for a nonzero computable ordinal. This extends a theorem proved for finite levels of the Ershov hierarchy in
[1]. As a consequence, it is stated that the family of all Σ-1
a
-sets has a computable positive undecidable numbering. In addition, for every ordinal notation a > 1, an infinite family of Σ-1
a
-sets is constructed which possesses a computable positive numbering but has no computable Friedberg numberings. This answers
the question of whether such families exist at any—finite or infinite—level of the Ershov hierarchy, which was originally
raised by Badaev and Goncharov only for the finite levels bigger than 1. 相似文献
15.
M. Kh. Faizrakhmanov 《Russian Mathematics (Iz VUZ)》2011,55(1):74-78
We prove that a partially ordered set of all computably enumerable (c. e.) degrees that are the least upper bounds of two superlow c. e. degrees is an upper semilattice not elementary equivalent to the semilattice of all c. e. degrees. 相似文献
16.
In an N-dimensional space, we consider the approximation of classes of translation-invariant periodic functions by a linear operator
whose kernel is the product of two kernels one of which is positive. We establish that the least upper bound of this approximation
does not exceed the sum of properly chosen least upper bounds in m-and ((N − m))-dimensional spaces. We also consider the cases where the inequality obtained turns into the equality.
__________
Translated from Ukrains’kyi Matematychnyi Zhurnal, Vol. 58, No. 1, pp. 12–19, January, 2006. 相似文献
17.
18.
19.
Let S
d-1 denote the (d − 1)-dimensional unit sphere centered at the origin of the d-dimensional Euclidean space. Let 0 < α < π. A set P of points in S
d-1 is called almost α-equidistant if among any three points of P there is at least one pair lying at spherical distance α. In
this note we prove upper bounds on the cardinality of P depending only on d.
This revised version was published online in August 2006 with corrections to the Cover Date. 相似文献
20.
Keith Johnson 《Journal of Algebraic Combinatorics》2009,30(2):233-253
If R is a Dedekind domain, P a prime ideal of R and S⊆R a finite subset then a P-ordering of S, as introduced by M. Bhargava in (J. Reine Angew. Math. 490:101–127, 1997), is an ordering {a
i
}
i=1
m
of the elements of S with the property that, for each 1<i≤m, the choice of a
i
minimizes the P-adic valuation of ∏
j<i
(s−a
j
) over elements s∈S. If S, S
′ are two finite subsets of R of the same cardinality then a bijection φ:S→S
′ is a P-ordering equivalence if it preserves P-orderings. In this paper we give upper and lower bounds for the number of distinct P-orderings a finite set can have in terms of its cardinality and give an upper bound on the number of P-ordering equivalence classes of a given cardinality. 相似文献