Descriptive set theory
From MaRDI portal
Publication:1139038
zbMath0433.03025MaRDI QIDQ1139038
Publication date: 1980
Published in: Studies in Logic and the Foundations of Mathematics (Search for Journal in Brave)
Descriptive set theory (03E15) Classes of sets (Borel fields, (sigma)-rings, etc.), measurable sets, Suslin sets, analytic sets (28A05) Research exposition (monographs, survey articles) pertaining to mathematical logic and foundations (03-02) Inner models, including constructibility, ordinal definability, and core models (03E45) Descriptive set theory (topological aspects of Borel, analytic, projective, etc. sets) (54H05) Recursive functions and relations, subrecursive hierarchies (03D20) Classification of real functions; Baire classification of sets and functions (26A21) Other set-theoretic hypotheses and axioms (03E65) Determinacy principles (03E60) Hierarchies of computability and definability (03D55) Abstract and axiomatic computability and recursion theory (03D75)
Related Items
On omega context free languages which are Borel sets of infinite rank. ⋮ On the classification of first order Gödel logics ⋮ Effective Borel measurability and reducibility of functions ⋮ Hierarchies in?-spaces and applications ⋮ The Strength of Blackwell determinacy ⋮ Recursion and topology on \(2^{\leq\omega}\) for possibly infinite computations ⋮ A Technique for Proving Uniformity ⋮ The dimensions of individual strings and sequences ⋮ V = Land Intuitive Plausibility in set Theory. A Case Study ⋮ The real core model and its scales ⋮ Projectively well-ordered inner models ⋮ Recursivity in Quantum Mechanics ⋮ The consistency strength of projective absoluteness ⋮ Definability and almost disjoint families ⋮ Bounds on Scott rank for various nonelementary classes ⋮ An extension of Borel determinacy ⋮ Functions of the First Baire Class with Values in Banach Spaces ⋮ Large cardinals and definable counterexamples to the continuum hypothesis ⋮ \(\Pi_ 1^ 1\) wellfounded relations ⋮ Determinacy from strong reflection ⋮ Compact covering and game determinacy ⋮ The full basis theorem does not imply analytic wellordering ⋮ Observations about Scott and Karp trees ⋮ \(\Pi_ 2^ 1\) Wadge degrees ⋮ Polynomial games and determinacy ⋮ Parameterized games of perfect information ⋮ Hod mice and the Mouse Set Conjecture ⋮ Computability on the Countable Ordinals and the Hausdorff-Kuratowski Theorem (Extended Abstract) ⋮ One-variable fragments of intermediate logics over linear frames ⋮ Set theory and the analyst ⋮ Applying generic coding with help to uniformizations ⋮ Big vee: the story of a function, an algorithm, and three mathematical worlds ⋮ Strength and Weakness in Computable Structure Theory ⋮ $$\Sigma _{1}^{1}$$ in Every Real in a $$\Sigma _{1}^{1}$$ Class of Reals Is $$\Sigma _{1}^{1}$$ ⋮ Distinguished trees, double-trees and lifting theorems ⋮ DESCRIPTIONS AND CARDINALS BELOW ⋮ ON THE NON-ENUMERABILITY OF L ⋮ On the topological complexity of \(\omega\)-languages of non-deterministic Petri nets ⋮ Some complete \(\omega\)-powers of a one-counter language, for any Borel class of finite rank ⋮ Borel complexity of the space of probability measures ⋮ The distribution of ITRM-recognizable reals ⋮ Uncomputability: The problem of induction internalized ⋮ Who Asked Us? How the Theory of Computing Answers Questions about Analysis ⋮ Generalized doubling meets Poincaré ⋮ On the time complexity of partial real functions ⋮ Projective uniformization revisited ⋮ The Prospects for Mathematical Logic in the Twenty-First Century ⋮ Hypermachines ⋮ Determinacy in strong cardinal models ⋮ The weak square property ⋮ Supercompactness within the projective hierarchy ⋮ Some dichotomy theorems for isomorphism relations of countable models ⋮ An infinite-game semantics for well-founded negation in logic programming ⋮ A universal coanalytic linear ordering ⋮ Thin equivalence relations and inner models ⋮ On the separation question for tree languages ⋮ Separation of analytic sets by rectangles of low complexity ⋮ An effective selection theorem ⋮ Bounding lemmata for non-deterministic halting times of transfinite Turing machines ⋮ 𝐴𝐷 and the very fine structure of 𝐿(ℝ) ⋮ A random set characterization of possibility measures ⋮ Two simple sets that are not positively Borel ⋮ A global wellordering of norms defined via Blackwell games ⋮ Specker’s theorem for Nöbeling’s group ⋮ Determinacy and weakly Ramsey sets in Banach spaces ⋮ A dichotomy result for a pointwise summable sequence of operators ⋮ Classical and effective descriptive complexities of \(\omega \)-powers ⋮ Codings of separable compact subsets of the first Baire class ⋮ Coding and definability in computable structures ⋮ Canonical structure in the universe of set theory. II. ⋮ Some results about Borel sets in descriptive set theory of hyperfinite sets ⋮ A co-analytic maximal set of orthogonal measures ⋮ Borel extractions of converging sequences in compact sets of Borel functions ⋮ On disjoint Borel uniformizations ⋮ Orbit cardinals: On the effective cardinalities arising as quotient spaces of the form \(X/G\) where \(G\) acts on a Polish space \(X\) ⋮ Analytic equivalence relations and bi-embeddability ⋮ Some applications of positive formulas in descriptive set theory and logic ⋮ A theorem about Σ¹₁ equivalence relations ⋮ On the pointwise implementation of near-actions ⋮ SUITABLE EXTENDER MODELS I ⋮ Locally finite ω-languages and effective analytic sets have the same topological complexity ⋮ Turing determinacy and the continuum hypothesis ⋮ Representing pointsets as unions of Borel sets ⋮ Properties of stationary statistical solutions of the three-dimensional Navier-Stokes equations ⋮ Descriptive inner model theory ⋮ Measure theory aspects of locally countable orderings ⋮ Forcing, games and families of closed sets ⋮ Ideal games and Ramsey sets ⋮ A Metamathematical Condition Equivalent to the Existence of a Complete Left Invariant Metric for a Polish Group ⋮ On learning to coordinate: random bits help, insightful normal forms, and competency isomorphisms ⋮ Definable elements of definable Borel sets ⋮ Linear Kripke frames and Gödel logics ⋮ Boolean operations, Borel sets, and Hausdorff's question ⋮ Unraveling \(\boldsymbol\Pi_1^1\) sets ⋮ The space of composants of an indecomposable continuum ⋮ The core model for almost linear iterations ⋮ Monadic second-order logic on tree-like structures ⋮ Effective metric spaces and representations of the reals. ⋮ Randomising realizability ⋮ On index of total boundedness of (strictly) \(o\)-bounded groups ⋮ Models of set theory in which the separation theorem fails ⋮ IN SEARCH OF ULTIMATE-LTHE 19TH MIDRASHA MATHEMATICAE LECTURES ⋮ Generalized reduction theorems for model-theoretic analogs of the class of coanalytic sets ⋮ On the ‘definability of definable’ problem of Alfred Tarski, Part II ⋮ Canonical measure assignments ⋮ There are 2^{ℵ₀} many 𝐻-degrees in the random reals ⋮ Continuum-many Boolean algebras of the form Borel ⋮ On the Topological Complexity of Infinitary Rational Relations ⋮ Undecidability of Topological and Arithmetical Properties of Infinitary Rational Relations ⋮ Turing Determinacy and Suslin sets ⋮ A Game Theoretical Approach to The Algebraic Counterpart of The Wagner Hierarchy : Part II ⋮ A dichotomy characterizing analytic digraphs of uncountable Borel chromatic number in any dimension ⋮ Coarse groups, and the isomorphism problem for oligomorphic groups ⋮ Fine hierarchies and Boolean terms ⋮ HODL(ℝ) is a Core Model Below Θ ⋮ The Set of Better Quasi Orderings is ∏ ⋮ Fine hierarchy of regular ω-languages ⋮ Measures: Back and Forth Between Point sets and Large sets ⋮ On the High Complexity of Petri Nets $$\omega $$-Languages ⋮ Extending the reach of the point-to-set principle ⋮ Large cardinals at the brink ⋮ How to Choose New Axioms for Set Theory? ⋮ Revisiting the fundamental theorem of calculus ⋮ ASSIGNING AN ISOMORPHISM TYPE TO A HYPERDEGREE ⋮ Finer topologies on pointsets in Polish spaces ⋮ Reductions on equivalence relations generated by universal sets ⋮ Injective tests of low complexity in the plane ⋮ Universal and complete sets in martingale theory ⋮ A good lightface \(\varDelta_n^1\) well-ordering of the reals does not imply the existence of boldface \(\mathbf{\Delta}_{n - 1}^1\) well-orderings ⋮ How to Compute Antiderivatives ⋮ Optimal Proofs of Determinacy ⋮ Liminf progress measures ⋮ Determinacy and the sharp function on objects of type k ⋮ Comparing notions of similarity for uncountable models ⋮ A dichotomy for the definable universe ⋮ Analytic equivalence relations and Ulm-type classifications ⋮ The Mathematical Development of Set Theory from Cantor to Cohen ⋮ Two Applications of Inner Model Theory to the Study of Sets ⋮ Variations of the Martin-Solovay tree ⋮ AD and patterns of singular cardinals below Θ ⋮ On ℵ1 many minimal models ⋮ The classification of hypersmooth Borel equivalence relations ⋮ The Borel Hierarchy Theorem from Brouwer's intuitionistic perspective ⋮ The complexity of recursion theoretic games ⋮ On the complexity of the relations of isomorphism and bi-embeddability ⋮ Set theoretic naturalism ⋮ Polynomial hulls of arcs and curves ⋮ Homogeneously Suslin sets in tame mice ⋮ Baire-class $\xi $ colorings: The first three levels ⋮ Tree structures associated to a family of functions ⋮ Random reals and possibly infinite computations Part I: Randomness in ∅′ ⋮ An unpublished theorem of Solovay on OD partitions of reals into two non-OD parts, revisited ⋮ Cocycles and continuity ⋮ Universal sets for pointsets properly on the nth level of the projective hierarchy ⋮ Gödel and Set Theory ⋮ Determinacy and the sharp function on the reals ⋮ Sandwiches of ages ⋮ Arc components in metric continua ⋮ On effective σ‐boundedness and σ‐compactness ⋮ The Laczkovich-Komjáth property for coanalytic equivalence relations ⋮ On the unique representation of families of sets ⋮ Finite high-order games and an inductive approach towards Gowers's dichotomy ⋮ Topics in invariant descriptive set theory ⋮ Gödel's Program Revisited Part I: The Turn to Phenomenology ⋮ THE GAME OPERATOR ACTING ON WADGE CLASSES OF BOREL SETS ⋮ Maximal chains in the Turing degrees ⋮ Polishness of some topologies related to word or tree automata ⋮ The Complexity of the Collection of Countable Linear Orders of the form I + I ⋮ Topological properties of omega context-free languages ⋮ Wadge hierarchy of omega context-free languages ⋮ Solution of the Baire Order Problem of Mauldin ⋮ Borel equivalence relations and classifications of countable models ⋮ Strong cardinals in the core model ⋮ Actions by the classical Banach spaces ⋮ Address at the Princeton University Bicentennial Conference on Problems of Mathematics (December 17–19, 1946), By Alfred Tarski ⋮ The Kechris-Woodin Rank is Finer Than the Zalcwasser Rank ⋮ On the complexity of Borel equivalence relations with some countability property ⋮ A SEPARATION RESULT FOR COUNTABLE UNIONS OF BOREL RECTANGLES ⋮ Some algebraic equivalent forms of $\mathbb {R}\subseteq L$ ⋮ Potential Wadge classes ⋮ Banach games ⋮ Determinacy and the sharp function on the reals ⋮ ω-powers and descriptive set theory ⋮ No topological condition implies equality of polynomial and rational hulls ⋮ Measures and their random reals ⋮ Borel complexity of isomorphism between quotient Boolean algebras ⋮ The extent of definable scales ⋮ INFINITARY TABLEAU FOR SEMANTIC TRUTH ⋮ Algorithmic Fractal Dimensions in Geometric Measure Theory ⋮ On the Expressive Power of Non-deterministic and Unambiguous Petri Nets over Infinite Words ⋮ THE PREHISTORY OF THE SUBSYSTEMS OF SECOND-ORDER ARITHMETIC ⋮ AD and the supercompactness of ℵ1 ⋮ Successive weakly compact or singular cardinals ⋮ The independence of ⋮ Large cardinals and large dilators ⋮ The Logic of Choice ⋮ The axiom of determinacy implies dependent choices in L(R) ⋮ The largest countable inductive set is a mouse set ⋮ New Directions in Descriptive Set Theory ⋮ On Σ11 equivalence relations with Borel classes of bounded rank ⋮ Incompleteness Theorems, Large Cardinals, and Automata over Infinite Words ⋮ Determinacy of Banach games ⋮ The structure of graphs all of whose Y-sections are internal sets ⋮ Decomposing Baire functions ⋮ Dual easy uniformization and model-theoretic descriptive set theory ⋮ Countable structures, Ehrenfeucht strategies, and Wadge reductions ⋮ Nonuniformization results for the projective hierarchy ⋮ Amenable versus hyperfinite Borel equivalence relations ⋮ Leavable Gambling Problems with Unbounded Utilities ⋮ On a Notion of Smallness for Subsets of the Baire Space ⋮ The equivalence of determinacy and iterated sharps ⋮ Non-uniformizable sets of second projective level with countable cross-sections in the form of Vitali classes ⋮ Lusin-Sierpiński index for the internal sets ⋮ On analytic filters and prefilters ⋮ Cofinal Families of Compact Subsets of an Analytic Set ⋮ On ideals of subsets of the plane and on Cohen reals ⋮ The topological Vaught's conjecture and minimal counterexamples ⋮ Computation over algebraic structures and a classification of undecidable problems ⋮ A comparison of concepts from computable analysis and effective descriptive set theory ⋮ Ramsey sets, the Ramsey ideal, and other classes overR ⋮ On the consistency strength of the inner model hypothesis ⋮ The truth is never simple ⋮ The Shrinking Property for NP and coNP ⋮ HIGHER RANDOMNESS AND GENERICITY ⋮ On the Denjoy rank, the Kechris-Woodin rank and the Zalcwasser rank ⋮ Parametrizations of Borel Sets with Large Sections ⋮ Recursion in Kolmogorov's R-operator and the ordinal σ3 ⋮ Selection theorems and treeability ⋮ Measurable Parametrizations of Sets in Product Spaces ⋮ Believing the axioms. II ⋮ A characterization of jump operators ⋮ AN ANALYSIS OF THE MODELS ⋮ Some applications of coarse inner model theory ⋮ A coanalytic Menger group that is not $\sigma$-compact ⋮ Towers Are Universally Measure Zero and Always of First Category ⋮ A Glimm-Effros Dichotomy for Borel Equivalence Relations ⋮ Borel OD sets of reals are OD-Borel in some simple models ⋮ Banach-Tarski Decompositions Using Sets with the Property of Baire ⋮ Classical and constructive hierarchies in extended intuitionistic analysis ⋮ Non-constructive Galois-Tukey connections ⋮ sets of reals ⋮ Polish group actions: Dichotomies and generalized elementary embeddings ⋮ Polish Group Actions and the Vaught Conjecture ⋮ ON RECOGNIZABLE LANGUAGES OF INFINITE PICTURES ⋮ Multiple Separation Theorems ⋮ The Structure of Hyperfinite Borel Equivalence Relations ⋮ Universal co-analytic sets ⋮ A Property Equivalent to the Existence of Scales ⋮ Selectors for Borel Sets with Large Sections ⋮ HOW CAN WE RECOGNIZE POTENTIALLY ${\bf\Pi}^{0}_{\xi}$ SUBSETS OF THE PLANE? ⋮ Homogeneous Borel Sets ⋮ On the Rosenthal Compacta and Analytic Sets ⋮ Foundations of BQO Theory ⋮ Representing Projective Sets as Unions of Borel Sets ⋮ Borel Orderings ⋮ Compact covering mappings between Borel sets and the size of constructible reals ⋮ On Mycielski Ideals ⋮ Increasing u2 by a stationary set preserving forcing ⋮ Monotone Reducibility Over the Cantor Space ⋮ The calculus of partition sequences, changing cofinalities, and a question of Woodin ⋮ Inner Model Operators and the Continuum Hypothesis ⋮ Effective refining of Borel coverings ⋮ Glimm-Effros for coanalytic equivalence relations ⋮ Projective prewellorderings vs projective wellfounded relations ⋮ The perfect set theorem and definable wellorderings of the continuum ⋮ Mansfield and Solovay type results on covering plane sets by lines ⋮ Cardinalities in the projective hierarchy ⋮ A dichotomy theorem for turbulence ⋮ A Game-Theoretic Characterization of Boolean Grammars ⋮ Minimal upper bounds for sequences of -degrees ⋮ Fixpoints, games and the difference hierarchy ⋮ Wadge Degrees ofω-Languages of Deterministic Turing Machines ⋮ Cardinality Quantifiers in MLO over Trees ⋮ Unnamed Item ⋮ Π11 Borel sets ⋮ On the Ramsey property for sets of reals ⋮ Ultrafilters which extend measures ⋮ An absoluteness principle for Borel sets ⋮ Measurable enumeration of eigenelements ⋮ A topological analog to the Rice-Shapiro index theorem ⋮ Borel and Analytic One-One Parametrizations of the Countable Sets of Reals ⋮ A Proof of Projective Determinacy ⋮ The fine structure of real mice ⋮ Extenders, embedding normal forms, and the Martin-Steel-theorem ⋮ Hurewicz-like tests for Borel subsets of the plane ⋮ Linear algebraic groups and countable Borel equivalence relations ⋮ Ideals without ccc and without property $ \boldsymbol( \mathbf{M} \boldsymbol)$ ⋮ Infinite time Turing machines ⋮ Forcing and reducibilities. III. Forcing in fragments of set theory ⋮ Vaught’s conjecture and the Glimm-Effros property for Polish transformation groups ⋮ Vaught’s conjecture on analytic sets ⋮ The Hausdorff-Ershov hierarchy in Euclidean spaces ⋮ The strength of Menger's conjecture ⋮ Monotone operators and first category sets ⋮ Some descriptive-set-theoretical problems in complexity theory ⋮ Infinite products in monoids ⋮ Topology and descriptive set theory ⋮ Sur la génération des fonctions boréliennes fortement affines sur un convexe compact métrisable. (On the generation of strongly affine Borel functions on a metrizable convex compact set) ⋮ Computational depth and reducibility ⋮ Borel measurable selections of Paretian utility functions ⋮ On Borel ideals ⋮ Beurling moving averages and approximate homomorphisms ⋮ Large cardinal axioms and independence: The continuum problem revisited ⋮ Is Gold-Putnam diagonalization complete? ⋮ The axiom of determinacy and the modern development of descriptive set theory ⋮ Alternating automata on infinite trees ⋮ On some extensions of the projective hierarchy ⋮ Approximating sets with equivalence relations ⋮ Towards a descriptive set theory for domain-like structures ⋮ Selctive ultrafilters and homogeneity ⋮ On minimal non-potentially closed subsets of the plane ⋮ Mouse sets ⋮ Game semantics for non-monotonic intensional logic programming ⋮ Narrow coverings of \(\omega\)-ary product spaces ⋮ Genericity and amalgamation of classes of Banach spaces ⋮ Infinite combinatorics and definability ⋮ The Galvin-Prikry theorem and set existence axioms ⋮ Computational inductive definability ⋮ Borel ideals vs. Borel sets of countable relations and trees ⋮ A covering lemma for \(K(\mathbb{R})\) ⋮ Fine hierarchy of regular \(\omega\)-languages ⋮ Ambiguity in omega context free languages ⋮ A combinatorial property of Fréchet iterated filters ⋮ Scales of minimal complexity in \({K(\mathbb{R})}\) ⋮ A hierarchy of deterministic context-free \(\omega\)-languages. ⋮ Borel hierarchy and omega context free languages. ⋮ The shrinking property for NP and coNP ⋮ Closed choice and a uniform low basis theorem ⋮ Counterexamples to countable-section \(\varPi_2^1\) uniformization and \(\varPi_3^1\) separation ⋮ A game-theoretic characterization of Boolean grammars ⋮ Equivalence between Wadge and Lipschitz determinacy ⋮ The natural semidirect product \({\mathbb{R}^n \rtimes G(n)}\) is algebraically determined ⋮ Totally non-proper ordinals beyond \(L(V_{\lambda +1})\) ⋮ Beyond Borel-amenability: scales and superamenable reducibilities ⋮ The effective theory of Borel equivalence relations ⋮ Forcing absoluteness and regularity properties ⋮ Higher Kurtz randomness ⋮ The determinacy strength of \(\Pi_2^1\)-comprehension ⋮ A partially non-proper ordinal beyond \(L(V_{\lambda +1})\) ⋮ Measurable, nonleavable gambling problems ⋮ Baire irresolvable spaces and lifting for a layered ideal ⋮ Uniquely universal sets ⋮ Kuratowski reduction in a \(\sigma \)-frame ⋮ Comparing Peano arithmetic, Basic Law V, and Hume's Principle ⋮ Large cardinals imply that every reasonably definable set of reals is Lebesgue measurable ⋮ Dense selections ⋮ Partition properties and well-ordered sequences ⋮ Projective subsets of separable metric spaces ⋮ Three ordinal ranks for the set of differentiable functions ⋮ The complexity of antidifferentiation ⋮ Borel quasi-orderings in subsystems of second-order arithmetic ⋮ Compact perfect sets in weak analytic spaces ⋮ Topological complexity of locally finite \(\omega\)-languages ⋮ Lowness of higher randomness notions ⋮ Fine hierarchies and m-reducibilities in theoretical computer science ⋮ Fairness, distances and degrees ⋮ Determinacy and extended sharp functions on the reals. II: Obtaining sharps from determinacy ⋮ Sets and supersets ⋮ Amenability, Kazhdan's property and percolation for trees, groups and equivalence relations ⋮ Effectively closed sets of measures and randomness ⋮ Graphs with \(\boldsymbol\Pi^ 0_ 1(\kappa)\) \(Y\)-sections ⋮ Query languages for hierarchic databases ⋮ On analytic and coanalytic function spaces \(C_ p(X)\) ⋮ Logic, sets, and mathematics ⋮ Descriptive classes of sets in nonseparable spaces ⋮ The isomorphism relation between tree-automatic structures ⋮ Some new results on decidability for elementary algebra and geometry ⋮ Regular variation without limits ⋮ Decidability and definability with circumscription ⋮ Decision problems for Turing machines ⋮ Characteristics of discrete transfinite time Turing machine models: Halting times, stabilization times, and normal form theorems ⋮ Continuous Fraïssé conjecture ⋮ Free distributive groupoids ⋮ Axioms of determinacy and biorthogonal systems ⋮ Mass problems associated with effectively closed sets ⋮ Projective absoluteness for Sacks forcing ⋮ Infinite combinatorics and the foundations of regular variation ⋮ The automorphism tower of a centerless group without choice ⋮ On approximate and algebraic computability over the real numbers ⋮ Borel equivalence relations induced by actions of the symmetric group ⋮ Is there a set of reals not in \(K(\mathbb{R})\)? ⋮ Applications of cut-free infinitary derivations to generalized recursion theory ⋮ A probabilistic dynamic logic ⋮ Determinacy implies that \(\aleph_ 2\) is supercompact ⋮ Simply connected compact subsets of the plane ⋮ An application of Shoenfield's absoluteness theorem to the theory of uniform distribution ⋮ Weak axioms of determinacy and subsystems of analysis. II \((\Sigma ^ 0_ 2\) games) ⋮ Regularity properties of definable sets of reals ⋮ The lack of definable witnesses and provably recursive functions in intuitionistic set theories ⋮ The pointwise view of determinacy: arboreal forcings, measurability, and weak measurability ⋮ Comparing inductive and circular definitions: Parameters, complexity and games
