bluuebunny/crossref_metadata_2025_split huggingface dataset:
Some theories with positive induction of ordinal strength φω0
Authors: Jäger Gerhard , Strahm Thomas 
Published: May 2006

AbstractThis paper deals with: (i) the theory which results from by restricting induction on the natural numbers to formulas which are positive in the fixed point constants, (ii) the theory BON(μ) plus various forms of positive induction, and (iii) a subtheory of Peano arithmetic with ordinals in which induction on the natural numbers is restricted to formulas which are Σ in the ordinals. We show that these systems have proof-theoretic strength φω0.
Decidability of the two-quantifier theory of the recursively enumerable weak truth-table degrees and other distributive upper semi-lattices
Authors: Ambos-Spies Klaus , Fejer Peter A. , Lempp Steffen , Lerman Manuel 
Published: May 2006

AbstractWe give a decision procedure for the ∀∃-theory of the weak truth-table (wtt) degrees of the recursively enumerable sets. The key to this decision procedure is a characterization of the finite lattices which can be embedded into the r.e.wtt-degrees by a map which preserves the least and greatest elements: a finite lattice has such an embedding if and only if it is distributive and the ideal generated by its cappable elements and the filter generated by its cuppable elements are disjoint.We formulate general criteria that allow one to conclude that a distributive upper semi-lattice has a decidable two-quantifier theory. These criteria are applied not only to the weak truth-table degrees of the recursively enumerable sets but also to various substructures of the polynomial many-one (pm) degrees of the recursive sets. These applications to thepmdegrees require no new complexity-theoretic results. The fact that thepm-degrees of the recursive sets have a decidable two-quantifier theory answers a question raised by Shore and Slaman in [21].
Some model theory for almost real closed fields
Authors: Delon Françoise , Farré Rafel 
Published: May 2006

AbstractWe study the model theory of fields k carrying a henselian valuation with real closed residue field. We give a criteria for elementary equivalence and elementary inclusion of such fields involving the value group of a not necessarily definable valuation. This allows us to translate theories of such fields to theories of ordered abelian groups, and we study the properties of this translation. We also characterize the first-order definable convex subgroups of a given ordered abelian group and prove that the definable real valuation rings of k are in correspondence with the definable convex subgroups of the value group of a certain real valuation of k.
Minimal complementation below uniform upper bounds for the arithmetical degrees
Authors: Kumabe Masahiro 
Published: May 2006

This paper was inspired by Lerman [15] in which he proved various properties of upper bounds for the arithmetical degrees. We discuss the complementation property of upper bounds for the arithmetical degrees. In Lerman [15], it is proved that uniform upper bounds for the arithmetical degrees are jumps of upper bounds for the arithmetical degrees. So any uniform upper bound for the arithmetical degrees is not a minimal upper bound for the arithmetical degrees. Given a uniform upper bound a for the arithmetical degrees, we prove a minimal complementation theorem for the upper bounds for the arithmetical degrees below a. Namely, given such a and b < a which is an upper bound for the arithmetical degrees, there is a minimal upper bound for the arithmetical degrees c such that b ∪ c = a. This answers a question in Lerman [15]. We prove this theorem by different methods depending on whether a has a function which is not dominated by any arithmetical function. We prove two propositions (see §1), of which the theorem is an immediate consequence.Our notation is almost standard. Let A ⊕ B = {2n∣n ∈ A} ∪ {2n + 1∣n + 1∣n ∈ B} for any sets A and B. Let ω be the set of nonnegative natural numbers.
If there is an exactly λ-free abelian group then there is an exactly λ-separable one in λ
Authors: Shelah Saharon 
Published: May 2006

AbstractWe give a solution stated in the title to problem 3 of part 1 of the problems listed in the book of Eklof and Mekler [2], p. 453. There, in pp. 241-242, this is discussed and proved in some cases. The existence of strongly λ-free ones was proved earlier by the criteria in [5] and [3]. We can apply a similar proof to a large class of other varieties in particular to the variety of (non-commutative) groups.
Cylindric modal logic
Authors: Venema Yde 
Published: May 2006

AbstractTreating the existential quantification ∃νi as a diamond ♢i and the identity νi = νj as a constant δij, we study restricted versions of first order logic as if they were modal formalisms. This approach is closely related to algebraic logic, as the Kripke frames of our system have the type of the atom structures of cylindric algebras; the full cylindric set algebras are the complex algebras of the intended multidimensional frames called cubes.The main contribution of the paper is a characterization of these cube frames for the finite-dimensional case and, as a consequence of the special form of this characterization, a completeness theorem for this class. These results lead to finite, though unorthodox, derivation systems for several related formalisms, e.g. for the valid n-variable first order formulas, for type-free valid formulas and for the equational theory of representable cylindric algebras. The result for type-free valid formulas indicates a positive solution to Problem 4.16 of Henkin, Monk and Tarski [16].
Compactly expandable models and stability
Authors: Casanovas Enrique 
Published: May 2006

In analogy to ω-logic, one defines M-logic for an arbitrary structure M (see [5],[6]). In M-logic only those structures are considered in which a special part, determined by a fixed unary predicate, is isomorphic to M. Let L be the similarity type of M and T its complete theory. We say that M-logic is κ-compact if it satisfies the compactness theorem for sets of < κ sentences. In this paper we introduce the related notion of compactness for expandability: a model M is κ-compactly expandable if for every extension T′ ⊇ T of cardinality < κ, if every finite subset of T′ can be satisfied in an expansion of M, then T′ can also be satisfied in an expansion of M. Moreover, M is compactly expandable if it is ∥M∥+-compactly expandable. It turns out that M-logic is κ-compact iff M is κ-compactly expandable.Whereas for first-order logic consistency and finite satisfiability are the same, consistency with T and finite satisfiability in M are, in general, no longer the same thing. We call the model Mκ-expandable if every consistent extension T′ ⊇ T of cardinality < κ can be satisfied in an expansion of M. We say that M is expandable if it is ∥M∥+-expandable. Here we study the relationship between saturation, expandability and compactness for expandability. There is a close parallelism between our results about compactly expandable models and some theorems of S. Shelah about expandable models, which are in fact expressed in terms of categoricity of PC-classes (see [7, Th. VI.5.3, VI.5.4 and VI.5.5]). Our results could be obtained directly from these theorems of Shelah if expandability and compactness for expandability were the same notion.
On Gödel's theorems on lengths of proofs I: Number of lines and speedup for arithmetics
Authors: Buss Samuel R. 
Published: May 2006

AbstractThis paper discusses lower bounds for proof length, especially as measured by number of steps (inferences). We give the first publicly known proof of Gödel's claim that there is superrecursive (in fact, unbounded) proof speedup of (i + l)st-order arithmetic over ith-order arithmetic, where arithmetic is formalized in Hilbert-style calculi with + and • as function symbols or with the language of PRA. The same results are established for any weakly schematic formalization of higher-order logic: this allows all tautologies as axioms and allows all generalizations of axioms as axioms.Our first proof of Gödel's claim is based on self-referential sentences: we give a second proof that avoids the use of self-reference based loosely on a method of Statman.
A jump operator for subrecursion theories
Authors: Heaton A.J. 
Published: May 2006

In classical recursion theory, the jump operator is an important concept fundamental in the study of degrees. In particular, it provides a way of defining the hyperarithmetic hierarchy by iterating over Kleene's O. In subrecursion theories, hierarchies (variants of the fast growing hierarchy) are also important in underlying the central concepts, e.g. in classifying provably recursive functions and associated independence results for given theories (see, e.g. [BW87], [HW96], [R84] and [Z77]). A major difference with the hyperarithmetic hierarchy is in the way each level of a subrecursive hierarchy is crucially dependent upon the system of ordinal notations used (see [F62]). This has been perhaps the major stumbling block in finding a classification of all general recursive functions using such hierarchies.Here we present a natural subrecursive analogue of the jump operator and prove that the hierarchy based on the ”subrecursive jump” is elementarily equivalent to the fast growing hierarchy.The paper is organised as follows. First the preliminary definitions are given together with a statement of the main theorem and a brief outline of its proof. The proof of the theorem is then given, with the more technical parts separated out as facts which are proven afterwards.We let {e}g(x) denote computation of the e-th partial recursion with oracle g, on input x. Furthermore [e] denotes the e-th elementary recursive function, defined so thatSimilarly, for a given oracle g the e-th relativized elementary function is denoted by [e]g.
Prime e.c. commutative rings in characteristic n ≥ 2
Authors: Saracino Dan 
Published: May 2006

Let CR denote the first-order theory of commutative rings with unity, formulated in the language L = 〈 +, •, 0, 1〉. Virtually everything that is known about existentially complete (e.c.) models of CR is contained in Cherlin's paper [2], where it is shown, in particular, that the e.c. models are not first-order axiomatizable. The purpose of this note is to show that, in analogy with the case of fields, there exists a unique prime e.c. model of CR in each characteristic n > 2. As a consequence we settle Problem 8 in the list of open questions at the end of Hodges' book Building models by games ([5], p. 278).By a “prime” e.c. model of characteristic n ≥ 2 we mean one that embeds in every e.c. model of characteristic n. (The embedding is not always elementary, since [2] not all e.c. models of characteristic n are elementarily equivalent.) The prime model is characterized by the fact that it is the union of a chain of finite subrings each of which is an amalgamation base for CR. In §1 we describe the finite amalgamation bases for CR and show that every finite model embeds in a finite amalgamation base; in §2 we use this information to obtain prime e.c. models and answer Hodges' question.Our results on prime e.c. models were obtained some years ago, during the fall term of 1982, while the author was a visitor at Wesleyan University. The author wishes to take this opportunity to thank the mathematics department at Wesleyan for its hospitality during that visit, and subsequent ones.
Transfering saturation, the finite cover property, and stability
Authors: Baldwin John T. , Grossberg Rami , Shelah Saharon 
Published: May 2006

AbstractSaturation is (μ, κ)-transferable in T if and only if there is an expansion T1 of T with |T1| = |T| such that if M is a μ-saturated model of T1 and |M| ≥ κ then the reduct M|L(T) is κ-saturated. We characterize theories which are superstable without f.c.p., or without f.c.p. as, respectively those where saturation is (ℵ0, λ)-transferable or (κ(T), λ)-transferable for all λ. Further if for some μ ≥ |T|,2μ > μ+, stability is equivalent to for all μ ≥ |T|, saturation is (μ, 2μ)-transferable.
An abstract algebraic logic approach to tetravalent modal logics
Authors: Font Josep Maria , Rius Miquel 
Published: May 2006

AbstractThis paper contains a joint study of two sentential logics that combine a many-valued character, namely tetravalence, with a modal character; one of them is normal and the other one quasinormal. The method is to study their algebraic counterparts and their abstract models with the tools of Abstract Algebraic Logic, and particularly with those of Brown and Suszko's theory of abstract logics as recently developed by Font and Jansana in their “A General Algebraic Semantics for Sentential Logics”. The logics studied here arise from the algebraic and lattice-theoretical properties we review of Tetravalent Modal Algebras, a class of algebras studied mainly by Loureiro, and also by Figallo. Landini and Ziliani, at the suggestion of the late Antonio Monteiro.
An elementary definability theorem for first order logic
Authors: Butz C. , Moerdijk I. 
Published: May 2006

In this paper, we will present a definability theorem for first order logic. This theorem is very easy to state, and its proof only uses elementary tools. To explain the theorem, let us first observe that if M is a model of a theory T in a language , then, clearly, any definable subset S ⊂ M (i.e., a subset S = {a ∣ M ⊨ φ(a)} defined by some formula φ) is invariant under all automorphisms of M. The same is of course true for subsets of Mn defined by formulas with n free variables.Our theorem states that, if one allows Boolean valued models, the converse holds. More precisely, for any theory T we will construct a Boolean valued model M, in which precisely the T -provable formulas hold, and in which every (Boolean valued) subset which is invariant under all automorphisms of M is definable by a formula .Our presentation is entirely selfcontained, and only requires familiarity with the most elementary properties of model theory. In particular, we have added a first section in which we review the basic definitions concerning Boolean valued models.
Implicit measurements of dynamic complexity properties and splittings of speedable sets
Authors: Jahn Michael A. 
Published: May 2006

AbstractWe prove that any speedable computably enumerable set may be split into a disjoint pair of speedable computably enumerable sets. This solves a longstanding question of J.B. Remmel concerning the behavior of computably enumerable sets in Blum's machine independent complexity theory. We specify dynamic requirements and implement a novel way of detecting speedability—by embedding the relevant measurements into the substage structure of the tree construction. Technical difficulties in satisfying the dynamic requirements lead us to implement “local” strategies that only look down the tree. The (obvious) problems with locality are then resolved by placing an isomorphic copy of the entire priority tree below each strategy (yielding a self-similar tree). This part of the construction could be replaced by an application of the Recursion Theorem, but shows how to achieve the same effect with a more direct construction.
Freeness in classes without equality
Authors: Elgueta Raimon 
Published: May 2006

AbstractThis paper is a continuation of [27], where we provide the background and the basic tools for studying the structural properties of classes of models over languages without equality. In the context of such languages, it is natural to make distinction between two kinds of classes, the so-calledabstruct classes, which correspond to those closed under isomorphic copies in the presence of equality, and thereduced classes, i.e., those obtained by factoring structures by their largest congruences. The generic problem described in [27] is to investigate under what conditions thisreduction processdoes not alter the metatheory of a class.Here we focus our attention on a concrete aspect of this generic problem that we import from universal algebra, namely the existence and description of free models. As in [27], we can find here again the basic notion ofprotoalgebraicity, which was originally introduced in [7] as the weakest condition to guarantee that the reduction process behaves reasonably well from an algebraic point of view. Our concern, however, takes us to handle a further notion, that ofsemialgebraicity, which corresponds to the notion ofequivalential logicof [18]; semialgebraicity turns out to be the property which ensures that freeness is fully preserved by the reduction process.
The emptiness problem for intersection types
Authors: Urzyczyn Paweł 
Published: May 2006

AbstractWe study the intersection type assignment system as defined by Barendregt, Coppo and Dezani. For the four essential variants of the system (with and without a universal type and with and without subtyping) we show that the emptiness (inhabitation) problem is recursively unsolvable. That is, there is no effective algorithm to decide if there is a closed term of a given type. It follows that provability in the logic of “strong conjunction” of Mints and Lopez-Escobar is also undecidable.
Quasi-o-minimal structures
Authors: Belegradek Oleg , Peterzil Ya'acov , Wagner Frank 
Published: May 2006

AbstractA structure (M, <, …) is called quasi-o-minimal if in any structure elementarily equivalent to it the definable subsets are exactly the Boolean combinations of 0-definable subsets and intervals. We give a series of natural examples of quasi-o-minimal structures which are not o-minimal; one of them is the ordered group of integers. We develop a technique to investigate quasi-o-minimality and use it to study quasi-o-minimal ordered groups (possibly with extra structure). Main results: any quasi-o-minimal ordered group is abelian; any quasi-o-minimal ordered ring is a real closed field, or has zero multiplication; every quasi-o-minimal divisible ordered group is o-minimal; every quasi-o-minimal archimedian densely ordered group is divisible. We show that a counterpart of quasi-o-minimality in stability theory is the notion of theory of U-rank 1.
On the equational theory of representable polyadic equality algebras
Authors: Németi István , Sági Gábor 
Published: May 2006

AbstractAmong others we will prove that the equational theory of ω dimensional representable polyadic equality algebras (RPEAω's) is not schema axiomatizable. This result is in interesting contrast with the Daigneault-Monk representation theorem, which states that the class of representable polyadic algebras is finite schema-axiomatizable (and hence the equational theory of this class is finite schema-axiomatizable. as well). We will also show that the complexity of the equational theory of RPEAω is also extremely high in the recursion theoretic sense. Finally, comparing the present negative results with the positive results of Ildikó Sain and Viktor Gyuris [12], the following methodological conclusions will be drawn: The negative properties of polyadic (equality) algebras can be removed by switching from what we call the “polyadic algebraic paradigm” to the “cylindric algebraic paradigm”.
A 1-generic degree with a strong minimal cover
Authors: Kumabe Masahiro 
Published: May 2006

We consider a set generic over the arithmetic sets. A subset A of the natural numbers is called n-generic if it is Cohen-generic for n-quantifier arithmetic. This is equivalent to saying that for every -set of strings S, there is a string σ ⊂ A such that σ ∈ S or no extension of σ is in S. By degree we mean Turing degree (of unsolvability). We call a degree n-generic if it has an n-generic representative. For a degree a, let D(≤ a) denote the set of degrees which are recursive in a.We say a is a strong minimal cover of g if every degree strictly below a is less than or equal to g. In this paper we show that there are a degree a and a 1-generic degree g < a such that a is a strong minimal cover of g. This easily implies that there is a 1-generic degree without the cupping property. Jockusch [7] showed that every 2-generic degree has the cupping property. Slaman and Steel [17] and independently Cooper [3] showed that there are recursively enumerable degrees a and b < a such that no degree c < a joins b above a. Take a 1-generic degree g below b. Then g does not have the cupping property.
Higher gap morasses, Ia: Gap-two morasses and condensation
Authors: Morgan Charles 
Published: May 2006

AbstractThis paper concerns the theory of morasses. In the early 1970s Jensen defined (k, α)-morasses for uncountable regular cardinals k and ordinals α < k. In the early 1980s Velleman defined (k, 1)-simplified morasses for all regular cardinals k. He showed that there is a (k, 1)-simplified morass if and only if there is (k, 1)-morass. More recently he defined (k, 2)-simplified morasses and Jensen was able to show that if there is a (k, 2)-morass then there is a (k, 2)-simplified morass.In this paper we prove the converse of Jensen's result, i.e., that if there is a (k, 2)-simplified morass then there is a (k, 2)-morass.
On the existence of strong chains in ℘(ω1)/Fin
Authors: Koszmider Piotr 
Published: May 2006

Abstract(Xα: α < ω2) ⊂ ℘(ω1) is a strong chain in ℘(ω1)/Fin if and only if Xβ – Xα is finite and Xα – Xβ is uncountable for each β < α < ω1. We show that it is consistent that a strong chain in ℘(ω1) exists. On the other hand we show that it is consistent that there is a strongly almost-disjoint family in ℘(ω1) but no strong chain exists: is used to construct a c.c.c forcing that adds a strong chain and Chang's Conjecture to prove that there is no strong chain.
The independence of the Prime Ideal Theorem from the Order-Extension Principle
Authors: Felgner U. , Truss J. K. 
Published: May 2006

AbstractIt is shown that the boolean prime ideal theorem BPIT: every boolean algebra has a prime ideal, does not follow from the order-extension principle OE: every partial ordering can be extended to a linear ordering. The proof uses a Fraenkel–Mostowski model, where the family of atoms is indexed by a countable universal-homogeneous boolean algebra whose boolean partial ordering has a ‘generic’ extension to a linear ordering. To illustrate the technique for proving that the order-extension principle holds in the model we also study Mostowski's ordered model, and give a direct verification of OE there. The key technical point needed to verify OE in each case is the existence of a support structure.
Upper bounds for standardizations and an application
Authors: Xi Hongwei 
Published: May 2006

AbstractWe present a new proof for the standardization theorem in λ-calculus, which is largely built upon a structural induction on λ-terms. We then extract some bounds for the number of β-reduction steps in the standard β-reduction sequence obtained from transforming a given β-reduction sequence, sharpening the standardization theorem. As an application, we establish a super exponential bound for the lengths of β-reduction sequences from any given simply typed λ-terms.
Uniform inseparability in explicit mathematics
Authors: Cantini Andrea , Minari Pierluigi 
Published: May 2006

AbstractWe deal with ontological problems concerning basic systems of explicit mathematics, as formalized in Jäger's language of types and names. We prove a generalized inseparability lemma, which implies a form of Rice's theorem for types and a refutation of the strong power type axiom POW+. Next, we show that POW+ can already be refuted on the basis of a weak uniform comprehension without complementation, and we present suitable optimal refinements of the remaining results within the weaker theory.