bluuebunny/crossref_metadata_2025_split huggingface dataset:
On the elementary theory of pairs of real closed fields. II
Authors: Baur Walter 
Published: May 2006

Let ℒ be the first order language of field theory with an additional one place predicate symbol. In [B2] it was shown that the elementary theory T of the class of all pairs of real closed fields, i.e., ℒ-structures ‹K, L›, K a real closed field, L a real closed subfield of K, is undecidable.The aim of this paper is to show that the elementary theory Ts of a nontrivial subclass of containing many naturally occurring pairs of real closed fields is decidable (Theorem 3, §5). This result was announced in [B2]. An explicit axiom system for Ts will be given later. At this point let us just mention that any model of Ts, is elementarily equivalent to a pair of power series fields ‹R0((TA)), R1((TB))› where R0 is the field of real numbers, R1 = R0 or the field of real algebraic numbers, and B ⊆ A are ordered divisible abelian groups. Conversely, all these pairs of power series fields are models of Ts.Theorem 3 together with the undecidability result in [B2] answers some of the questions asked in Macintyre [M]. The proof of Theorem 3 uses the model theoretic techniques for valued fields introduced by Ax and Kochen [A-K] and Ershov [E] (see also [C-K]). The two main ingredients are(i) the completeness of the elementary theory of real closed fields with a distinguished dense proper real closed subfield (due to Robinson [R]),(ii) the decidability of the elementary theory of pairs of ordered divisible abelian groups (proved in §§1-4).I would like to thank Angus Macintyre for fruitful discussions concerning the subject. The valuation theoretic method of classifying theories of pairs of real closed fields is taken from [M].
Model-complete theories of formally real fields and formally p-adic fields
Authors: Wheeler William H. 
Published: May 2006

The complete, model-complete theories of pseudo-algebraically closed fields were characterized completely in [11]. That work constituted the first step towards determining all the model-complete theories of fields in the usual language of fields. In this paper the second step is taken. Namely, the methods of [11] are extended to characterize the complete, model-complete theories of pseudo-real closed fields and pseudo-p-adically closed fields.In order to unify the treatment of these two types of fields, the relevant properties of real closed ordered fields and p-adically closed valued fields are abstracted. The subsequent investigation of model-complete theories of fields is based entirely on these properties. The properties were selected in order to solve three problems: (1) finding universal theories with the joint embedding property, (2) finding first order conditions in the usual language of fields which are necessary and sufficient for a polynomial over a field to have a zero in a formally real or formally p-adic extension of that field, and (3) finding subgroups of Galois groups whose fixed fields are formally real or formally p-adic.This paper is related to, and uses in §1 but not in the other sections, parts of K. McKenna's work [8] on model-complete theories of ordered fields and p-valued fields. However, the results herein are not direct consequences of his work, both because these results apply to a more general situation and because they use a different formal language. Concerning the latter point, in some instances, such as real closed ordered fields and p-adically closed valued fields, model-complete theories in expanded languages do yield model-complete theories of ordinary fields other than theories of pseudo-algebraically closed fields. However, in other cases, such as differentially closed fields, this is not so.
Busy beaver sets and the degrees of unsolvability
Authors: Daley Robert P. 
Published: May 2006

In this paper we show how some of the finite injury priority arguments can be simplified by making explicit use of the primitive notions of axiomatic computational complexity theory. Phrases such as “perform n steps in the enumeration of Wi” certainly bear witness to the fact that many of these complexity notions have been used implicitly from the early days of recursive function theory. However, other complexity notions such as that of an “honest” function are not so apparent, neither explicitly nor implicitly. Accordingly, one of the main factors in our simplification of these diagonalization arguments is the replacement of the characteristic function χA of a set A by the function νA, which is the next-element function of the set A. Another important factor is the use of busy beaver sets (see [3]) to provide the basis for the required diagonalizations thereby permitting rather simple and explicit descriptions of the sets constructed. Although the differences between the priority method and our method of construction are subtle, they are nonetheless real and noteworthy.In preparation for the results which follow we devote the remainder of this section to the requisite definitions and notions as well as some preliminary lemmas. A more comprehensive discussion of many of the notions in this section can be found in [3]. Since we will be dealing extensively with relative computations most of our notions here have been correspondingly relativized.
Properties of subtle cardinals
Authors: Henrion Claudia 
Published: May 2006

Subtle cardinals were first introduced in a paper by Jensen and Kunen [JK]. They show that ifκis subtle then ◇κholds. Subtle cardinals also play an important role in [B1], where Baumgartner proposed that certain large cardinal properties should be considered as properties of their associated normal ideals. He shows that in the case of ineffables, the ideals are particularly useful, as can be seen by the following theorem,κis ineffable if and only ifκis subtle andΠ½-indescribableandthe subtle andΠ½-indescribable ideals cohere, i.e. they generate a proper, normal ideal (which in fact turns out to be the ineffable ideal).In this paper we examine properties of subtle cardinals and consider methods of forcing that destroy the property of subtlety while maintaining other properties. The following is a list of results.1) We relativize the following two facts about subtle cardinals:i) ifκisn-subtle then {α<κ:αis notn-subtle} isn-subtle, andii) ifκis (n+ 1)-subtle then {α<κ:αisn-subtle} is in the (n+ 1)-subtle filter to subsets ofκ:i′) ifAis ann-subtle subset ofκthen {α ϵ A:A∩αis notn-subtle} isn-subtle, andii′) ifAis an (n+ 1)-subtle subset ofκthen {α ϵ A:A∩αisn-subtle} is (n+ 1)-subtle.2) We show that although a stationary limit of subtles is subtle, a subtle limit of subtles is not necessarily 2-subtle.3) In §3 we use the technique of forcing to turn a subtle cardinal into aκ-Mahlo cardinal that is no longer subtle.4) In §4 we extend the results of §3 by showing how to turn an (n+ 1)-subtle cardinal into ann-subtle cardinal that is no longer (n+ 1)-subtle.
Relative lawlessness in intuitionistic analysis
Authors: Moschovakis Joan Rand 
Published: May 2006

AbstractThis paper introduces, as an alternative to the (absolutely) lawless sequences of Kreisel and Troelstra, a notion of choice sequence lawless with respect to a given class of lawlike sequences. For countable , the class of -lawless sequences is comeager in the sense of Baire. If a particular well-ordered class of sequences, generated by iterating definability over the continuum, is countable then the -lawless sequences satisfy the axiom of open data and the continuity principle for functions from lawless to lawlike sequences, but fail to satisfy Troelstra's extension principle. Classical reasoning is used.
Elimination of quantifiers for ordered valuation rings
Authors: Dickmann M. A. 
Published: May 2006

Cherlin and Dickmann [2] proved that the theory RCVR of real closed (valuation) rings admits quantifier-elimination (q.e.) in the language ℒ = {+, −, ·, 0, 1, <, ∣} for ordered rings augmented by the divisibility relation “∣”. The purpose of this paper is to prove a form of converse of this result:Theorem. Let T be a theory of ordered commutative domains (which are not fields), formulated in the language ℒ. In addition we assume that:(1) The symbol “∣” is interpreted as the honest divisibility relation:
(2) The following divisibility property holds in T:If T admits q.e. in ℒ, then T = RCVR.We do not know at present whether the restriction imposed by condition (2) can be weakened.The divisibility property (DP) has been considered in the context of ordered valued fields; see [4] for example. It also appears in [2], and has been further studied in Becker [1] from the point of view of model theory. Ordered domains in which (DP) holds are called in [1] convexly ordered valuation rings, for reasons which the proposition below makes clear. The following summarizes the basic properties of these rings:Proposition I [2, Lemma 4]. (1) Let A be a linearly ordered commutative domain. The following are equivalent:(a) A is a convexly ordered valuation ring.(b) Every ideal (or, equivalently, principal ideal) is convex in A.(c) A is a valuation ring convex in its field of fractions quot(A).(d) A is a valuation ring and its maximal ideal MA is convex (in A or, equivalently, in quot (A)).(e) A is a valuation ring and its maximal ideal is bounded by ± 1.
Simple r. e. degree structures
Authors: Lubarsky Robert S. 
Published: May 2006

Much of recursion theory centers on the structures of different kinds of degrees. Classically there are the Turing degrees and r. e. Turing degrees. More recently, people have studied α-degrees for α an ordinal, and degrees over E-closed sets and admissible sets. In most contexts, deg(0) is the bottom degree and there is a jump operator' such that d' is the largest degree r. e. in d and d' > d. Both the degrees and the r. e. degrees usually have a rich structure, including a relativization to the cone above a given degree.A natural exception to this pattern was discovered by S. Friedman [F], who showed that for certain admissible ordinals β the β-degrees ≥ 0′ are well-ordered, with successor provided by the jump.For r. e. degrees, natural counterexamples are harder to come by. This is because the constructions are priority arguments, which require only mild restrictions on the ground model. For instance, if an admissible set has a well-behaved pair of recursive well-orderings then the priority construction of an intermediate r. e. degree (i.e., 0 < d < 0′) goes through [S]. It is of interest to see just what priority proofs need by building (necessarily pathological) admissible sets with few r. e. degrees.Harrington [C] provides an admissible set with two r. e. degrees, via forcing. A limitation of his example is that it needs ω1 (more accurately, a local version thereof) as a parameter. In this paper, we find locally countable admissible sets, some with three r. e. degrees and some with four.
A note on a proof of Hilbert's second ε-theorem
Authors: Ferrari Pier Luigi 
Published: May 2006

The aim of this short note is to correct an error in the proof in [1], more precisely in Remark 1 on page 395, where it is stated that any improper word has rank ≥2. This claim is false; and, consequently, Remark 2, asserting that any 1,0-deduction does not contain improper Q-terms, also fails immediately. In fact, let us consider the wordIt is easily seen that the rank of W is 1, but W is obviously improper. We remark that it is possible, in the same way, to give examples of improper words of rank 1 containing (without subordination) ε-subterms of arbitrarily high rank. In the following section we sketch a corrected version of the proof in order to eliminate all improper ε-terms.We refer to the notation and definitions of [1]. A more extended description of the theories involved can be found in [2].
Completeness of transfinite evaluation in an extension of the lambda calculus
Authors: Sanchis Luis E. 
Published: May 2006

The lambda calculus was conceived by Church, and to some extent by Curry (see [1] and [2]), as a general theory of functions, more precisely as a formalization of two basic functional concepts: application and abstraction. This claim to universality was impossible to maintain, for it soon became apparent that functions in the calculus are required to have properties which are by no means universal. Self-application is certainly a very special feature, but more relevant from our point of view is the existence of fixed points, which is definitely a nonuniversal property of functions. This situation was not ignored, but was considered rather as a form of inconsistency very much related to the paradoxes of set theory (for example, see the discussion of the paradoxical combinator in [2]).More recently, the lambda calculus has been studied by people in computer science, and as a result the algorithmic nature of the system has been more explicitly recognized. Eventually, the right approach was taken by D. Scott (see [4] and [5]) who restricted the objects of the calculus to continuous functionals over complete lattices, which can be combined in structures where application and abstraction are properly interpreted. It soon became clear that complete lattices were not necessary, and more general structures were introduced. On the other hand the requirement of continuity was essential for the construction, and has remained a basic feature. It is one of the purposes of this paper to show that in the general situation continuity can be replaced by monotonicity.The work of Scott was extended by Wadsworth [6], who gave a precise formulation of the operational semantics, and proved the equivalence to Scott's interpretation.
The contributions of Alfred Tarski to algebraic logic
Authors: Monk J. Donald 
Published: May 2006

One of the most extensive parts of Tarski's contributions to logic is his work on the algebraization of the subject. His work here involves Boolean algebras, relation algebras, cylindric algebras, Boolean algebras with operators, Brouwerian algebras, and closure algebras. The last two are less developed in his work, although his contributions are basic to other work in those subjects. At any rate, not being conversant with the latest developments in those fields, we shall concentrate on an exposition of Tarski's work in the first four areas, trying to put them in the perspective of present-day developments.For useful comments, criticisms, and suggestions, the author is indebted to Steven Givant, Leon Henkin, Wilfrid Hodges, Bjarni Jónsson, Roger Lyndon, and Robert Vaught.
Why Solovay real produces Cohen real
Authors: Pawlikowski Janusz 
Published: May 2006

AbstractAn explanation is given of why, after adding to a model M of ZFC first a Solovay real r and next a Cohen real c, in M[r] [c] a Cohen real over M[c] is produced. It is also shown that a Solovay algebra iterated with a Cohen algebra can be embedded into a Cohen algebra iterated with a Solovay algebra.
The ideal structure of existentially closed algebras
Authors: Eklof Paul C. , Mez Hans-Christian 
Published: May 2006

Throughout this paper, ⊿ will denote a commutative ring with multiplicative identity, 1. The algebras we consider will be associative ⊿-algebras which are not necessarily commutative and do not necessarily contain a multiplicative identity. By standard methods, every ⊿-algebra can be embedded in an existentially closed (e.c.) Δ-algebra—and even in one which is existentially universal (e.u.). (See §0 for more details.)We shall be studying the ideals of e.c. ⊿-algebras. Since every ideal is a sum of principal ideals, a natural place to begin is with principal ideals. In §1 we show that for an algebraically closed (a.c.) ⊿-algebra A, and elements a, b in A, whether or not b belongs to the principal ideal (a)A generated by a, depends only on the underlying ⊿-module structure of A; more precisely, for b to belong to (a)A it is necessary and sufficient that b satisfies every positive existential formula θ(ν) in the language of ⊿-modules which is satisfied by a (cf. Corollary 1.8). For special classes of rings ⊿ this condition can be simplified (Proposition 1.10): e.g. for Prüfer rings it is enough to consider formulas of the form ∃x(λx = μν); and for regular rings it is enough to consider formulas μν = 0 (where λ, μ ∈ ⊿).In §2 we use the results of §1 to study e.c. and e.u. algebras over a principal ideal domain (p.i.d.) ⊿ (Note that for ⊿ = Z this includes the case of e.c. rings.) We obtain a necessary and sufficient condition for an a.c. ⊿-algebra to be e.c. (Theorem 2.4). We also show (Theorem 2.2) that in an a.c. ⊿-algebra A every element that is divisible by all nonzero elements of ⊿ belongs to the divisible part D(A) of A. (It should be noted that, while a.c. ⊿-modules are always divisible [ES], an e.c. ⊿-algebra is never divisible: see the end of §0. Moreover, an e.c. ⊿-algebra always contains torsion-free elements: see Remark 2.3.) We prove that every bounded ideal in an a.c. ⊿-algebra is principal (2.7).
Complexity of κ-ultrafilters and inner models with measurable cardinals
Authors: Sureson Claude 
Published: May 2006

The purpose of this paper is to establish a connection between the complexity of κ-ultrafilters over a measurable cardinal κ, and the existence of ascending Rudin-Keisler chains of κ-ultrafilters and of inner models with several measurable cardinals.If V is a model of ZFC + “There exists a measurable cardinal κ”, then V satisfies “There exists a normal κ-ultrafilter”, that is to say a “simple” κ-ultrafilter. The only known examples of “complex” κ-ultrafilters have been constructed by Kanamori [2], Ketonen [4] and Kunen (cf. [2]) with stronger hypotheses than measurability: compactness or supercompactness. Using the notions of skies and constellations defined by Kanamori [2] for the measurable case, and which witness the complexity of a κ-ultrafilter, we shall show the necessity of such assumptions, namely:Theorem 1. If λ < κ is a strongly inaccessible cardinal, the existence of a κ-ultrafilter with more than λ constellations implies that there is an inner model with two measurable cardinals if λ = ω and λ + 1 measurable cardinals otherwise.Theorem 2. Let θ < κ be an arbitrary ordinal. If there is a κ-ultrafilter such that the order-type of its skies is greater than ωθ, then there exists an inner model with θ + 1 measurable cardinals.And as a corollary, we obtain:Theorem 3. Let μ < κ be a regular cardinal. If there exists a κ-ultrafilter containing the closed-unbounded subsets of κ and {α < κ: cf(α) = μ}, then there is an inner model with two measurable cardinals if μ = ω, and μ + 1 measurable cardinals otherwise.
Banach games
Authors: Freiling Chris 
Published: May 2006

Abstract.Banach introduced the following two-person, perfect information, infinite game on the real numbers and asked the question: For which sets A ⊆ R is the game determined?Rules: The two players alternate moves starting with player I. Each move an is legal iff it is a real number and 0 < an, and for n > 1, an < an−1. The first player to make an illegal move loses. Otherwise all moves are legal and I wins iff exists and .We will look at this game and some variations of it, called Banach games. In each case we attempt to find the relationship between Banach determinacy and the determinacy of other well-known and much-studied games.
Heine-Borel does not imply the Fan Theorem
Authors: Moerdijk Ieke 
Published: May 2006

This paper deals with locales and their spaces of points in intuitionistic analysis or, if you like, in (Grothendieck) toposes. One of the important aspects of the problem whether a certain locale has enough points is that it is directly related to the (constructive) completeness of a geometric theory. A useful exposition of this relationship may be found in [1], and we will assume that the reader is familiar with the general framework described in that paper.We will consider four formal spaces, or locales, namely formal Cantor space C, formal Baire space B, the formal real line R, and the formal function space RR being the exponential in the category of locales (cf. [3]). The corresponding spaces of points will be denoted by pt(C), pt(B), pt(R) and pt(RR). Classically, these locales all have enough points, of course, but constructively or in sheaves this may fail in each case. Let us recall some facts from [1]: the assertion that C has enough points is equivalent to the compactness of the space of points pt(C), and is traditionally known in intuitionistic analysis as the Fan Theorem (FT). Similarly, the assertion that B has enough points is equivalent to the principle of (monotone) Bar Induction (BI). The locale R has enough points iff its space of points pt(R) is locally compact, i.e. the unit interval pt[0, 1] ⊂ pt(R) is compact, which is of course known as the Heine-Borel Theorem (HB). The statement that RR has enough points, i.e. that there are “enough” continuous functions from R to itself, does not have a well-established name. We will refer to it (not very imaginatively, I admit) as the principle (EF) of Enough Functions.
A note on interpretations of many-sorted theories
Authors: Hook Julian L. 
Published: May 2006

Whenever many-sorted theories are discussed in logic texts (e.g., [3, pp. 483–485]), it is fashionable to observe that every many-sorted theory can be effectively replaced by an equally powerful one-sorted theory *. The theory * contains for each sort σ of a unary predicate symbol Sσ used to indicate that an individual is of sort σ; the nonlogical axioms of * are the “translations” of those of together with axioms asserting that there is at least one individual of each sort and that all function symbols behave properly with respect to sorts. This observation suggests that perhaps many-sorted theories are no more useful than one-sorted theories. That this is not always the case has been pointed out previously [1, p. 13]. The content of this note is that can be interpretable in without * being interpretable in *.If a function symbol f in a many-sorted theory takes as its arguments n terms a1,…, an of sorts σ1, …, σn, respectively and produces a term fa1 … an of sort σ, then f is said to be of type (σ1, …, σn;σ). Likewise, a predicate symbol is of type (σ1, …, σn) if it takes as its arguments n terms of sorts σ1, …, σn. We assume that for each sort σ there is a predicate symbol = σ of type (σ, σ).
Disturbing arithmetic
Authors: Grilliot Thomas J. 
Published: May 2006

One long-range objective of logic is to find models of arithmetic with noteworthy properties, perhaps properties that imply some long-standing number theoretic conjectures. In areas of mathematics such as algebra or set theory, new models are often made by extending old models, that is, by adjoining new elements to already existing models. Usually the extension retains most of the characteristics of the old model with at least one exception that makes the new model interesting. However, such a scheme is difficult in the area of arithmetic. Many interesting properties of the fine structure of arithmetic are diophantine and hence unchangeable in extensions. For instance, one cannot change a prime number into a composite one by adjoining new elements.One could possibly get around this diophantine difficulty in one of two ways. One way is to change the usual language of addition and multiplication to an equivalent language that does not transmit so much information to extensions. For instance, multiplication is definable from the squaring function, as one sees from the identity 2xy = (x + y)2 − x2 − y2, and the squaring function in turn is definable either from the unary square predicate (as one sees from the fact that n = m2 if n and n + 2m + 1 are successive squares) or from the divisor relation (as one sees from the fact that n = m2 if n is the smallest number such that m divides n and m + 1 divides n + m). Either of these two alternatives to multiplication might make for interesting extensions.