bluuebunny/crossref_metadata_2025_split huggingface dataset:
Forcing the failure of CH by adding a real
Authors: Shelah Saharon , Woodin Hugh 
Published: May 2006

We prove several independence results relevant to an old question in the folklore of set theory. These results complement those in [Sh, Chapter XIII, §4]. The question is the following. Suppose V ⊨ “ZFC + CH” and r is a real not in V. Must V[r] ⊨ CH? To avoid trivialities assume = .We answer this question negatively. Specifically we find pairs of models (W, V) such that W ⊨ ZFC + CH, V = W[r], r a real, = and V ⊨ ¬CH. Actually we find a spectrum of such pairs using ZFC up to “ZFC + there exist measurable cardinals”. Basically the nicer the pair is as a solution, the more we need to assume in order to construct it.The relevant results in [Sh, Chapter XIII] state that if a pair (of inner models) (W, V) satisfies (1) and (2) then there is an inaccessible cardinal in L; if in addition V ⊨ 2ℵ0 > ℵ2 then 0# exists; and finally if (W, V) satisfies (1), (2) and (3) with V ⊨ 2ℵ0 > ℵω, then there is an inner model with a measurable cardinal.Definition 1. For a pair (W, V) we shall consider the following conditions:(1) V = W[r], r a real, = , W ⊨ ZFC + CH but CH fails in V.(2) W ⊨ GCH.(3) W and V have the same cardinals.
The consistency strength of the free-subset property for ωω
Authors: Koepke Peter 
Published: May 2006

A subset X of a structure S is called free in S if ∀x ∈ Xx ∉ S[X − {x}]; here, S[Y] is the substructure of S generated from Y by the functions of S. For κ, λ, μ cardinals, let Frμ(κ, λ) be the assertion:for every structure S with κ ⊂ S which has at most μ functions and relations there is a subset X ⊂ κ free in S of cardinality ≥ λ.We show that Frω(ωω, ω), the free-subset property for ωω, is equiconsistent with the existence of a measurable cardinal (2.2,4.4). This answers a question of Devlin [De].In the first section of this paper we prove some combinatorial facts about Frμ(κ, λ); in particular the first cardinal κ such that Frω(κ, ω) is weakly inaccessible or of cofinality ω (1.2). The second section shows that, under Frω(ωω, ω), ωω is measurable in an inner model. For the convenience of readers not acquainted with the core model κ, we first deduce the existence of 0# (2.1) using the inner model L. Then we adapt the proof to the core model and obtain that ωω is measurable in an inner model. For the reverse direction, we essentially apply a construction of Shelah [Sh] who forced Frω(ωω, ω) over a ground model which contains an ω-sequence of measurable cardinals. We show in §4 that indeed a coherent sequence of Ramsey cardinals suffices. In §3 we obtain such a sequence as an endsegment of a Prikry sequence.
A preservation theorem for ec-structures with applications
Authors: Albert Michael H. 
Published: May 2006

AbstractWe characterize the model companions of universal Horn classes generated by a two-element algebra (or ordered two-element algebra). We begin by proving that given two mutually model consistent classes M and N of (respectively ) structures, with , , provided that an -definability condition for the function and relation symbols of holds. We use this, together with Post's characterization of ISP(A), where A is a two-element algebra, to show that the model companions of these classes essentially lie in the classes of posets and semilattices, or characteristic two groups and relatively complemented distributive lattices.
A note on elementary equivalence of C(K) spaces
Authors: Heinrich S. , Henson C. Ward , Moore L. C. 
Published: May 2006

In this paper we give a closer analysis of the elementary properties of the Banach spaces C(K), where K is a totally disconnected, compact Hausdorff space, in terms of the Boolean algebra B(K) of clopen subsets of K. In particular we sharpen a result in [4] by showing that if B(K1) and B(K2) satisfy the same sentences with ≤ n alternations of quantifiers, then the same is true of C(K1) and C(K2). As a consequence we show that for each n there exist C(K) spaces which are elementarily equivalent for sentences with ≤ n quantifier alternations, but which are not elementary equivalent in the full sense. Thus the elementary properties of Banach spaces cannot be determined by looking at sentences with a bounded number of quantifier alternations.The notion of elementary equivalence for Banach spaces which is studied here was introduced by the second author [4] and is expressed using the language of positive bounded formulas in a first-order language for Banach spaces. As was shown in [4], two Banach spaces are elementarily equivalent in this sense if and only if they have isometrically isomorphic Banach space ultrapowers (or, equivalently, isometrically isomorphic nonstandard hulls.)We consider Banach spaces over the field of real numbers. If X is such a space, Bx will denote the closed unit ball of X, Bx = {x ϵ X∣ ∣∣x∣∣ ≤ 1}. Given a compact Hausdorff space K, we let C(K) denote the Banach space of all continuous real-valued functions on K, under the supremum norm. We will especially be concerned with such spaces when K is a totally disconnected compact Hausdorff space. In that case B(K) will denote the Boolean algebra of all clopen subsets of K. We adopt the standard notation from model theory and Banach space theory.
Martin's axiom and a regular topological space with uncountable net weight whose countable product is hereditarily separable and hereditarily Lindelöf
Authors: Ciesielski Krzysztof 
Published: May 2006

In [1, p. 51] A. V. Arhangel'skiĭ, in connection with the problems of L-spaces and S-spaces, examined further the notions of hereditary separability and hereditary Lindelöfness. In particular he considered the following property P: “Every regular topological space has a countable net weight provided its countable product is hereditarily Lindelöf and hereditarily separable.” He noticed that the continuum hypothesis implies negation of the property P and posed a question: “Do Martin's Axiom and the negation of the continuum hypothesis imply P?” The purpose of this paper is to give a negative answer to this question.The set-theoretical and topological notation that we use is standard and can be found in [6] and [5] respectively.Throughout the paper we will use the notation H(X, Y) to denote the set of all finite functions from a set X to Y.Theorem. Con(ZFC) → Con(ZFC + MA + ¬CH + there exists a 0-dimensional Hausdorff space X such that nw(X) = с and nw(Y) = ω for any Y ϵ [X]<с).Proof. Let M be a model of ZFC satisfying CH and let F be an M-generic filter over the Cohen forcing {H(ω2 × ω2, 2), ⊃). Then f = ⋃F is a function and f: ω2 × ω2 → 2.
Isolated types in a weakly minimal set
Authors: Buechler Steven 
Published: May 2006

AbstractTheorem A. Let T be a small superstable theory, A a finite set, and ψ a weakly minimal formula over A which is contained in some nontrivial type which does not have Morley rank. Then ψ is contained in some nonalqebraic isolated type over A.As an application we proveTheorem B. Suppose that T is small and superstable, A is finite, and there is a nontrivial weakly minimal type p ∈ S(A) which does not have Morley rank. Then the prime model over A is not minimal over A.
MM. Borel, Tits, Zil′ber et le Général Nonsense
Authors: Poizat Bruno 
Published: May 2006

Le rêve secret de tout logicien, c’est de prouver un résultat mathématique significatif avec des moyens de fortune; ce rêve se réalise parfois de manière quelque peu biaisée, le théorème obtenu n’étant qu’une version trop simplifiée, ou bien trop adaptée aux besoins de la logique, pour convaincre un mathématicien normal. C’est pour cela que j’annonce d’emblée la couleur, et que je précise les règles du jeu: la version du théorème de Borel-Tits que je vais montrer, concernant les groupes algébriques simples sur un corps de base algébriquement clos, sera considérée comme pratiquement évidente par un géomètre; mais c’est, à mon avis, la seule qui ait un intérêt pour un théoricien des modèles.Quand on entreprend ainsi de redémontrer une version simple d’un résultat par ailleurs bien connu, le seul intérêt est dans la méthode: ce que je veux, ici, c’est présenter une preuve qui n’utilise aucune information, ou presque, sur la structure algébrique de ces groupes; il est même souhaitable d’oublier qu’il s’agit de groupes linéaires! Elle repose sur des résultats généraux concernant les groupes de rang de Morley fini, dus à divers auteurs, dont le principal, Boris Iosifovič Zil′ber, a déjà fait une tentative similaire [Zil′ber 1984]; je poursuis ici cette tentative, mais en me limitant à des arguments encore moins spécifiques au contexte de la géométrie.Si je fais ainsi, ce n’est pas pour donner l’impression que l’unique ambition de la théorie des modèles est de montrer des résultats triviaux par des méthodes triviales.
Boolean simple groups and boolean simple rings
Authors: Takeuti Gaisi 
Published: May 2006

Let be a complete Boolean algebra and G a finite simple group in the Scott-Solovay -valued model V() of set theory. If we observe G outside V(), then we get a new group which is denoted by Ĝ. In general, Ĝ is not finite nor simple. Nevertheless Ĝ satisfies every property satisfied by a finite simple group with some translation. In this way, we can get a class of groups for which we can use a well-developed theory of the finite simple groups. We call Ĝ Boolean simple if G is simple in some V(). In the same way we define Boolean simple rings. The main purpose of this paper is a study of structures of Boolean simple groups and Boolean simple rings. As for Boolean simple rings, K. Eda previously constructed Boolean completion of rings with a certain condition. His construction is useful for our purpose.The present work is a part of a series of systematic applications of Boolean valued method. The reader who is interested in this subject should consult with papers by Eda, Nishimura, Ozawa, and the author in the list of references.
Σ2-collection and the infinite injury priority method
Authors: Mytilinaios Michael E. , Slaman Theodore A. 
Published: May 2006

AbstractWe show that the existence of a recursively enumerable set whose Turing degree is neither low nor complete cannot be proven from the basic axioms of first order arithmetic (P−) together with Σ2-collection (BΣ2). In contrast, a high (hence, not low) incomplete recursively enumerable set can be assembled by a standard application of the infinite injury priority method. Similarly, for each n, the existence of an incomplete recursively enumerable set that is neither lown nor highn-1, while true, cannot be established in P− + BΣn+1. Consequently, no bounded fragment of first order arithmetic establishes the facts that the highn and lown jump hierarchies are proper on the recursively enumerable degrees.
Relational structures determined by their finite induced substructures
Authors: Hodkinson I. M. , Macpherson H. D. 
Published: May 2006

AbstractA countably infinite relational structure M is called absolutely ubiquitous if the following holds: whenever N is a countably infinite structure, and M and N have the same isomorphism types of finite induced substructures, there is an isomorphism from M to N. Here a characterisation is given of absolutely ubiquitous structures over languages with finitely many relation symbols. A corresponding result is proved for uncountable structures.
Partition properties and Prikry forcing on simple spaces
Authors: Henle J. M. 
Published: May 2006

One of the simplest and yet most fruitful ideas in forcing was the notion of Karel Prikry in which he used a measure on a cardinal κ to change the cofinality of κ to ω without collapsing it. The idea has found connections to almost every branch of modern set theory, from large cardinals to small, from combinatorics to models, from Choice to Determinacy, and from consistency to inconsistency. The long list of generalizers and modifiers includes Apter, Gitik, Henle, Spector, Shelah, Mathias, Magidor, Radin, Blass and Kimchi.This paper is about generalizing Prikry forcing and partition properties to “simple spaces”. The concept of a simple space is itself the generalization of those combinatorial objects upon which the notions of “measurable”, “compact”, “supercompact”, “huge”, etc. are based. Simple spaces were introduced in [ADHZ1] and [ADHZ2] together with a broader generalization, “filter spaces”. The definition provided here is a small simplification of earlier versions. The author is indebted to Mitchell Spector, whose careful reading turned up numerous errors, some subtle, some flagrant.In this first section, we review simple spaces briefly, including a short introduction to the space Qκλ. In §2, we describe our generalizations of partition property and Prikry forcing, and discuss the relationship between them. In §3, we find a partition property for the huge space [λ]κ, but show that Prikry forcing here is impossible. We find partition properties for Qκλ and show that Prikry forcing can be done here.
Undecidability and initial segments of the (r.e.) tt-degrees
Authors: Haught Christine Ann , Shore Richard A. 
Published: May 2006

A notion of reducibility ≤r between sets is specified by giving a set of procedures for computing one set from another. We say that a set A is r-reducible to a set B, A ≤rB, if one of the procedures applied to B gives A. Associated with any such reducibility notion is the structure of r-degrees, the equivalence classes of sets with respect to this reducibility, with the induced ordering. The most general notion of a computable reducibility is that of Turing, ≤T. Here we say that A ≤TB if there is a Turing machine φe which, when equipped with an oracle for B, computes A: φeB = A. Such Turing degree computations are characterized by the phenomenon that only during the computation itself do we discover which questions about B need to be answered to compute A(x). In contrast, for nearly all other computable reducibilities the set of questions needed is given in advance by a recursive procedure. Perhaps the most common example of such a procedure is many-one reducibility, ≤m: A ≤mB if there is a recursive function f such that x ∈ A ⇔ f(x) ∈ B.Reducibilities with the property that the output, A(x), is determined by the answers that B gives to a set of questions calculated recursively from x are said to be of tabular type. The most general tabular reducibility is called truth-table reducibility, ≤tt. The procedures [e] associated with this reducibility are specified by a recursive function f (= {e}) which, for each x, gives a set of n questions about the oracle and, for each of the possible 2n sets of answers, gives the corresponding output. As usual this defines A ≤ttB as “there is an e such that [e]B = A”. It is with this notion of reducibility and the associated tt-degrees that we shall be concerned in this paper. Basic information on several such strong reducibilities can be found in Rogers [28]. For more information we recommend the survey articles by Odifreddi [25] and Degtev [2] as well as Odifreddi's book [26].
Effective model theory vs. recursive model theory
Authors: Chisholm John 
Published: May 2006

Recursive model theory is supposed to be the study of the effectiveness of constructions and theorems in model theory. This often involves getting “effective” versions of various classical model-theoretic notions. The traditional way of doing this is to restrict attention to recursive models, and recursive isomorphisms between them, etc. Thus for example the following definition appears in the literature (in [3] and [1]).Definition. Given a recursive model A and an n Є ω, a subset R ⊆ An is called intrinsically r.e. provided that for every recursive model B ≈ A, the isomorphic image in B of R is an r.e. subset of Bn.It is clear that if R is definable by a (recursive, infinitary) Σ10 formula (with finitely many parameters from A), then R is intrinsically r.e. It seems natural for the converse to be true. Indeed, provided that (A, R) is sufficiently “regular” in a sense made precise in a theorem of Ash and Nerode (see [3]), the converse is true. However, if we drop the (rather strong) regularity conditions, there exist “pathological” examples of intrinsically r.e. relations which are not definable by a Σ10 formula (see [7]).In this paper, we suggest a rather different approach to studying the effectiveness of model theory, an approach we have dubbed “effective model theory”. The basic idea is to allow arbitrary nonrecursive models, but to require all notions to be relativized to the complexity of the models involved. (Much the same notion has been used in [2] under the name “relatively recursive model theory”.) Thus for example we have the following effective model theory version of the property of being intrinsically r.e.
Partial realizations of Hilbert's program
Authors: Simpson Stephen G. 
Published: May 2006

§0. Introduction. What follows is a write-up of my contribution to the symposium “Hilbert's Program Sixty Years Later” which was sponsored jointly by the American Philosophical Association and the Association for Symbolic Logic. The symposium was held on December 29,1985 in Washington, D. C. The panelists were Solomon Feferman, Dag Prawitz and myself. The moderator was Wilfried Sieg. The research which I discuss here was partially supported by NSF Grant DMS-8317874.I am grateful to the organizers of this timely symposium on an important topic. As a mathematician I particularly value the opportunity to address an audience consisting largely of philosophers. It is true that I was asked to concentrate on the mathematical aspects of Hilbert's program. But since Hilbert's program is concerned solely with the foundations of mathematics, the restriction to mathematical aspects is really no restriction at all.Hilbert assigned a special role to a certain restricted kind of mathematical reasoning known as finitistic. The essence of Hilbert's program was to justify all of set-theoretical mathematics by means of a reduction to finitism. It is now well known that this task cannot be carried out. Any such possibility is refuted by Gödel's theorem. Nevertheless, recent research has revealed the feasibility of a significant partial realization of Hilbert's program. Despite Gödel's theorem, one can give a finitistic reduction for a substantial portion of infinitistic mathematics including many of the best-known nonconstructive theorems. My purpose here is to call attention to these modern developments.
A proofless proof of the Barwise compactness theorem
Authors: Howard Mark 
Published: May 2006

AbstractWe prove a theorem (1.7) about partial orders which can be viewed as a version of the Barwise compactness theorem which does not mention logic. The Barwise compactness theorem is easily equivalent to 1.7 + “Every Henkin set has a model”. We then make the observation that 1.7 gives us the definability of forcing for quantifier-free sentences in the forcing language and use this to give a direct proof of the truth and definability lemmas of forcing.
A normalization theorem for set theory
Authors: Bailin Sidney C. 
Published: May 2006

In this paper we present a normalization theorem for a natural deduction formulation of Zermelo set theory. Our result gets around M. Crabbe's counterexample to normalizability (Hallnäs [3]) by adding an inference rule of the formand requiring that this rule be used wherever it is applicable. Alternatively, we can regard the result as pertaining to a modified notion of normalization, in which an inferenceis never considered reducible if A is T Є T, even if R is an elimination rule and the major premise of R is the conclusion of an introduction rule. A third alternative is to regard (1) as a derived rule: using the general well-foundedness rulewe can derive (1). If we regard (2) as neutral with respect to the normality of derivations (i.e., (2) counts as neither an introduction nor an elimination rule), then the resulting proofs are normal.
Ordinal numbers and the Hilbert basis theorem
Authors: Simpson Stephen G. 
Published: May 2006

In [5] and [21] we studied countable algebra in the context of “reverse mathematics”. We considered set existence axioms formulated in the language of second order arithmetic. We showed that many well-known theorems about countable fields, countable rings, countable abelian groups, etc. are equivalent to the respective set existence axioms which are needed to prove them.One classical algebraic theorem which we did not consider in [5] and [21] is the Hilbert basis theorem. Let K be a field. For any natural number m, let K[x1,…,xm] be the ring of polynomials over K in m commuting indeterminates x1,…,xm. The Hilbert basis theorem asserts that for all K and m, every ideal in the ring K[x1,…,xm] is finitely generated. This theorem is of fundamental importance for invariant theory and for algebraic geometry. There is also a generalization, the Robson basis theorem [11], which makes a similar but more restrictive assertion about the ring K〈x1,…,xm〉 of polynomials over K in mnoncommuting indeterminates.In this paper we study a certain formal version of the Hilbert basis theorem within the language of second order arithmetic. Our main result is that, for any or all countable fields K, our version of the Hilbert basis theorem is equivalent to the assertion that the ordinal number ωω is well ordered. (The equivalence is provable in the weak base theory RCA0.) Thus the ordinal number ωω is a measure of the “intrinsic logical strength” of the Hilbert basis theorem. Such a measure is of interest in reference to the historic controversy surrounding the Hilbert basis theorem's apparent lack of constructive or computational content.
Markov's principle, isols and Dedekind finite sets
Authors: McCarty Charles 
Published: May 2006

Markov's principle is more than a convenience in constructive arithmetic and analysis; it is absolutely essential to significant areas of constructive cardinal arithmetic. In turn, logical relations among intuitively appealing principles of constructive cardinal arithmetic parallel relations between MPS and other “problematic axioms” for constructive mathematics, such as the limited principle of omniscience. Finally, simple closure properties on the Dedekind finite sets provide ready examples of statements which are strictly weaker than Markov's principle and yet are independent of extensions of IZF.MPS, Markov's principle with variables over sets, is equivalent to each of these elementary properties of ⊿, the class of Dedekind finite sets:1. ∀A(A Є ⊿ ↔ CP(A)).2. [*]A Є ⊿ ↔ ∀B (A + B is infinite ↔ B is infinite).3. [**]A Є ⊿ ↔ ∀B((A + 1) x B is infinite ↔ B is infinite).CP is Tarski's cancellation property. Consequently, MPS is tantamount, in constructive mathematics, to the standard classical characterizations of ⊿ in terms of cardinality.[*] and [**] imply that ⊿ is closed under addition and multiplication. Closure under addition is, in turn, constructively equivalent to the closure of ⊿ under all combinatorial functions and to the fact that ⊿ is closed under each strict combinatorial function individually. Generally speaking, a function on P(ω) is combinatorial whenever it preserves finiteness, respects cardinality and has a “moduluslike” associate function. It is strict when it is strictly increasing relative to the subset ordering, [cf. §6 for precise definitions.] From this, we see that MPS is foundational for cardinal arithmetic on the constructive Dedekind finite sets.