bluuebunny/crossref_metadata_2025_split huggingface dataset:
A jump class of noncappable degrees
Authors: Cooper S. B. 
Published: May 2006

Friedberg [3] showed that every degree of unsolvability above 0′ is the jump of some degree, and Sacks [9] showed that the degrees above 0′ which are recursively enumerable (r.e.) in 0′ are the jumps of the r.e. degrees.In this paper we examine the extent to which the Sacks jump theorem can be combined with the minimal pair theorem of Lachlan [4] and Yates [13]. We prove below that there is a degree c > 0′ which is r.e. in 0′ but which is not the jump of half a minimal pair of r.e. degrees.This extends Yates' result [13] proving the existence of noncappable degrees (that is, r.e. degrees a < 0′ for which there is no corresponding r.e. b > 0 with a ∩ b = 0).It also throws more light on the class PS of promptly simple degrees. It was shown by Ambos-Spies, Jockusch, Shore and Soare [1] that PS coincides with the class NC of noncappable degrees, and with the class LC of all low-cuppable degrees, and (using earlier work of Maass, Shore and Stob [5]) that PS splits every class Hn or Ln, n ≥ 0, in the high-low hierarchy of r.e. degrees.If c > 0′, with c r.e. in 0′, letand call c−1 the jump class for c. It is easy to see that every jump class contains members of PS (= NC = LC). By Sacks [8] there exists a low a ∈ LC, where of course [a, 0′] (= {br.e. ∣a ≤ b ≤ 0′}) ⊆ LC = PS. But by Robinson [7] [a, 0′] intersects with every jump class.
The structure of algebraically and existentially closed Stone and double Stone algebras
Authors: Clark David M. 
Published: May 2006

In this paper we study the varieties of Stone algebras (S, ∧, ∨, *, 0, 1) and double Stone algebras (D, ∧, ∨, *, +, 0, 1). Our primary interest is to give a structural description of the algebraically and existentially closed members of both classes. Our technique is an application of the natural dualities of Davey [6] and Clark and Krauss [5]. This approach gives a description of the desired models as the algebras of all continuous structure-preserving maps from certain structured Boolean spaces into the generating algebra for the variety. In each case the resulting description can be converted in a natural way into a finite ∀∃-axiomatization for these models. For Stone algebras these axioms appeared earlier in Schmid [20], [21] and in Schmitt [22].Since both cases we consider satisfy the amalgamation property, the existentially closed members form a model companion for the variety which is also its model completion. Moreover, it is also ℵ0 categorical and its countably infinite member is the unique countable homogeneous universal model for the variety. In the case of Stone algebras, explicit constructions for this model appear in Schmitt [22] and Weispfenning [23]. We give here an explicit construction for double Stone algebras of S. Hayes.This work was motivated by a problem of Stanley Burris. In [4] Burris and Werner superseded many previous results by showing that for any finite algebra A, the universal Horn class ISP has a model companion. Weispfenning [24], [25] discovered that this model companion is always ℵ0 categorical and has a primitive recursive ∀∃-axiomatization. In spite of these very general theorems, there are few instances in which a structural description of the (any!) existentially closed members of ISP is available. Burris and Werner [4] solve this problem in a special setting.
Regressive partitions and Borel diagonalization
Authors: Kanamori Akihiro 
Published: May 2006

Several rather concrete propositions about Borel measurable functions of several variables on the Hilbert cube (countable sequences of reals in the unit interval) were formulated by Harvey Friedman [F1] and correlated with strong set-theoretic hypotheses. Most notably, he established that a “Borel diagonalization” proposition P is equivalent to: for any a ⊆ co and n ⊆ ω there is an ω-model of ZFC + ∃κ(κ is n-Mahlo) containing a. In later work (see the expository Stanley [St] and Friedman [F2]), Friedman was to carry his investigations further into propositions about spaces of groups and the like, and finite propositions. He discovered and analyzed mathematical propositions which turned out to have remarkably strong consistency strength in terms of large cardinal hypotheses in set theory.In this paper, we refine and extend Friedman's work on the Borel diagonalization proposition P. First, we provide more combinatorics about regressive partitions and n-Mahlo cardinals and extend the approach to the context of the Erdös cardinals In passing, a combinatorial proof of a well-known result of Silver about these cardinals is given. Incorporating this work and sharpening Friedman's proof, we then show that there is a level-by-level analysis of P which provides for each n ⊆ ω a proposition almost equivalent to: for any a ⊆ co there is an ω-model of ZFC + ∃κ(κ is n-Mahlo) containing a. Finally, we use the combinatorics to bracket a natural generalization Sω of P between two large cardinal hypotheses.
Recursively enumerable m- and tt-degrees. I: The quantity of m-degrees
Authors: Downey R. G. 
Published: May 2006

In [1], Degtëv constructed a nonzero r.e. tt-degree containing a single r.e. m-degree. It is not difficult to construct an r.e. tt-degree containing infinitely many r.e. m-degrees (Fischer [6]); indeed, in [3], the author constructed an r.e. tt-degree with no greatest r.e. m-degree. Odifreddi [12, Problem 10] asked if every r.e. tt-degree contains either one or infinitely many r.e. m-degrees. The goal of this paper is to solve Odifreddi's question by showing:Theorem. There exists a nonzero r.e. tt-degree containing exactly 3 r.e. m-degrees.This theorem can be extended to show that there exist r.e. tt-degrees with arbitrarily large finite numbers of r.e. m-degrees.We remark that save for the aforementioned results, very little is known about the structures that can be realized as the collection of r.e. m-degrees within an r.e. tt-degree. It seems conceivable that the methods of the present paper may be useful in, for example, embedding distributive (semi) lattices into such structures.In part II of this paper [4], we continue our analysis of r.e. m- and tt-degrees. We define an r.e. tt-degree to be singular if it contains a single r.e. m-degree, and an r.e. T-degree a to be singular if a contains a singular r.e. tt-degree.In [4] we study the distribution (in the r.e. T-degrees) of singular tt-degrees. We show that 0′T is singular (solving a question of Odifreddi [11]), and that the singular T-degrees are dense, but also we construct a nonsingular T-degree. The techniques used for the first results extend those of §2 of the present paper.
Indiscernible sequences in a model which fails to have the order property
Authors: Grossberg Rami 
Published: May 2006

AbstractBasic results on the model theory of substructures of a fixed model are presented. The main point is to avoid the use of the compactness theorem, so this work can easily be applied to the model theory of Lω1,ω and its relatives. Among other things we prove the following theorem:Let M be a model, and let λ be a cardinal satisfying λ∣L(M)∣ = λ. If M does not have the ω-order property, then for every A ⊆ M, ∣A∣ ≤ λ, and every I ⊆ M of cardinality λ+ there exists J ⊆ I cardinality λ+ which is an indiscernible set over A.This is an improvement of a result of S. Shelah.
Stratification and cut-elimination
Authors: Crabbé Marcel 
Published: May 2006

In this paper, we show the normalization of proofs of NF (Quine's New Foundations; see [15]) minus extensionality. This system, called SF (Stratified Foundations) differs in many respects from the associated system of simple type theory. It is written in a first order language and not in a multi-sorted one, and the formulas need not be stratifiable, except in the instances of the comprehension scheme. There is a universal set, but, for a similar reason as in type theory, the paradoxical sets cannot be formed.It is not immediately apparent, however, that SF is essentially richer than type theory. But it follows from Specker's celebrated result (see [16] and [4]) that the stratifiable formula (extensionality → the universe is not well-orderable) is a theorem of SF.It is known (see [11]) that this set theory is consistent, though the consistency of NF is still an open problem.The connections between consistency and cut-elimination are rather loose. Cut-elimination generally implies consistency. But the converse is not true. In the case of set theory, for example, ZF-like systems, though consistent, cannot be freed of cuts because the separation axioms allow the formation of sets from unstratifiable formulas. There are nevertheless interesting partial results obtained when restrictions are imposed on the removable cuts (see [1] and [9]). The systems with stratifiable comprehension are the only known set-theoretic systems that enjoy full cut-elimination.
Quantales and (noncommutative) linear logic
Authors: Yetter David N. 
Published: May 2006

It is the purpose of this paper to make explicit the connection between J.-Y. Girard's “linear logic” [4], and certain models for the logic of quantum mechanics, namely Mulvey's “quantales” [9]. This will be done not only in the case of commutative linear logic, but also in the case of a version of noncommutative linear logic suggested, but not fully formalized, by Girard in lectures given at McGill University in the fall of 1987 [5], and which for reasons which will become clear later we call “cyclic linear logic”.For many of our results on quantales, we rely on the work of Niefield and Rosenthal [10].The reader should note that by “the logic of quantum mechanics” we do not mean the lattice theoretic “quantum logics” of Birkhoff and von Neumann [1], but rather a logic involving an associative (in general noncommutative) operation “and then”. Logical validity is intended to embody empirical verification (whether a physical experiment, or running a program), and the validity of A & B (in Mulvey's notation) is to be regarded as “we have verified A, and then we have verified B”. (See M. D. Srinivas [11] for another exposition of this idea.)This of course is precisely the view of the “multiplicative conjunction”, ⊗, in the phase semantics for Girard's linear logic [4], [5]. Indeed the quantale semantics for linear logic may be regarded as an element-free version of the phase semantics.
Two incomplete anti-realist modal epistemic logics
Authors: Williamson Timothy 
Published: May 2006

Many phrases have been used to express what are sometimes called anti-realist conceptions of truth: ‘verifiability’, ‘knowability’, ‘rational acceptability’, ‘warranted assertability’. In spite of their obvious differences, all four of these phrases have a common form; each is a cognitive attitude modified by ‘-ability’. They speak of the possibility of verification, knowledge, rational acceptance or warranted assertion. Schematically, it seems to be claimed that it is true that A if and only if it is possible that it is E'd that A, where ‘E’ is to be replaced by some cognitive verb and ‘A’ by any indicative sentence of the class to which the anti-realist conception is being claimed to apply. Since truth is redundant as a sentential operator, this boils down to the following thesis, where ‘p’ is a propositional variable and ‘M’ expresses the appropriate kind of possibility:(*) also formalizes views such as Putnam's: ‘To claim a statement is true is to claim it could be justified’ [11, p. 56]. It is no doubt a crude model for anti-realism, but one has to start somewhere; by seeing how and why more sophisticated versions of anti-realism differ from (*) one should be able to understand them better too. Moreover, if an anti-realist rejects the equation of truth with, say, warranted assertibility, arguing that truth is rather to be identified with the possibility of getting into a position in which one's warrant to assert somehow cannot be overturned, the form of (*) is preserved, for truth is still being identified with the possibility of something.
Théories complètes de paires de corps valués henseliens
Authors: Leloup Gérard 
Published: May 2006

Un prolongement de l'étude d'une théorie T, dans le langage , consiste à s'intéresser à la théorie T* des paires de modèles de T, c'est-à-dire les structures de la forme (K ⊊ L) où K ⊨ T, L ⊨ T, K ≺ L, dans le langage où E est un prédicat pour la sous-structure. Les propriétés de la théorie T ne se transmettent pas toujours à T*, particulièrement en ce qui concerne la complétude et la décidabilité. On trouve des illustrations de cas opposés dans les théories de corps:—si T est la théorie des corps algébriquement clos de caractéristique fixée, T* est complète et décidable;—si T est la théorie des corps réels clos, T est complète et décidable, mais T* est indécidable, et admet complétions différentes.Nous allons nous intéresser ici aux paires de corps valués henseliens, et plus particulièrement au cas de caractéristique résiduelle nulle, de la forme (K ⊊ L, υ) où (K, υ) n'est pas nécessairement une sous-structure élémentaire de (L, υ). Ax, Kochen et Ershov ont montré que la théorie d'un corps valué henselien de caractéristique résiduelle nulle est entièrement déterminée par la théorie de son corps de restes et par la théorie de son groupe de valuation; par ailleurs, de résultats analogues existent pour certains corps de caractéristique résiduelle non nulle.
Finite injury and Σ1-induction
Authors: Mytilinaios Michael 
Published: May 2006

AbstractWorking in the language of first-order arithmetic we consider models of the base theory P−. Suppose M is a model of P− and let M satisfy induction for Σ1-formulas. First it is shown that the Friedberg-Muchnik finite injury argument can be performed inside M, and then, using a blocking method for the requirements, we prove that the Sacks splitting construction can be done in M. So, the “amount” of induction needed to perform the known finite injury priority arguments is Σ1-induction.
The well-foundedness of the Mitchell order
Authors: Steel J. R. 
Published: May 2006

Let E ⊲ F iff E and F are extenders and E ∈ Ult(V, F). Intuitively, E ⊲ F implies that E is weaker—embodies less reflection—than F. The relation ⊲ was first considered by W. Mitchell in [M74], where it arises naturally in connection with inner models and coherent sequences. Mitchell showed in [M74] that the restriction of ⊲ to normal ultrafilters is well-founded.The relation ⊲ is now known as the Mitchell order, although it is not actually an order. It is irreflexive, and its restriction to normal ultrafilters is transitive, but under mild large cardinal hypotheses, it is not transitive on all extenders. Here is a counterexample. Let κ be (λ + 2)-strong, where λ > κ and λ is measurable. Let E be an extender with critical point κ and let U be a normal ultrafilter with critical point λ such that U ∈ Ult(V, E). Let i: V → Ult(V, U) be the canonical embedding. Then i(E) ⊲ U and U ⊲ E, but by 3.11 of [MS2], it is not the case that i(E) ⊲ E. (The referee pointed out the following elementary proof of this fact. Notice that i ↾ Vλ+2 ∈ Ult(V, E) and X ∈ Ea ⇔ X ∈ i(E)i(a). Moreover, we may assume without loss of generality that = support(E). Thus, if i(E) ∈ Ult(V, E), then E ∈ Ult(V, E), a contradiction.)By going to much stronger extenders, one can show the Mitchell order is not well-founded. The following example is well known. Let j: V → M be elementary, with Vλ ⊆ M for λ = joω(crit(j)). (By Kunen, Vλ+1 ∉ M.) Let E0 be the (crit(j), λ) extender derived from j, and let En+1 = i(En), where i: V → Ult(V, En) is the canonical embedding. One can show inductively that En is an extender over V, and thereby, that En+1 ⊲ En for all n < ω. (There is a little work in showing that Ult(V, En+1) is well-founded.)
Reducts of some structures over the reals
Authors: Peterzil Ya′acov 
Published: May 2006

AbstractWe consider reducts of the structure ℛ = 〈ℝ, +, ·, <〉 and other real closed fields. We compete the proof that there exists a unique reduct between 〈ℝ, +, <,λa〉a ∈ ℝ and ℛ, and we demonstrate how to recover the definition of multiplication in more general contexts than the semialgebraic one. We then conclude a similar result for reducts between 〈ℝ, ·, <〉 and ℛ and for general real closed fields.
A note on Mathematics of infinity
Authors: Palmgren Erik 
Published: May 2006

In the paper Mathematics of infinity, Martin-Löf extends his intuitionistic type theory with fixed “choice sequences”. The simplest, and most important instance, is given by adding the axiomsto the type of natural numbers. Martin-Löf's type theory can be regarded as an extension of Heyting arithmetic (HA). In this note we state and prove Martin-Löf's main result for this choice sequence, in the simpler setting of HA and other arithmetical theories based on intuitionistic logic (Theorem A). We also record some remarkable properties of the resulting systems; in general, these lack the disjunction property and may or may not have the explicit definability property. Moreover, they represent all recursive functions by terms.
Addendum to “A structure theorem for strongly abelian varieties”
Authors: Hart Bradd , Starchenko Sergei 
Published: May 2006

By a variety we mean a class of algebras in a language , containing only function symbols, which is closed under homomorphisms, submodels, and products. A variety is said to be strongly abelian if for any term in , the quasi-identityholds in .In [1] it was proved that if a strongly abelian variety has less than the maximal possible uncountable spectrum, then it is equivalent to a multisorted unary variety. Using Shelah's Main Gap theorem one can conclude that if is a classifiable (superstable without DOP or OTOP and shallow) strongly abelian variety then is a multisorted unary variety. In fact, it was known that this conclusion followed from the assumption of superstable without DOP alone.This paper is devoted to the proof that the superstability assumption is enough to obtain the same structure result. This fulfills a promise made in [2]. Namely, we will prove the followingTheorem 0.1. If is a superstable strongly abelian variety, then it is multisorted unary.
An inside view of EXP; or, The closed fragment of the provability logic of IΔ0 + Ω1 with a prepositional constant for EXP
Authors: Visser Albert 
Published: May 2006

AbstractIn this paper I give a characterization of the closed fragment of the provability logic of I Δ0 + EXP with a propositional constant for EXP. In three appendices many details on arithmetization are provided.
Lambek's categorical proof theory and Läuchli's abstract realizability
Authors: Harnik Victor , Makkai Michael 
Published: May 2006

In this paper we give an introduction to categorical proof theory, and reinterpret, with improvements, Läuchli's work on abstract realizability restricted to propositional logic (but see [M1] for predicate logic). Partly to make some points of a foundational nature, we have included a substantial amount of background material. As a result, the paper is (we hope) readable with a knowledge of just the rudiments of category theory, the notions of category, functor, natural transformation, and the like. We start with an extended introduction giving the background, and stating what we do with a minimum of technicalities.In three publications [L1, 2, 3] published in the years 1968, 1969 and 1972, J. Lambek gave a categorical formulation of the notion of formal proof in deductive systems in certain propositional calculi. The theory is also described in the recent book [LS]. See also [Sz].The basic motivation behind Lambek's theory was to place proof theory in the framework of modern abstract mathematics. The spirit of the latter, at least for the purposes of the present discussion, is to organize mathematical objects into mathematical structures. The specific kind of structure we will be concerned with is category.In Lambek's theory, one starts with an arbitrary theory in any one of several propositional calculi. One has the (formal) proofs (deductions) in the given theory of entailments A ⇒ B, with A and B arbitrary formulas. One introduces an equivalence relation on proofs under which, in particular, equivalent proofs are proofs of the same entailment; equivalence of proofs is intended to capture the idea of the proofs being only inessentially different. One forms a category whose objects are the formulas of the underlying language of the theory, and whose arrows from A to B, with the latter arbitrary formulas, are the equivalence classes of formal proofs of A ⇒ B.
The Baire category theorem in weak subsystems of second-order arithmetic
Authors: Brown Douglas K. , Simpson Stephen G. 
Published: May 2006

AbstractWorking within weak subsystems of second-order arithmetic Z2 we consider two versions of the Baire Category theorem which are not equivalent over the base system RCA0. We show that one version (B.C.T.I) is provable in RCA0 while the second version (B.C.T.II) requires a stronger system. We introduce two new subsystems of Z2, which we call and , and , show that suffices to prove B.C.T.II. Some model theory of and its importance in view of Hilbert's program is discussed, as well as applications of our results to functional analysis.
Consequences of arithmetic for set theory
Authors: Halbeisen Lorenz , Shelah Saharon 
Published: May 2006

AbstractIn this paper, we consider certain cardinals in ZF (set theory without AC, the axiom of choice). In ZFC (set theory with AC), given any cardinals and , either ≤ or ≤ . However, in ZF this is no longer so. For a given infinite set A consider seq1-1(A), the set of all sequences of A without repetition. We compare |seq1-1(A)|, the cardinality of this set, to ||, the cardinality of the power set of A. What is provable about these two cardinals in ZF? The main result of this paper is that ZF ⊢ ∀A(| seq1-1(A)| ≠ ||), and we show that this is the best possible result. Furthermore, it is provable in ZF that if B is an infinite set, then | fin(B)| < | (B*)| even though the existence for some infinite set B* of a function ƒ from fin(B*) onto (B*) is consistent with ZF.
Indécidabilité des corps de courbe réelle
Authors: Bélair Luc , Duret Jean-Louis 
Published: May 2006

Nous dirons qu'un corps (commutatif) K est un corps de courbe réelle sur le corps k si et seulement si c'est une extension de k, ordonnable, finiment engendrée et de degré de transcendance 1 sur k, telle que k soit relativement algébriquement clos dans K. Un tel corps est le corps d'une courbe (plane) définie sur k. De plus si k est réel-clos, toute courbe définie sur k dont K est le corps, a un point régulier rationnel sur k; en effet soit I ⊂ k[X0,…, Xn] l'idéal d'une telle courbe Γ; on a donc: K = k[x0,…, xn] où x0,…, xn sont les classes d'équivalence de X0,…, Xn; (x0,…, xn) est un point régulier de Γ dans la clôture réelle de K, et par modèle-complétude, Γ a un point régulier rationnel sur k.Notre but est d'étendre les résultats de Raphael Robinson [6] sur l'indécidabilité des corps de fractions rationnelles sur un corps ordonnable (dans le langage des corps). Comme lui, nous donnerons une méthode qui ne s'applique que lorsque le corps de base k est réel-clos, et une seconde méthode générate.
Accessible telephone directories
Authors: Goode John B. 
Published: May 2006

AbstractWe reduce to a standard circuit-size complexity problem a relativisation of the P=NP question that we believe to be connected with the same question in the model for computation over the reals defined by L. Blum. M. Shub, and S. Smale. On this occasion, we set the foundations of a general theory for computation over an arbitrary structure, extending what these three authors did in the case of rings.