bluuebunny/crossref_metadata_2025_split huggingface dataset:
Comparing incomparable kleene degrees
Authors: Welch Philip 
Published: May 2006

In the December 1982 issue of this Journal Weitkamp [W] posed some questions concerning the incomparability of certain “r.e.” sets for the notion of Kleene reducibility. He asked whether the incomparability of, for example, the Friedman set F (defined below) and the set WI0 (the set of reals coding wellfounded trees of admissible height) was equivalent to the existence of 0#, since forcing over L with a set of conditions could not achieve this. We answer this by showing that in a certain class generic extension of L they are comparable, but 0# does not exist. This is an application of Jensen's coding theorem (cf. [BJW]), using a modified construction due to René David [D]. Indeed the result here is a simple application of his result. Define F as follows:Harrington showed, in effect, that one could not add a cone of Turing degrees to this set by forcing with sets of conditions over L. The method used here does add a cone of Turing degrees to a much simpler set RI1 (defined below)—and indeed the whole process could be viewed as forcing over L to obtain the determinacy of certain rather simple sets. It is the determinacy of the game with payoff set RI1 that ensures the comparability of F and WI0 (amongst many others).We shall refrain from repeating all the basic definitions and lemmas since the reader can readily refer to [W]; we shall give the basic necessities.
Determinacy of Banach games
Authors: Becker Howard 
Published: May 2006

For any A ⊂ R, the Banach game B(A) is the following infinite game on reals: Players I and II alternately play positive real numbers a1; a2, a3, a4,… such that for n > 1, an < an−1. Player I wins iff ai exists and is in A.This type of game was introduced by Banach in 1935 in the Scottish Book [15], Problem 43. The (rather vague) problem which Banach posed was to characterize those sets A for which I (II) has a winning strategy in B(A). (There are three parts to Problem 43. In the first, Mazur defined a game G**(A) for every set A ⊂ R and conjectured that II has a winning strategy in G**(A) iff A is meager and I has a winning strategy in G**(A) iff A is comeager in some neighborhood; this conjecture was proved by Banach. Presumably Banach had this result in mind when he asked the question about B(A), and hoped for a similar type of characterization.) Incidentally, Problem 43 of the Scottish Book appears to be the first time infinite games of any sort were studied by mathematicians.This paper will not provide the reader with any answer to Banach's question. I know of no nontrivial way to characterize when player I (or II) wins, and I suspect there is none. This paper is concerned with a different (also rather vague) question: For which sets A is the Banach game B(A) determined? To say that B(A) is determined means, of course, that one of the players has a winning strategy for B(A).
Variations on promptly simple sets
Authors: Maass Wolfgang 
Published: May 2006

In this paper we answer the question of whether all low sets with the splitting property are promptly simple. Further we try to make the role of lowness properties and prompt simplicity in the construction of automorphisms of the lattice of r.e. (recursively enumerable) sets more perspicuous. It turns out that two new properties of r.e. sets, which are dual to each other, are essential in this context: the prompt and the low shrinking property.In an earlier paper [4] we had shown (using Soare's automorphism construction [10] and [12]) that all r.e. generic sets are automorphic in the lattice ℰ of r.e. sets under inclusion. We called a set A promptly simple if Ā is infinite and there is a recursive enumeration of A and the r.e. sets (We)e∈N such that if We is infinite then there is some element (or equivalently: infinitely many elements) x of We such that x gets into A “promptly” after its appearance in We (i.e. for some fixed total recursive function f we have x ∈ Af(s), where s is the stage at which x entered We). Prompt simplicity in combination with lowness turned out to capture those properties of r.e. generic sets that were used in the mentioned automorphism result. In a following paper with Shore and Stob [7] we studied an ℰ-definable consequence of prompt simplicity: the splitting property.
Remarks on weak notions of saturation in models of Peano arithmetic
Authors: Kaufmann Matt , Schmerl James H. 
Published: May 2006

This paper is a sequel to our earlier paper [2] entitled Saturation and simple extensions of models of Peano arithmetic. Among other things, we will answer some of the questions that were left open there. In §1 we consider the question of whether there are lofty models of PA which have no recursively saturated, simple extensions. We are still unable to answer this question; but we do show in that section that these models are precisely the lofty models which are not recursively saturated and which are κ-like for some regular κ. In §2 we use diagonal methods to produce minimal models of PA in which the standard cut is recursively definable, and other minimal models in which the standard cut is not recursively definable. In §3 we answer two questions from [2] by exhibiting countable models of PA which, in the terminology of this paper, are uniformly ω-lofty but not continuously ω-lofty and others which are continuously ω-lofty but not recursively saturated. We also construct a model (assuming ◇) which is not recursively saturated but every proper, simple cofinal extension of which is ℵ1-saturated. Finally, in §4 we answer another question from [2] by proving that for regular κ ≥ ℵ1; every κ-saturated model of PA has a κ-saturated proper, simple extension which is not κ+-saturated.Our notation and terminology are quite standard. Anything unfamiliar to the reader and not adequately denned here is probably defined in §1 of [2]. All models considered are models of Peano arithmetic.
Alfred Tarski's work in model theory
Authors: Vaught Robert L. 
Published: May 2006

We will consider Tarski's work in pure model theory and classical logic. His work in applied model theory—the model theory of various special theories—is discussed by Doner and van den Dries [1987], and McNulty [1986]. (However, the separation of “pure” and “applied” only becomes natural as the subjects mature; so we shall discuss applied model theory at least to some extent in Tarski's earlier work.)Alfred Tarski (1901–1983) was awarded a Ph.D. in mathematics at Warsaw University in 1924. His teachers included the two leaders of the renowned Polish logic school, the logician-philosophers L. Leśniewski and J. Łukasiewicz. (Very soon Tarski was recognized as the third leader of the school.) Another teacher was the philosopher T. Kotarbiński, to whom Tarski dedicated his collected papers [56m]. Leśniewski was Tarski's thesis advisor; he transmitted to Tarski his interests in the metalanguage and in the theory of definition. Tarski's thesis ([23a], [24]) was about protothetic—the sentential calculus augmented by quantifiable variables ranging over truth functions. Its main result was that all the connectives are definable using only ↔ and ∀. By the same year, 1924, Tarski also had begun his prolific writings in set theory, and had discovered together with S. Banach, the leader of the Polish mathematicians, their famous “paradox” [24d] in measure theory. (For details see Lévy [1987].)In 1927-29 Tarski held a seminar at Warsaw University on results he obtained in 1926-28. The seminar lay at the heart of what is now called model theory. The brief history of model theory up to that time had begun with the paper of L. Löwenheim [1915].
Bad models in nice neighborhoods
Authors: Millar Terry 
Published: May 2006

This paper contains an example of a decidable theory which has1) only a countable number of countable models (up to isomorphism);2) a decidable saturated model; and3) a countable homogeneous model that is not decidable.By the results in [1] and [2], this can happen if and only if the set of types realized by the homogeneous model (the type spectrum of the model) is not .If Γ and Σ are types of a theory T, define Γ ◁ Σ to mean that any model of T realizing Γ must realize Σ. In [3] a decidable theory is constructed that has only countably many countable models, only recursive types, but whose countable saturated model is not decidable. This is easy to do if the restriction on the number of countable models is lifted; the difficulty arises because the set of types must be recursively complex, and yet sufficiently related to control the number of countable models. In [3] the desired theory T is such thatis a linear order with order type ω*. Also, the set of complete types of T is not . The last feature ensures that the countable saturated model is not decidable; the first feature allows the number of countable models to be controlled.
Polynomial rings and weak second-order logic
Authors: Bauval Anne 
Published: May 2006

This article is a rewriting of my Ph.D. Thesis, supervised by Professor G. Sabbagh, and incorporates a suggestion from Professor B. Poizat. My main result can be crudely summarized (but see below for detailed statements) by the equality: first-order theory of F[Xi]i∈I = weak second-order theory of F.§I.1. Conventions. The letter F will always denote a commutative field, and I a nonempty set. A field or a ring (A; +, ·) will often be written A for short. We shall use symbols which are definable in all our models, and in the structure of natural numbers (N; +, ·):— the constant 0, defined by the formula Z(x): ∀y (x + y = y);— the constant 1, defined by the formula U(x): ∀y (x · y = y);— the operation ∹ x − y = z ↔ x = y + z;— the relation of division: x ∣ y ↔ ∃ z(x · z = y).A domain is a commutative ring with unity and without any zero divisor.By “… → …” we mean “… is definable in …, uniformly in any model M of L”.All our constructions will be uniform, unless otherwise mentioned.§I.2. Weak second-order models and languages. First of all, we have to define the models Pf(M), Sf(M), Sf′(M) and HF(M) associated to a model M = {A; ℐ) of a first-order language L [CK, pp. 18–20]. Let L1 be the extension of L obtained by adjunction of a second list of variables (denoted by capital letters), and of a membership symbol ∈. Pf(M) is the model (A, Pf(A); ℐ, ∈) of L1, (where Pf(A) is the set of finite subsets of A. Let L2 be the extension of L obtained by adjunction of a second list of variables, a membership symbol ∈, and a concatenation symbol ◠.
A note on nonmultidimensional superstable theories
Authors: Pillay Anand , Steinhorn Charles 
Published: May 2006

In this paper we prove that if T is the complete elementary diagram of a countable structure and is a theory as in the title, then Vaught's conjecture holds for T. This result is Theorem 7, below. In the process of establishing this proposition, in Theorem 3 we give a sufficient condition for a superstable theory having only countably many types without parameters to be ω-stable. Familiarity with the rudiments of stability theory, as presented in [3] and [4], will be supposed throughout. The notation used is, by now, standard.We begin by giving a new proof of a lemma due to J. Saffe in [6]. For T stable, recall that the multiplicity of a type p over a set A ⊆ ℳ ⊨ T is the cardinality of the collection of strong types over A extending p.Lemma 1 (Saffe). Let T be stable, A ⊆ ℳ ⊨ T. If t(b̄, A) has infinite multiplicity and t(c̄, A) has finite multiplicity, then t(b̄, A ∪ {c̄}) has infinite multiplicity.Proof. We suppose not and work for a contradiction. Let ‹b̄γ:γ ≤ α›, α ≥ ω, be a list of elements so that t(b̄γ, A) = t(b̄, A) for all γ ≤ α, and st(b̄γ, A) ≠ st(b̄δ, A) for γ ≠ δ. Furthermore, let c̄γ satisfy t(b̄γ∧c̄γ, A) = t(b̄ ∧ c̄, A) for each γ < α.Since t(c̄, A) has finite multiplicity, we may assume for all γ, δ < α. that st(c̄γ, A) = st(c̄δ, A). For each γ < α there is an automorphism fγ of the so-called “monster model” of T (a sufficiently large, saturated model of T) that preserves strong types over A and is such that f(c̄γ) = c̄0.
One theorem of Zil′ber's on strongly minimal sets
Authors: Buechler Steven 
Published: May 2006

AbstractSuppose D ⊂ M is a strongly minimal set definable in M with parameters from C. We say D is locally modular if for all X, Y ⊂ D, with X = acl(X ∪ C)∩D, Y = acl(Y ∪ C) ∩ D and X ∩ Y ≠ ∅,We prove the following theorems.Theorem 1. Suppose M is stable and D ⊂ M is strongly minimal. If D is not locally modular then inMeqthere is a definable pseudoplane.(For a discussion of Meq see [M, §A].) This is the main part of Theorem 1 of [Z2] and the trichotomy theorem of [Z3].Theorem 2. Suppose M is stable and D, D′ ⊂ M are strongly minimal and nonorthogonal. Then D is locally modular if and only if D′ is locally modular.
Some model theory of modules. III. On infiniteness of sets definable in modules
Authors: Rothmaler Philipp 
Published: May 2006

This is the third and last part of an investigation in several topics of first order model theory of modules which I began in Some model theory of modules. I. On total transcendence of modules (this Journal, vol. 48 (1983), pp. 570–574) and continued in Some model theory of modules. II. On stability and categoricity of flat modules (this Journal, vol. 48 (1983), pp. 970–985). Throughout I refer to these papers as “Part I” and “Part II”.Although these parts are only loosely connected, I will tacitly use the notation and preliminaries already introduced in the preceding ones. Further details are given in §0. Concerning Part II, the reader is assumed to be familiar with most of §1, a very small part of §4, and the criterion for elementary equivalence of modules over regular rings given in §3 (Lemma 20) of that part.Using those tools in this paper I consider completeness of the (elementary) theory of all modules (and of some of its extensions) (§2), and eliminability of cardinality quantifiers in the elementary theories of modules (§3).§2 is almost entirely devoted to a new short proof based on the technique developed in Part II of a theorem of Tukavkin which seems to be the first relevant result concerning the completeness of the theory of all modules (after the simple observation that any theory of infinite vector spaces is complete).
Some undecidability results in strong algebraic languages
Authors: Kalfa Cornelia 
Published: May 2006

The recursively unsolvable halting problem for Turing machines is reduced to the problem of the existence or not of an algorithm for deciding whether a field is finite. The latter problem is further reduced to the decision problem of each of propertiesfor recursive sets Σ of equations of strong algebraic languages with infinitely many operation symbols.Decision problems concerning properties of sets of equations were first raised by Tarski [9] and subsequently examined by Perkins [6], McKenzie [4], McNulty [5] and Pigozzi [7]. Perkins is the only one who studied recursive sets; the others investigated finite sets. Since the undecidability of properties Pi for recursive sets of equations does not imply any answer to the corresponding decision problems for finite sets, the latter problems remain open.The work presented here is part of my Ph.D. thesis [2]. I thank Wilfrid Hodges, who supervised it.An algebraic language is a first-order language with equality but without relation symbols. It is here denoted by , where Qi is an operation symbol and cj, is a constant symbol.
A recursion theoretic analysis of the clopen Ramsey theorem
Authors: Clote Peter 
Published: May 2006

AbstractSolovay has shown that if F: [ω]ω → 2 is a clopen partition with recursive code, then there is an infinite homogeneous hyperarithmetic set for the partition (a basis result). Simpson has shown that for every 0α, where α is a recursive ordinal, there is a clopen partition F: [ω]ω → 2 such that every infinite homogeneous set is Turing above 0α (an anti-basis result). Here we refine these results, by associating the “order type” of a clopen set with the Turing complexity of the infinite homogeneous sets. We also consider the Nash-Williams barrier theorem and its relation to the clopen Ramsey theorem.
Questions about quantifiers
Authors: van Benthem Johan 
Published: May 2006

The importance of the logical ‘generalized quantifiers’ (Mostowski [1957]) for the semantics of natural language was brought out clearly in Barwise & Cooper [1981]. Basically, the idea is that a quantifier phrase QA (such as “all women”, “most children”, “no men”) refers to a set of sets of individuals, viz. those B for which (QA)B holds. Thus, e.g., given a fixed model with universe E,where ⟦A⟧ is the set of individuals forming the extension of the predicate “A” in the model. This point of view permits an elegant and uniform semantic treatment of the subject-predicate form that pervades natural language.Such denotations of quantifier phrases exhibit familiar mathematical structures. Thus, for instance, all A produces filters, and no A produces ideals. The denotation of most A is neither; but it is still monotone, in the sense of being closed under supersets. Mere closure under subsets occurs too; witness a quantifier phrase like few A. These mathematical structures are at present being used in organizing linguistic observations and formulating hypotheses about them. In addition to the already mentioned paper of Barwise & Cooper, an interesting example is Zwarts [1981], containing applications to the phenomena of “negative polarity” and “conjunction reduction”. In the course of the latter investigation, several methodological issues of a wider logical interest arose, and these have inspired the present paper.In order to present these issues, let us shift the above perspective, placing the emphasis on quantifier expressions per se (“all”, “most”, “no”, “some”, etcetera), viewed as denoting relations Q between sets of individuals.
Spector forcing
Authors: Henle J. M. 
Published: May 2006

AbstractForcing with [Κ]κ over a model of set theory with a strong partition cardinal, M. Spector produced a generic ultrafilter G on κ such that κκ/G is not well-founded.Theorem. Let G be Spector-generic over a model M of , for all α < κ.1) Every cardinal (well-ordered or not) of M is a cardinal of M[G].2) If A ∈ M[G] is a well-ordered subset of M, then Ae M. Let Φ = Κκ/G.3) There is an ultrafilter U on Φ such that every member of U has a subset of type Φ, and the intersection of any well-ordered subset of U is in U.4) Φ satisfies for all α <ℵ1 and all ordinals β.5) There is a linear order Φ′ with property 3) above which is not “weakly compact”, i.e., Φ′ ↛ (Φ′)2.
An extension of the nondiamond theorem in classical and α-recursion theory
Authors: Ambos-Spies Klaus 
Published: May 2006

Lachlan's nondiamond theorem [7, Theorem 5] asserts that there is no embedding of the four-element Boolean algebra (diamond) in the recursively enumerable degrees which preserves infima, suprema, and least and greatest elements. Lachlan observed that, essentially by relativization, the theorem can be extended toUsing the Sacks splitting theorem he concluded that there exists a pair of r.e. degrees which does not have an infimum, thus showing that the r.e. degrees do not form a lattice.We will first prove the following extension of (1):where an r.e. degree a is non-b-cappable if . From (2) we obtain more information about pairs of r.e. degrees without infima: For every nonzero low r.e. degree there exists an incomparable one such that the two degrees do not have an infimum and there is an r.e. degree which is not half of a pair of incomparable r.e. degrees which has an infimum in the low r.e. degrees. Probably the most interesting corollary of (2) is that the join of any cappable r.e. degree (i.e. half of a minimal pair) and any low r.e. degree is incomplete. Consequently there is an incomplete noncappable degree above every incomplete r.e. degree. Cooper's result [3] that ascending sequences of uniformly r.e. degrees can have minimal upper bounds in the set R of r.e. degrees is another corollary of (2).
On Σ11 equivalence relations with Borel classes of bounded rank
Authors: Sami Ramez L. 
Published: May 2006

AbstractIn Baire space we define a sequence of equivalence relations ‹Ev ∣ v < , each Ev being with classes in + v + 1 and such that (i) Ev does not have perfectly many classes, and (ii) is countable iff < ω1. This construction can be extended cofinally in . A new proof is given of a theorem of Hausdorff on partitions of R into ω1 many sets.
Extension of relatively σ-additive probabilities on Boolean algebras of logic
Authors: Amer Mohamed A. 
Published: May 2006

AbstractContrary to what is stated in Lemma 7.1 of [8], it is shown that some Boolean algebras of finitary logic admit finitely additive probabilities that are not σ-additive. Consequences of Lemma 7.1 are reconsidered. The concept of a C-σ-additive probability ℬ (where ℬ and C are Boolean algebras, and ℬ ⊆ C) is introduced, and a generalization of Hahn's extension theorem is proved. This and other results are employed to show that every S̄(L)-σ-additive probability on s̄(L) can be extended (uniquely, under some conditions) to a σ-additive probability on S̄(L), where L belongs to a quite extensive family of first order languages, and S̄(L) and s̄(L) are, respectively, the Boolean algebras of sentences and quantifier free sentences of L.
Provability in finite subtheories of PA and relative interpretability: a modal investigation
Authors: Montagna Franco 
Published: May 2006

By Solovay's theorem [16], the modal logic of provability GL gives a complete description of the propositional schemata involving the provability predicate PrPA(x) for Peano arithmetic PA, which are provable in PA. However, many important aspects of provability cannot be fully expressed in terms of PrPA(x). For this reason, many authors have introduced extensions of GL which take account either of Rosser constructions or of other important metamathematical formulas (see, for example, [5], [6], [14], [16], and [19]). In this paper, we concentrate on the modal logic of the provability predicate for finitely axiomatizable subtheories of PA; the interest of this modal logic is based on the following facts. First of all, it provides a modal translation of a very important property of PA, namely the essential reflexiveness. Secondly, in view of Orey's theorem [10] it constitutes a possible approach to the study of interpretability of finite extensions of PA. Indeed, by Orey's theorem PA + θ is interpretable in PA + θ′ iff for every n, and, therefore, relative interpretability of finitely axiomatizable extensions of PA can be expressed by means of the provability predicate for finitely axiomatizable subtheories of PA.In §1, we introduce three modal logics extending GL and discuss their arithmetical interpretations; §2 deals with Kripke semantics for two of these logics. In §3, a theorem on arithmetical completeness is shown, which characterizes the logic of the provability predicate for finitely axiomatizable subtheories of PA; a uniform version of this theorem is proved in §4.