Locally finite omega languages were introduced by Ressayre [Formal languages defined by the underlying structure of their words. J Symb Log 53(4):1009–1026, 1988]. These languages are defined by local sentences and extend ω-languages accepted by Büchi automata or defined by monadic second order sentences. We investigate their topological complexity. All locally finite ω-languages are analytic sets, the class LOC ω of locally finite ω-languages meets all finite levels of the Borel hierarchy and there exist some locally finite ω-languages which are (...) Borel sets of infinite rank or even analytic but non-Borel sets. This gives partial answers to questions of Simonnet (Automates et Théorie Descriptive, Ph.D. Thesis. Université Paris 7, March 1992) and of Duparc et al. [Computer science and the fine structure of Borel sets. Theor Comput Sci 257(1–2):85–105, 2001]. (shrink)

The topological arithmetical hierarchy is the effective version of the Borel hierarchy. Its class Δta 2 is just large enough to include several types of pointsets in Euclidean spaces ℝ k which are fundamental in computable analysis. As a crossbreed of Hausdorff's difference hierarchy in the Borel class ΔB 2 and Ershov's hierarchy in the class Δ0 2 of the arithmetical hierarchy, the Hausdorff-Ershov hierarchy introduced in this paper gives a powerful classification within Δta 2. This is based on suitable (...) characterizations of the sets from Δta 2 which are obtained in a close analogy to those of the ΔB 2 sets as well as those of the Δ0 2 sets. A helpful tool in dealing with resolvable sets is contributed by the technique of depth analysis. On this basis, the hierarchy properties, in particular the strict inclusions between classes of different levels, can be shown by direct constructions of witness sets. The Hausdorff-Ershov hierarchy runs properly over all constructive ordinals, in contrast to Ershov's hierarchy whose denotation-independent version collapses at level ω 2. Also, some new characterizations of concepts of decidability for pointsets in Euclidean spaces are presented. (shrink)

The Infinite Time Turing Machine model [8] of Hamkins and Kidder is, in an essential sense, a "Σ₂-machine" in that it uses a Σ₂ Liminf Rule to determine cell values at limit stages of time. We give a generalisation of these machines with an appropriate Σ n rule. Such machines either halt or enter an infinite loop by stage ζ(n) = df μζ(n)[∃Σ(n) > ζ(n) L ζ(n) ≺ Σn L Σ(n) ], again generalising precisely the ITTM case. The collection of (...) such machines taken together computes precisely those reals of the least model of analysis. (shrink)

We consider ω n -automatic structures which are relational structures whose domain and relations are accepted by automata reading ordinal words of length ω n for some integer n ≥ 1. We show that all these structures are ω-tree-automatic structures presentable by Muller or Rabin tree automata. We prove that the isomorphism relation for ω 2 -automatic (resp. ω n -automatic for n > 2) boolean algebras (respectively, partial orders, rings, commutative rings, non commutative rings, non commutative groups) is not (...) determined by the axiomatic system ZFC. We infer from the proof of the above result that the isomorphism problem for ω n -automatic boolean algebras, n ≥ 2, (respectively, rings, commutative rings, non commutative rings, non commutative groups) is neither a ${\mathrm{\Sigma }}_{2}^{1}-\mathrm{s}\mathrm{e}\mathrm{t}$ nor a ${\mathrm{\Pi }}_{2}^{1}-\mathrm{s}\mathrm{e}\mathrm{t}$ . We obtain that there exist infinitely many ω n -automatic, hence also ω-tree-automatic, atomless boolean algebras $\mathcal{B}_{n}$ , n ≥ 1, which are pairwise isomorphic under the continuum hypothesis CH and pairwise non isomorphic under an alternate axiom AT, strengthening a result of [14]. (shrink)

Let E be a coanalytic equivalence relation on a Polish space X and (A n ) n∈ω a sequence of analytic subsets of X. We prove that if lim sup n∈K A n meets uncountably many E-equivalence classes for every K ∈ [ω] ω , then there exists a K ∈ [ω] ω such that ⋂ n∈K A n contains a perfect set of pairwise E-inequivalent elements.

The research presented in this paper was motivated by our aim to study a problem due to J. Bourgain [3]. The problem in question concerns the uniform boundedness of the classical separation rank of the elements of a separable compact set of the first Baire class. In the sequel we shall refer to these sets (separable or non-separable) as Rosenthal compacta and we shall denote by ∝(f) the separation rank of a real-valued functionfinB1(X), withXa Polish space. Notice that in [3], (...) Bourgain has provided a positive answer to this problem in the case ofKsatisfyingwithXa compact metric space. The key ingredient in Bourgain's approach is that whenever a sequence of continuous functions pointwise converges to a functionf, then the possible discontinuities of the limit function reflect a local ℓ1-structure to the sequence (fn)n. More precisely the complexity of this ℓ1-structure increases as the complexity of the discontinuities offdoes. This fruitful idea was extensively studied by several authors (c.f. [5], [7], [8]) and for an exposition of the related results we refer to [1]. It is worth mentioning that A.S. Kechris and A. Louveau have invented the rank rND(f) which permits the link between thec0-structure of a sequence (fn)nof uniformly bounded continuous functions and the discontinuities of its pointwise limit. Rosenthal'sc0-theorem [11] and thec0-index theorem [2] are consequences of this interaction.Passing to the case where either (fn)nare not continuous orXis a non-compact Polish space, this nice interaction is completely lost. (shrink)

Using possibly infinite computations on universal monotone Turing machines, we prove Martin-Löf randomness in ∅' of the probability that the output be in some set.

We improve results of Marczewski, Frankiewicz, Brown, and others comparing the σ-ideals of measure zero, meager, Marczewski measure zero, and completely Ramsey null sets; in particular, we remove CH from the hypothesis of many of Brown's constructions of sets lying in some of these ideals but not in others. We improve upon work of Marczewski by constructing, without CH, a nonmeasurable Marczewski measure zero set lacking the property of Baire. We extend our analysis of σ-ideals to include the completely Ramsey (...) null sets relative to a Ramsey ultrafilter and obtain all 32 possible examples of sets in some ideals and not others, some under the assumption of MA, but most in ZFC alone. We also improve upon the known constructions of a Marczewski measure zero set which is not Ramsey by using a set theoretic hypothesis which is weaker than those used by other authors. We give several consistency proofs: one concerning the relative sizes of the covering numbers for the meager sets and the completely Ramsey null sets; another concerning the size of non(CRU 0); and a third concerning the size of add(CRU 0). We also study those classes of perfect sets which are bases for the class of always first category sets. (shrink)

§0. Preface. There has been an expectation that the endgame of the more tenacious problems raised by the Los Angeles ‘cabal’ school of descriptive set theory in the 1970's should ultimately be played out with the use of inner model theory. Questions phrased in the language of descriptive set theory, where both the conclusions and the assumptions are couched in terms that only mention simply definable sets of reals, and which have proved resistant to purely descriptive set theoretic arguments, may (...) at last find their solution through the connection between determinacy and large cardinals.Perhaps the most striking example was given by [24], where the core model theory was used to analyze the structure of HOD and then show that all regular cardinals below ΘL are measurable. John Steel's analysis also settled a number of structural questions regarding HODL, such as GCH.Another illustration is provided by [21]. There an application of large cardinals and inner model theory is used to generalize the Harrington-Martin theorem that determinacy implies )determinacy.However, it is harder to find examples of theorems regarding the structure of the projective sets whose only known proof from determinacy assumptions uses the link between determinacy and large cardinals. We may equivalently ask whether there are second order statements of number theory that cannot be proved under PD–the axiom of projective determinacy–without appealing to the large cardinal consequences of the PD, such as the existence of certain kinds of inner models that contain given types of large cardinals. (shrink)

We improve results of Marczewski, Frankiewicz, Brown, and others comparing the $\sigma$-ideals of measure zero, meager, Marczewski measure zero, and completely Ramsey null sets; in particular, we remove CH from the hypothesis of many of Brown's constructions of sets lying in some of these ideals but not in others. We improve upon work of Marczewski by constructing, without CH, a nonmeasurable Marczewski measure zero set lacking the property of Baire. We extend our analysis of $\sigma$-ideals to include the completely Ramsey (...) null sets relative to a Ramsey ultrafilter and obtain all 32 possible examples of sets in some ideals and not others, some under the assumption of MA, but most in ZFC alone. We also improve upon the known constructions of a Marczewski measure zero set which is not Ramsey by using a set theoretic hypothesis which is weaker than those used by other authors. We give several consistency proofs: one concerning the relative sizes of the covering numbers for the meager sets and the completely Ramsey null sets; another concerning the size of non; and a third concerning the size of add$. We also study those classes of perfect sets which are bases for the class of always first category sets. (shrink)

The basic purpose of this essay, the first of an intended pair, is to interpret standard von Neumann quantum theory in a framework of iterated measure algebraic truth for mathematical (and thus mathematical-physical) assertions — a framework, that is, in which the truth-values for such assertions are elements of iterated boolean measure-algebras (cf. Sections 2.2.9, 5.2.1–5.2.6 and 5.3 below).The essay itself employs constructions of Takeuti's boolean-valued analysis (whose origins lay in work of Scott, Solovay, Krauss and others) to provide a (...) metamathematical interpretation of ideas sometimes considered disparate, heuristic, or simply ill-defined: the collapse of the wave function, for example; Everett's many worlds'-construal of quantum measurement; and a natural product space of contextual (nonlocal) hidden variables. (shrink)

We show that every analytic filter is generated by a Π 0 2 prefilter, every Σ 0 2 filter is generated by a Π 0 1 prefilter, and if $P \subseteq \mathscr{P}(\omega)$ is a Σ 0 2 prefilter then the filter generated by it is also Σ 0 2 . The last result is unique for the Borel classes, as there is a Π 0 2 -complete prefilter P such that the filter generated by it is Σ 1 1 -complete. (...) Also, no complete coanalytic filter is generated by an analytic prefilter. The proofs use König's infinity lemma, a normal form theorem for monotone analytic sets, and Wadge reductions. (shrink)

We consider fine hierarchies in recursion theory, descriptive set theory, logic and complexity theory. The main results state that the sets of values of different Boolean terms coincide with the levels of suitable fine hierarchies. This gives new short descriptions of these hierarchies and shows that collections of sets of values of Boolean terms are almost well ordered by inclusion. For the sake of completeness we mention also some earlier results demonstrating the usefulness of fine hierarchies.

We develop a variant of Least Fixed Point logic based on First Orderlogic with a relaxed version of guarded quantification. We develop aGame Theoretic Semantics of this logic, and find that under reasonableconditions, guarding quantification does not reduce the expressibilityof Least Fixed Point logic. But we also find that the guarded version ofa least fixed point algorithm may have a greater time complexity thanthe unguarded version, by a linear factor.

Maddy's notion of restrictiveness has many problematic aspects, one of them being that it is almost impossible to show that a theory is not restrictive. In this note the author addresses a crucial question of Martin Goldstern (Vienna) and points to some directions of future research.

For countable structures U and B, let $\mathfrak{U}\overset{\alpha}{\rightarrow}\mathfrak{B}$ abbreviate the statement that every Σ0 α (Lω1,ω) sentence true in U also holds in B. One can define a back and forth game between the structures U and B that determines whether $\mathfrak{U}\overset{\alpha}{\rightarrow}\mathfrak{B}$ . We verify that if θ is an Lω,ω sentence that is not equivalent to any Lω,ω Σ0 n sentence, then there are countably infinite models U and B such that $\mathfrak{U} \vDash \theta, \mathfrak{B} \vDash \neg \theta$ , (...) and $\mathfrak{U}\overset{n}{\rightarrow}\mathfrak{B}$ . For countable languages L there is a natural way to view L structures with universe ω as a topological space, XL. Let [U] = {B ∈ XL∣B ≅ U} denote the isomorphism class of U. Let U and B be countably infinite nonisomorphic L structures, and let $C \subseteq \omega^\omega$ be any Π0 α subset. Our main result states that if $\mathfrak{U}\overset{\alpha}{\rightarrow}\mathfrak{B}$ , then there is a continuous function f: ωω → XL with the property that $x \in C \Rightarrow f(x) \in \lbrack\mathfrak{U}\rbrack$ and $x \notin C \Rightarrow f(x) \in \lbrack\mathfrak{B}\rbrack$ . In fact, for α ≤ 3, the continuous function f can be defined from the $\overset{\alpha}{\rightarrow}$ relation. (shrink)

LetXbe a standard Borel space, and letEbe acountableBorel equivalence relation onX, i.e., a Borel equivalence relationEfor which every equivalence class [x]Eis countable. By a result of Feldman-Moore [FM],Eis induced by the orbits of a Borel action of a countable groupGonX.The structure of general countable Borel equivalence relations is very little understood. However, a lot is known for the particularly important subclass consisting of hyperfinite relations. A countable Borel equivalence relation is calledhyperfiniteif it is induced by a Borel ℤ-action, i.e., by (...) the orbits of a single Borel automorphism. Such relations are studied and classified in [DJK]. It is shown in Ornstein-Weiss [OW] and Connes-Feldman-Weiss [CFW] that for every Borel equivalence relationEinduced by a Borel action of a countable amenable groupGonXand for every probability measure μ onX, there is a Borel invariant setY⊆Xwith μ = 1 such thatE↾Y is hyperfinite. Motivated by this result, Weiss [W2] raised the question of whether everyEinduced by a Borel action of a countable amenable group is hyperfinite. Later on Weiss showed that this is true forG= ℤn. However, the problem is still open even for abelianG. Our main purpose here is to provide a weaker affirmative answer for general amenableG. We need a definition first. Given two standard Borel spacesX, Y, auniversally measurableisomorphism betweenXandYis a bijection ƒ:X→Ysuch that both ƒ, ƒ-1are universally measurable. Notice now that to assert that a countable Borel equivalence relation onXis hyperfinite is trivially equivalent to saying that there is a standard Borel spaceYand a hyperfinite Borel equivalence relationFonY, which isBorelisomorphic toE, i.e., there is a Borel bijection ƒ:X→YwithxEy⇔ ƒFƒ. We have the following theorem. (shrink)

First-order Gödel logics are a family of finite- or infinite-valued logics where the sets of truth values V are closed subsets of [0,1] containing both 0 and 1. Different such sets V in general determine different Gödel logics GV (sets of those formulas which evaluate to 1 in every interpretation into V). It is shown that GV is axiomatizable iff V is finite, V is uncountable with 0 isolated in V, or every neighborhood of 0 in V is uncountable. Complete (...) axiomatizations for each of these cases are given. The r.e. prenex, negation-free, and existential fragments of all first-order Gödel logics are also characterized. (shrink)

The study of continuous group actions is ubiquitous in mathematics, and perhaps the most general kinds of actions for which we can hope to prove theorems in just ZFC are those where a Polish group acts on a Polish space.For this general class we can find works such as [29] that build on ideas from ergodic theory and examine actions of locally compact groups in both the measure theoretic and topological contexts. On the other hand a text in model theory, (...) such as [12], will typically consider issues bearing on the actions by the symmetric group of all permutations of the integers. More generally [1] shows that the orbit equivalence relations induced by closed subgroups of the infinite symmetric group can be reduced to the isomorphism relation on corresponding classes of countable models.This paper considers a third category formed by the continuous actions of separable Banach spaces on Polish spaces. These examples cannot be subsumed under the two earlier headings, and it is known from [10] that theBorel cardinalitiesof the quotient spaces that arise from such actions are incomparable with the equivalence relations induced by the symmetric group or any locally compact Polish group action.One of the first things to be addressed concerns the complexity of these equivalence relations. This question forappears in [1]. (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)

We characterize, in terms of determinacy, the existence of 0 ♯♯ as well as the existence of each of the following: 0 ♯♯♯ , 0 ♯♯♯♯ ,0 ♯♯♯♯♯ , .... For k ∈ ω, we define two classes of sets, (k * Σ 0 1 ) * and (k * Σ 0 1 ) * + , which lie strictly between $\bigcup_{\beta and Δ(ω 2 -Π 1 1 ). We also define 0 1♯ as 0 ♯ and in general, 0 (...) (k + 1)♯ as (0 k♯) ♯ . We then show that the existence of 0 (k + 1)♯ is equivalent to the determinacy of ((k + 1) * Σ 0 1 ) * as well as the determinacy of (k * Σ 0 1 ) * +. (shrink)

We consider fixed point logics, i.e., extensions of first order predicate logic with operators defining fixed points. A number of such operators, generalizing inductive definitions, have been studied in the context of finite model theory, including nondeterministic and alternating operators. We review results established in finite model theory, and also consider the expressive power of the resulting logics on infinite structures. In particular, we establish the relationship between inflationary and nondeterministic fixed point logics and second order logic, and we consider (...) questions related to the determinacy of games associated with alternating fixed points. (shrink)

Before one can construct scales of minimal complexity in the Real Core Model, K(R), one needs to develop the fine-structure theory of K(R). In this paper, the fine structure theory of mice, first introduced by Dodd and Jensen, is generalized to that of real mice. A relative criterion for mouse iterability is presented together with two theorems concerning the definability of this criterion. The proof of the first theorem requires only fine structure; whereas, the second theorem applies to real mice (...) satisfying AD and follows from a general definability result obtained by abstracting work of John Steel on L(R). In conclusion, we discuss several consequences of the work presented in this paper relevant to two issues: the complexity of scales in K(R) and the strength of the theory ZF + AD + ¬ DC R. (shrink)

Let J be any proper ideal of subsets of the real line R which contains all finite subsets of R. We define an ideal J * ∣B as follows: X ∈ J * ∣B if there exists a Borel set $B \subset R \times R$ such that $X \subset B$ and for any x ∈ R we have $\{y \in R: \langle x,y\rangle \in B\} \in \mathscr{J}$ . We show that there exists a family $\mathscr{A} \subset \mathscr{J}^\ast\mid\mathscr{B}$ of power ω (...) 1 such that $\bigcup\mathscr{A} \not\in \mathscr{J}^\ast\mid\mathscr{B}$ . In the last section we investigate properties of ideals of Lebesgue measure zero sets and meager sets in Cohen extensions of models of set theory. (shrink)

The choice construct (choose x: φ(x)) is useful in software specifications. We study extensions of first-order logic with the choice construct. We prove some results about Hilbert's ε operator, but in the main part of the paper we consider the case when all choices are independent.

The consistency of a second-order version of Morley’s Theorem on the number of countable models was proved in [EHMT23] with the aid of large cardinals. We here dispense with them.

We isolate two abstract determinacy theorems for games of length $\omega_1$ from work of Neeman and use them to conclude, from large-cardinal assumptions and an iterability hypothesis in the region of measurable Woodin cardinals thatif the Continuum Hypothesis holds, then all games of length $\omega_1$ which are provably $\Delta_1$ -definable from a universally Baire parameter are determined;all games of length $\omega_1$ with payoff constructible relative to the play are determined; andif the Continuum Hypothesis holds, then there is a model of (...) ${\mathsf{ZFC}}$ containing all reals in which all games of length $\omega_1$ definable from real and ordinal parameters are determined. (shrink)

We prove a number of results on the determinacy of σ-projective sets of reals, i.e., those belonging to the smallest pointclass containing the open sets and closed under complements, countable unions, and projections. We first prove the equivalence between σ-projective determinacy and the determinacy of certain classes of games of variable length <ω^2 (Theorem 2.4). We then give an elementary proof of the determinacy of σ-projective sets from optimal large-cardinal hypotheses (Theorem 4.4). Finally, we show how to generalize the proof (...) to obtain proofs of the determinacy of σ-projective games of a given countable length and of games with payoff in the smallest σ-algebra containing the projective sets, from corresponding assumptions (Theorem 5.1, Theorem 5.4). (shrink)

Penelope Maddy has recently addressed the set-theoretic multiverse, and expressed reservations on its status and merits ([Maddy, 2017]). The purpose of the paper is to examine her concerns, by using the interpretative framework of set-theoretic naturalism. I first distinguish three main forms of 'multiversism', and then I proceed to analyse Maddy's concerns. Among other things, I take into account salient aspects of multiverse-related mathematics , in particular, research programmes in set theory for which the use of the multiverse seems to (...) be crucial, and show how one may provide responses to Maddy's concerns based on a careful analysis of 'multiverse practice'. (shrink)

Developing an analogue of Solovay reducibility in the higher recursion setting, we show that results from the classical computably enumerable case can be extended to the new context.

We show that the Axiom of Dependent Choice,, holds in countably iterable, passive premice constructed over their reals which satisfy the Axiom of Determinacy,, in a background universe. This generalizes an argument of Kechris for using Steel's analysis of scales in mice. In particular, we show that for any and any countable set of reals A so that and, we have that.

In this paper we give a proof of the II12-completeness of the set of countable better quasi orderings . This result was conjectured by Clote in [2] and proved by the author in his Ph.d. thesis [6] . Here we prove it using Simpson's definition of better quasi ordering and as little bqo theory as possible.

We give a fairly complete account which first shows that the solution to the inner model problem for one supercompact cardinal will yield an ultimate version ofLand then shows that the various current approaches to inner model theory must be fundamentally altered to provide that solution.

We extend in a natural way the operation of Turing machines to infinite ordinal time, and investigate the resulting supertask theory of computability and decidability on the reals. Everyset. for example, is decidable by such machines, and the semi-decidable sets form a portion of thesets. Our oracle concept leads to a notion of relative computability for sets of reals and a rich degree structure, stratified by two natural jump operators.

Though many working mathematicians embrace a rough and ready form of Platonism, that venerable position has suffered a checkered philosophical career. Indeed the three schools of thought with which most of us began our official philosophizing about mathematics—Intuitionism, Formalism, and Logicism—all stand in fundamental disagreement with Platonism. Nevertheless, various versions of Platonistic thinking survive in contemporary philosophical circles. The aim of this paper is to describe these views, and, as my title suggests, to trace their roots.I'll begin with some preliminary (...) remarks about the big three schools. This seems a reasonable approach to the issues both because most observers are familiar, at least in a general way, with the tenets of Intuitionism, Formalism, and Logicism, and because it is in reaction to these that contemporary Platonism has taken shape. (shrink)

In this paper we shall answer some questions in the set theory of L, the universe of all sets constructible from the reals. In order to do so, we shall assume ADL, the hypothesis that all 2-person games of perfect information on ω whose payoff set is in L are determined. This is by now standard practice. ZFC itself decides few questions in the set theory of L, and for reasons we cannot discuss here, ZFC + ADL yields the most (...) interesting “completion” of the ZFC-theory of L.ADL implies that L satisfies “every wellordered set of reals is countable”, so that the axiom of choice fails in L. Nevertheless, there is a natural inner model of L, namely HODL, which satisfies ZFC.. The superscript “L” indicates, here and below, that the notion in question is to be interpreted in L.) HODL is reasonably close to the full L, in ways we shall make precise in § 1. The most important of the questions we shall answer concern HODL: what is its first order theory, and in particular, does it satisfy GCH?These questions first drew attention in the 70's and early 80's. (shrink)

A pervasive thought in contemporary philosophy of mathematics is that in order to justify reflection principles, one must hold universism: the view that there is a single universe of pure sets. I challenge this kind of reasoning by contrasting universism with a Zermelian form of multiversism. I argue that if extant justifications of reflection principles using notions of richness are acceptable for the universist, then the Zermelian can use similar justifications. However, I note that for some forms of richness argument, (...) the status of reflection principles as axioms is left open for the Zermelian. (shrink)

The formalist philosophy of mathematics (in its purest, most extreme version) is widely regarded as a “discredited position”. This pure and extreme version of formalism is called by some authors “game formalism”, because it is alleged to represent mathematics as a meaningless game with strings of symbols. Nevertheless, I would like to draw attention to some arguments in favour of game formalism as an appropriate philosophy of real mathematics. For the most part, these arguments have not yet been used or (...) were neglected in past discussions. (shrink)

It is a commonplace of set theory to say that there is no set of all well-orderings nor a set of all sets. We are implored to accept this due to the threat of paradox and the ensuing descent into unintelligibility. In the absence of promising alternatives, we tend to take up a conservative stance and tow the line: there is no universe. In this paper, I am going to challenge this claim by taking seriously the idea that we can (...) talk about the collection of all the sets and many more collections beyond that. A method of articulating this idea is offered through an indefinitely extending hierarchy of set theories. It is argued that this approach provides a natural extension to ordinary set theory and leaves ordinary mathematical practice untouched. (shrink)

The pluralist sheds the more traditional ideas of truth and ontology. This is dangerous, because it threatens instability of the theory. To lend stability to his philosophy, the pluralist trades truth and ontology for rigour and other ‘fixtures’. Fixtures are the steady goal posts. They are the parts of a theory that stay fixed across a pair of theories, and allow us to make translations and comparisons. They can ultimately be moved, but we tend to keep them fixed temporarily. Apart (...) from considering rigour of proof as a fixture, I discuss fixed models, invariant notions and fixed information about objects across theories. There are other fixtures, but it is enough to start with these. (shrink)

The study of Borel equivalence relations under Borel reducibility has developed into an important area of descriptive set theory. The dichotomies of Silver [20] and Harrington, Kechris and Louveau [6] show that with respect to Borel reducibility, any Borel equivalence relation strictly above equality on ω is above equality on , the power set of ω, and any Borel equivalence relation strictly above equality on the reals is above equality modulo finite on . In this article we examine the effective (...) content of these and related results by studying effectively Borel equivalence relations under effectively Borel reducibility. The resulting structure is complex, even for equivalence relations with finitely many equivalence classes. However use of Kleene’s O as a parameter is sufficient to restore the picture from the noneffective setting. A key lemma is that of the existence of two effectively Borel sets of reals, neither of which contains the range of the other under any effectively Borel function; the proof of this result applies Barwise compactness to a deep theorem of Harrington establishing for any recursive ordinal α the existence of singletons whose α-jumps are Turing incomparable. (shrink)