bluuebunny/crossref_metadata_2025_split huggingface dataset:
Recursion in a quantifier vs. elementary induction
Authors: Kolaitis Phokion G. 
Published: May 2006

Spector [21] proved that a relation R on ω is Π11 if and only if it is (positive elementary) inductive on the structure 〈ω, +, ·〉; Kleene [8] showed that R is Π11 if and only if it is semirecursive in the type 2 object E. These two “constructive” characterizations of the Π11 relations have led to the independent study of (positive elementary) induction and recursion in E on an arbitrary structure, as natural generalizations of the theory of Π11 relations on (ω, +, · 〉.The theory of (positive elementary) induction on an arbitrary structure was developed by Moschovakis in his book Elementary induction on abstract structures (EIAS); one of the most important theorems there is a generalization of the classical theorem of Spector [20] and Gandy [3] about the Π11 relations on ω: a relation R is inductive on an acceptable structure . if and only if there is a formula φ(Y, x) of the language of such that:where HYP is the collection of hyperelementary relations on .Moschovakis [17] and Kechris and Moschovakis [6] showed how to develop the theory of recursion in higher types as a chapter in the general theory of inductive definability. This approach to recursion in higher types makes it possible to use methods from the theory of inductive definability in studying recursion in E.In this paper we establish some results about recursion in E on a structure which bolster the naturalness of this theory and contribute to its comparison with (positive elementary) induction.
Ramsey cardinals and constructibility
Authors: Mitchell William 
Published: May 2006

Large cardinal properties divide rather strikingly into two groups. “Small” large cardinal properties such as weak compactness always relativize to L, while in contrast “large” large cardinal properties such as Ramsey are incompatible with L. These properties seem to be similar otherwise and this sense of similarity is reinforced by the fact that many of the large cardinals do exist in the L-like model L(μ). This paper will show that the division is caused by an artificially restrictive class of “constructible” sets rather than an essential difference in the properties themselves. Specifically, we consider the class K of sets constructible from mice as defined by Dodd and Jensen [3] and proveTheorem 1. If ρ is Ramsey then ρ is Ramsey in K.A modification of the proof will showTheorem 2. If ρ is Jonson, then ρ is Ramsey in K.Since Ramsey implies Jonson this shows that the notions are equiconsistent. Theorem 2 was proved by Kunen [5] under the assumption that V = L(μ).The proof of Theorems 1 and 2 depends heavily on results of Dodd and Jensen [3] about K and mice. These results are stated without proof in §2. §2 also contains elementary (to a reader familiar with the theory of iterated ultrapowers) proofs of special cases of some of these lemmas sufficient to give a self contained proof of the following corollary of Theorem 1:Corollary. If ρ ≤ κ,ρ is Ramsey and L(μ) ⊨ μ is a measure on κ then L(μ) ⊨ ρ is Ramsey.
Automorphisms of supermaximal subspaces
Authors: Downey R. G. , Hird G. R. 
Published: May 2006

An infinite-dimensional vector space V∞ over a recursive field F is called fully effective if V∞ is a recursive set identified with ω upon which the operations of vector addition and scalar multiplication are recursive functions, identity is a recursive relation, and V∞ has a dependence algorithm, that is a uniformly effective procedure which when applied to x, a1,…,an, ∈ V∞ determines whether or not x is an element of {a1,…,an}* (the subspace generated by {a1,…,an}). The study of V∞, and of its lattice of r.e. subspaces L(V∞), was introduced in Metakides and Nerode [15]. Since then both V∞ and L(V∞) (and many other effective algebraic systems) have been studied quite intensively. The reader is directed to [5] and [17] for a good bibliography in this area, and to [15] for any unexplained notation and terminology.In [15] Metakides and Nerode observed that a study of L(V∞) may in some ways be modelled upon a study of L(ω), the lattice of r.e. sets. For example, they showed how an e-state construction could be modified to produce an r.e. maximal subspace, where M ∈ L(V∞) is maximal if dim(V∞/M) = ∞ and, for all W ∈ L(V∞), if W ⊃ M then either dim(W/M) < ∞ or dim(V∞/W) < ∞.However, some of the most interesting features of L(V∞) are those which do not have analogues in L(ω). Our concern here, which is probably one of the most striking characteristics of L(V∞), falls into this category. We say M ∈ L(V∞) is supermaximal if dim(V∞/M) = ∞ and for all W ∈ L(V∞), if W ⊃ M then dim(W/M) < ∞ or W = V∞. These subspaces were discovered by Kalantari and Retzlaff [13].
Bounded existential induction
Authors: Wilmers George 
Published: May 2006

The present work may perhaps be seen as a point of convergence of two historically distinct sequences of results. One sequence of results started with the work of Tennenbaum [59] who showed that there could be no nonstandard recursive model of the system PA of first order Peano arithmetic. Shepherdson [65] on the other hand showed that the system of arithmetic with open induction was sufficiently weak to allow the construction of nonstandard recursive models. Between these two results there remained for many years a large gap occasioned by a general lack of interest in weak systems of arithmetic. However Dana Scott observed that the addition alone of a nonstandard model of PA could not be recursive, while more recently McAloon [82] improved these results by showing that even for the weaker system of arithmetic with only bounded induction, neither the addition nor the multiplication of a nonstandard model could be recursive.Another sequence of results starts with the work of Lessan [78], and independently Jensen and Ehrenfeucht [76], who showed that the structures which may be obtained as the reducts to addition of countable nonstandard models of PA are exactly the countable recursively saturated models of Presburger arithmetic. More recently, Cegielski, McAloon and the author [81] showed that the above result holds true if PA is replaced by the much weaker system of bounded induction.However in both the case of the Tennenbaum phenomenon and in that of the recursive saturation of addition the problem remained open as to how strong a system was really necessary to generate the required phenomenon. All that was clear a priori was that open induction was too weak to produce either result.
On minimal pairs of enumeration degrees
Authors: McEvoy Kevin , Cooper S. Barry 
Published: May 2006

For sets of natural numbers A and B, A is enumeration reducible to B if there is some effective algorithm which when given any enumeration of B will produce an enumeration of A. Gutteridge [5] has shown that in the upper semilattice of the enumeration degrees there are no minimal degrees (see Cooper [3]), and in this paper we study those pairs of degrees with gib 0. Case [1] constructed a minimal pair. This minimal pair construction can be relativised to any gib, and following a suggestion of Jockusch we can also fix one of the degrees and still construct the pair. These methods yield an easier proof of Case's exact pair theorem for countable ideals. 0″ is an upper bound for the minimal pair constructed in §1, and in §2 we improve this bound to any Σ2-high Δ2 degree. In contrast to this we show that every low degree c bounds a degree a which is not in any minimal pair bounded by c. The structure of the co-r.e. e-degrees is isomorphic to that of the r.e. Turing degrees, and Gutteridge has constructed co-r.e. degrees which form a minimal pair in the e-degrees. In §3 we show that if a, b is any minimal pair of co-r.e. degrees such that a is low then a, b is a minimal pair in the e-degrees (and so Gutteridge's result follows). As a corollary of this we can embed any countable distributive lattice and the two nondistributive five-element lattices in the e-degrees below 0′. However the lowness assumption is necessary, as we also prove that there is a minimal pair of (high) r.e. degrees which is not a minimal pair in the e-degrees (under the isomorphism). In §4 we present more concise proofs of some unpublished work of Lagemann on bounding incomparable pairs and embedding partial orderings.As usual, {Wi}i ∈ ω is the standard listing of the recursively enumerable sets, Du is the finite set with canonical index u and {‹ m, n ›}m, n ∈ ω is a recursive, one-to-one coding of the pairs of numbers onto the numbers. Capital italic letters will be variables over sets of natural numbers, and lower case boldface letters from the beginning of the alphabet will vary over degrees.
Between strong and superstrong
Authors: Baldwin Stewart 
Published: May 2006

Definition. A cardinal κ is strong iff for every x there is an elementary embedding j:V → M with critical point κ such that x ∈ M.κ is superstrong iff ∃j:V → M with critical point κ such that Vj(κ) ∈ M.These definitions are natural weakenings of supercompactness and hugeness respectively and display some of the same relations. For example, if κ is superstrong then Vκ ⊨ “∃ proper class of strong cardinals”, but the smallest superstrong cardinal is less than the smallest strong cardinal (if both types exist). (See [SRK] and [Mo] for the arguments involving supercompact and huge, which translate routinely to strong and superstrong.)Given any two types of large cardinals, a typical vague question which is often asked is “How large is the gap in consistency strength?” In one sense the gap might be considered relatively small, since the “higher degree” strong cardinals described below (a standard trick that is nearly always available) and the Shelah and Woodin hierarchies of cardinals (see [St] for a definition of these) seem to be (at least at this point in time) the only “natural” large cardinal properties lying between strong cardinals and superstrong cardinals in consistency strength.
Attention à la marche!
Authors: Poizat Bruno 
Published: May 2006

Quoi qu'en pensent certains, la déviation de Saharon Shelah n'est pas qu'une construction technique servant à un résultat plus technique encore, le théorème de classification; c'est la notion de dépendance la plus générale qui soit apparue dans un contexte mathématique, si bien que toute propriété qu'on pourra attribuer à cette déviation sera, dans le fond, une propriété de la notion même de corrélation.L'auteur de ces lignes a trouvé la vie beaucoup plus plaisante quand il a pu lire la déviation, associée à une théorie stable T, dans un ordre qu'il était facile de définir sur les types complets au-dessus des modèles de T; s'il a qualifié cet ordre de “fondamental”, ce n'est pas pour donner une emphase hors de propos à sa modeste contribution au démélage de l'échevau shelahien, mais parce que le rang U de Lascar n'était autre que le rang de fondation de l'ordre fondamental.L'ordre fondamental condense l'essentiel de la déviation, sous une forme pour ainsi dire graphique; certes, tout ne peut s'y retrouver, et en particulier des théories peuvent avoir des ordres fondamentaux semblables si on se limite aux 1-types, et fort différents si on regarde aussi les bitypes; mais il est clair que dès qu'apparait l'ordre fondamental se pose de façon urgente le problème de décrire tous les ordres qui peuvent être ordre fondamental d'une théorie stable: tant que ce programme n'est pas rempli, il reste des propriétés cachées de la déviation.
Stability theory for topological logic, with applications to topological modules
Authors: Kucera T. G. 
Published: May 2006

In this paper I show how to develop stability theory within the context of the topological logic first introduced by McKee [Mc 76], Garavaglia [G 78] and Ziegler [Z 76]. I then study some specific applications to topological modules; in particular I prove two quantifier élimination theorems, one a generalization of a result of Garavaglia.In the first section I present a summary of basic results on topological model theory, mostly taken from the book of Flum and Ziegler [FZ 80]. This is done primarily to fix notation, but I also introduce the notion of anLt-elementary substructure. The important point with this concept, as with many others, appears to be to allow only individuals to appear as parameters, not open sets.In the second section I begin the study of stability theory forLt. I first develop a translation of the topological languageLtinto an ordinary first-order languageL*. The first main theorem is (2.3), which shows that the translation is faithful to the model-theoretic content ofLt, and provides the necessary tools for studyingLttheories in the context of ordinary first-order logic. The translation allows me to considerindividual stability theoryforLt: the stability-theoretic study of those types ofLtin which only individual variables occur freely and in which only individuals occur as parameters. I originally developed this stability theory entirely withinLt; the fact that the theorems and their proofs were virtually identical to those in ordinary first order logic suggested the reduction fromLttoL*.
Inverse topological systems and compactness in abstract model theory
Authors: Mundici Daniele 
Published: May 2006

AbstractGiven an abstract logic , generated by a set of quantifiers Qi, one can construct for each type τ a topological space Sτ, exactly as one constructs the Stone space for τ in first-order logic. Letting T be an arbitrary directed set of types, the set is an inverse topological system whose bonding mappings are naturally determined by the reduct operation on structures. We relate the compactness of to the topological properties of ST. For example, if I is countable then is compact iff for every τ each clopen subset of Sτ is of finite type and Sτ, is homeomorphic to limST, where T is the set of finite subtypes of τ. We finally apply our results to concrete logics.
Toward useful type-free theories. I
Authors: Feferman Solomon 
Published: May 2006

There is a distinction betweensemantical paradoxeson the one hand andlogicalormathematical paradoxeson the other, going back to Ramsey [1925]. Those falling under the first heading have to do with such notions astruth, assertion(orproposition), definition, etc., while those falling under the second have to do withmembership, class, relation, function(and derivative notions such ascardinalandordinal number), etc. There are a number of compelling reasons for maintaining this separation but, as we shall see, there are also many close parallels from the logical point of view.The initial solutions to the paradoxes on each side—namely Russell's theory of types for mathematics and Tarski's hierarchy of language levels for semantics— were early recognized to be excessively restrictive. The first really workable solution to the mathematical paradoxes was provided by Zermelo's theory of sets, subsequently improved by Fraenkel. The informal argument that the paradoxes are blocked in ZF is that its axioms are true in thecumulative hierarchy of setswhere (i) unlike the theory of types, a set may have members of various (ordinal) levels, but (ii) as in the theory of types, the level of a set is greater than that of each of its members. Thus in ZF there is no set of all sets, nor any Russell set {x∣x∉x} (which would be universal since∀x(x∉x) holds in ZF). Nor is there a set of all ordinal numbers (and so the Burali-Forti paradox is blocked).
Effectively nowhere simple sets
Authors: Miller D. , Remmel J. B. 
Published: May 2006

An r.e. set A is nowhere simple if for every r.e. set We such that We − A is infinite, there is an infinite r.e. set W such that W ⊆ We − A. The definition of nowhere simple sets is due to R. Shore in [4]. In [4], Shore studied various properties of nowhere simple sets and showed that they could be used to give an elegant and simple proof of the fact that every nontrivial class of r.e. sets C closed under recursive isomorphisms is an automorphism base for , the lattice of r.e. sets modulo finite sets, (that is, an automorphism α of is completely determined by its action on C; see Theorem 8 of [4]). Shore also defined the notion of effectively nowhere simple sets.Definition. An r.e. set A is effectively nowhere simple if there is a recursive function f such that for every i, Wf(i) ⊆ Wi − A and Wf(i) is infinite iff Wi − A is infinite. f is called a witness function for A.Other than to produce examples of effectively nowhere simple sets and nowhere simple sets that are not effectively nowhere simple, Shore did not concern himself with the properties of effectively nowhere simple sets since he felt that effectively nowhere simple sets were unlikely to be lattice invariant in either E, the lattice of r.e. sets, or in .
An extended joint consistency theorem for a family of free modal logics with equality
Authors: Gumb Raymond D. 
Published: May 2006

In this paper, we establish an extended joint consistency theorem for an infinite family of free modal logics with equality. The extended joint consistency theorem incorporates the Craig and Lyndon interpolation lemmas and the Robinson joint consistency theorem. In part, the theorem states that two theories which are jointly unsatisfiable are separated by a sentence in the vocabulary common to both theories.Our family of free modal logics includes the free versions of I, M, and S4 studied by Leblanc [5, Chapters 8 and 9], supplemented with equality as in [3]. In the relational semantics for these logics, there is no restriction on the accessibility relation in I, while in M(S4) the restriction is reflexivity (refiexivity and transitivity). We say that a restriction on the accessibility relation countenances backward-looping if it implies a sentence of the form ∀x1 …xn(x1Rx2 &…&xn ⊃ xkRxj) (1 ≤ j < k ≤ n ≥ 2), where the xi (1 ≤ i ≤ n) are distinct individual variables. Just as reflexivity and transitivity do not countenance backward-looping, neither do any of the restrictions in our family of free modal logics. (The above terminology is derived from the effect of such restrictions on Kripke tableaux constructions.) The Barcan formula, its converse, the Fitch formula, and the formula T ≠ T′ ⊃ □T ≠ T′ do not hold in our logics.
Epistemic arithmetic is a conservative extension of intuitionistic arithmetic
Authors: Goodman Nicolas D. 
Published: May 2006

Questions about the constructive or effective character of particular arguments arise in several areas of classical mathematics, such as in the theory of recursive functions and in numerical analysis. Some philosophers have advocated Lewis's S4 as the proper logic in which to formalize such epistemic notions. (The fundamental work on this is Hintikka [4].) Recently there have been studies of mathematical theories formalized with S4 as the underlying logic so that these epistemic notions can be expressed. (See Shapiro [7], Myhill [5], and Goodman [2]. The motivation for this work is discussed in Goodman [3].) The present paper is a contribution to the study of the simplest of these theories, namely first-order arithmetic as formalized in S4. Following Shapiro, we call this theory epistemic arithmetic (EA). More specifically, we show that EA is a conservative extension of Hey ting's arithmetic HA (ordinary first-order intuitionistic arithmetic). The question of whether EA is conservative over HA was raised but left open in Shapiro [7].The idea of our proof is as follows. We interpret EA in an infinitary propositional S4, pretty much as Tait, for example, interprets classical arithmetic in his infinitary classical propositional calculus in [8]. We then prove a cut-elimination theorem for this infinitary propositional S4. A suitable version of the cut-elimination theorem can be formalized in HA. For cut-free infinitary proofs, there is a reflection principle provable in HA. That is, we can prove in HA that if there is a cut-free proof of the interpretation of a sentence ϕ then ϕ is true. Combining these results shows that if the interpretation of ϕ is provable in EA, then ϕ is provable in HA.
Existentially closed torsion-free nilpotent groups of class three
Authors: Maier Berthold J. 
Published: May 2006

We denote by and the classes of torsion-free nilpotent groups of nilpotency class at most two and three, respectively. In this paper we show that most of the known results about existentially closed (e.c.) groups in remain true in : Up to isomorphism, there exist only countably many countable e.c. groups and they are distinguished by the ranks of their centers. An e.c. group is finitely (infinitely) generic if and only if the center has dimension one (≥ω). Apart from trivial exceptions, e.c, algebraically closed, and “closed with respect to systems of equations in one unknown” are equivalent.Let K be a class of groups. A group G ϵ K is called existentially closed in K if G contains a solution of any finite system Σ of equations and inequations with constants in G and one or more unknowns, provided that Σ has a solution in some in K. If Σ may contain equations (in at most n unknowns) only, G is called algebraically closed (n-unknown closed [1]). We use the abbreviations e.c, a.c and n-u.c. throughout. For more background on these terms the reader is referred to [3] and [4]. We also assume a basic knowledge of generic structures. The main group theoretic notions needed here are explained in §2; [2] and [11] are the general references for this field.
On choice sequences determined by spreads
Authors: van der Hoeven Gerrit , Moerdijk Ieke 
Published: May 2006

From the moment choice sequences appear in Brouwer's writings, they do so as elements of a spread. This led Kreisel to take the so-called axiom of spreaddata as the basic axiom in a formal theory of choice sequences (Kreisel [1965, pp. 133–136]). This axiom expresses the idea that to be given a choice sequence means to be given a spread to which the choice sequence belongs. Subsequently, however, it was discovered that there is a formal clash between this axiom and closure of the domain of choice sequences under arbitrary (lawlike) continuous operations (Troelstra [1968]). For this reason, the formal system CS was introduced (Kreisel and Troelstra [1970]), in which spreaddata is replaced by analytic data. In this system CS, the domain of choice sequences is closed under all continuous operations, and therefore it provides a workable basis for intuitionistic analysis. But the problem whether the axiom of spreaddata is compatible with closure of the domain of choice sequences under the continuous operations from a restricted class, which is still rich enough to validate the typical axioms of continuous choice, remained open. It is precisely this problem that we aim to discuss in this paper.Recall that a spread is a (lawlike, inhabited) decidable subtree S of the tree N< N of all finite sequences, having all branches infinite: