Seminar
| Parent Program: | |
|---|---|
| Location: | SLMath: Online/Virtual |
To participate in this seminar, please register here: https://www.msri.org/seminars/25206
Hilbert’s Tenth Problem was the only decision problem among his twenty-three problems. Precise mathematical theory of (in)computability and its interaction with number theory led to the negative solution of the problem. The seminar will focus on modern topics on computability-theoretic phenomena in number-theoretic and other algebraic and model-theoretic structures.
Cardinal Characteristics And The Generic Muchnik Degrees
To participate in this seminar, please register here: https://www.msri.org/seminars/25206
In set theory, cardinal characteristics of the continuum are uncountable cardinals that are consistently strictly between aleph_0 and 2^aleph_0, which capture a combinatorial property of the set of reals in the model of set theory. For example, the dominating number is the least cardinality of a set F of functions so that every member of omega^omega is dominated by a member of F. The bounding number is the least cardinality of a set F so that for every g in omega^omega there is some f in F which escapes g.
Rupprecht and Brendle, Brooke-Taylor, Ng, Nies brought the ideas of cardinal characteristics of the continuum into computability theory. In this setting, largeness of a set is translated into complexity of an oracle. For example, the analog of the dominating number is the set of degrees which can compute a function that escapes every computable function. The analog of the bounding number is the set of degrees which can compute a function which dominates every computable function. (These may seem inverted, but we consider the oracle to be “big” if the collection of computable functions is not “large” in the set-theoretic sense relative to the oracle.)
I will present another approach to understanding generic Muchnik degrees, this time in terms of cardinal characteristics. We define the generic co-spectrum of a structure to be the collection of f in omega^omega which are computable from every countable copy of A in some/any generic extension V[G] which makes A countable. We then say, for example, that a structure is self-dominating if every presentation of A in V[G] computes a function which dominates every member of its co-spectrum. We also define the analogous notion of being self-escaping. We will see that Cantor space is not self-escaping, while Baire space is even self-dominating. We use this to give a natural construction of a degree strictly between the two which is self-escaping but not self-dominating. This gives a new intermediate structure. We note that this intermediate structure has the same complexity profile as Cantor space, so it cannot be separated using complexity profiles. (Joint work with Joseph S. Miller, Noah Schweber, and Mariya Soskova.)
No Notes/Supplements UploadedCardinal Characteristics And The Generic Muchnik Degrees
| H.264 Video | 25182_28680_8484_Cardinal_Characteristics_and_the_Generic_Muchnik_Degrees.mp4 |