Multi angle

H 1 Randomness connecting to set theory and to reverse mathematics

Auteurs : Nies, André (Auteur de la Conférence)
CIRM (Editeur )

    Loading the player...

    Résumé : I will discuss two recent interactions of the field called randomness via algorithmic tests. With Yokoyama and Triplett, I study the reverse mathematical strength of two results of analysis. (1) The Jordan decomposition theorem says that every function of bounded variation is the difference of two nondecreasing functions. This is equivalent to ACA or to WKL, depending on the formalisation. (2) A theorem of Lebesgue states that each function of bounded variation is differentiable almost everywhere. This turns out to be equivalent WWKL (with some fine work left to be done on the amount of induction needed). The Gamma operator maps Turing degrees to real numbers; a smaller value means a higher complexity. This operator has an analog in the field of cardinal characteristics along the lines of the Rupprecht correspondence [4]; also see [1]. Given a real p between 0 and 1/2, d(p) is the least size of a set G so that for each set x of natural numbers, there is a set y in G such that x and y agree on asymptotically more than p of the bits. Clearly, d is monotonic. Based on Monin's recent solution to the Gamma question (see [3] for background, and the post in [2] for a sketch), I will discuss the result with J. Brendle that the cardinal d(p) doesn't depend on p. Remaining open questions in computability (is weakly Schnorr engulfing equivalent to "Gamma = 0"?) nicely match open questions about these cardinal characteristics.

    Codes MSC :
    03D25 - Recursively enumerable sets and degrees
    03F60 - Constructive and recursive analysis
    68Q30 - Algorithmic information theory (Kolmogorov complexity, etc.)
    03D32 - Algorithmic randomness and dimension

      Informations sur la Vidéo

      Langue : Anglais
      Date de publication : 07/07/2016
      Date de captation : 23/06/2016
      Collection : Computer Science ; Logic and Foundations
      Sous collection : Research talks
      Format : MP4
      Domaine : Logic and Foundations ; Computer Science
      Durée : 00:41:43
      Audience : Chercheurs ; Doctorants , Post - Doctorants
      Download : https://videos.cirm-math.fr/2016-06-23_Nies.mp4

    Informations sur la rencontre

    Nom de la rencontre : Computability, randomness and applications / Calculabilité, hasard et leurs applications
    Organisateurs de la rencontre : Bienvenu, Laurent ; Jeandel, Emmanuel ; Porter, Christopher
    Dates : 20/06/2016 - 24/06/2016
    Année de la rencontre : 2016
    URL Congrès : http://conferences.cirm-math.fr/1408.html

    Citation Data

    DOI : 10.24350/CIRM.V.19007003
    Cite this video as: Nies, André (2016). Randomness connecting to set theory and to reverse mathematics. CIRM. Audiovisual resource. doi:10.24350/CIRM.V.19007003
    URI : http://dx.doi.org/10.24350/CIRM.V.19007003

    Voir aussi


    1. [1] Brendle, J., Brooke-Taylor, A., Ng, K.M., & Nies, A. (2013). An analogy between cardinal characteristics and highness properties of oracles. In X. Zhao, Q. Feng, B. Kim, & L. Yu (Eds.), Proceedings of the 13th Asian Logic Conference (pp. 1–28). Singapore: World Scientific - http://www.worldscientific.com/worldscibooks/10.1142/9596

    2. [2] Nies, A. Logic Blog 2016. In cs.auckland.ac.nz/?nies - https://www.cs.auckland.ac.nz/~nies/

    3. [3] Monin, B., & Nies, A. (2015). A unifying approach to the Gamma question. In Proceedings of the 2015 30th Annual ACM/IEEE Symposium on Logic in Computer Science (pp. 585-596). Washington: IEEE press - http://dx.doi.org/10.1109/LICS.2015.60

    4. [4] Rupprecht, N. Effective correspondents to cardinal characteristics in Cicho?'s diagram. PhD thesis. Ann Arbor: University of Michigan, 2010 - http://hdl.handle.net/2027.42/77915

Titres de périodiques et e-books électroniques (Depuis le CIRM)

Ressources Electroniques

Books & Print journals

Recherche avancée