En poursuivant votre navigation sur ce site, vous acceptez l'utilisation d'un simple cookie d'identification. Aucune autre exploitation n'est faite de ce cookie. OK
1

Randomness connecting to set theory and to reverse mathematics

Sélection Signaler une erreur
Multi angle
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

    Réalisateur : Hennenfent, Guillaume
    Langue : Anglais
    Date de publication : 07/07/2016
    Date de captation : 23/06/2016
    Sous collection : Research talks
    arXiv category : Computer Science ; Logic
    Domaine : Logic and Foundations ; Computer Science
    Format : MP4 (.mp4) - HD
    Durée : 00:41:43
    Audience : Researchers
    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

Données de citation

DOI : 10.24350/CIRM.V.19007003
Citer cette vidéo: 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

Bibliographie

  • [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] Nies, A. Logic Blog 2016. In cs.auckland.ac.nz/?nies - https://www.cs.auckland.ac.nz/~nies/

  • [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] 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



Sélection Signaler une erreur