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

Bookmarks Report an error
Multi angle
Authors : ... (Author of the conference)
... (Publisher )

Loading the player...

Abstract : 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.

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

    Information on the Video

    Language : English
    Available date : 07/07/2016
    Conference Date : 23/06/2016
    Subseries : Research talks
    arXiv category : Computer Science ; Logic
    Mathematical Area(s) : Logic and Foundations ; Computer Science
    Format : MP4 (.mp4) - HD
    Video Time : 00:41:43
    Targeted Audience : Researchers
    Download : https://videos.cirm-math.fr/2016-06-23_Nies.mp4

Information on the Event

Event Title : Computability, randomness and applications / Calculabilité, hasard et leurs applications
Dates : 20/06/2016 - 24/06/2016
Event Year : 2016
Event URL : http://conferences.cirm-math.fr/1408.html

Citation Data

DOI : 10.24350/CIRM.V.19007003
Cite this video as: (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

See Also

Bibliography

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



Bookmarks Report an error