We sketch a broadening of the Gupta-Belnap notion of a circular or revision theoretic definition into that of a more generalized form incorporating ideas of Kleene’s generalized or higher type recursion. This thereby connects the philosophically motivated, and derived, notion of a circular definition with an older form of definition by recursion using functionals, that is functions of functions, as oracles. We note that Gupta and Belnap’s notion of ‘categorical in L’ can be formulated in at least one of these (...) schemes. (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.

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)

§1. I will start with a quick definition of descriptive set theory: It is the study of the structure of definable sets and functions in separable completely metrizable spaces. Such spaces are usually called Polish spaces. Typical examples are ℝn, ℂn, Hilbert space and more generally all separable Banach spaces, the Cantor space 2ℕ, the Baire space ℕℕ, the infinite symmetric group S∞, the unitary group, the group of measure preserving transformations of the unit interval, etc.In this theory sets are (...) classified in hierarchies according to the complexity of their definitions and the structure of sets in each level of these hierarchies is systematically analyzed. In the beginning we have the Borel sets in Polish spaces, obtained by starting with the open sets and closing under the operations of complementation and countable unions, and the corresponding Borel hierarchy. After this come the projective sets, obtained by starting with the Borel sets and closing under the operations of complementation and projection, and the corresponding projective hierarchy.There are also transfinite extensions of the projective hierarchy and even much more complex definable sets studied in descriptive set theory, but I will restrict myself here to Borel and projective sets, in fact just those at the first level of the projective hierarchy, i.e., the Borel (), analytic () and coanalytic () sets. (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)

Les questions fondationnelles en logique et en mathématiques, les questions de fond et de fondements sont-elles des questions qui relèvent de la foi ou de la croyance ou des questions susceptibles d'analyse rigoureuse et philosophiquement décidables? C'est cette interrogation que je veux développer et à laquelle j'apporterai une réponse personnelle.

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 if V = L then there is a $\Pi _{1}^{1}$ maximal orthogonal (i.e., mutually singular) set of measures on Cantor space. This provides a natural counterpoint to the well-known theorem of Preiss and Rataj [16] that no analytic set of measures can be maximal orthogonal.

Strengthening a theorem of Hjorth this paper gives a new characterization of which Polish groups admit compatible complete left invariant metrics. As a corollary it is proved that any Polish group without a complete left invariant metric has a continuous action on a Polish space whose associated orbit equivalence relation is not essentially countable.

Model-theoretic 1-types overa given first-order theory T may be construed as natural metalogical miniatures of G. W. Leibniz' ``complete individual notions'', ``substances'' or ``substantial forms''. This analogy prompts this essay's modal semantics for an essentiallyundecidable first-order theory T, in which one quantifies over such ``substances'' in a boolean universe V(C), where C is the completion of the Lindenbaum-algebra of T.More precisely, one can define recursively a set-theoretic translate of formulae N of formulae of a normal modal theory Tm based on (...) T, such that the counterpart `i' of a the modal variable `xi' of L(Tm) in this translation-scheme ranges over elements of V(C) that are 1-types of T with value 1 (sometimes called `definite' C-valued 1-types of T). (shrink)

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)

Let X and Y be uncountable Polish spaces. We show in ZF that there is a coanalytic subset P of X × Y with countable sections which cannot be expressed as the union of countably many partial coanalytic, or even PCA = Σ 1 2 , graphs. If X = Y = ω ω , P may be taken to be Π 1 1 . Assuming stronger set theoretic axioms, we identify the least pointclass such that any such coanalytic P (...) can be expressed as the union of countably many graphs in this pointclass. This last result is extended (under suitable hypotheses) to all levels of the projective hierarchy. (shrink)

Let X, Y be Polish spaces,,. We say A is universal for Γ provided that each x‐section of A is in Γ and each element of Γ occurs as an x‐section of A. An equivalence relation generated by a set is denoted by, where. The following results are shown: If A is a set universal for all nonempty closed subsets of Y, then is a equivalence relation and. If A is a set universal for all countable subsets of Y, then (...) is a equivalence relation, and and ; if, then ; if every set is Lebesgue measurable or has the Baire property, then. for, if every set has the Baire property, and E is any equivalence relation, then. (shrink)

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)

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)

In Baire space N = ω ω we define a sequence of equivalence relations $\langle E_\nu| \nu , each E v being Σ 1 1 with classes in Π 0 1 + ν + 1 and such that (i) E ν does not have perfectly many classes, and (ii) N/E ν is countable iff $\omega^L_\nu . This construction can be extended cofinally in (δ 1 3 ) L . A new proof is given of a theorem of Hausdorff on partitions (...) of R into ω 1 many Π 0 3 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 prove a recursion theoretic characterization of the Topological Vaught Conjecture in the Zermelo‐Fraenkel set theory by using tools from effective descriptive set theory and by revisiting the result of Miller that orbits in Polish G‐spaces are Borel sets.

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.

This paper studies homogeneously Suslin (hom) sets of reals in tame mice. The following results are established: In 0 ¶ the hom sets are precisely the [Symbol] sets. In M n every hom set is correctly [Symbol] and (δ + 1)-universally Baire where ä is the least Woodin. In M u every hom set is <λ-hom, where λ is the supremum of the Woodins.

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)

We study the sets of the infinite sentences constructible with a dictionary over a finite alphabet, from the viewpoint of descriptive set theory. Among others, this gives some true co-analytic sets. The case where the dictionary is finite is studied and gives a natural example of a set at level ω of the Wadge hierarchy.

In the presence of large cardinals, or sufficient determinacy, every equivalence relation in L(R) either admits a wellordered separating family or continuously reduces E 0.

The four authors present their speculations about the future developments of mathematical logic in the twenty-first century. The areas of recursion theory, proof theory and logic for computer science, model theory, and set theory are discussed independently.

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)

We prove that the determinacy of Gale-Stewart games whose winning sets are accepted by realtime 1-counter Büchi automata is equivalent to the determinacy of analytic Gale-Stewart games which is known to be a large cardinal assumption. We show also that the determinacy of Wadge games between two players in charge ofω-languages accepted by 1-counter Büchi automata is equivalent to the analytic Wadge determinacy. Using some results of set theory we prove that one can effectively construct a 1-counter Büchi automatonand a (...) Büchi automatonsuch that: There exists a model of ZFC in which Player 2 has a winning strategy in the Wadge gameW,L()); There exists a model of ZFC in which the Wadge gameW,L()) is not determined. Moreover these are the only two possibilities, i.e. there are no models of ZFC in which Player 1 has a winning strategy in the Wadge gameW,L()). (shrink)

The existence of a countable complete theory with exactly ℵ 1 many minimal models is independent of ZFC + ¬CH.

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)

Using Steel's recent result that assuming AD, in L[R] below Θ, κ is regular $\operatorname{iff} \kappa$ is measurable, we mimic below Θ certain earlier results of Gitik. In particular, we construct via forcing a model in which all uncountable cardinals below Θ are singular and a model in which the only regular uncountable cardinal below Θ is ℵ 1.

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.

Jensen's celebrated Covering Lemma states that if 0# does not exist, then for any uncountable set of ordinals X, there is a Y∈L such that X⊆Y and |X| = |Y|. Working in ZF + AD alone, we establish the following analog: If ℝ# does not exist, then L(ℝ) and V have exactly the same sets of reals and for any set of ordinals X with |X| ≥ΘL(ℝ), there is a Y∈L(ℝ) such that X⊆Y and |X| = |Y|. Here ℝ is (...) the set of reals and Θ is the supremum of the ordinals which are the surjective image of ℝ. (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)

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.