We study the relative computational power of structures related to the ordered field of reals, specifically using the notion of generic Muchnik reducibility. We show that any expansion of the reals by a continuous function has no more computing power than the reals, answering a question of Igusa, Knight, and Schweber [7]. On the other hand, we show that there is a certain Borel expansion of the reals that is strictly more powerful than the reals and such that any Borel (...) quotient of the reals reduces to it. (shrink)

Let A be a standard transitive admissible set. Σ 1 -separation is the principle that whenever X and Y are disjoint Σ A 1 subsets of A then there is a Δ A 1 subset S of A such that $X \subseteq S$ and $Y \cap S = \varnothing$ . Theorem. If A satisfies Σ 1 -separation, then (1) If $\langle T_n\mid n is a sequence of trees on ω each of which has at most finitely many infinite paths in (...) A then the function $n\mapsto$ (set of infinite paths in A through T n ) is in A. (2) If A is not closed under hyperjump and α = On A then A has in it a nonstandard model of V = L whose ordinal standard part is α. Theorem. Let α be any countable admissible ordinal greater than ω. Then there is a model of Σ 1 -separation whose height is α. (shrink)

This paper sets out a predicative response to the Russell-Myhill paradox of propositions within the framework of Church’s intensional logic. A predicative response places restrictions on the full comprehension schema, which asserts that every formula determines a higher-order entity. In addition to motivating the restriction on the comprehension schema from intuitions about the stability of reference, this paper contains a consistency proof for the predicative response to the Russell-Myhill paradox. The models used to establish this consistency also model other axioms (...) of Church’s intensional logic that have been criticized by Parsons and Klement: this, it turns out, is due to resources which also permit an interpretation of a fragment of Gallin’s intensional logic. Finally, the relation between the predicative response to the Russell-Myhill paradox of propositions and the Russell paradox of sets is discussed, and it is shown that the predicative conception of set induced by this predicative intensional logic allows one to respond to the Wehmeier problem of many non-extensions. (shrink)

Frege's Grundgesetze was one of the 19th century forerunners to contemporary set theory which was plagued by the Russell paradox. In recent years, it has been shown that subsystems of the Grundgesetze formed by restricting the comprehension schema are consistent. One aim of this paper is to ascertain how much set theory can be developed within these consistent fragments of the Grundgesetze, and our main theorem shows that there is a model of a fragment of the Grundgesetze which defines a (...) model of all the axioms of Zermelo-Fraenkel set theory with the exception of the power set axiom. The proof of this result appeals to G\"odel's constructible universe of sets, which G\"odel famously used to show the relative consistency of the continuum hypothesis. More specifically, our proofs appeal to Kripke and Platek's idea of the projectum within the constructible universe as well as to a weak version of uniformization (which does not involve knowledge of Jensen's fine structure theory). The axioms of the Grundgesetze are examples of abstraction principles, and the other primary aim of this paper is to articulate a sufficient condition for the consistency of abstraction principles with limited amounts of comprehension. As an application, we resolve an analogue of the joint consistency problem in the predicative setting. (shrink)

In this paper we show how the assumption of the generalized continuum hypothesis (GCH) can be removed or partially removed from proofs in Zermelo-Frankel set theory (ZF) of statements expressible in the simple theory of types. We assume the reader is familiar with the latter language, especially with the classification of formulas and sentences of that language into Σκη and Πκη form (cf. [1]) and with how that language can be relatively interpreted into the language of ZF.

It is well known that the hypothesis that all real numbers are constructible in the sense of Gödel [1] implies the existence of a Σ21well-ordering of the Baire space [1, p. 67]. We are concerned with the converse to this theorem. From the assumption of the existence of a Σ21well-ordering with total domain, we derive various consequences which in the presence of a nonconstructible real seem highly pathological. However, while several of these consequences are obviously absurd, none have as yet (...) been disproven. Indeed some of the stranger consistency proofs of Jensen seem to indicate that there is a possibility that they may be consistent. I am referring to such results as existence of a model for ZF set theory in which the degrees of constructibility form a sequence of typeω+ 1 with the st degree being the only one which contains a nonconstructible real, and that degree being the degree of a Δ31nonconstructible real.In what follows we shall use the small Greek lettersα, β, γto range over the Baire spaceNNwhereNis the set of natural numbers. We assume that the reader is familiar with the use of trees to encode closed subsets of this space. The class Σ21is the collection of all those subsets of the Baire space which can be defined by a formula which is Σ21in a constructible parameter. Correspondingly Π21will be taken to mean Π11in a constructible parameter. The proof of the first lemma is left as an exercise. It involves nothing more than coding perfect sets by trees and then counting quantifiers. (shrink)

We present an introductory survey to first order logic for metric structures and its applications to C*-algebras.

In this paper we investigate strong logics of first and second order that have certain absoluteness properties. We begin with an investigation of first order logic and the strong logics ω-logic and β-logic, isolating two facets of absoluteness, namely, generic invariance and faithfulness. It turns out that absoluteness is relative in the sense that stronger background assumptions secure greater degrees of absoluteness. Our aim is to investigate the hierarchies of strong logics of first and second order that are generically invariant (...) and faithful against the backdrop of the strongest large cardinal hypotheses. We show that there is a close correspondence between the two hierarchies and we characterize the strongest logic in each hierarchy. On the first-order side, this leads to a new presentation of Woodin's Ω-logic. On the second-order side, we compare the strongest logic with full second-order logic and argue that the comparison lends support to Quine's claim that second-order logic is really set theory in sheep's clothing. (shrink)

In [3] F. P. Ramsey proved as a theorem of Zermelo-Fraenkel set theory (ZF) with the Axiom of Choice (AC) the following result:(1) Theorem. Let A be an infinite class. For each integer n and partition {X, Y} of the size n subsets of A, there exists an infinite subclass of A all of whose size n subsets are contained in only one of X or Y.

Azriel Levy did fundamental work in set theory when it was transmuting into a modern, sophisticated field of mathematics, a formative period of over a decade straddling Cohen’s 1963 founding of forcing. The terms “Levy collapse”, “Levy hierarchy”, and “Levy absoluteness” will live on in set theory, and his technique of relative constructibility and connections established between forcing and definability will continue to be basic to the subject. What follows is a detailed account and analysis of Levy’s work and contributions (...) to set theory. (shrink)

In “Models and Reality”, H. Putnam formulated his model-theoretic argument against “metaphysical realism”. The article proposes a meta-reconstruction of Putnam’s model-theoretic argument in the light of two mutually compatible interpretations of it–elaborated by Manuel Garcia-Carpintero and Igor van Douven. A critical reflection on these interpretations and their adequacy for Putnam’s argument allows us to expose new theses coherent with Putnam’s reasoning and indicate new paths to improve this argument for our reconstruction task. In particular, we show that Putnam’s position may (...) be coherent with van Douven’s versions of Global Descriptivism under some conditions, but Putnam cannot reject realism as quickly as Carpintero suggests. We show that Suszko’s canonic axiomatic system and Sneed’s concept of theory may provide valuable support for Putnam’s argument. Finally, we critically evaluate Carpintero’s theses about the genesis of unintended interpretations of our languages, adopting the machinery of the Upward Skolem–Loewenheim Theorem and Knight’s Theorem. (shrink)

Assuming $\underset{\sim}{\Pi}^1_2$ determinacy, the model L[ T 2 ] does not depend on the choice of T 2.

For a canonical model of set theory whose projective theory of the real numbers is stable under set forcing extensions, a set of reals of minimal complexity is constructed which fails to be universally Baire. The construction uses a general method for generating non-universally Baire sets via the Levy collapse of a cardinal, as well as core model techniques. Along the way it is shown (extending previous results of Steel) how sufficiently iterable fine structure models recognize themselves as global core (...) models. (shrink)

Shoenfield [8] has shown that a hierarchy for the functions recursive in a type-2 object can be set up whenever E2 (the type-2 object that introduces numerical quantification) is recursive in that type-2 object. With a restriction that we will discuss in the next paragraph, Moschovakis [4, pp. 254–259] has solved the analogous problem for type-3 objects. His method seems to generalize for any type-n object, where n ≥ 2. We will solve this same problem of finding hierarchies based on (...) type-n objects by a different method. Instead of using ordinal notations for indexing stages of hierarchies, as do Shoenfield and Moschovakis, we will define notation-independent stages. (shrink)

It was questions about points on the real line that initiated the study of set theory. Points paved the way to point sets and these to ever more abstract sets. And there was more: Reflection on structural properties of point sets not only initiated the study of ordinary sets; it also supplied blueprints for defining extra-ordinary, “large” sets, transcending those provided by standard set theory. In return, the existence of such large sets turned out critical to settling open conjectures about (...) point sets.How to explain such action at a distance between the very large and the rather small? Rather than having an air of magic, could these results rest on deep structural similarities between the two superficially distant species of sets?In this essay I dissect one group of such two-way results. Their linchpin is the notion of measure.§1. Vitali's impossibility result. Our starting point is a problem in measure theory regarding the notion of “Lebesgue measure.” Before presenting the problem, I would like to review the notion of Lebesgue measure. Rather than listing its main properties, I would like to show how Lebesgue measure is born out of an attempt to generalize the notion of the length of an interval to arbitrary sets of reals. One tries to approximate arbitrary sets of reals by intervals, in the hope that the lengths of the intervals will induce a measure on these sets. (shrink)