Representations of measurable sets in computable measure theory

This article is a fundamental study in computable measure theory. We use the framework of TTE, the representation approach, where computability on an abstract set X is defined by representing its elements with concrete "names", possibly countably infinite, over some alphabet {\Sigma}. As a basic computability structure we consider a computable measure on a computable $\sigma$-algebra. We introduce and compare w.r.t. reducibility several natural representations of measurable sets. They are admissible and generally form four different equivalence classes. We then compare our representations with those introduced by Y. Wu and D. Ding in 2005 and 2006 and claim that one of our representations is the most useful one for studying computability on measurable functions.

• Publication year

  2014

• Venue

  Log. Methods Comput. Sci.

• Publication date

  2014-07-13

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.2168/LMCS-10(3:7)2014arXiv 1407.3485
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Computability of the ergodic decomposition

  2013cited by this paper
• Computability of Probability Distributions and Characteristic Functions

  2013cited by this paper
• Computability on random events and variables in a computable probability space

  2012cited by this paper
• Computability of the Radon-Nikodym Derivative

  2011cited by this paper
• Algorithmic tests and randomness with respect to a class of measures

  2011cited by this paper
• A constructive version of Birkhoff's ergodic theorem for Martin-Löf random points

  2010cited by this paper
• Effective Choice and Boundedness Principles in Computable Analysis

  2009cited by this paper
• Randomness on Computable Probability Spaces—A Dynamical Point of View

  2009cited by this paper
• Weihrauch degrees, omniscience principles and weak computability

  2009cited by this paper
• Absolutely non-computable predicates and functions in analysis†

  2009cited by this paper
• Computable de Finetti measures

  2009cited by this paper
• Elementary Computable Topology

  2009influential reference
• Dynamics and abstract computability: Computing invariant measures

  2009cited by this paper
• Notions of Probabilistic Computability on Represented Spaces

  2008cited by this paper
• A Tutorial on Computable Analysis

  2008influential reference
• Computability of probability measures and Martin-Löf randomness over metric spaces

  2007cited by this paper
• Effective symbolic dynamics, random points, statistical behavior, complexity and entropy

  2007cited by this paper
• A computable approach to measure and integration theory

  2007cited by this paper
• Admissible representations for probability measures

  2007cited by this paper
• Computability of measurable sets via effective topologies

  2006cited by this paper
• Computability of measurable sets via effective metrics

  2005influential reference
• A Computable Version of the Daniell-Stone Theorem on Integration and Linear Functionals

  2005cited by this paper
• Computable Analysis

  2005influential reference
• Uniform test of algorithmic randomness over a general space

  2003cited by this paper
• Admissible representations for continuous computations

  2003cited by this paper
• Computability on subsets of metric spaces

  2003influential reference
• Effectivity in Spaces with Admissible Multirepresentations

  2002cited by this paper
• Extended admissibility

  2002cited by this paper
• Admissible representations for continuous computations

  2002cited by this paper
• Computability on Random Variables

  1999cited by this paper
• Computability on the Probability Measureson the Borel Sets of the Unit Interval

  1997cited by this paper
• Handbook of Analysis and Its Foundations

  1996cited by this paper
• Domain theory and integration

  1994cited by this paper
• The Degrees of Discontinuity of some Translators Between Representations of the Real Numbers

  1992cited by this paper
• Real Analysis: Modern Techniques and Their Applications

  1984influential reference
• Wahrscheinlichkeitstheorie und Grundzuge der Maßtheorie

  1968cited by this paper

• Computable Measure Theory and Algorithmic Randomness

  2021cites this paper
• Computability of Subsets of Metric Spaces

  2021cites this paper
• On the logical and computational properties of the Vitali covering theorem

  2019cites this paper
• Representations in measure theory: between a non-computable rock and a hard to prove place.

  2019cites this paper
• Computing Haar Measures

  2019cites this paper
• On the close interaction between algorithmic randomness and constructive/computable measure theory

  2018cites this paper
• From propositional logic to plausible reasoning: A uniqueness theorem

  2017cites this paper
• Computability on measurable functions

  2016influential citation
• Computable Qualitative Probability

  year unknowncites this paper