bluuebunny/crossref_metadata_2025_split huggingface dataset:
Every 2-random real is Kolmogorov random
Authors: Miller Joseph S. 
Published: March 2005

Abstract.We study reals with infinitely many incompressible prefixes. Call A ∈ 2ωKolmogorov random if . where C denotes plain Kolmogorov complexity. This property was suggested by Loveland and studied by Martin-Löf. Schnorr and Solovay. We prove that 2-random reals are Kolmogorov random. Together with the converse—proved by Nies. Stephan and Terwijn [11]—this provides a natural characterization of 2-randomness in terms of plain complexity. We finish with a related characterization of 2-randomness.
Almost everywhere domination
Authors: Dobrinen Natasha L. , Simpson Stephen G. 
Published: March 2005

Abstract.A Turing degree a is said to be almost everywhere dominating if, for almost all X ∈ 2ω with respect to the “fair coin” probability measure on 2ω, and for all g: ω → ω Turing reducible to X, there exists f: ω → ω of Turing degree a which dominates g. We study the problem of characterizing the almost everywhere dominating Turing degrees and other, similarly defined classes of Turing degrees. We relate this problem to some questions in the reverse mathematics of measure theory.
Theories of presheaf type
Authors: Beke Tibor 
Published: March 2005

Let us say that a geometric theory T is of presheaf type if its classifying topos is (equivalent to) a presheaf topos. (We adhere to the convention that geometric logic allows arbitrary disjunctions, while coherent logic means geometric and finitary.) Write Mod(T) for the category of Set-models and homomorphisms of T. The next proposition is well known; see, for example, MacLane–Moerdijk [13], pp. 381-386, and the textbook of Adámek–Rosický [1] for additional information:Proposition 0.1. For a category , the following properties are equivalent:(i) is a finitely accessible category in the sense of Makkai–Paré [14], i.e., it has filtered colimits and a small dense subcategory of finitely presentable objectsii) is equivalent to Pts, the category of points of some presheaf topos(iii) is equivalent to the free filtered cocompletion (also known as Ind-) of a small category .(iv) is equivalent to Mod(T) for some geometric theory of presheaf type.Moreover, if these are satisfied for a given , then the —in any of (i), (ii) and (iii)—can be taken to be the full subcategory of consisting of finitely presentable objects. (There may be inequivalent choices of , as it is in general only determined up to idempotent completion; this will not concern us.)This seems to completely solve the problem of identifying when T is of presheaf type: check whether Mod(T) is finitely accessible and if so, recover the presheaf topos as Set-functors on the full subcategory of finitely presentable models. There is a subtlety here, however, as pointed out (probably for the first time) by Johnstone [10].
A structural investigation on formal topology: coreflection of formal covers and exponentiability
Authors: Maietti Maria Emilia , Valentini Silvio 
Published: March 2005

Abstract.We present and study the category of formal topologies and some of its variants. Two main results are proven. The first is that, for any inductively generated formal cover, there exists a formal topology whose cover extends in the minimal way the given one. This result is obtained by enhancing the method for the inductive generation of the cover relation by adding a coinductive generation of the positivity predicate. Categorically, this result can be rephrased by saying that inductively generated formal topologies are coreflective into inductively generated formal covers.The second result is that unary formal covers are exponentiable in the category of inductively generated formal covers and hence, thanks to the coreflection, unary formal topologies are exponentiable in the category of inductively generated formal topologies.From a localic point of view the exponentiability of unary formal topologies means that algebraic dcpos are exponentiable in the category of open locales. But, the coreflection theorem states that open locales are coreflective in locales and hence, as a consequence of well-known impredicative results on exponentiable locales, it allows to prove that locally compact open locales are exponentiable in the category of open locales.
Elimination theory for addition and the frobenius map in polynomial rings
Authors: Pheidas Thanases , Zahidi Karim 
Published: March 2005

Abstract.We develop an elimination theory for addition and the Frobenius map over rings of polynomials. As a consequence we show that if F is a countable, recursive and perfect field of positive characteristic p, with decidable theory, then the structure of addition, the Frobenius map x → xp and the property ‘x ∈ F1, over the ring of polynomials F[T], has a decidable theory.
Higher-order semantics and extensionality
Authors: Benzmüller Christoph , Brown Chad E. , Kohlhase Michael 
Published: March 2005

Abstract.In this paper we re-examine the semantics of classical higher-order logic with the purpose of clarifying the role of extensionality. To reach this goal, we distinguish nine classes of higher-order models with respect to various combinations of Boolean extensionality and three forms of functional extensionality. Furthermore, we develop a methodology of abstract consistency methods (by providing the necessary model existence theorems) needed to analyze completeness of (machine-oriented) higher-order calculi with respect to these model classes.
Comparing DNR and WWKL
Authors: Ambos-Spies Klaus , Kjos-Hanssen Bjørn , Lempp Steffen , Slaman Theodore A. 
Published: March 2005

Abstract.In Reverse Mathematics, the axiom system DNR. asserting the existence of diagonally non-recursive functions, is strictly weaker than WWKL0 (weak weak König's Lemma).
A finite model-theoretical proof of a property of bounded query classes within PH
Authors: Kołodziejczyk Leszek Aleksander 
Published: March 2005

Abstract.We use finite model theory (in particular, the method of FM-truth definitions, introduced in [MM01] and developed in [K04], and a normal form result akin to those of [Ste93] and [G97]) to prove:Let m ≥ 2. Then:(A) If there exists k such that NP⊆ Σm TIME(nk)∩ Πm TIME(nk), then for every r there exists kr such that :(B) If there exists a superpolynomial time-constructible function f such that NTIME(f), then additionally .This strengthens a result by Mocas [M96] that for any r, .In addition, we use FM-truth definitions to give a simple sufficient condition for the arity hierarchy to be strict over finite models.
Bounding prime models
Authors: Csima Barbara F. , Hirschfeldt Denis R. , Knight Julia F. , Soare Robert I. 
Published: March 2005

Abstract.A set X is prime bounding if for every complete atomic decidable (CAD) theory T there is a prime model of T decidable in X. It is easy to see that X = 0′ is prime bounding. Denisov claimed that every X <T 0′ is not prime bounding, but we discovered this to be incorrect. Here we give the correct characterization that the prime bounding sets X ≤τ 0′ are exactly the sets which are not low2. Recall that X is low2 if X″ ≤τ 0″. To prove that a low2 set X is not prime bounding we use a 0′ -computable listing of the array of sets {Y : Y ≤τX } to build a CAD theory T which diagonalizes against all potential X-decidable prime models of T, To prove that any non-low2X is indeed prime bounding. we fix a function f ≤TX that is not dominated by a certain 0′-computable function that picks out generators of principal types. Given a CAD theory T. we use f to eventually find, for every formula φ(x̄) con sistent with T. a principal type which contains it. and hence to build an X-decidable prime model of T. We prove the prime bounding property equivalent to several other combinatorial properties, including some related to the limitwise monotonic functions which have been introduced elsewhere in computable model theory.
Bi-coloured fields on the complex numbers
Authors: Zilber B. 
Published: March 2005

Abstract.We consider two theories of “bad fields” constructed by B.Poizat using Hrushovski's amalgamation and show that these theories have natural models representable as the field of complex numbers with a distinguished subset given as a union of countably many real analytic curves. One of the two examples is based on the complex exponentiation and the proof assumes Schanuel's conjecture.
Some model theory of sheaves of modules
Authors: Prest Mike , Puninskaya Vera , Ralph Alexandra 
Published: March 2005

Abstract.We explore some topics in the model theory of sheaves of modules. First we describe the formal language that we use. Then we present some examples of sheaves obtained from quivers. These, and other examples, will serve as illustrations and as counterexamples. Then we investigate the notion of strong minimality from model theory to see what it means in this context. We also look briefly at the relation between global, local and pointwise versions of properties related to acyclicity.
Generalized high degrees have the complementation property
Authors: Greenberg Noam , Montalbán Antonio , Shore Richard A. 
Published: March 2005

Abstract.We show that if d ∈ GH1 then (≤ d) has the complementation property, i.e., for all a < d there is some b < d such that a ∧ b = 0 and a ∨ b = d.
Coordinatisation by binding groups and unidimensionality in simple theories
Authors: Shami Ziv 
Published: March 2005

Abstract.In a simple theory with elimination of finitary hyperimaginaries if tp(a) is real and analysable over a definable set Q, then there exists a finite sequence (ai \ i ≤ n*) ⊆ dcleq(a) with an* = a such that for every i ≤ n* if pi = tp(ai/{aj |j < i}) then Aut(pi / Q) is type-definable with its action on . A unidimensional simple theory eliminates the quantifier ∃∞ and either interprets (in Ceq) an infinite type-definable group or has the property that ACL(Q) = C for every infinite definable set Q.
Local homogeneity
Authors: Baizhanov Bektur , Baldwin John T. 
Published: March 2005

Abstract.We study the expansion of stable structures by adding predicates for arbitrary subsets. Generalizing work of Poizat-Bouscaren on the one hand and Baldwin-Benedikt-Casanovas-Ziegler on the other we provide a sufficient condition (Theorem 4.7) for such an expansion to be stable. This generalization weakens the original definitions in two ways: dealing with arbitrary subsets rather than just submodels and removing the ‘small’ or ‘belles paires’ hypothesis. We use this generalization to characterize in terms of pairs, the ‘triviality’ of the geometry on a strongly minimal set (Theorem 2.5). Call a set A benign if any type over A in the expanded language is determined by its restriction to the base language. We characterize the notion of benign as a kind of local homogenity (Theorem 1.7). Answering a question of [8] we characterize the property that M has the finite cover property over A (Theorem 3.9).
More on regular reduced products
Authors: Kennedy Juliette Cara , Shelah Saharon 
Published: March 2005

Abstract.The authors show, by means of a finitary version of the combinatorial principle of [7]. the consistency of the failure, relative to the consistency of supercompact cardinals, of the following: for all regular filters D on a cardinal λ. if Mi and Ni are elementarily equivalent models of a language of size ≤ λ, then the second player has a winning strategy in the Ehrenfeucht-Fraïssé game of length λ+ on ΠiMi/D and ΠiNi/D. If in addition 2λ = λ+ and i < λ implies |Mi| + |Ni| ≤ λ+ this means that the ultrapowers are isomorphic. This settles negatively conjecture 18 in [2].
Jonsson-like partition relations and j: V → V
Authors: Apter Arthur W. , Sargsyan Grigor 
Published: March 2005

Abstract.Working in the theory ”ZF + There is a nontrivial elementary embedding j : V → V“, we show that a final segment of cardinals satisfies certain square bracket finite and infinite exponent partition relations. As a corollary to this, we show that this final segment is composed of Jonsson cardinals. We then show how to force and bring this situation down to small alephs. A prototypical result is the construction of a model for ZF in which every cardinal μ ≥ ℵ2 satisfies the square bracket infinite exponent partition relation . We conclude with a discussion of some consistency questions concerning different versions of the axiom asserting the existence of a nontrivial elementary embedding j: V → V. By virtue of Kunen's celebrated inconsistency result, we use only a restricted amount of the Axiom of Choice.
Theories of arithmetics in finite models
Authors: Krynicki Michał , Zdanowski Konrad 
Published: March 2005

AbstractWe investigate theories of initial segments of the standard models for arithmetics. It is easy to see that if the ordering relation is definable in the standard model then the decidability results can be transferred from the infinite model into the finite models. On the contrary we show that the Σ2–theory of multiplication is undecidable in finite models. We show that this result is optimal by proving that the Σ1–theory of multiplication and order is decidable in finite models as well as in the standard model. We show also that the exponentiation function is definable in finite models by a formula of arithmetic with multiplication and that one can define in finite models the arithmetic of addition and multiplication with the concatenation operation.We consider also the spectrum problem. We show that the spectrum of arithmetic with multiplication and arithmetic with exponentiation is strictly contained in the spectrum of arithmetic with addition and multiplication.
Model completeness of o-minimal structures expanded by Dedekind cuts
Authors: Tressl Marcus 
Published: March 2005

§1. Introduction. LetMbe a totally ordered set. A (Dedekind) cutpofMis a couple (pL,pR) of subsetspL,pRofMsuch thatpL⋃pR=MandpL<pR, i.e.,a<bfor alla∈pL,b∈pR. In this article we are looking for model completeness results of o-minimal structuresMexpanded by a setpLfor a cutpofM. This means the following. LetMbe an o-minimal structure in the languageLand supposeMis model complete. LetDbe a new unary predicate and letpbe a cut of (the underlying ordered set of)M. Then we are looking for a natural, definable expansion of theL(D)-structure (M,pL) which is model complete.The first result in this direction is a theorem of Cherlin and Dickmann (cf. [Ch-Dic]) which says that a real closed field expanded by a convex valuation ring has a model complete theory. This statement translates into the cuts language as follows. IfZis a subset of an ordered setMwe writeZ+for the cutpwithpR= {a∈M∣a>Z} andZ−for the cutqwithqL= {a∈M∣a<Z}.
Generic substitutions
Authors: Panti Giovanni 
Published: March 2005

AbstractUp to equivalence, a substitution in propositional logic is an endomorphism of its free algebra. On the dual space, this results in a continuous function, and whenever the space carries a natural measure one may ask about the stochastic properties of the action. In classical logic there is a strong dichotomy: while over finitely many propositional variables everything is trivial, the study of the continuous transformations of the Cantor space is the subject of an extensive literature, and is far from being a completed task. In many-valued logic this dichotomy disappears: already in the finite-variable case many interesting phenomena occur, and the present paper aims at displaying some of these.
The finite model property for knotted extensions of propositional linear logic
Authors: van Alten C. J. 
Published: March 2005

AbstractThe logics considered here are the propositional Linear Logic and propositional Intuitionistic Linear Logic extended by a knotted structural rule: . It is proved that the class of algebraic models for such a logic has the finite embeddability property, meaning that every finite partial subalgebra of an algebra in the class can be embedded into a finite full algebra in the class. It follows that each such logic has the finite model property with respect to its algebraic semantics and hence that the logic is decidable.
The computable dimension of trees of infinite height
Authors: Miller Russell 
Published: March 2005

AbstractWe prove that no computable tree of infinite height is computably categorical, and indeed that all such trees have computable dimension ω. Moreover, this dimension is effectively ω, in the sense that given any effective listing of computable presentations of the same tree, we can effectively find another computable presentation of it which is not computably isomorphic to any of the presentations on the list.
Subsets of superstable structures are weakly benign
Authors: Baizhanov Bektur , Baldwin John T. , Shelah Saharon 
Published: March 2005

Baizhanov and Baldwin [1] introduce the notions of benign and weakly benign sets to investigate the preservation of stability by naming arbitrary subsets of a stable structure. They connect the notion with work of Baldwin, Benedikt, Bouscaren, Casanovas, Poizat, and Ziegler. Stimulated by [1], we investigate here the existence of benign or weakly benign sets.Definition 0.1. (1) The set A is benign in M if for every α, β ∊ M if p = tp(α/A) = tp(β/A) then tp*(α/A) = tp*(β/A) where the *-type is the type in the language L* with a new predicate P denoting A.(2) The set A is weakly benign in M if for every α,β ∊ M if p = stp(α/A) = stp(β/A) then tp*(α/A) = tp*(β/A) where the *-type is the type in language with a new predicate P denoting A.Conjecture 0.2 (too optimistic). If M is a model of stable theory T and A ⊆ M then A is benign.Shelah observed, after learning of the Baizhanov-Baldwin reductions of the problem to equivalence relations, the following counterexample.Lemma 0.3. There is an ω-stable rank 2 theory T with ndop which has a model M and set A such that A is not benign in M.
Computable categoricity of trees of finite height
Authors: Lempp Steffen , McCoy Charles , Miller Russell , Solomon Reed 
Published: March 2005

AbstractWe characterize the structure of computably categorical trees of finite height, and prove that our criterion is both necessary and sufficient. Intuitively, the characterization is easiest to express in terms of isomorphisms of (possibly infinite) trees, but in fact it is equivalent to a -condition. We show that all trees which are not computably categorical have computable dimension ω. Finally, we prove that for every n ≥ 1 in ω, there exists a computable tree of finite height which is Σ30-categorical but not Δn3-categorical
Interpolation for extended modal languages
Authors: ten Cate Balder 
Published: March 2005

AbstractSeveral extensions of the basic modal language are characterized in terms of interpolation. Our main results are of the following form: Language L′ is the least expressive extension of L with interpolation. For instance, let ℳ(D) be the extension of the basic modal language with a difference operator [7], First-order logic is the least expressive extension of ℳ(D) with interpolation. These characterizations are subsequently used to derive new results about hybrid logic, relation algebra and the guarded fragment.
On the weak non-finite cover property and the n-tuples of simple structures
Authors: Vassiliev Evgueni 
Published: March 2005

AbstractThe weak non-finite cover property (wnfcp) was introduced in [1] in connection with “axiomatizability” of lovely pairs of models of a simple theory. We find a combinatorial condition on a simple theory equivalent to the wnfcp, yielding a direct proof that the non-finite cover property implies the wnfcp, and that the wnfcp is preserved under reducts. We also study the question whether the wnfcp is preserved when passing from a simple theory T to the theory Tp of lovely pairs of models of T (true in the stable case). While the question remains open, we show, among other things, that if (for a T with the wnfcp) Tp is low, then TP has the wnfcp. To study this question, we describe “double lovely pairs”, and, along the way, we develop the notion of a “lovely n-tuple” of models of a simple theory, which is an analogue of the notion of a beautiful tuple of models of stable theories [2].
On the definable ideal generated by nonbounding c.e. degrees
Authors: Yu Liang , Yang Yue 
Published: March 2005

AbstractLet [NB]1 denote the ideal generated by nonbounding c.e. degrees and NCup the ideal of noncuppable c.e. degrees. We show that both [NB]1 ∩ NCup and the ideal generated by nonbounding and noncuppable degrees are new, in the sense that they are different from M, [NB]1 and NCup—the only three known definable ideals so far.
On an algebra of lattice-valued logic
Authors: Hansen Lars 
Published: March 2005

AbstractThe purpose of this paper is to present an algebraic generalization of the traditional two-valued logic. This involves introducing a theory of automorphism algebras, which is an algebraic theory of many-valued logic having a complete lattice as the set of truth values. Two generalizations of the two-valued case will be considered, viz., the finite chain and the Boolean lattice. In the case of the Boolean lattice, on choosing a designated lattice value, this algebra has binary retracts that have the usual axiomatic theory of the propositional calculus as suitable theory. This suitability applies to the Boolean algebra of formalized token models [2] where the truth values are, for example, vocabularies. Finally, as the actual motivation for this paper, we indicate how the theory of formalized token models [2] is an example of a many-valued predicate calculus.
Relative randomness and real closed fields
Authors: Raichev Alexander 
Published: March 2005

AbstractWe show that for any real number, the class of real numbers less random than it, in the sense of rK-reducibility, forms a countable real closed subfield of the real ordered field. This generalizes the well-known fact that the computable reals form a real closed field.With the same technique we show that the class of differences of computably enumerable reals (d.c.e. reals) and the class of computably approximable reals (c.a. reals) form real closed fields. The d.c.e. result was also proved nearly simultaneously and independently by Ng (Keng Meng Ng, Master's Thesis, National University of Singapore, in preparation).Lastly, we show that the class of d.c.e. reals is properly contained in the class or reals less random than Ω (the halting probability), which in turn is properly contained in the class of c.a. reals, and that neither the first nor last class is a randomness class (as captured by rK-reducibility).
The isomorphism problem for computable Abelian p-groups of bounded length
Authors: Calvert Wesley 
Published: March 2005

AbstractTheories of classification distinguish classes with some good structure theorem from those for which none is possible. Some classes (dense linear orders, for instance) are non-classifiable in general, but are classifiable when we consider only countable members. This paper explores such a notion for classes of computable structures by working out a sequence of examples.We follow recent work by Goncharov and Knight in using the degree of the isomorphism problem for a class to distinguish classifiable classes from non-classifiable. In this paper, we calculate the degree of the isomorphism problem for Abelian p-groups of bounded Ulm length. The result is a sequence of classes whose isomorphism problems are cofinal in the hyperarithmetical hierarchy. In the process, new back-and-forth relations on such groups are calculated.
On relatively analytic and Borel subsets
Authors: Miller Arnold W. 
Published: March 2005

AbstractDefine to be the smallest cardinality of a function f: X→Y with I, X, Y, ⊆ 2ω such that there is no Borel function g ⊇ f. In this paper we prove that it is relatively consistent with ZFC to have b < where b is, as usual, smallest cardinality of an unbounded family in Ωω. This answers a question raised by Zapletal.We also show that it is relatively consistent with ZFC that there exists X ⊆ 2ω such that the Borei order of X is bounded but there exists a relatively analytic subset of X which is not relatively coanalytic. This answers a question of Mauldin.