bluuebunny/crossref_metadata_2025_split huggingface dataset:
Uniqueness and characterization of prime models over sets for totally transcendental first-order theories
Authors: Shelah Saharon 
Published: May 2006

If T is a complete first-order totally transcendental theory then over every T-structure A there is a prime model unique up to isomorphism over A. Moreover M is a prime model over A iff: (1) every finite sequence from M realizes an isolated type over A, and (2) there is no uncountable indiscernible set over A in M.The existence of prime models was proved by Morley [3] and their uniqueness for countable A by Vaught [9]. Sacks asked (see Chang and Keisler [1, question 25]) whether the prime model is unique. After proving this I heard Ressayre had proved that every two strictly prime models over any T-structure A are isomorphic, by a strikingly simple proof. From this followsIf T is totally transcendental, M a strictly prime model over A then every elementary permutation of A can be extended to an automorphism of M. (The existence of M follows by [3].)By our results this holds for any prime model. On the other hand Ressayre's result applies to more theories. For more information see [6, §0A]. A conclusion of our theorem is the uniqueness of the prime differentially closed field over a differential field. See Blum [8] for the total transcendency of the theory of differentially closed fields.We can note that the prime model M over A is minimal over A iff in M there is no indiscernible set over A (which is infinite).
Nonrecursive tilings of the plane. I
Authors: Hanf William 
Published: May 2006

A finite set of tiles (unit squares with colored edges) is said to tile the plane if there exists an arrangement of translated (but not rotated or reflected) copies of the squares which fill the plane in such a way that abutting edges of the squares have the same color. The problem of whether there exists a finite set of tiles which can be used to tile the plane but not in any periodic fashion was proposed by Hao Wang [9] and solved by Robert Berger [1]. Raphael Robinson [7] gives a more detailed history and a very economical solution to this and related problems; we will assume that the reader is familiar with §4 of [7]. In 1971, Dale Myers asked whether there exists a finite set of tiles which can tile the plane but not in any recursive fashion. If we make an additional restriction (called the origin constraint) that a given tile must be used at least once, then the positive answer is given by the main theorem of this paper. Using the Turing machine constructed here and a more complicated version of Berger and Robinson's construction, Myers [5] has recently solved the problem without the origin constraint.Given a finite set of tiles T1, …, Tn, we can describe a tiling of the plane by a function f of two variables ranging over the integers. f(i, j) = k specifies that the tile Tk is to be placed at the position in the plane with coordinates (i, j). The tiling will be said to be recursive if f is a recursive function.
An incomplete nonnormal extension of S3
Authors: Schumm George F. 
Published: May 2006

Fine [1] and Thomason [4] have recently shown that the familiar relational semantics of Kripke [2] is inadequate for certain normal extensions of T and S4. It is here shown that the more general semantics developed by Kripke in [3] to handle nonnormal modal logics is likewise inadequate for certain of those logics.The interest of incompleteness results, such as those of Fine and Thomason, is of course a function of one's expectations. Define a “normal” logic too broadly and it is not surprising that a given semantics is not adequate for all normal logics. In the case of relational semantics, for example, one would want to require at least that a normal logic contain T, the logic determined by the class of all normal frames, and that it be closed under certain (though perhaps not all) rules of inference which are validity preserving in such frames. The adequacy of that semantics will otherwise be ruled out at the outset.For Kripke a logic is normal if it contains all tautologies, □p→p and □ (p → q)→(□p → □q), and is closed under the rules of substitution, modus ponens and necessitation (from A infer □A). T is the smallest normal logic, and this fact, together with the “naturalness” of the definition and the enormous number of normal logics which have been shown to be complete, made it plausible to suppose that Kripke's original semantics was adequate for all normal logics. That it is not is indeed surprising and would seem to reveal a genuine shortcoming.
String theory
Authors: Corcoran John , Frank William , Maloney Michael 
Published: May 2006

AbstractFor eachn> 0, two alternative axiomatizations of the theory of strings overnalphabetic characters are presented. One class of axiomatizations derives from Tarski's system of theWahrheitsbegriffand uses thencharacters and concatenation as primitives. The other class involves usingncharacter-prefixing operators as primitives and derives from Hermes'Semiotik. All underlying logics are second order. It is shown that, for eachn, the two theories are synonymous in the sense of deBouvere. It is further shown that each member of one class is synonymous with each member of the other class; thus that all of the theories are synonymous with each other and with Peano arithmetic. Categoricity of Peano arithmetic then implies categoricity of each of the above theories.
Cores of Π11 sets of reals
Authors: Blass Andreas , Cenzer Douglas 
Published: May 2006

A classical result of descriptive set theory expresses every co-analytic subset of the real line as the union of an increasing sequence of Borel sets, the length of the chain being at most the first uncountable ordinal ℵ1 (see [5], [8]). An effective analog of this theorem, obtained by replacing co-analytic (Π11) and Borel (Δ11) with their lightface analogs, would represent every Π11 subset of the real line as the union of a chain of Δ11 sets. No such analog is true, however, because some Δ11 sets are not the union of their Δ11 subsets. For example, the set W, consisting of those reals which code well-orderings (in some standard coding) is Π11, but, by the boundedness principle ([3], [9]), any Δ11 subset of W contains codes only for well-orderings shorter than ω1, the first nonrecursive ordinal. Accordingly, we define the core of a Π11 set to be the union of its Δ11 subsets; clearly this is the largest subset of the given Π11 set for which an effective version of the classical representation could exist.In §1, we develop the elementary properties of cores of Π11 sets. For example, such a core is itself Π11 and can be represented as the union of a chain of Δ11 sets in a natural way; the chain will have length at most ω1. We show that the core of a Π11 set is “almost all” of the set, while on the other hand there are uncountable Π11 sets with empty cores.
An ω1-categorical ring which is not almost strongly minimal
Authors: Podewski K.-P. , Reineke J. 
Published: May 2006

A very important example of almost strongly minimal theories are the algebraically closed fields. A. Macintyre has shown [3] that every ω1-categorical field is algebraically closed. Therefore every ω1-categorical field is almost strongly minimal. It will be shown that not every ω1-categorical ring is almost strongly minimal.Let R0 be the factor ring C[y/(y2), where C[y] is the ring of polynomials in the indeterminate y over the field of complex numbers and (y2) the ideal generated by y2 in C[y].It is straightforward to prove that R0 has the following properties:1. R0 is a commutative ring with identity.2. R0 is of characteristic 0.3. For every polynomial p(x) = ∑ a1x1 ∈ R0[x] with of ai2 ≠ 0 for some i > 0 there is an a ∈ R0 such that p(a) · p(a) = 0.4. For all x, y ∈ R0 such that x2 = 0 and y ≠ 0 there exists a z ∈ R0 with y · z = x.5. There is an x ≠ 0 such that x2 = 0.These properties can be ∀∃-axiomatised in a countable first order logic (see [4]). Let T be the set of these sentences. With Theorem 7 we get that T is model-complete.If R is a model of T then I shall denote {a ∈ R ∣ a2 = 0}.
On subcreative sets and S-reducibility
Authors: Gill John T. , Morris Paul H. 
Published: May 2006

AbstractSubcreative sets, introduced by Blum, are known to coincide with the effectively speedable sets. Subcreative sets are shown to be the complete sets with respect to S-reducibility, a special case of Turing reducibility. Thus a set is effectively speedable exactly when it contains the solution to the halting problem in an easily decodable form. Several characterizations of subcreative sets are given, including the solution of an open problem of Blum, and are used to locate the subcreative sets with respect to the complete sets of other reducibilities. It is shown that q-cylindrification is an order-preserving map from the r.e. T-degrees to the r.e. S-degrees. Consequently, T-complete sets are precisely the r.e. sets whose q-cylindrifications are S-complete.
An α-finite injury method of the unbounded type
Authors: Chong C. T. 
Published: May 2006

Let α be an admissible ordinal. In this paper we study the structure of the upper semilattice of α-recursively enumerable degrees. Various results about the structure which are of fundamental importance had been obtained during the past two years (Sacks-Simpson [7], Lerman [4], Shore [9]). In particular, the method of finite priority argument of Friedberg and Muchnik was successfully generalized in [7] to an α-finite priority argument to give a solution of Post's problem for all admissible ordinals. We refer the reader to [7] for background material, and we also follow closely the notations used there.Whereas [7] and [4] study priority arguments in which the number of injuries inflicted on a proper initial segment of requirements can be effectively bounded (Lemma 2.3 of [7]), we tackle here priority arguments in which no such bounds exist. To this end, we focus our attention on the fine structure of Lα, much in the fashion of Jensen [2], and show that we can still use a priority argument on an indexing set of requirements just short enough to give us the necessary bounds we seek.
Generalized interpolation theorems
Authors: Garland Stephen J. 
Published: May 2006

Chang [1], [2] has proved the following generalization of the Craig interpolation theorem [3]: For any first-order formulas φ and ψ with free first- and second-order variables among ν1, …, νn, R and ν1, …, νn, S respectively, and for any sequence Q1, …, Qn of quantifiers such that Q1 is universal whenever ν1 is a second-order variable, ifthen there is a first-order formula θ with free variables among ν1, …, νn such that(Note that the Craig interpolation theorem is the special case of Chang's theorem in which Q1, …, Qn are all universal quantifiers.) Chang also raised the question [2, Remark (k)] as to whether the Lopez-Escobar interpolation theorem [6] for the infinitary language Lω1ω possesses a similar generalization. In this paper, we show that the answer to Chang's question is affirmative and, moreover, that several interpolation theorems for applied second-order languages for number theory also possess such generalizations.Maehara and Takeuti [7] have established independently proof-theoretic interpolation theorems for first-order logic and Lω1ω which have as corollaries both Chang's theorem and its analog for Lω1ω. Our proofs are quite different from theirs and rely on model-theoretic techniques stemming from the analogy between the theory of definability in Lω1ω and the theory of Borel and analytic sets of real numbers, rather than the technique of cut-elimination.
Borel sets and hyperdegrees
Authors: Friedman Harvey M. 
Published: May 2006

This paper is concerned with the hyderdegrees of elements of uncountable Borel subsets of ωω. The Borel subsets of ωω are the so-called Δ11 subsets of ωω, which are the subsets of ωω that are Δ11 in some parameter f: ω → ω.The results of this paper were inspired by two earlier results about the hyperdegrees of elements of Σ11 subsets of ωω. The first is known as the Gandy basis theorem, and asserts that the collection of functions of strictly lower hyperdegree than the hyperjump form a basis for the Σ11 subsets of ωω (see Rogers [3, p. 421]). The second is that there exists an uncountable Σ11 subset of ωω no element of which is hyperarithmetic in any other. The latter is credited to Feferman in Harrison [1], and appears there as Corollary 2.7, p. 537.Two questions arise. Can we find other basis theorems if we replace Σ11 by Δ11 in Gandy's result? Can we replace Σ11 by Δ11 in Feferman's result?We simultaneously answer the first positively, and the second negatively by proving that any hyperdegree, in which the hyperjump is hyperarithmetic, forms a basis for the Δ11 subsets of ωω with no hyperarithmetic elements. We conjecture that this holds also for uncountable Δ11 subsets of ωω. This conjecture is open despite the recent claim in Notices of the American Mathematical Society, vol. 19 (1972), p. A616, Abstract 696-02-10.
Algebraically closed commutative rings
Authors: Cherlin G. L. 
Published: May 2006

A commutative ring A is said to be algebraically closed if every finite system of polynomial equations and inequations in one or more variables with coefficients in A which has a solution in some (commutative) extension of A already has a solution in A. Abraham Robinson's study of model-theoretic forcing has provided powerful new tools for the study of algebraically closed structures in general, and will be applied here to the study of algebraically closed commutative rings. Familiarity with the model-theoretic notions connected with the study of algebraically closed structures is assumed; for background consult [1], [2], and [3].Our main results are the following:1. The theory of commutative rings with identity has no model companion in the sense of Robinson.2. The Hilbert Nullstellensatz, suitably formulated for the class of algebraically closed commutative rings, holds for finitely generated polynomial ideals but fails for certain infinitely generated polynomial ideals.3. If A is algebraically closed, then A/rad A need not be algebraically closed as a semiprime ring: If A is finitely generic then A/rad A is algebraically closed as a semiprime ring, but if A is infinitely generic then A/rad A is not algebraically closed as a semiprime ring.
Recursively enumerable generic sets
Authors: Maass Wolfgang 
Published: May 2006

AbstractWe show that one can solve Post's Problem by constructing generic sets in the usual set theoretic framework applied to tiny universes. This method leads to a new class of recursively enumerable sets: r.e. generic sets. All r.e. generic sets are low and simple and therefore of Turing degree strictly between 0 and 0′. Further they supply the first example of a class of low recursively enumerable sets which are automorphic in the lattice ℰ of recursively enumerable sets with inclusion. We introduce the notion of a promptly simple set. This describes the essential feature of r.e. generic sets with respect to automorphism constructions.
Models of arithmetic and closed ideals
Authors: Knight Julia , Nadel Mark 
Published: May 2006

A set J of Turing degrees is called an ideal if (1) J ≠ ∅, (2) for any pair of degrees ã, , if ã, ϵ J, then ã ⋃ ϵJ, and (3) for any ⋃ ϵ J and any , if < ⋃, then ϵ J. A set J of degrees is said to be closed if for any theory T with a set of axioms of degree in J, T has a completion of degree in J.Closed ideals of degrees arise naturally in the following way. If is a recursively saturated structure, let I() = { for some ā ϵ }. Let D() = {: is recursive in d-saturated}. (Recursive in d-saturation is defined like recursive saturation except that the sets of formulas considered are recursive in d.) These two sets of degrees were investigated in [2]. It was shown that if is a recursively saturated model of P, Pr = Th(ω, +), or Pr′ = Th(Z, +, 1), then I() = D(), and this set is a closed ideal. Any closed ideal J can be represented as I() = D() for some recursively saturated model of Pr′. For sets J of power at most ℵ1, Pr′ can be replaced by P.Assuming CH, all closed ideals have power at most ℵ1, but if CH fails, there are closed ideals of power greater than ℵ1, and it is not known whether these can be represented as I() = D() for a recursively saturated model of P.In the present paper, it will first be shown that information about representation of closed ideals provides new information about an old problem of MacDowell and Specker [6] and extends an old result of Scott [8] in a natural way. It will also be shown that the representation results from [2] answer a problem of Friedman [1]. This part of the paper is aimed at convincing the reader that representation problems are worth investigating.
Σ1-separation
Authors: Abramson Fred G. 
Published: May 2006

AbstractLet A be a standard transitive admissible set. Σ1-separation is the principle that whenever X and Y are disjoint Σ1A subsets of A then there is a ⊿1A subset S of A such that X ⊆ S and Y ∩ S = ∅.Theorem. If satisfies Σ-separation, then(1) If 〈Tn∣n < ω) ϵ A is a sequence of trees on ω each of which has at most finitely many infinite paths in A then the function n ↦ (set of infinite paths in A through Tn) is in A.(2) If A is not closed under hyperjump and α = OnA then A has in it a nonstandard model of V = L whose ordinal standard part is α.Theorem. Let α be any countable admissible ordinal greater than ω. Then there is a model of Σ1-separation whose height is α.
Recursion theory on orderings. I. A model theoretic setting
Authors: Metakides G. , Remmel J.B. 
Published: May 2006

In [6], Metakides and Nerode introduced the study of the lattice of recursively enumerable substructures of a recursively presented model as a means to understand the recursive content of certain algebraic constructions. For example, the lattice of recursively enumerable subspaces,, of a recursively presented vector spaceV∞has been studied by Kalantari, Metakides and Nerode, Retzlaff, Remmel and Shore. Similar studies have been done by Remmel [12], [13] for Boolean algebras and by Metakides and Nerode [9] for algebraically closed fields. In all of these models, the algebraic closure of a set is nontrivial. (The formal definition of the algebraic closure of a setS, denoted cl(S), is given in §1, however in vector spaces, cl(S) is just the subspace generated byS, in Boolean algebras, cl(S) is just the subalgebra generated byS, and in algebraically closed fields, cl(S) is just the algebraically closed subfield generated byS.)In this paper, we give a general model theoretic setting (whose precise definition will be given in §1) in which we are able to give constructions which generalize many of the constructions of classical recursion theory. One of the main features of the modelswhich we study is that the algebraic closure of setis just itself, i.e., cl(S) = S. Examples of such models include the natural numbers under equality 〈N, = 〉, the rational numbers under the usual ordering 〈Q, ≤〉, and a large class ofn-dimensional partial orderings.
Notes on the stability of separably closed fields
Authors: Wood Carol 
Published: May 2006

AbstractThe stability of each of the theories of separably closed fields is proved, in the manner of Shelah's proof of the corresponding result for differentially closed fields. These are at present the only known stable but not superstable theories of fields. We indicate in §3 how each of the theories of separably closed fields can be associated with a model complete theory in the language of differential algebra. We assume familiarity with some basic facts about model completeness [4], stability [7], separably closed fields [2] or [3], and (for §3 only) differential fields [8].
On definition trees of ordinal recursive functionals: Reduction of the recursion orders by means of type level raising
Authors: Terlouw Jan 
Published: May 2006

It is known that every < ε0-recursive function is also a primitive recursive functional. Kreisel has proved this by means of Gödel's functional-interpretation, using that every < ε0-recursive function is provably recursive in Heyting's arithmetic [2, §3.4]. Parsons obtained a refinement of Kreisel's result by a further examination of Gödel's interpretation with regard to type levels [3, Theorem 5], [4, §4]. A quite different proof is provided by the research into extensions of the Grzegorczyk hierarchy as done by Schwichtenberg and Wainer: this yields another characterization of the < ε0-recursive functions from which easily appears that these are primitive recursive functionals (see [5] in combination with [6, Chapter II]).However, these proofs are indirect and do not show how, in general, given a definition tree of an ordinal recursive functional, transfinite recursions can be replaced (in a straightforward way) by recursions over wellorderings of lower order types. The argument given by Tait in [9, pp. 189–191] seems to be an improvement in this respect, but the crucial step in it is (at least in my opinion) not very clear.
AD and the supercompactness of ℵ1
Authors: Becker Howard 
Published: May 2006

Since the discovery of forcing in the early sixties, it has been clear that many natural and interesting mathematical questions are not decidable from the classical axioms of set theory, ZFC. Therefore some mathematicians have been studying the consequences of stronger set theoretic assumptions. Two new types of axioms that have been the subject of much research are large cardinal axioms and axioms asserting the determinacy of definable games. The two appear at first glance to be unrelated; one of the most surprising discoveries of recent research is that this is not the case.In this paper we will be assuming the axiom of determinacy (AD) plus the axiom of dependent choice (DC). AD is false, since it contradicts the axiom of choice. However every set in L[R] is ordinal definable from a real. Our axiom that definable games are determined implies that every game in L[R] is determined (in V), and since a strategy is a real, it is determined in L[R]. That is, L[R] ⊨ AD. The axiom of choice implies L[R] ⊨ DC. So by embedding ourselves in L[R], we can assume AD + DC and begin proving theorems. These theorems true in L[R] imply corresponding theorems in V, by e.g. changing “every set” to “every set in L[R]”. For more information on AD as an axiom, and on some of the points touched on here, the reader should consult [14], particularly §§7D and 8I. In this paper L[R] will no longer even be mentioned. We just assume AD for the rest of the paper.
On the interpolation theorem for the logic of constant domains
Authors: López-Escobar E. G. K. 
Published: May 2006

In Gabbay [1] it is stated as an open problem whether or not Craig's Theorem holds for the logic of constant domains CD, i.e. for the extension of the intuitionistic predicate calculus, IPC, obtained by adding the schema; . Then in the later article, [2], Gabbay gives a proof of it. The proof given in [2] is via Robinson's (weak) consistency theorem and depends on relatively complicated (Kripke-) model-theoretical constructions developed in [1] (see p. 392 of [1] for a brief sketch of the method). The aim of this note is to show that the interpolation theorem for CD can also be obtained, by simple proof-theoretic methods, from §80 of Kleene's Introduction to Metamathematics [3].GI is the classical formal system whose postulates are given on p. 442 of [3]. Let GD be the system obtained from GI by the following modifications: (1) the sequents of GD are to have at most two formulas in their succedents and (2) the intuitionistic restriction that Θ be empty is required for the succedent rules (→ ¬) and (→ ⊃). It is a simple matter to show that: , x not free in . It then follows that, using Theorem 46 of [3], if then .