共查询到20条相似文献,搜索用时 15 毫秒
1.
L.R. Galminas 《Archive for Mathematical Logic》2000,39(8):605-629
Downey and Remmel have completely characterized the degrees of c.e. bases for c.e. vector spaces (and c.e. fields) in terms
of weak truth table degrees. In this paper we obtain a structural result concerning the interaction between the c.e. Turing
degrees and the c.e. weak truth table degrees, which by Downey and Remmel's classification, establishes the existence of c.e.
vector spaces (and fields) with the strong antibasis property (a question which they raised). Namely, we construct c.e. sets
such that the c.e. W-degrees below that of A are disjoint from the nonzero c.e. T-degrees below that of A and comparable to that of B.
Received: 2 December 1998 相似文献
2.
We study the filter ℒ*(A) of computably enumerable supersets (modulo finite sets) of an r-maximal set A and show that, for some such set A, the property of being cofinite in ℒ*(A) is still Σ0
3-complete. This implies that for this A, there is no uniformly computably enumerable “tower” of sets exhausting exactly the coinfinite sets in ℒ*(A).
Received: 6 November 1999 / Revised version: 10 March 2000 /?Published online: 18 May 2001 相似文献
3.
Marat M. Arslanov Iskander Sh. Kalimullin Andrea Sorbi 《Archive for Mathematical Logic》2001,40(8):597-614
We show that the Δ0
2 enumeration degrees are dense. We also show that for every nonzero n-c. e. e-degree a, with n≥ 3, one can always find a nonzero 3-c. e. e-degree b such that b < a on the other hand there is a nonzero ωc. e. e-degree which bounds no nonzero n-c. e. e-degree.
Received: 13 June 2000 / Published online: 3 October 2001 相似文献
4.
Adam R. Day 《Annals of Pure and Applied Logic》2010,161(12):1588-1602
The computable Lipschitz reducibility was introduced by Downey, Hirschfeldt and LaForte under the name of strong weak truth-table reducibility (Downey et al. (2004) [6]). This reducibility measures both the relative randomness and the relative computational power of real numbers. This paper proves that the computable Lipschitz degrees of computably enumerable sets are not dense. An immediate corollary is that the Solovay degrees of strongly c.e. reals are not dense. There are similarities to Barmpalias and Lewis’ proof that the identity bounded Turing degrees of c.e. sets are not dense (George Barmpalias, Andrew E.M. Lewis (2006) [2]), however the problem for the computable Lipschitz degrees is more complex. 相似文献
5.
We study the computably enumerable sets in terms of the: 相似文献
6.
We 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 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 computes , we show that there is a ceer R such that , for every finite ordinal n, but, for all k, (here Id is the identity equivalence relation). We show that if are notations of the same ordinal less than , then , but there are notations of such that and are incomparable. Moreover, there is no non-universal ceer which is an upper bound for all the ceers of the form where a is a notation for . 相似文献
7.
Frank Stephan 《Archive for Mathematical Logic》2001,40(7):489-513
One-sided classifiers are computable devices which read the characteristic function of a set and output a sequence of guesses
which converges to 1 iff the set on the input belongs to the gven class. Such a classifier istwo-sided if the sequence of
its output in addition converges to 0 on setsnot belonging to the class. The present work obtains the below mentionedresults
for one-sided classes (= Σ0
2 classes) with respect to four areas: Turing complexity, 1-reductions, index sets and measure.
There are one-sided classes which are not two-sided. This can have two reasons: (1) the class has only high Turing complexity.
Then there are some oracles which allow to construct noncomputale two-sided classifiers. (2) The class is difficult because
of some topological constraints and then there are also no nonrecursive two-sided classifiers. For case (1), several results
are obtainedto localize the Turing complexity of certain types of one-sided classes.
The concepts of 1-reduction, 1-completeness and simple sets is transferred to one-sided classes: There are 1-complete classes
and simple classes, but no class is at the same time 1-complete nd simple.
The one-sided classes have a natural numbering. Most of the common index sets relative to this numbering have the high complexity
Π1
1: the index set of the class {0,1}∞, the index set of the equality problem and the index set of all two-sided classes. On the other side the index set of the
empty class has complexity Π0
2; Π0
2 and Σ0
2 are the least complexities any nontrivial index set can have.
Lusin showed that any one-sided class is measurable. Concerning the effectiveness of this measure, it is shown that a one-sided
class has recursive measure 0 if it has measure 0, but that thre are one-sided classes having measure 1 without having measure
1 effectively. The measure of a two-sided class can be computed in the limit.
Received: 2 December 1999 / Revised version: 28 February 2000 / Published online: 15 June 2001 相似文献
8.
We investigate the index sets associated with the degree structures of computable sets under the parameterized reducibilities
introduced by the authors. We solve a question of Peter Cholakand the first author by proving the fundamental index sets associated
with a computable set A, {e : W
e
≤
q
u
A} for q∈ {m, T} are Σ4
0 complete. We also show hat FPT(≤
q
n
), that is {e : W
e
computable and ≡
q
n
?}, is Σ4
0 complete. We also look at computable presentability of these classes.
Received: 13 July 1996 / Revised version: 14 April 2000 / Published online: 18 May 2001 相似文献
9.
Gilles Pisier 《Mathematische Zeitschrift》2000,235(1):53-81
For every integer , there is a unital closed subalgebra with similarity degree equal precisely to d, in the sense of our previous paper. This means that for any unital homomorphism we have with independent of u, and the exponent d in this estimate cannot be improved. The proof that the degree is larger than crucially uses an upper bound for the norms of certain Gaussian random matrices due to Haagerup and Thorbj?rnsen. We also
include several complements to our previous publications on the same subject.
Received: 25 April, 1999; Accepted: 23 June, 1999 相似文献
10.
A class K of structures is controlled if, for all cardinals λ, the relation of L
∞,λ-equivalence partitions K into a set of equivalence classes (as opposed to a proper class). We prove that the class of doubly transitive linear orders
is controlled, while any pseudo-elementary class with the ω-independence property is not controlled.
Received: 23 September 1998 / Revised version: 6 July 1999 / Published online: 21 December 2000 相似文献
11.
George Davie 《Archive for Mathematical Logic》2001,40(8):629-638
Let ω be a Kolmogorov–Chaitin random sequence with ω1:
n
denoting the first n digits of ω. Let P be a recursive predicate defined on all finite binary strings such that the Lebesgue measure of the set {ω|∃nP(ω1:
n
)} is a computable real α. Roughly, P holds with computable probability for a random infinite sequence. Then there is an algorithm which on input indices for any
such P and α finds an n such that P holds within the first n digits of ω or not in ω at all. We apply the result to the halting probability Ω and show that various generalizations of
the result fail.
Received: 1 December 1998 / Published online: 3 October 2001 相似文献
12.
For arbitrary finite group and countable Dedekind domain such that the residue field is finite for every maximal -ideal , we show that the localizations at every maximal ideal of two -lattices are isomorphic if and only if the two lattices satisfy the same first order sentences. Then we investigate generalizations
of the above results to arbitrary -torsion-free -modules and we apply the previous results to show the decidability of the theory of -lattices. Eventually, we show that -lattices have undecidable theory.
Received November 28, 1995 相似文献
13.
Alex M. McAllister 《Archive for Mathematical Logic》2001,40(3):147-165
Continuing work begun in [10], we utilize a notion of forcing for which the generic objects are structures and which allows
us to determine whether these “generic” structures compute certain sets and enumerations. The forcing conditions are bounded
complexity types which are consistent with a given theory and are elements of a given Scott set. These generic structures
will “represent” this given Scott set, in the sense that the structure has a certain weak saturation property with respect
to bounded complexity types in the Scott set. For example, if ? is a nonstandard model of PA, then ? represents the Scott
set ? = n∈ω | ?⊧“the nth prime divides a” | a∈?.
The notion of forcing yields two main results. The first characterizes the sets of natural numbers computable in all models
of a given theory representing a given Scott set. We show that the characteristic function of such a set must be enumeration
reducible to a complete existential type which is consistent with the given theory and is an element of the given Scott set.
The second provides a sufficient condition for the existence of a structure ? such that ? represents a countable jump ideal
and ? does not compute an enumeration of a given family of sets ?. This second result is of particular interest when the family
of sets which cannot be enumerated is ? = Rep[Th(?)]. Under this additional assumption, the second result generalizes a result on TA [6] and on certain other completions
of PA [10]. For example, we show that there also exist models of completions of ZF from which one cannot enumerate the family
of sets represented by the theory.
Received: 8 October 1997 / Published online: 25 January 2001 相似文献
14.
Silvio Valentini 《Archive for Mathematical Logic》2001,40(7):475-488
We provide a new and elementary proof of strong normalization for the lambda calculus of intersection types. It uses no strong
method, like for instance Tait-Girard reducibility predicates, but just simple induction on type complexity and derivation length and thus it is obviously formalizable within first order
arithmetic. To obtain this result, we introduce a new system for intersection types whose rules are directly inspired by the
reduction relation. Finally, we show that not only the set of strongly normalizing terms of pure lambda calculus can be characterized
in this system, but also that a straightforward modification of its rules allows to characterize the set of weakly normalizing
terms.
Received: 15 June 1998 / Revised version: 15 November 1999 / Published online: 15 June 2001 相似文献
15.
Jan von Plato 《Archive for Mathematical Logic》2001,40(7):541-567
The structure of derivations in natural deduction is analyzed through isomorphism with a suitable sequent calculus, with
twelve hidden convertibilities revealed in usual natural deduction. A general formulation of conjunction and implication elimination
rules is given, analogous to disjunction elimination. Normalization through permutative conversions now applies in all cases.
Derivations in normal form have all major premisses of elimination rules as assumptions. Conversion in any order terminates.
Through the condition that in a cut-free derivation of the sequent Γ⇒C, no inactive weakening or contraction formulas remain in Γ, a correspondence with the formal derivability relation of natural
deduction is obtained: All formulas of Γ become open assumptions in natural deduction, through an inductively defined translation.
Weakenings are interpreted as vacuous discharges, and contractions as multiple discharges. In the other direction, non-normal
derivations translate into derivations with cuts having the cut formula principal either in both premisses or in the right
premiss only.
Received: 1 December 1998 / Revised version: 30 June 2000 / Published online: 18 July 2001 相似文献
16.
Todd Eisworth 《Archive for Mathematical Logic》2001,40(3):235-242
We investigate a two-player game involving pairs of filters on ω. Our results generalize a result of Shelah ([7] Chapter
VI) dealing with applications of game theory in the study of ultrafilters.
Received: 28 September 1998 / Published online: 25 January 2001 相似文献
17.
Heike Mildenberger 《Archive for Mathematical Logic》2001,40(2):93-112
We show that the Filter Dichotomy Principle implies that there are exactly four classes of ideals in the set of increasing
functions from the natural numbers. We thus answer two open questions on consequences of ? < ?. We show that ? < ? implies
that ? = ?, and that Filter Dichotomy together with ? < ? implies ? < ?. The technical means is the investigation of groupwise
dense sets, ideals, filters and ultrafilters. With related techniques we prove the new inequality ?≤ cf(?).
Received: 9 October 1998 / Revised version: 18 August 1999 / Published online: 21 December 2000 相似文献
18.
The axiom of choice is equivalent to the shrinking principle: every indexed cover of a set has a refinement with the same
index set which is a partition. A simple and direct proof of this equivalence is given within an elementary fragment of constructive
Zermelo–Fraenkel set theory. Variants of the shrinking principle are discussed, and it is related to a similar but different
principle formulated by Vaught. 相似文献
19.
Toshiyuki Sugawa 《Mathematische Zeitschrift》2001,238(2):317-333
A compact set C in the Riemann sphere is called uniformly perfect if there is a uniform upper bound on the moduli of annuli which separate
C. Julia sets of rational maps of degree at least two are uniformly perfect. Proofs have been given independently by Ma né
and da Rocha and by Hinkkanen, but no explicit bounds are given. In this note, we shall provide such an explicit bound and,
as a result, give another proof of uniform perfectness of Julia sets of rational maps of degree at least two. As an application,
we provide a lower estimate of the Hausdorff dimension of the Julia sets. We also give a concrete bound for the family of
quadratic polynomials in terms of the parameter c.
Received: 7 June 1999; in final form: 9 November 1999 / Published online: 17 May 2001 相似文献
20.
Kyriakos Keremedis 《Archive for Mathematical Logic》2001,40(8):569-580
We show that some well known theorems in topology may not be true without the axiom of choice.
Received: 29 August 1995 / Revised version: 23 June 2000 / Published online: 3 October 2001 相似文献