Kihara, Ng, and Pauly have studied various classes that arise from different spaces. They show that any enumeration degree is contained in a class arising from some computable, submetrizable space, and that no T1-space contains all enumeration degrees. Similarly, they separate T2-classes from T1-classes, and T2.5-classes from T2-classes. We give separations of the T2.5-classes from the submetrizable classes using the Arens co-d-CEA degrees and the Roy halfgraph above degrees.
We will continue in this direction showing (non)reductions between problems related to the Cantor-Bendixson theorem with particular attention paid to classifying them for every computable Polish space X. This leads us to the result that, while PKX and wCBX (i.e., same as PKX but where the output also provides a listing of the elements in the scattered part) are equivalent for any space X that we consider, the problem CBX (i.e., same as wCBX but where the output provides also the cardinality of the scattered part) "almost" splits into two Weihrauch degrees, one having as representative PKX and the other having CBNN.
This is joint work with Alberto Marcone and Manlio Valenti.
We present a new result toward showing the decidability by proving that no so-called Ahmad triple can exist. At the end, we will sketch how this proof can be obtained by varying a direct proof of Ahmad (1990) that there is no symmetric Ahmad pair; on the other hand, we also show that our result cannot be strengthened to so-called weak Ahmad triples.
Our work centers on the characterization of reductions between Π12-problems P and Q in terms of winning strategies in certain games. These characterizations were originally introduced by Hirschfeldt and Jockusch in [1]. I will discuss extensions and generalizations of these characterizations, including a certain notion of compactness that allows us, for strategies satisfying particular conditions, to bound the number of moves it takes to win. This bound is independent of the instance of the problem P being considered. This allows us to develop the idea of Weihrauch and generalized Weihrauch reductions over some base theory. Here, we will focus on the base theory RCA0 and the weaker system RCA*0. In this talk, I will explore these notions of reductions among various principles, including bounding and induction principles. I will present a metatheorem that allows us to obtain many nonreductions between these principles.
[1] D. R. Hirschfeldt and C. G. Jockusch, Jr.: On notions of computability-theoretic reduction between Π12-principles. Journal of Mathematical Logic 16 (1650002), 59 pp. (2016)
I will present the generalization of the point-to-set principle from Euclidean spaces to arbitrary separable metric spaces and to a large class of gauge families.
Then I will demonstrate the power of our extended point-to-set principle by using it to prove new theorems about classical fractal dimensions in hyperspaces.
(The results presented are joint work with Jack Lutz and Neil Lutz).
This talk is aimed at a general audience of mathematical logicians. You don't need to know what most of the terms in the last paragraph mean. It would be good to know the basics of category theory, including examples of functors from the category of sets to itself. To get the most out of it, it might be good to look up the connection of definition by recursion on the natural numbers with initial algebras of the functor 1 + X on Set.
This talk reports on joint work with several groups in the past 5-10 years.
This is joint work with Simon Huttegger and Sean Walsh.
The dimension spectrum sp(L) is the set of all effective dimensions of individual points on L. Jack Lutz, in the early 2000s, posed the dimension spectrum conjecture. This conjecture states that, for every line L, sp(L) contains a unit interval. In this talk, we present a proof of the dimension spectrum conjecture. We also discuss its relation to open problems in geometric measure theory, and avenues for future research.
We investigate the cohesive powers of computable linear orders, with special emphasis on computable copies of ω. If L is a computable copy of ω that is computably isomorphic to the standard presentation of ω, then every cohesive power of L has order-type ω+ζη. However, there are computable copies of ω, necessarily not computably isomorphic to the standard presentation, having cohesive powers not elementarily equivalent to ω+ζη. For example, we show that there is a computable copy of ω with a cohesive power of order-type ω+η. Our most general result is that if X ⊆ N-{0} is a Boolean combination of Σ02-sets, thought of as a set of finite order-types, then there is a computable copy of ω with a cohesive power of order-type ω+σ(X ∪ {ω+ζη+ω*}), where σ(X ∪ {ω+ζη+ω*}) denotes the shuffle sum of the order-types in X and the order-type ω+ζη+ω*. Furthermore, if X is finite and non-empty, then there is a computable copy of ω with a cohesive power of order-type ω+σ(X).
This is a joint work with Rumen Dimitrov, Valentina Harizanov, Andrey Morozov, Paul Shafer and Stefan Vatev.
It was partially supported by Bulgarian National Science Fund KP-06-Austria-04/06.08.2019, FNI-SU 80-10-136/26.03.2021.
Joint work with Klaus Ambos-Spies, Martin Monath and Keng Meng Ng.
The Σ02-enumeration degrees are analogous to the computably enumerable (c.e.) Turing degrees, but these structures are not elementarily equivalent as partial orders. Indeed, Ahmad showed that there are incomparable Σ02-enumeration degrees a and b such that if c < a, then c < b, implying that a cannot be expressed as the join of two degrees below it. This stands in contrast to the Sacks Splitting Theorem for the c.e. Turing degrees.
One can view Ahmad's result as a two-quantifier sentence in the language of partial orders which holds in the Σ02-enumeration degrees. While it is easy to compute whether a given one-quantifier sentence is true in the Σ02-enumeration degrees (because all finite partial orders embed), the corresponding task for two-quantifier sentences (which corresponds to an extension of embeddings problem) is not known to be algorithmically decidable. Towards solving this problem, we investigate the extent to which Ahmad's result can be generalized. For instance, we show that it does not generalize to triples: For any incomparable Σ02-enumeration degrees a, b and c, there is some x such that one of the following holds: x is below a but not below b, or x is below b but not below c.
We shall also discuss speculative generalizations of the above result, and how they may lead to an algorithm which decides a class of two-quantifier sentences in the Σ02-enumeration degrees.
The theorem is due to David Marker building on work by Scott, Tennenbaum, Matiyasevich, Solovay, Goncharov, and Peretyatkin. I promise no original results.