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 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)

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)

. Remarkably, despite the tremendous success of axiomatic set-theory in mathematics, logic and meta-mathematics, e.g., model-theory, two philosophical worries about axiomatic set-theory as the adequate catch of the set-concept keep haunting it. Having dealt with one worry in a previous paper in this journal, we now fulfil a promise made there, namely to deal with the second worry. The second worry is the Skolem Paradox and its ensuing Skolemite skepticism. We present a comparatively novel and simple analysis of the argument (...) of the Skolemite skeptic, which will reveal a general assumption concerning the meaning of the set-concept (we call it Connexion M). We argue that the Skolemite skeptics argument is a petitio principii and that consequently we find ourselves in a dialectical situation of stalemate.Few (if any) working set-theoreticians feel a tension – let alone see a paradox – between, on the one hand, what the Löwenheim–Skolem theorems and related results seem to be telling us about the set-concept, and, on the other hand, their uncompromising and successful use of the set-concept and their continuing enthusiasm about it, in other words: their lack of skepticism about the set-concept. Further, most (if not all) working settheoreticians have a relaxed attitude towards the ubiquitous undecidability phenomenon in set-theory, rather than a worrying one. We argue these are genuine philosophical problems about the practice of set-theory. We propound solutions, which crucially involve a renunciation of Connexion M. This breaks the dialectical situation of stalemate against the Skolemite skeptic. (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)

From the hypothesis that all Turing closed games are determined we prove: (1) the Continuum Hypothesis and (2) every subset of ℵ1 is constructible from a real.

We show that the members of a certain class of semi-proper iterations do not add countable sets of ordinals. As a result, starting from suitable large cardinals one can obtain a model in which the Continuum Hypothesis holds and every function from ω1 to ω1 is bounded on a club by a canonical function for an ordinal less than ω2.

Let ξ ≥ 1 be a countable ordinal. We study the Borel subsets of the plane that can be made [Formula: see text] by refining the Polish topology on the real line. These sets are called potentially [Formula: see text]. We give a Hurewicz-like test to recognize potentially [Formula: see text] sets.

A lattice L is coordinatizable, if it is isomorphic to the lattice L of principal right ideals of some von Neumann regular ring R. This forces L to be complemented modular. All known sufficient conditions for coordinatizability, due first to von Neumann, then to Jónsson, are first-order. Nevertheless, we prove that coordinatizability of lattices is not first-order, by finding a non-coordinatizable lattice K with a coordinatizable countable elementary extension L. This solves a 1960 problem of Jónsson. We also prove that (...) there is no [Formula: see text] statement equivalent to coordinatizability. Furthermore, the class of coordinatizable lattices is not closed under countable directed unions; this solves another problem of Jónsson from 1962. (shrink)

We carry out a systematic study of decidability for theories of real vector spaces, inner product spaces, and Hilbert spaces and of normed spaces, Banach spaces and metric spaces, all formalized using a 2-sorted first-order language. The theories for list turn out to be decidable while the theories for list are not even arithmetical: the theory of 2-dimensional Banach spaces, for example, has the same many-one degree as the set of truths of second-order arithmetic.We find that the purely universal and (...) purely existential fragments of the theory of normed spaces are decidable, as is the ∀∃ fragment of the theory of metric spaces. These results are sharp of their type: reductions of Hilbertʼs 10th problem show that the ∃∀ fragments for metric and normed spaces and the ∀∃ fragment for normed spaces are all undecidable. (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 present game-theoretic characterizations of the complexity/expressibility measures “dimension” and “the number of variables” as Least Fixed Point queries. As an example, we use these characterizations to compute the dimension and number of variables of Connectivity and Connectivity.

We give a simple game-theoretic proof of Silver's theorem that every analytic set is Ramsey. A set P of subsets of ω is called Ramsey if there exists an infinite set H such that either all infinite subsets of H are in P or all out of P. Our proof clarifies a strong connection between the Ramsey property of partitions and the determinacy of infinite games.

This paper is an attempt to convince anti-realists that their correct intuitions against the metaphysical inflationism derived from some versions of mathematical realism do not force them to embrace non-standard, epistemic approaches to truth and existence. It is also an attempt to convince mathematical realists that they do not need to implement their perfectly sound and judicious intuitions with the anti-intuitive developments that render full-blown mathematical realism into a view which even Gödel considered objectionable. I will argue for the following (...) two theses: that realism, in its standard characterization, is our default position, a position in agreement with our pre-theoretical intuitions and with the results of our best semantic theories, and that most of the metaphysical qualms usually related to it depends on a poor understanding of truth and existence as higher-order concepts. (shrink)

A nontrivial ring with unit eliminates imaginaries just in case its complete theory has the following property: every definable m-ary equivalence relation E may be defined by a formula f = f, where f is an m-ary definable function. We show that for certain natural expansions of the field of p-adic numbers, elimination of imaginaries fails or is independent of ZPC. Similar results hold for certain fields of formal power series.

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.

The interaction between large cardinals, determinacy of two-person perfect information games, and inner model theory has been a singularly powerful driving force in modern set theory during the last three decades. For the outsider the intellectual excitement is often tempered by the somewhat daunting technicalities, and the seeming length of study needed to understand the flow of ideas. The purpose of this article is to try and give a short, albeit rather rough, guide to the broad lines of development.

It is known that infinitely many Medvedev degrees exist inside the Muchnik degree of any nontrivial Π10 subset of Cantor space. We shed light on the fine structures inside these Muchnik degrees related to learnability and piecewise computability. As for nonempty Π10 subsets of Cantor space, we show the existence of a finite-Δ20-piecewise degree containing infinitely many finite-2-piecewise degrees, and a finite-2-piecewise degree containing infinitely many finite-Δ20-piecewise degrees 2 denotes the difference of two Πn0 sets), whereas the greatest degrees in (...) these three “finite-Γ-piecewise” degree structures coincide. Moreover, as for nonempty Π10 subsets of Cantor space, we also show that every nonzero finite-2-piecewise degree includes infinitely many Medvedev degrees, every nonzero countable-Δ20-piecewise degree includes infinitely many finite-piecewise degrees, every nonzero finite-2-countable-Δ20-piecewise degree includes infinitely many countable-Δ20-piecewise degrees, and every nonzero Muchnik degree includes infinitely many finite-2-countable-Δ20-piecewise degrees. Indeed, we show that any nonzero Medvedev degree and nonzero countable-Δ20-piecewise degree of a nonempty Π10 subset of Cantor space have the strong anticupping properties. Finally, we obtain an elementary difference between the Medvedev degree structure and the finite-Γ-piecewise degree structure of all subsets of Baire space by showing that none of the finite-Γ-piecewise structures is Brouwerian, where Γ is any of the Wadge classes mentioned above. (shrink)

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)

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.

Local sentences and the formal languages they define were introduced by Ressayre in. We prove that locally finite ω‐languages and effective analytic sets have the same topological complexity: the Borel and Wadge hierarchies of the class of locally finite ω‐languages are equal to the Borel and Wadge hierarchies of the class of effective analytic sets. In particular, for each non‐null recursive ordinal there exist some ‐complete and some ‐complete locally finite ω‐languages, and the supremum of the set of Borel ranks (...) of locally finite ω‐languages is the ordinal, which is strictly greater than the first non‐recursive ordinal. This gives an answer to the question of the topological complexity of locally finite ω‐languages, which was asked by Simonnet and also by Duparc, Finkel, and Ressayre in. Moreover we show that the topological complexity of a locally finite ω‐language defined by a local sentence φ may depend on the models of the Zermelo‐Fraenkel axiomatic system. Using similar constructions as in the proof of the above results we also show that the equivalence, the inclusion, and the universality problems for locally finite ω‐languages are ‐complete, hence highly undecidable. (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.

We prove that a Borel subset of the product of two internal setsX andY all of whoseY-sections are ∏ 1 0 (K)(∑ 1 0 (K)) sets is the intersection (union) of a countable sequence of Borel graphs with internalY-sections. As a consequence we prove some standard results about the domains of graphs in the product of two topological spaces all of whose horizontal section are compact (open) sets. A version of classical Vitali-Lusin theorem for those types of graphs is given (...) as well as a new proof (and an extension) of a classical result of Kunugui. (shrink)

We consider morphisms between binary relations that are used in the theory of cardinal characteristics. In [8] we have shown that there are pairs of relations with no Borel morphism connecting them. The reason was a strong impact of the first of the two functions that constitute a morphism, the so-called function on the questions. In this work we investigate whether the second half, the function on the answers' side, has a similarly strong impact. The main question is: Does the (...) nonexistence of a Borel morphism imply the non-existence of a morphism that is only Borel on the answers' side? We give sufficient conditions for an affirmative answer. The results are applied to the unsplitting relations where it has been open whether there is a morphism that is Borel on the answers' side. (shrink)

In intuitionistic analysis, a subset of a Polish space like or is called positively Borel if and only if it is an open subset of the space or a closed subset of the space or the result of forming either the countable union or the countable intersection of an infinite sequence of (earlier constructed) positively Borel subsets of the space. The operation of taking the complement is absent from this inductive definition, and, in fact, the complement of a positively Borel (...) set is not always positively Borel itself (see Veldman, 2008a). The main result of Veldman (2008a) is that, assuming Brouwer's Continuity Principle and an Axiom of Countable Choice, one may prove that the hierarchy formed by the positively Borel sets is genuinely growing: every level of the hierarchy contains sets that do not occur at any lower level. The purpose of the present paper is a different one: we want to explore the truly remarkable fine structure of the hierarchy. Brouwer's Continuity Principle again is our main tool. A second axiom proposed by Brouwer, his Thesis on Bars is also used, but only incidentally. (shrink)

We describe the inner models with representatives in all equivalence classes of thin equivalence relations in a given projective pointclass of even level assuming projective determinacy. The main result shows that these models are characterized by their correctness and the property that they correctly compute the tree from the appropriate scale. The main step towards this characterization shows that the tree from a scale can be reconstructed in a generic extension of an iterate of a mouse. We then construct models (...) with this property as generic extensions of iterates of mice under the assumption that the corresponding projective ordinal is below ω2ω2. On the way, we consider several related problems, including the question when forcing does not add equivalence classes to thin projective equivalence relations. For instance, we show that if every set has a sharp, then reasonable forcing does not add equivalence classes to thin provably View the MathML source Δ1/3 equivalence relations, and generalize this to all projective levels. (shrink)