bluuebunny/crossref_metadata_2025_split huggingface dataset:
Definability of r. e. sets in a class of recursion theoretic structures
Authors: Byerly Robert E. 
Published: May 2006

It is known [4, Theorem 11-X(b)] that there is only one acceptable universal function up to recursive isomorphism. It follows from this that sets definable in terms of a universal function alone are specified uniquely up to recursive isomorphism. (An example is the set K, which consists of all n such that {n}(n) is defined, where λn, m{n}(m) is an acceptable universal function.) Many of the interesting sets constructed and studied by recursion theorists, however, have definitions which involve additional notions, such as a specific enumeration of the graph of a universal function. In particular, many of these definitions make use of the interplay between the purely number-theoretic properties of indices of partial recursive functions and their purely recursion-theoretic properties.This paper concerns r.e. sets that can be defined using only a universal function and some purely number-theoretic concepts. In particular, we would like to know when certain recursion-theoretic properties of r.e. sets definable in this way are independent of the particular choice of universal function (equivalently, independent of the particular way in which godel numbers are identified with natural numbers).We will first develop a suitable model-theoretic framework for discussing this question. This will enable us to classify the formulas defining r.e. sets by their logical complexity. (We use the number of alternations of quantifiers in the prenex form of a formula as a measure of logical complexity.) We will then be able to examine the question at each level.This work is an approach to the question of when the recursion-theoretic properties of an r.e. set are independent of the particular parameters used in its construction. As such, it does not apply directly to the construction techniques most commonly used at this time for defining particular r.e. sets, e.g., the priority method. A more direct attack on this question for these techniques is represented by such works as [3] and [5]. However, the present work should be of independent interest to the logician interested in recursion theory.
On the strength of the Sikorski extension theorem for Boolean algebras
Authors: Bell J.L. 
Published: May 2006

The Sikorski Extension Theorem [6] states that, for any Boolean algebra A and any complete Boolean algebra B, any homomorphism of a subalgebra of A into B can be extended to the whole of A. That is,Inj: Any complete Boolean algebra is injective (in the category of Boolean algebras).The proof of Inj uses the axiom of choice (AC); thus the implication AC → Inj can be proved in Zermelo-Fraenkel set theory (ZF). On the other hand, the Boolean prime ideal theoremBPI: Every Boolean algebra contains a prime ideal (or, equivalently, an ultrafilter)may be equivalently stated as:The two element Boolean algebra 2 is injective,and so the implication Inj → BPI can be proved in ZF.In [3], Luxemburg surmises that this last implication cannot be reversed in ZF. It is the main purpose of this paper to show that this surmise is correct. We shall do this by showing that Inj implies that BPI holds in every Boolean extension of the universe of sets, and then invoking a recent result of Monro [5] to the effect that BPI does not yield this conclusion.
Probabilities over rich languages, testing and randomness
Authors: Gaifman Haim , Snir Marc 
Published: May 2006

The basic concept underlying probability theory and statistics is a function assigning numerical values (probabilities) to events. An “event” in this context is any conceivable state of affairs including the so-called “empty event”—an a priori impossible state. Informally, events are described in everyday language (e.g. “by playing this strategy I shall win $1000 before going broke”). But in the current mathematical framework (first proposed by Kolmogoroff [Ko 1]) they are identified with subsets of some all-inclusive set Q. The family of all events constitutes a field, or σ-field, and the logical connectives ‘and’, ‘or’ and ‘not’ are translated into the set-theoretical operations of intersection, union and complementation. The points of Q can be regarded as possible worlds and an event as the set of all worlds in which it takes place. The concept of a field of sets is wide enough to accommodate all cases and to allow for a general abstract foundation of the theory. On the other hand it does not reflect distinctions that arise out of the linguistic structure which goes into the description of our events. Since events are always described in some language they can be indentified with the sentences that describe them and the probability function can be regarded as an assignment of values to sentences. The extensive accumulated knowledge concerning formal languages makes such a project feasible. The study of probability functions defined over the sentences of a rich enough formal language yields interesting insights in more than one direction.Our present approach is not an alternative to the accepted Kolmogoroff axiomatics. In fact, given some formal language L, we can consider a rich enough set, say Q, of models for L (called also in this work “worlds”) and we can associate with every sentence the set of all worlds in Q in which the sentence is true. Thus our probabilities can be considered also as measures over some field of sets. But the introduction of the language adds mathematical structure and makes for distinctions expressing basic intuitions that cannot be otherwise expressed. As an example we mention here the concept of a random sequence or, more generally, a random world, or a world which is typical to a certain probability distribution.
On a condition for Cohen extensions which preserve precipitous ideals
Authors: Kakuda Yuzuru 
Published: May 2006

T. Jech and K. Prikry introduced the concept of precipitous ideals as a counterpart of measurable cardinals for small cardinals (Jech and Prikry [1]). To get a precipitous ideal on ℵ1( W. Mitchell used the Cohen extension by the standard Levy collapse that makes κ = ℵ1, where κ is a measurable cardinal in the ground model (Jech, Magidor, Mitchell and Prikry [2]). His proof essentially used the fact that , where is the notion of forcing of Levy collapse and j is the elementary embedding obtained by a normal ultrafilter on κ.On the other hand, we know that has the κ-chain condition. In this paper, we show that the κ-chain condition for notions of forcing plays an essential role for preserving normal precipitous ideals. Namely,Theorem 1. Let κ be a regular uncountable cardinal and I a normal ideal on κ. Let be a notion of forcing with the κ-chain condition. Then, I is precipitous iff ⊩“the ideal on κ generated by I is precipitous”.As an application of Theorem 1, we have the following theorem.Theorem 2. Let κ be a regular uncountable cardinal, and Γ be a κ-saturated normal ideal on κ. Then, {a < κ; the ideal of thin sets on a is precipitous} has either Γ-measure one or Γ-measure zero, and the ideal of thin sets on κ is precipitous iff {α< κ; the ideal of thin sets on α is precipitous) has Γ-measure one.
Some model theory of modules. II. on stability and categoricity of flat modules
Authors: Rothmaler Philipp 
Published: May 2006

This is the second part of a study on model theory of modules begun in [RO]. Throughout, I refer to that paper as “Part I”. I observed there a coincidence between some algebraic and logical points of view in the theory of modules, which led to a convenient representation of p.p. definable sets in flat modules (§1); it becomes especially nice in the case of regular rings (cf. Remark 7 in Part I). Using this in the present paper I obtain a simplified criterion for total transcendence and superstability in the case of flat modules. This enables me to give, besides partial results for arbitrary flat modules (§2), a complete description of the stability classes for modules over regular rings (§3). Particularly, it turns out that a totally transcendental module over a regular ring can be regarded as a module over a semisimple ring (cf. Remark 10 in Part I). This is the crucial observation for the examination of categoricity here: By Morley's theorem, a countable ℵ1-categorical theory is totally transcendental. Consequently, an ℵ1-categorical module over a countable regular ring can be regarded as a module over a semisimple ring. That is why I separately treat categoricity of modules over semisimple rings (§4), even without any assumption on the power of the ring. As a consequence I obtain a complete description of ℵ1-categorical modules over countable regular rings (§5). In the investigation presented here the main tool is the technique of idempotents avoiding the commutativity assumption made in the corresponding results of Garavaglia [GA 1, pp. 86–88], who used maximal ideals for that purpose. At the end of the present paper I show how to derive these latter results in our context.On the way I simplify the known criterion for elementary equivalence for modules over regular rings (§3), which simplifies again in case of semisimple rings (§4). Such a criterion is needed in order to construct Vaughtian pairs (in the categoricity consideration) and it turns out to be useful also for another purpose treated in the third part of this series of papers.
Canonical modal logics and ultrafilter extensions
Authors: van Benthem J. F. A. K. 
Published: May 2006

In this paper thecanonicalmodal logics, a kind of complete modal logics introduced in K. Fine [4] and R. I. Goldblatt [5], will be characterized semantically using the concept of anultrafilter extension, an operation on frames inspired by the algebraic theory of modal logic. Theorem 8 of R. I. Goldblatt and S. K. Thomason [6] characterizing the modally definable Σ⊿-elementary classes of frames will follow as a corollary. A second corollary is Theorem 2 of [4] which states that any complete modal logic defining a Σ⊿-elementary class of frames is canonical.The main tool in obtaining these results is the duality between modal algebras and general frames developed in R. I. Goldblatt [5]. The relevant notions and results from this theory will be stated in §2. The concept of a canonical modal logic is introduced and motivated in §3, which also contains the above-mentioned theorems. In §4, a kind of appendix to the preceding discussion, preservation of first-order sentences under ultrafilter extensions (and some other relevant operations on frames) is discussed.The modal language to be considered here has an infinite supply of proposition letters (p, q, r, …), a propositional constant ⊥ (the so-calledfalsum, standing for a fixed contradiction), the usual Boolean operators ¬ (not), ∨ (or), ∨ (and), → (if … then …), and ↔ (if and only if)—with ¬ and ∨ regarded as primitives—and the two unary modal operators ◇ (possibly) and □ (necessarily)— ◇ being regarded as primitive. Modal formulas will be denoted by lower case Greek letters, sets of formulas by Greek capitals.
Théories instables
Authors: Poizat Bruno 
Published: May 2006

L'absence ou la présence de la propriété d'indépendance, introduite par Shelah, est sans aucun doute une mesure significative de la complexité, du point de vue de la théorie des modèles, d'une théorie instable. Il importe donc de distinguer les théories qui ont cette propriété de celles qui ne l'ont pas; le critère de Keisler [1] et de Shelah [5], qui consiste à compter le nombre de types qu'on peut obtenir sur un ensemble de paramètres de cardinal λ, n'emporte la décision que si l'on nie assez brutalement l'hypothèse du continu généralisée. Je propose ici de compter, étant donnée une partie X, de cardinal λ, d'un espace de types Si(M), quel peut être le cardinal de l'adhérence de X; ce point de vue équivaut au précédent si la théorie T est stable (voir la remarque après le Théorème 7); et si T n'a pas la propriété d'indépendance ce cardinal est au plus 2λ, tandis que si T a la propriété d'indépendance il peut atteindre 22λ (Théorème 7). Cela donne, indépendamment d'hypothèses de théorie des ensembles, une mesure quantitative de la plus grande complexité des espaces de types s'il y a propriété d'indépendance; et sous la forme du Théorème 8, cela devient un test très maniable dans les situations concrètes, car l'expérience m'a prouvé que les cohéritiers d'un type sont toujours faciles à déterminer.Dans une première section, je considère un type complet p au dessus d'un modèle M d'une théorie complète T, et parmi les fils de p sur une extension élémentaire de M j'en distingue certains que j'appelle fils spéciaux de p: cette notion est naturelle et utile pour la suite, car le critère que j'ai décrit revient à prouver l'abondance de certains fils spéciaux d'un même type; on notera au passage le Théorème 3.Le théorème de caractérisation de la propriété d'indépendance est prouvé dans une deuxième section, grâce à un résultat de combinatoire (Théorème 6); j'y montre aussi, à titre d'illustration, qu'un ordre total n'a jamais la propriété d'indépendance.
The generalised RK-order, orthogonality and regular types for modules
Authors: Prest Mike 
Published: May 2006

I characterise various model-theoretic properties of types, in complete theories of modules, in terms of the algebraic structure of pure-injective modules. More specifically, I consider the generalised RK-order, and the relation of domination between types, orthogonality of types, and regular types. It will be seen that, essentially, it is the stationary types over pure-injective models which bear the algebraic structural information.For background in the model theory of modules, see [4], [5], [13], [17], [19], and for the model-theoretic background [10], [11], [12], [18]. More specific references will be given in the text. I summarise some principal definitions and results below. First, though, let me describe the main results.Throughout this paper, R will be a ring with 1; the language will be that for (right R-) modules. All types will be complete types in a complete theory, T, of R-modules. The notation is reserved for an extremely saturated model of T, inside which all “small” situations may be found. Thus, sets of parameters are just subsets of , and all models will be elementary substructures of . A positive primitive, or pp, formula is one which is equivalent to a formula of the formwith the rij ∈ R.Suppose that p and q are 1-types over a pure-injective model M.
The degree of the set of sentences of predicate provability logic that are true under every interpretation
Authors: Boolos George , McGee Vann 
Published: May 2006

The formalism of P(redicate) P(rovability) L(ogic) is the result of adjoining the unary operator □ to first-order logic without identity, constants, or function symbols. The term “provability” indicates that □ is to be “read” as “it is provable in P(eano) A(rithmetic) that…” and that the formulae of predicate provability logic are to be interpreted via formulae of PA as follows.Pr(x), alias Bew(x), is the standard provability predicate of PA. For any formula F of PA, Pr[F] is the formula of PA that expresses the PA-provability of F “of” the values of the variables free in F, i.e., it is the formula of PA with the same free variables as F that expresses the PA-provability of the result of substituting for each variable free in F the numeral for the value of that variable. For the details of the construction of Pr[F], the reader may consult [B2, p. 42]. If F is a sentence of PA, then Pr[F] = Pr(‘F’), the sentence that expresses the PA-provability of F.Let υ1, υ2,… be an enumeration of the variables of PA. An interpretation * of a formula ϕ of PPL is a function which assigns to each predicate symbol P of ϕ a formula P* of the language of arithmetic whose free variables are the first n variables of PA, where n is the degree of P.
Alfred Tarski and undecidable theories
Authors: McNulty George F. 
Published: May 2006

Alfred Tarski identified decidability within various logical formalisms as one of the principal themes for investigation in mathematical logic. This is evident already in the focus of the seminar he organized in Warsaw in 1926. Over the ensuing fifty-five years, Tarski put forth a steady stream of theorems concerning decidability, many with far-reaching consequences. Just as the work of the 1926 seminar reflected Tarski's profound early interest in decidability, so does his last work, A formalization of set theory without variables, a monograph written in collaboration with S. Givant [8−m]. An account of the Warsaw seminar can be found in Vaught [1986].Tarski's work on decidability falls into four broad areas: elementary theories which are decidable, elementary theories which are undecidable, the undecidability of theories of various restricted kinds, and what might be called decision problems of the second degree. An account of Tarski's work with decidable elementary theories can be found in Doner and van den Dries [1987] and in Monk [1986] (for Boolean algebras). Vaught [1986] discusses Tarski's contributions to the method of quantifier elimination. Our principal concern here is Tarski's work in the remaining three areas.We will say that a set of elementary sentences is a theory provided it is closed with respect to logical consequence and we will say that a theory is decidable or undecidable depending on whether it is a recursive or nonrecursive set. The notion of a theory may be restricted in a number of interesting ways. For example, an equational theory is just the set of all universal sentences, belonging to some elementary theory, whose quantifier-free parts are equations between terms.
Functors and ordinal notations. II: A functorial construction of the Bachmann hierarchy
Authors: Girard Jean-Yves , Vauzeilles Jacqueline 
Published: May 2006

This paper is the sequel of “a functorial construction of the Veblen hierarchy” [GV]: it was announced in it.We define the notion of garden (Definition I.1.6), that is a functorial version of a Bachmann collection: in a garden Jy, at each ordinal x ≤ y, of cofinality Ω, is associated an Ω-flower (Definition I.1.1); we define also the notion of a function compatible with a garden (Definition I.3.3). We construct a hierarchy of functors from Ω to Ω (for each x ≤ y and x ∈ Jy) and for each function (f ∈ I(x, y) compatible with Jy a natural transformation T(f) from to ; we show that, if the garden is Gε Ω + 1 (Definition I.2.1), then, for each ordinal x ≤ εΩ + 1, the hierarchy of functions coincides exactly with the usual hierarchy ψx constructed using the usual Bachmann collection of height εΩ + 1, and founded on composition (that is, ψx + 1 = ψx ˚ ψ1; then, (0) is the usual Howard ordinal. We show also, that for eac x ≤ y, φx is an Ω-flower, and so we can use this hierarchy of functors for ordinal notations: see Chapter II of -logic [G].The construction made in this article corresponds, essentially, to Chapter V of -logic [G]: the exact connections between these two works will be the matter of a subsequent article.
The model theory of finitely generated finite-by-abelian groups
Authors: Oger Francis 
Published: May 2006

AbstractIn [O1], we gave algebraic characterizations of elementary equivalence for finitely generated finite-by-abelian groups, i.e. finitely generated FC-groups. We also provided several examples of finitely generated finite-by-abelian groups which are elementarily equivalent without being isomorphic.In this paper, we shall use our previous results to describe precisely the models of the theories of finitely generated finite-by-abelian groups and the elementary embeddings between these models.
Determinateness of certain almost-Borel games
Authors: Wolf Robert S. 
Published: May 2006

AbstractWe prove (in ZFC Set Theory) that all infinite games whose winning sets are of the following forms are determined:(1) (A − S) ∪ B, where A is , , and the game whose winning set is B is “strongly determined” (meaning that all of its subgames are determined).(2) A Boolean combination of sets and sets smaller than the continuum.This also enables us to show that strong determinateness is not preserved under complementation, improving a result of Morton Davis which required the continuum hypothesis to prove this fact.Various open questions related to the above results are discussed. Our main conjecture is that (2) above remains true when is replaced by “Borel”.
The status of the axiom of choice in set theory with a universal set
Authors: Forster T. E. 
Published: May 2006

The purpose of this paper is not to produce a survey of systems with a universal set: we do not yet understand them well enough. Rather it will concentrate on one particular aspect of them: the curious circumstance that there are half-a-dozen or so distinct proofs of ~ AC available in set theories with a universal set. This began to emerge in 1953 when Specker published in [2] a proof of ~ AC in Quine's system NF. Until recently this was an isolated phenomenon and poorly understood. The proof answered few questions and seemed rather ad hoc, thus inviting an investigation to determine whether this was an artefact caused by the particular axioms for NF, or part of a general conflict between the demands of big sets and AC.We will start with an informal discussion of the genesis of set theories with a universal set, collecting, en route, a number of desiderata for such theories. A number of new refutations of AC in systems meeting some or all of these conditions will then be presented. The conclusion the reader is invited to draw is that any sensible set theory with a universal set will probably have trouble with AC.Why do set theory with V e V at all? It contradicts conventional wisdom which teaches us that e is wellfounded. It must be said for this doctrine (let us abbreviate it to WOOF) that it has enabled the rapid execution of the logicist programme, so if that were the sole purpose of set theory we could consider ourselves well served. However most pure mathematicians are platonists and study things not because they are useful but simply because they are there. And the belief that V is not there can, after all, only be the result of early conditioning.
Second-order languages and mathematical practice
Authors: Shapiro Stewart 
Published: May 2006

There are well-known theorems in mathematical logic that indicate rather profound differences between the logic of first-order languages and the logic of second-order languages. In the first-order case, for example, there is Gödel's completeness theorem: every consistent set of sentences (vis-à-vis a standard axiomatization) has a model. As a corollary, first-order logic is compact: if a set of formulas is not satisfiable, then it has a finite subset which also is not satisfiable. The downward Löwenheim-Skolem theorem is that every set of satisfiable first-order sentences has a model whose cardinality is at most countable (or the cardinality of the set of sentences, whichever is greater), and the upward Löwenheim-Skolem theorem is that if a set of first-order sentences has, for each natural number n, a model whose cardinality is at least n, then it has, for each infinite cardinal κ (greater than or equal to the cardinality of the set of sentences), a model of cardinality κ. It follows, of course, that no set of first-order sentences that has an infinite model can be categorical. Second-order logic, on the other hand, is inherently incomplete in the sense that no recursive, sound axiomatization of it is complete. It is not compact, and there are many well-known categorical sets of second-order sentences (with infinite models). Thus, there are no straightforward analogues to the Löwenheim-Skolem theorems for second-order languages and logic.There has been some controversy in recent years as to whether “second-order logic” should be considered a part of logic, but this boundary issue does not concern me directly, at least not here.