Independence Results in Set Theory

L’Ipotesi del Continuo, formulata da Cantor nel 1878, è una delle congetture più note della teoria degli insiemi. Il Problema del Continuo, che ad essa è collegato, fu collocato da Hilbert, nel 1900, fra i principali problemi insoluti della matematica. A seguito della dimostrazione di indipendenza dell’Ipotesi del Continuo dagli assiomi della teoria degli insiemi, lo status attuale del problema è controverso. In anni più recenti, la ricerca di una soluzione del Problema del Continuo è stata anche una delle ragioni (...) fondamentali per la ricerca di nuovi assiomi in matematica. L’articolo fornisce un quadro generale dei risultati matematici fondamentali, e un’analisi di alcune delle questioni filosofiche connesse al Problema del Continuo. (shrink)

The Hyperuniverse Programme, introduced in Arrigoni and Friedman (2013), fosters the search for new set-theoretic axioms. In this paper, we present the procedure envisaged by the programme to find new axioms and the conceptual framework behind it. The procedure comes in several steps. Intrinsically motivated axioms are those statements which are suggested by the standard concept of set, i.e. the `maximal iterative concept', and the programme identi fies higher-order statements motivated by the maximal iterative concept. The satisfaction of these statements (...) (H-axioms) in countable transitive models, the collection of which constitutes the `hyperuniverse' (H), has remarkable 1st-order consequences, some of which we review in section 5. (shrink)

Discussion of new axioms for set theory has often focused on conceptions of maximality, and how these might relate to the iterative conception of set. This paper provides critical appraisal of how certain maximality axioms behave on different conceptions of ontology concerning the iterative conception. In particular, we argue that forms of multiversism and actualism face complementary problems. The latter view is unable to use maximality axioms that make use of extensions, where the former has to contend with the existence (...) of extensions violating maximality axioms. An analysis of two kinds of multiversism, a Zermelian form and Skolemite form, leads to the conclusion that the kind of maximality captured by an axiom differs substantially according to background ontology. (shrink)

We will give a simple philosophical "proof" of the negation of Cantor's continuum hypothesis (CH). (A formal proof for or against CH from the axioms of ZFC is impossible; see Cohen [1].) We will assume the axioms of ZFC together with intuitively clear axioms which are based on some intuition of Stuart Davidson and an old theorem of Sierpinski and are justified by the symmetry in a thought experiment throwing darts at the real number line. We will in fact show (...) why there must be an infinity of cardinalities between the integers and the reals. We will also show why Martin's Axiom must be false, and we will prove the extension of Fubini's Theorem for Lebesgue measure where joint measurability is not assumed. Following the philosophy--if you reject CH you are only two steps away from rejecting the axiom of choice (AC)--we will point out along the way some extensions of our intuition which contradict AC. (shrink)

The multiverse view in set theory, introduced and argued for in this article, is the view that there are many distinct concepts of set, each instantiated in a corresponding set-theoretic universe. The universe view, in contrast, asserts that there is an absolute background set concept, with a corresponding absolute set-theoretic universe in which every set-theoretic question has a definite answer. The multiverse position, I argue, explains our experience with the enormous range of set-theoretic possibilities, a phenomenon that challenges the universe (...) view. In particular, I argue that the continuum hypothesis is settled on the multiverse view by our extensive knowledge about how it behaves in the multiverse, and as a result it can no longer be settled in the manner formerly hoped for. (shrink)

This third edition, now available in paperback, is a follow up to the author's classic Boolean-Valued Models and Independence Proofs in Set Theory. It provides an exposition of some of the most important results in set theory obtained in the 20th century: the independence of the continuum hypothesis and the axiom of choice.

A proof of the (propositional) Craig interpolation theorem for cut-free sequent calculus yields that a sequent with a cut-free proof (or with a proof with cut-formulas of restricted form; in particular, with only analytic cuts) with k inferences has an interpolant whose circuit-size is at most k. We give a new proof of the interpolation theorem based on a communication complexity approach which allows a similar estimate for a larger class of proofs. We derive from it several corollaries: (1) Feasible (...) interpolation theorems for the following proof systems: (a) resolution (b) a subsystem of LK corresponding to the bounded arithmetic theory S 2 2 (α) (c) linear equational calculus (d) cutting planes. (2) New proofs of the exponential lower bounds (for new formulas) (a) for resolution ([15]) (b) for the cutting planes proof system with coefficients written in unary ([4]). (3) An alternative proof of the independence result of [43] concerning the provability of circuit-size lower bounds in the bounded arithmetic theory S 2 2 (α). In the other direction we show that a depth 2 subsystem of LK does not admit feasible monotone interpolation theorem (the so called Lyndon theorem), and that a feasible monotone interpolation theorem for the depth 1 subsystem of LK would yield new exponential lower bounds for resolution proofs of the weak pigeonhole principle. (shrink)

Machine generated contents note: 1. Introduction Juliette Kennedy and Roman Kossak; 2. Historical remarks on Suslin's problem Akihiro Kanamori; 3. The continuum hypothesis, the generic-multiverse of sets, and the [OMEGA] conjecture W. Hugh Woodin; 4. [omega]-Models of finite set theory Ali Enayat, James H. Schmerl and Albert Visser; 5. Tennenbaum's theorem for models of arithmetic Richard Kaye; 6. Hierarchies of subsystems of weak arithmetic Shahram Mohsenipour; 7. Diophantine correct open induction Sidney Raffer; 8. Tennenbaum's theorem and recursive reducts James H. (...) Schmerl; 9. History of constructivism in the 20th century A. S. Troelstra; 10. A very short history of ultrafinitism Rose M. Cherubin and Mirco A. Mannucci; 11. Sue Toledo's notes of her conversations with Gödel in 1972-1975 Sue Toledo; 12. Stanley Tennenbaum's Socrates Curtis Franks; 13. Tennenbaum's proof of the irrationality of [the square root of] 2́. (shrink)

We present some new set and class theoretic independence results from ZFC and NBGC that are particularly simple and close to the primitives of membership and equality. They are shown to be equivalent to familiar small large cardinal hypotheses. We modify these independendent statements in order to give an example of a sentence in set theory with 5 quantifiers which is independent of ZFC. It is known that all 3 quantifier sentences are decided in a weak fragment of ZF without (...) power set. (shrink)

We extend an independence result proved in our earlier paper "Solovay's Theorem Cannot Be Simplified" (Annals of Pure and Applied Logic 112 (2001)). Our method uses the Barwise.

In the article the problem of independence in mathematics is discussed. The status of the continuum hypothesis, large cardinal axioms and the axiom of constructablility is presented in some detail. The problem whether incompleteness is really relevant for ordinary mathematics and for empirical science is investigated. Another aim of the article is to give some arguments for the thesis that the problem of reliability and justification of new axioms is well-posed and worthy of attention. In my opinion, investigations concerning the (...) status of independent sentences give insight into our understanding of mathematical concepts, of mathematical knowledge and of the role of mathematics in empirical science. (shrink)

This is the third edition of a book originally published in the 1970s; it provides a systematic and nicely organized presentation of the elegant method of using Boolean-valued models to prove independence results. Four things are new in the third edition: background material on Heyting algebras, a chapter on ‘Boolean-valued analysis’, one on using Heyting algebras to understand intuitionistic set theory, and an appendix explaining how Boolean and Heyting algebras look from the perspective of category theory. The book presents results (...) from a number of set theorists and includes an insightful and informative foreword by Dana Scott. Bell's presentation is lively and pleasant to read, and the material is given in a nicely cohesive way.One obvious reason to be interested in independence proofs is that they concern the important question, what is the set-theoretic hierarchy like? The proofs in Bell's book cover some of the most basic and fundamental independence results, such as those concerning the size of the continuum, the independence of the Axiom of Choice from ZF, cardinal collapsing, Souslin's hypothesis, and Martin's Axiom.Since Gödel's incompleteness theorem, it has been known that for any serious candidate list of set-theoretic axioms, there will be statements neither provable nor disprovable from those axioms. What is really interesting, however, and what the independence proofs discussed here show, is how many of the most natural questions about sets are not decided by the standard axioms of ZFC, and how …. (shrink)

It is often alleged that, unlike typical axioms of mathematics, the Continuum Hypothesis (CH) is indeterminate. This position is normally defended on the ground that the CH is undecidable in a way that typical axioms are not. Call this kind of undecidability “absolute undecidability”. In this paper, I seek to understand what absolute undecidability could be such that one might hope to establish that (a) CH is absolutely undecidable, (b) typical axioms are not absolutely undecidable, and (c) if a mathematical (...) hypothesis is absolutely undecidable, then it is indeterminate. I shall argue that on no understanding of absolute undecidability could one hope to establish all of (a)–(c). However, I will identify one understanding of absolute undecidability on which one might hope to establish both (a) and (c) to the exclusion of (b). This suggests that a new style of mathematical antirealism deserves attention—one that does not depend on familiar epistemological or ontological concerns. The key idea behind this view is that typical mathematical hypotheses are indeterminate because they are relevantly similar to CH. (shrink)

In this paper, I pursue such a logical foundation for arithmetic in a variant of Zermelo set theory that has axioms of subset separation only for quantifier-free formulae, and according to which all sets are Dedekind finite. In section 2, I describe this variant theory, which I call ZFin0. And in section 3, I sketch foundations for arithmetic in ZFin0 and prove that certain foundational propositions that are theorems of the standard Zermelian foundation for arithmetic are independent of ZFin0.<br><br>An equivalent (...) theory of sets and an equivalent foundation for arithmetic was introduced by John Mayberry and developed by the current author in his doctoral thesis. In that thesis, the independence results mentioned above are proved using proof-theoretic methods. In this paper, I offer model-theoretic proofs of the central independence results using the technique of cumulation models, which was introduced by Steve Popham, a doctoral student of Mayberry<br>from the early 1980s. (shrink)

A bi-infinite approximate fixed point of type (n,k) is an approximate fixed point of type (n,k) whose terms are biinfinite; i.e., contain infin-itely many positive and infinitely many negative elements.

S. Adams, W. Ambrose, A. Andretta, H. Becker, R. Camerlo, C. Champetier, J.P.R. Christensen, D.E. Cohen, A. Connes. C. Dellacherie, R. Dougherty, R.H. Farrell, F. Feldman, A. Furman, D. Gaboriau, S. Gao, V. Ya. Golodets, P. Hahn, P. de la Harpe, G. Hjorth, S. Jackson, S. Kahane, A.S. Kechris, A. Louveau,, R. Lyons, P.-A. Meyer, C.C. Moore, M.G. Nadkarni, C. Nebbia, A.L.T. Patterson, U. Krengel, A.J. Kuntz, J.-P. Serre, S.D. Sinel'shchikov, T. Slaman, Solecki, R. Spatzier, J. Steel, D. Sullivan, S. (...) Thomas, A. Valette, V.S. Varadarajan, B. Velickovic, B. Weiss, J.D.M. Wright, R.J. Zimmer. (shrink)

Acceptable programming systems have many nice properties like s-m-n-Theorem, Composition and Kleene Recursion Theorem. Those properties are sometimes called control structures, to emphasize that they yield tools to implement programs in programming systems. It has been studied, among others by Riccardi and Royer, how these control structures influence or even characterize the notion of acceptable programming system. The following is an investigation, how these control structures behave in the more general setting of complete numberings as defined by Mal'cev and Eršov.

A Kripke-style semantics developed by de Jongh and Veltman is used to investigate relations between several extensions of interpretability logic, IL.

We prove independence results concerning the number of nonisomorphic models (using the S-chain condition and S-properness) and the consistency of "ZCF + 2 ℵ 0 = ℵ 2 + there is a universal linear order of power ℵ 1 ". Most of these results were announced in [Sh 4], [Sh 5]. In subsequent papers we shall prove an analog f MA for forcing which does not destroy stationary subsets of ω 1 , investigate D-properness for various filters and prove the (...) consistency with G.C.H. of an axiom implying SH (for ℵ 1 ), and connected results. (shrink)

Let NBG be von Neumann-Bernays-Gödel set theory without the axiom of choice and let NBGA be the modification which allows atoms. In this paper we consider some of the well-known class or global forms of the wellordering theorem, the axiom of choice, and maximal principles which are known to be equivalent in NBG and show they are not equivalent in NBGA.