Results for 'Borel computability'

1000+ found
Order:
  1.  17
    Borel Complexity and Computability of the Hahn–Banach Theorem.Vasco Brattka - 2008 - Archive for Mathematical Logic 46 (7-8):547-564.
    The classical Hahn–Banach Theorem states that any linear bounded functional defined on a linear subspace of a normed space admits a norm-preserving linear bounded extension to the whole space. The constructive and computational content of this theorem has been studied by Bishop, Bridges, Metakides, Nerode, Shore, Kalantari Downey, Ishihara and others and it is known that the theorem does not admit a general computable version. We prove a new computable version of this theorem without unrolling the classical proof of the (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   5 citations  
  2.  15
    Effective Borel Degrees of Some Topological Functions.Guido Gherardi - 2006 - Mathematical Logic Quarterly 52 (6):625-642.
    The focus of this paper is the incomputability of some topological functions using the tools of Borel computability theory, as introduced by V. Brattka in [3] and [4]. First, we analyze some basic topological functions on closed subsets of ℝn, like closure, border, intersection, and derivative, and we prove for such functions results of Σ02-completeness and Σ03-completeness in the effective Borel hierarchy. Then, following [13], we re-consider two well-known topological results: the lemmas of Urysohn and Urysohn-Tietze for (...)
    Direct download  
     
    Export citation  
     
    Bookmark   1 citation  
  3.  24
    Effective Borel Measurability and Reducibility of Functions.Vasco Brattka - 2005 - Mathematical Logic Quarterly 51 (1):19-44.
    The investigation of computational properties of discontinuous functions is an important concern in computable analysis. One method to deal with this subject is to consider effective variants of Borel measurable functions. We introduce such a notion of Borel computability for single-valued as well as for multi-valued functions by a direct effectivization of the classical definition. On Baire space the finite levels of the resulting hierarchy of functions can be characterized using a notion of reducibility for functions and (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   23 citations  
  4.  22
    Borel Equivalence Relations and Lascar Strong Types.Krzysztof Krupiński, Anand Pillay & Sławomir Solecki - 2013 - Journal of Mathematical Logic 13 (2):1350008.
    The "space" of Lascar strong types, on some sort and relative to a given complete theory T, is in general not a compact Hausdorff topological space. We have at least three aims in this paper. The first is to show that spaces of Lascar strong types, as well as other related spaces and objects such as the Lascar group Gal L of T, have well-defined Borel cardinalities. The second is to compute the Borel cardinalities of the known examples (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  5.  25
    Computing the Complexity of the Relation of Isometry Between Separable Banach Spaces.Julien Melleray - 2007 - Mathematical Logic Quarterly 53 (2):128-131.
    We compute here the Borel complexity of the relation of isometry between separable Banach spaces, using results of Gao, Kechris [2], Mayer-Wolf [5], and Weaver [8]. We show that this relation is Borel bireducible to the universal relation for Borel actions of Polish groups. (© 2007 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim).
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  6.  11
    Infinite Computations with Random Oracles.Merlin Carl & Philipp Schlicht - 2017 - Notre Dame Journal of Formal Logic 58 (2):249-270.
    We consider the following problem for various infinite-time machines. If a real is computable relative to a large set of oracles such as a set of full measure or just of positive measure, a comeager set, or a nonmeager Borel set, is it already computable? We show that the answer is independent of ZFC for ordinal Turing machines with and without ordinal parameters and give a positive answer for most other machines. For instance, we consider infinite-time Turing machines, unresetting (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  7.  8
    A Computable Version of Banach’s Inverse Mapping Theorem.Vasco Brattka - 2009 - Annals of Pure and Applied Logic 157 (2-3):85-96.
    Given a program of a linear bounded and bijective operator T, does there exist a program for the inverse operator T−1? And if this is the case, does there exist a general algorithm to transfer a program of T into a program of T−1? This is the inversion problem for computable linear operators on Banach spaces in its non-uniform and uniform formulation, respectively. We study this problem from the point of view of computable analysis which is the Turing machine based (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  8.  8
    Turing Computable Embeddings.F. Knight Julia, Miller Sara & M. Vanden Boom - 2007 - Journal of Symbolic Logic 72 (3):901-918.
    In [3], two different effective versions of Borel embedding are defined. The first, called computable embedding, is based on uniform enumeration reducibility, while the second, called Turing computable embedding, is based on uniform Turing reducibility. While [3] focused mainly on computable embeddings, the present paper considers Turing computable embeddings. Although the two notions are not equivalent, we can show that they behave alike on the mathematically interesting classes chosen for investigation in [3]. We give a “Pull-back Theorem”, saying that (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   7 citations  
  9.  36
    The Steel Hierarchy of Ordinal Valued Borel Mappings.J. Duparc - 2003 - Journal of Symbolic Logic 68 (1):187-234.
    Given well ordered countable sets of the form $\lamphi$, we consider Borel mappings from $\lamphiom$ with countable image inside the ordinals. The ordinals and $\lamphiom$ are respectively equipped with the discrete topology and the product of the discrete topology on $\lamphi$. The Steel well-ordering on such mappings is defined by $\phi\minf\psi$ iff there exists a continuous function $f$ such that $\phi\leq\psi\circ f$ holds for any $x\in\lamphiom$. It induces a hierarchy of mappings which we give a complete description of. We (...)
    Direct download (9 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  10.  10
    Computability Theory, Nonstandard Analysis, and Their Connections.Dag Normann & Sam Sanders - 2019 - Journal of Symbolic Logic 84 (4):1422-1465.
    We investigate the connections between computability theory and Nonstandard Analysis. In particular, we investigate the two following topics and show that they are intimately related. A basic property of Cantor space$2^ $ is Heine–Borel compactness: for any open covering of $2^ $, there is a finite subcovering. A natural question is: How hard is it to compute such a finite subcovering? We make this precise by analysing the complexity of so-called fan functionals that given any $G:2^ \to $, (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  11.  8
    Turing Degrees in Polish Spaces and Decomposability of Borel Functions.Vassilios Gregoriades, Takayuki Kihara & Keng Meng Ng - 2020 - Journal of Mathematical Logic 21 (1):2050021.
    We give a partial answer to an important open problem in descriptive set theory, the Decomposability Conjecture for Borel functions on an analytic subset of a Polish space to a separable metrizable space. Our techniques employ deep results from effective descriptive set theory and recursion theory. In fact it is essential to extend several prominent results in recursion theory (e.g. the Shore-Slaman Join Theorem) to the setting of Polish spaces. As a by-product we give both positive and negative results (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  12.  66
    Classification From a Computable Viewpoint.Wesley Calvert & Julia F. Knight - 2006 - Bulletin of Symbolic Logic 12 (2):191-218.
    Classification is an important goal in many branches of mathematics. The idea is to describe the members of some class of mathematical objects, up to isomorphism or other important equivalence, in terms of relatively simple invariants. Where this is impossible, it is useful to have concrete results saying so. In model theory and descriptive set theory, there is a large body of work showing that certain classes of mathematical structures admit classification while others do not. In the present paper, we (...)
    Direct download (14 more)  
     
    Export citation  
     
    Bookmark   8 citations  
  13.  77
    The Extent of Computation in Malament–Hogarth Spacetimes.P. D. Welch - 2008 - British Journal for the Philosophy of Science 59 (4):659-674.
    We analyse the extent of possible computations following Hogarth ([2004]) conducted in Malament–Hogarth (MH) spacetimes, and Etesi and Németi ([2002]) in the special subclass containing rotating Kerr black holes. Hogarth ([1994]) had shown that any arithmetic statement could be resolved in a suitable MH spacetime. Etesi and Németi ([2002]) had shown that some relations on natural numbers that are neither universal nor co-universal, can be decided in Kerr spacetimes, and had asked specifically as to the extent of computational limits there. (...)
    Direct download (10 more)  
     
    Export citation  
     
    Bookmark   10 citations  
  14.  6
    A Journey Through Computability, Topology and Analysis.Manlio Valenti - 2022 - Bulletin of Symbolic Logic 28 (2):266-267.
    This thesis is devoted to the exploration of the complexity of some mathematical problems using the framework of computable analysis and descriptive set theory. We will especially focus on Weihrauch reducibility as a means to compare the uniform computational strength of problems. After a short introduction of the relevant background notions, we investigate the uniform computational content of problems arising from theorems that lie at the higher levels of the reverse mathematics hierarchy.We first analyze the strength of the open and (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  15.  17
    Uniformity, Universality, and Computability Theory.Andrew S. Marks - 2017 - Journal of Mathematical Logic 17 (1):1750003.
    We prove a number of results motivated by global questions of uniformity in computabi- lity theory, and universality of countable Borel equivalence relations. Our main technical tool is a game for constructing functions on free products of countable groups. We begin by investigating the notion of uniform universality, first proposed by Montalbán, Reimann and Slaman. This notion is a strengthened form of a countable Borel equivalence relation being universal, which we conjecture is equivalent to the usual notion. With (...)
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  16. Topological Complexity of Locally Finite Ω-Languages.Olivier Finkel - 2008 - Archive for Mathematical Logic 47 (6):625-651.
    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 (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  17.  32
    The Hausdorff-Ershov Hierarchy in Euclidean Spaces.Armin Hemmerling - 2006 - Archive for Mathematical Logic 45 (3):323-350.
    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 (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark  
  18.  12
    Completion of Choice.Vasco Brattka & Guido Gherardi - 2021 - Annals of Pure and Applied Logic 172 (3):102914.
    We systematically study the completion of choice problems in the Weihrauch lattice. Choice problems play a pivotal rôle in Weihrauch complexity. For one, they can be used as landmarks that characterize important equivalences classes in the Weihrauch lattice. On the other hand, choice problems also characterize several natural classes of computable problems, such as finite mind change computable problems, non-deterministically computable problems, Las Vegas computable problems and effectively Borel measurable functions. The closure operator of completion generates the concept of (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   5 citations  
  19.  38
    Infinite Time Decidable Equivalence Relation Theory.Samuel Coskey & Joel David Hamkins - 2011 - Notre Dame Journal of Formal Logic 52 (2):203-228.
    We introduce an analogue of the theory of Borel equivalence relations in which we study equivalence relations that are decidable by an infinite time Turing machine. The Borel reductions are replaced by the more general class of infinite time computable functions. Many basic aspects of the classical theory remain intact, with the added bonus that it becomes sensible to study some special equivalence relations whose complexity is beyond Borel or even analytic. We also introduce an infinite time (...)
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  20.  2
    Complexity of Index Sets of Descriptive Set-Theoretic Notions.Reese Johnston & Dilip Raghavan - 2022 - Journal of Symbolic Logic 87 (3):894-911.
    Descriptive set theory and computability theory are closely-related fields of logic; both are oriented around a notion of descriptive complexity. However, the two fields typically consider objects of very different sizes; computability theory is principally concerned with subsets of the naturals, while descriptive set theory is interested primarily in subsets of the reals. In this paper, we apply a generalization of computability theory, admissible recursion theory, to consider the relative complexity of notions that are of interest in (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  21.  40
    Probability Measures in the Logic of Nilpotent Minimum.Stefano Aguzzoli & Brunella Gerla - 2010 - Studia Logica 94 (2):151-176.
    We axiomatize the notion of state over finitely generated free NM-algebras, the Lindenbaum algebras of pure Nilpotent Minimum logic. We show that states over the free n -generated NM-algebra exactly correspond to integrals of elements of with respect to Borel probability measures.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  22.  1
    Results on Martin’s Conjecture.Patrick Lutz - 2021 - Bulletin of Symbolic Logic 27 (2):219-220.
    Martin’s conjecture is an attempt to classify the behavior of all definable functions on the Turing degrees under strong set theoretic hypotheses. Very roughly it says that every such function is either eventually constant, eventually equal to the identity function or eventually equal to a transfinite iterate of the Turing jump. It is typically divided into two parts: the first part states that every function is either eventually constant or eventually above the identity function and the second part states that (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  23.  6
    Classical and Effective Descriptive Complexities of Ω-Powers.Olivier Finkel & Dominique Lecomte - 2009 - Annals of Pure and Applied Logic 160 (2):163-191.
    We prove that, for each countable ordinal ξ≥1, there exist some -complete ω-powers, and some -complete ω-powers, extending previous works on the topological complexity of ω-powers [O. Finkel, Topological properties of omega context free languages, Theoretical Computer Science 262 669–697; O. Finkel, Borel hierarchy and omega context free languages, Theoretical Computer Science 290 1385–1405; O. Finkel, An omega-power of a finitary language which is a borel set of infinite rank, Fundamenta informaticae 62 333–342; D. Lecomte, Sur les ensembles (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  24.  3
    Finding Descending Sequences Through Ill-Founded Linear Orders.Jun le Goh, Arno Pauly & Manlio Valenti - 2021 - Journal of Symbolic Logic 86 (2):817-854.
    In this work we investigate the Weihrauch degree of the problem Decreasing Sequence of finding an infinite descending sequence through a given ill-founded linear order, which is shared by the problem Bad Sequence of finding a bad sequence through a given non-well quasi-order. We show that $\mathsf {DS}$, despite being hard to solve, is rather weak in terms of uniform computational strength. To make the latter precise, we introduce the notion of the deterministic part of a Weihrauch degree. We then (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  25.  11
    On a Metric Generalization of the Tt-Degrees and Effective Dimension Theory.Takayuki Kihara - 2019 - Journal of Symbolic Logic 84 (2):726-749.
    In this article, we study an analogue of tt-reducibility for points in computable metric spaces. We characterize the notion of the metric tt-degree in the context of first-level Borel isomorphism. Then, we study this concept from the perspectives of effective topological dimension theory and of effective fractal dimension theory.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  26.  22
    Characterizations of the Class ~2^T^a Over Euclidean Spaces.Armin Hemmerling - 2004 - Mathematical Logic Quarterly 50 (4):507.
    We present some characterizations of the members of Δta2, that class of the topological arithmetical hierarchy which is just large enough to include several fundamental types of sets of points in Euclidean spaces ℝk. The limit characterization serves as a basic tool in further investigations. The characterization by effective difference chains of effectively exhaustible sets yields only a hierarchy within a subfield of Δta2. Effective difference chains of transfinite order types, consisting of complements of effectively exhaustible sets, as well as (...)
    Direct download  
     
    Export citation  
     
    Bookmark   1 citation  
  27. Computer Science Logic 11th International Workshop, Csl '97 : Annual Conference of the Eacsl, Aarhus, Denmark, August 23-29, 1997 : Procedings. [REVIEW]M. Nielsen, Wolfgang Thomas & European Association for Computer Science Logic - 1998
     
    Export citation  
     
    Bookmark  
  28.  1
    Computer Science Logic: 10th International Workshop, Csl '96, Annual Conference of the Eacsl, Utrecht, the Netherlands, September 21 - 27, 1996, Selected Papers. [REVIEW]D. van Dalen, M. Bezem & European Association for Computer Science Logic - 1997 - Springer Verlag.
    The related fields of fractal image encoding and fractal image analysis have blossomed in recent years. This book, originating from a NATO Advanced Study Institute held in 1995, presents work by leading researchers. It is developing the subjects at an introductory level, but it also has some recent and exciting results in both fields. The book contains a thorough discussion of fractal image compression and decompression, including both continuous and discrete formulations, vector space and hierarchical methods, and algorithmic optimizations. The (...)
    Direct download  
     
    Export citation  
     
    Bookmark  
  29. Borel and Baire Reducibility.Harvey Friedman - manuscript
    The Borel reducibility theory of Polish equivalence relations, at least in its present form, was initiated independently in [FS89] and [HKL90]. There is now an extensive literature on this topic, including fundamental work on the Glimm-Effros dichotomy in [HKL90], on countable Borel equivalence relations in [DJK94], and on Polish group actions in [BK96].
     
    Export citation  
     
    Bookmark  
  30. Borel Hierarchy (Σ 0.Alexander S. Kechris - 1999 - Bulletin of Symbolic Logic 5 (2).
  31. Borel . - Pages Choisies. [REVIEW]P. Lévy - 1971 - Revue Philosophique de la France Et de l'Etranger 161:233.
     
    Export citation  
     
    Bookmark  
  32.  45
    On Borel Equivalence Relations in Generalized Baire Space.Sy-David Friedman & Tapani Hyttinen - 2012 - Archive for Mathematical Logic 51 (3-4):299-304.
    We construct two Borel equivalence relations on the generalized Baire space κ κ , κ <κ = κ > ω, with the property that neither of them is Borel reducible to the other. A small modification of the construction shows that the straightforward generalization of the Glimm-Effros dichotomy fails.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  33.  13
    Borel's Conjecture in Topological Groups.Fred Galvin & Marion Scheepers - 2013 - Journal of Symbolic Logic 78 (1):168-184.
    We introduce a natural generalization of Borel's Conjecture. For each infinite cardinal number $\kappa$, let ${\sf BC}_{\kappa}$ denote this generalization. Then ${\sf BC}_{\aleph_0}$ is equivalent to the classical Borel conjecture. Assuming the classical Borel conjecture, $\neg{\sf BC}_{\aleph_1}$ is equivalent to the existence of a Kurepa tree of height $\aleph_1$. Using the connection of ${\sf BC}_{\kappa}$ with a generalization of Kurepa's Hypothesis, we obtain the following consistency results: 1. If it is consistent that there is a 1-inaccessible cardinal (...)
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  34.  17
    The Borel Hierarchy Theorem From Brouwer's Intuitionistic Perspective.Wim Veldman - 2008 - Journal of Symbolic Logic 73 (1):1-64.
    In intuitionistic analysis, "Brouwer's Continuity Principle" implies, together with an "Axiom of Countable Choice", that the positively Borel sets form a genuinely growing hierarchy: every level of the hierarchy contains sets that do not occur at any lower level.
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  35.  18
    The Borel Complexity of Isomorphism for Theories with Many Types.David Marker - 2007 - Notre Dame Journal of Formal Logic 48 (1):93-97.
    During the Notre Dame workshop on Vaught's Conjecture, Hjorth and Kechris asked which Borel equivalence relations can arise as the isomorphism relation for countable models of a first-order theory. In particular, they asked if the isomorphism relation can be essentially countable but not tame. We show this is not possible if the theory has uncountably many types.
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   5 citations  
  36.  8
    Comparing Borel Reducibility and Depth of an Ω-Stable Theory.Martin Koerwien - 2009 - Notre Dame Journal of Formal Logic 50 (4):365-380.
    In "A proof of Vaught's conjecture for ω-stable theories," the notions of ENI-NDOP and eni-depth have been introduced, which are variants of the notions of NDOP and depth known from Shelah's classification theory. First, we show that for an ω-stable first-order complete theory, ENI-NDOP allows tree decompositions of countable models. Then we discuss the relationship between eni-depth and the complexity of the isomorphism relation for countable models of such a theory in terms of Borel reducibility as introduced by Friedman (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark  
  37.  32
    Beyond Borel-Amenability: Scales and Superamenable Reducibilities.Luca Motto Ros - 2010 - Annals of Pure and Applied Logic 161 (7):829-836.
    We analyze the degree-structure induced by large reducibilities under the Axiom of Determinacy. This generalizes the analysis of Borel reducibilities given in Alessandro Andretta and Donald A. Martin [1], Luca Motto Ros [6] and Luca Motto Ros. [5] e.g. to the projective levels.
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  38. Borel, E. - Le Hasard. [REVIEW]M. Davidson - 1916 - Scientia 10 (19):147.
    No categories
     
    Export citation  
     
    Bookmark  
  39. BOREL, E. - Le hasard. [REVIEW]M. Davidson - 1916 - Scientia 10 (19):147.
    No categories
     
    Export citation  
     
    Bookmark  
  40.  10
    Borel Partitions of Infinite Subtrees of a Perfect Tree.A. Louveau, S. Shelah & B. Veličković - 1993 - Annals of Pure and Applied Logic 63 (3):271-281.
    Louveau, A., S. Shelah and B. Velikovi, Borel partitions of infinite subtrees of a perfect tree, Annals of Pure and Applied Logic 63 271–281. We define a notion of type of a perfect tree and show that, for any given type τ, if the set of all subtrees of a given perfect tree T which have type τ is partitioned into two Borel classes then there is a perfect subtree S of T such that all subtrees of S (...)
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   6 citations  
  41.  18
    Borel Separability of the Coanalytic Ramsey Sets.Alan D. Taylor - 2006 - Annals of Pure and Applied Logic 144 (1-3):130-132.
    Let AC and AI denote the collections of graphs with vertex set ω and which have, respectively, no infinite independent subgraph, and no infinite complete subgraph. Both AC and AI are coanalytic sets of reals that are not analytic, and they are disjoint by Ramsey’s theorem. We prove that there exists a Borel set separating AC and AI, and we discuss the sense in which this is an infinite analogue of a weak version of.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark  
  42.  9
    On Borel Ideals.Fons van Engelen - 1994 - Annals of Pure and Applied Logic 70 (2):177-203.
    We show that a first category homogeneous zero-dimensional Borel set X can be embedded in as an ideal on ω if and only if X is homeomorphic to X × X if and only if X is Wadge-equivalent to X × X. Furthermore, we determine the Wadge classes of such X, thus giving a complete picture of the possible descriptive complexity of Borel ideals on ω. We also discuss the connection with ideals of compact sets.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   9 citations  
  43.  24
    Borel Reducibility and Hölder(Α) Embeddability Between Banach Spaces.Longyun Ding - 2012 - Journal of Symbolic Logic 77 (1):224-244.
    We investigate Borel reducibility between equivalence relations $E(X;p)=X^{\mathbb{N}}/\ell_{p}(X)'s$ where X is a separable Banach space. We show that this reducibility is related to the so called Hölder(α) embeddability between Banach spaces. By using the notions of type and cotype of Banach spaces, we present many results on reducibility and unreducibility between E(L r ; p)'s and E(c 0 ; p)'s for r, p ∈ [1, +∞). We also answer a problem presented by Kanovei in the affirmative by showing that (...)
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  44.  18
    Borel Globalizations of Partial Actions of Polish Groups.H. Pinedo & C. Uzcategui - 2018 - Archive for Mathematical Logic 57 (5-6):617-627.
    We show that the enveloping space \ of a partial action of a Polish group G on a Polish space \ is a standard Borel space, that is to say, there is a topology \ on \ such that \\) is Polish and the quotient Borel structure on \ is equal to \\). To prove this result we show a generalization of a theorem of Burgess about Borel selectors for the orbit equivalence relation induced by a group (...)
    No categories
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark  
  45.  39
    Decomposing Borel Functions and Structure at Finite Levels of the Baire Hierarchy.Janusz Pawlikowski & Marcin Sabok - 2012 - Annals of Pure and Applied Logic 163 (12):1748-1764.
    We prove that if f is a partial Borel function from one Polish space to another, then either f can be decomposed into countably many partial continuous functions, or else f contains the countable infinite power of a bijection that maps a convergent sequence together with its limit onto a discrete space. This is a generalization of a dichotomy discovered by Solecki for Baire class 1 functions. As an application, we provide a characterization of functions which are countable unions (...)
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  46.  24
    No Borel Connections for the Unsplitting Relations.Heike Mildenberger - 2002 - Mathematical Logic Quarterly 48 (4):517-521.
    We prove that there is no Borel connection for non-trivial pairs of unsplitting relations. This was conjectured in [3].
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  47.  16
    Weak Borel Chromatic Numbers.Stefan Geschke - 2011 - Mathematical Logic Quarterly 57 (1):5-13.
    Given a graph G whose set of vertices is a Polish space X, the weak Borel chromatic number of G is the least size of a family of pairwise disjoint G -independent Borel sets that covers all of X. Here a set of vertices of a graph G is independent if no two vertices in the set are connected by an edge.We show that it is consistent with an arbitrarily large size of the continuum that every closed graph (...)
    Direct download  
     
    Export citation  
     
    Bookmark   1 citation  
  48.  47
    A Borel Reducibility Theory for Classes of Countable Structures.Harvey Friedman & Lee Stanley - 1989 - Journal of Symbolic Logic 54 (3):894-914.
    We introduce a reducibility preordering between classes of countable structures, each class containing only structures of a given similarity type (which is allowed to vary from class to class). Though we sometimes work in a slightly larger context, we are principally concerned with the case where each class is an invariant Borel class (i.e. the class of all models, with underlying set $= \omega$, of an $L_{\omega_1\omega}$ sentence; from this point of view, the reducibility can be thought of as (...)
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark   42 citations  
  49.  13
    Borel Equivalence Relations Which Are Highly Unfree.Greg Hjorth - 2008 - Journal of Symbolic Logic 73 (4):1271-1277.
    There is an ergodic, measure preserving, countable Borel equivalence relation E on a standard Borel probability space (X, µ) such that E\c is not essentially free on any conull C ⊂ X.
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  50. New Borel Independence Results.Harvey Friedman - manuscript
    S. Adams, W. Ambrose, A. Andretta, H. Becker, R. Camerlo, C. Champetier, J.P.R. Christensen, D.E. Cohen, A. Connes. C. Dellacherie, R. Dougherty, R.H. Farrell, F. Feldman, A. Furman, D. Gaboriau, S. Gao, V. Ya. Golodets, P. Hahn, P. de la Harpe, G. Hjorth, S. Jackson, S. Kahane, A.S. Kechris, A. Louveau,, R. Lyons, P.-A. Meyer, C.C. Moore, M.G. Nadkarni, C. Nebbia, A.L.T. Patterson, U. Krengel, A.J. Kuntz, J.-P. Serre, S.D. Sinel'shchikov, T. Slaman, Solecki, R. Spatzier, J. Steel, D. Sullivan, S. (...)
     
    Export citation  
     
    Bookmark  
1 — 50 / 1000