Réunion d'hiver SMC 2019

Toronto, 6 - 9 décembre 2019

Théorie de la calculabilité
Org: Barbara Csima (Waterloo) et Antonio Montalban (The University of California, Berkeley)
[PDF]

RACHAEL ALVIR, University of Notre Dame Scott Complexity and Finitely $\alpha$-generated Structures [PDF]

Every countable structure is $\aleph_0$-categorical in $L_{\omega_1 \omega}$ and axiomatized by a single sentence called its \emph{Scott Sentence}. A normal form exists for formulas of $L_{\omega_1 \omega}$, so each formula is equivalent to a $\Pi_{\alpha}$ or $\Sigma_{\alpha}$ one for some $\alpha$. A conjunction of a $\Sigma_{\alpha}$ and a $\Pi_{\alpha}$ sentence is $d$-$\Sigma_{\alpha}$.

Every finitely generated structure $A$ has a $\Sigma_3$ Scott sentence, but combining the results of \cite{harrho} and \cite{aletal} shows $A$ has a $d$-$\Sigma_2$ Scott sentence iff $A$ is self-reflective iff a generating tuple has a $\Pi_1$-definable automorphism orbit. In this talk, we show a structure with a $\Sigma_{\alpha + 2}$ Scott sentence and no $\Pi_{\alpha + 1 }$ Scott sentence generalizes a finitely generated structure, and call such structures \emph{finitely $\alpha$-generated}. We show a finitely $\alpha$-generated structure has a $d$-$\Sigma_{\alpha + 1}$ Scott sentence iff it is $\alpha$-reflective iff some $\alpha$-generator has a $\Pi_{\alpha}$-definable automorphism orbit.

Montalb\'an has suggested (recent folklore) that a structure $A$'s complexity, in the sense intended by Scott rank, is measured by computing the least $\lambda, \Gamma$ such that $A$ has a $\Sigma_{\lambda}$ Scott sentence and some tuple witnessing this fact has a $\Gamma$-definable automorphism orbit. Our result shows $A$'s least complexity Scott sentence determines this information. \begin{thebibliography}{10}

\bibitem{aletal} {\scshape Rachael Alvir, Julia Knight, and Charles McCoy}, {\itshape Complexiy of Scott sentences}, {\bfseries\itshape Forthcoming.} \bibitem{harrho} {\scshape Matthew Harrison-Trainor and Meng-che Ho}, {\itshape On optimal Scott sentences of finitely generated algebraic structures}, {\bfseries\itshape Proceedings of the American mathematical society}, vol.~146 (2018), no.~10, pp.~4473--4485. \end{thebibliography}

DAVID BELANGER, Ghent University A more uniform Friedberg-Muchnik theorem [PDF]

We construct a pair of Turing-incomparable r.e. sets, in a way that works both in models of $I\Sigma_1$ and in models of $B\Sigma_1$ without $I\Sigma_1$. This improves a result of Chong and Mourad.

DOUG CENZER The Rate of Randomness Extraction [PDF]

This paper investigates the extraction rate for continuous functions $F$ on the Cantor space $2^N$. This measures the relative amount of input from $X$ needed to determine a given length of the output $Y = F(X)$. In particular, we look at the extraction rates for the computing randoms using the Levin-Kautz and other methods. We examine the average extraction rates for total and almost total computable functionals $F$, as well as the extraction rates on random inputs. We also examine the average extraction rates for random continuous functions.

CHRIS CONIDIS, College of Staten Island The combinatorics of minimal prime ideals in Noetherian rings [PDF]

We analyze the reverse mathematical strength of the theorem from Commutative Algebra that says a Neotherian ring has finitely many minimal prime ideals. In particular we will show that this statement follows from the Chain-Antichain Principle but does not follow from weak K\"onig's Lemma.

PAUL-ELLIOT ANGLES D'AURIAC, LACL Infinite computations, randomness and genericity [PDF]

The study of Infinite-Time Turing machines, ITTMs for short, goes back to a paper by Hamkins and Lewis. Informally these machines work like regular Turing machines, with in addition that the time of computation can be any ordinal. This model of infinite time computation differs from the main other definition for infinite computations, $\alpha$-recursion, which corresponds to $\Sigma_1$-definability in $L_\alpha$. In the former, there is no bound in the time of computation allowed, but a bound on the storage space as it is not possible to keep track of all the previous stages. In the latter, all previous stages are accessible but the time of computation is bounded in advance.

Recently Carl and Schlicht used the ITTM model to extend algorithmic randomness and effective genericity notions in these settings. In this talk, we present a general framework to study randomness and genericity within Godel's constructible hierarchy. Using this framework, we answered several of Carl and Schlicht's open questions and we asked new ones. In particular the question about the separation of two randomness notions related to ITTMs and $\alpha$-recursion is particularly interesting. Intuitively, these notion seems to be different, as their $\Pi^1_1$-analogue do, but the proof does not lift. In order to argue that it is not absurd to think that these two randomness notions may actually coincide, we showed that it is the case for their categorical analogues.

DAMIR DZHAFAROV, Univerisity of Connecticut Reverse math and the game-theoretic framework [PDF]

Hirschfeldt and Jockusch (2016) introduced a two-player game in which winning strategies for one or the other player precisely correspond to implications and non-implications between given Pi12 principles over omega-models of RCA0. They also introduced a version of this game that similarly captures provability over (full) RCA0. We generalize this game for provability over arbitrary subsystems of second-order arithmetic, and establish a compactness argument that shows that certain winning strategies can always be chosen to win in a number of moves bounded by a number independent of the instance of the principles being considered. Our compactness result also generalizes an old proof-theoretic fact due to H. Wang, and has a number of other applications. This is joint work with Denis Hirschfeldt and Sarah Reitzes.

VALENTINA HARIZANOV, George Washington University Degrees of decidable and computable categoricity [PDF]

Complexity of isomorphisms of decidable and, more generally, computable structures plays an important role in computable model theory. The degree of decidable categoricity of a decidable model is the least Turing degree, if it exists, which computes at least one isomorphism between the model and each of its decidable isomorphic copies. The degree of computable categoricity of a computable model is defined similarly by considering computable instead of decidable isomorphic copies. We will present some recent results on the degrees of computable categoricity and the degrees of decidable categoricity for structures from several natural classes.

DENIS HIRSCHFELDT, University of Chicago A minimal pair in the generic degrees [PDF]

I will outline the construction of a minimal pair in the generic degrees, which contrasts with Igusa's result that there are no minimal pairs for relative generic computability. I will also discuss several remaining related open questions.

JULIA KNIGHT, University of Notre Dame Copying one of a pair of structures [PDF]

I will talk on joint work with Rachael Alvir and Timothy Burchfield on the following problem.

Problem: For a pair of structures $\mathcal{A}$ and $\mathcal{B}$, when is there a uniform effective procedure that, given copies of both structures, unlabeled, always produces a copy of $\mathcal{A}$?

We have partial results.

JUN LE GOH, University of Wisconsin-Madison Inseparable $\Pi^1_1$ sets [PDF]

We investigate analogs of the theory of effectively inseparable pairs of recursively enumerable sets to $\Pi^1_1$ sets of numbers and $\Pi^1_1$ sets of reals. These are used to derive completeness results, such as an unpublished result of Harrington about jump hierarchies.

JUSTIN MILLER, University of Notre Dame Intrinsic Density and Intrinsically Small Sets [PDF]

One potentially troubling feature in the study of asymptotic computability is that every nonzero Turing degree contains a set which is ``almost computable'' in an artificially unenlightening way. In response, Astor introduced the notion of intrinsic density, i.e. asymptotic density invariant under computable permutation, with the goal of ensuring that ``almost computable'' sets cannot be achieved by trivial codings. We discuss some properties of intrinsically small sets (those with intrinsic density 0), and show that by requiring an error set to be intrinsically small rather than just small in the traditional asymptotic computability sense we avoid the aforementioned problem. We also briefly remark upon which reals can be achieved as the intrinsic density of a set.

RUSSELL MILLER, Queens College & CUNY Graduate Center A Computability-Theoretic Proof of Lusin's Theorem [PDF]

In real analysis, Lusin's Theorem states that for every Borel-measurable function $f:\mathbb R\to\mathbb R$ and every $\epsilon >0$, there exists a continuous function $g:\mathbb R\to\mathbb R$ that equals $f$ except on a set of measure $<\epsilon$. This is often viewed as one of Littlewood's Three Principles: every measurable function is almost continuous. We will present a proof of this theorem using computable analysis, centered around the relativization of the known fact that for computable ordinals $\alpha$, almost all subsets $A$ of $\omega$ have the property that $A^{(\alpha)}\leq_T \emptyset^{(\alpha)}\oplus A$.

LUDOVIC PATEY, CNRS SRT22 does not imply RT22 over omega-models [PDF]

Ramsey's theorem for pairs and two colors ($\mathsf{RT}^2_2$) asserts the existence, for every 2-coloring of the pairs of integers, of an infinite set of integers, all the pairs of which are monochromatic. $\mathsf{SRT}^2_2$ is the restriction of Ramsey's theorem for pairs to stable 2-colorings, that is, 2-colorings with an asymptotic behavior. It was a long-standing open question whether $\mathsf{SRT}^2_2$ implies $\mathsf{RT}^2_2$ over standard models. In this talk, we present the various techniques used in the proof separating $\mathsf{SRT}^2_2$ from $\mathsf{RT}^2_2$. This is a joint work with Benoit Monin.

JAN REIMANN, Pennsylvania State University Turing Degrees and Randomness for Continuous Measures [PDF]

We study degree-theoretic properties of reals that are not random with respect to any continuous probability measure (NCR). To this end, we introduce a family of Hausdorff measures based on the dissipation function of a continuous probability measure, parameterized by a natural number $n$. The corresponding Solovay tests then induce an $\omega$-hierarchy of randomness tests with respect to a continuous measure. We use this hierarchy to prove the existence of NCR elements in a wide range of Turing degrees. We also use it to study the relation between continuous randomness and initial segment Kolmogorov complexity. This is joint work with Mingyang Li.

DINO ROSSEGGER, University of Waterloo Analytic complete equivalence relations and their degree spectra [PDF]

A well known result in descriptive set theory by Louveau and Rosendal shows that the bi-embeddability relation on the class of graphs is a $\pmb \Sigma^1_1$-complete equivalence relation with respect to Borel reducibility. We give a Borel reduction from bi-embeddability on graphs to elementary bi-embeddability on graphs and thus obtain that elementary bi-embeddability on graphs is also $\pmb \Sigma^1_1$-complete. An analysis of this reduction shows that it is computable, i.e., can be realized by a Turing operator, and that it is faithful on equivalence classes. These facts let us obtain results on the relationship between the degree spectra under these equivalence relations, i.e., the sets of Turing degrees of the bi-embeddable, respectively, elementary bi-embeddable copies of a given structure. They also motivate the study of a new type of reduction which allows us to study the relationship between degree spectra relative to different equivalence relations and in different classes of structures.

NOAH SCHWEBER Realizability and computable structures [PDF]

I will present some results on an analogue of realizability for computable infinitary formulas in general computable structures.

THEODORE SLAMAN, University of California Berkeley The AE-theory of the Enumeration Degrees [PDF]

It is open whether there is a decision procedure for the AE-theory of the Enumeration Degrees. We will exhibit a decision procedure for the Extension of Embeddings Problem and a conjectured strengthening to decide the AE-theory.

REED SOLOMON, University of Connecticut Relatively decidable theories [PDF]

A computably enumerable theory $T$ is relatively decidable if for every countable model of $T$, the elementary diagram is computable from the atomic diagram. In this talk, I will discuss joint work with Jennifer Chubb and Russell Miller about relatively decidable theories and about the uniform version of this property. Recently, Matthew Harrison-Trainor has disproved a conjecture characterizing relatively decidable theories by showing that the index set for these theories is $\Pi^1_1$ complete.

LINDA WESTRICK, Penn State University Completely determined Borel sets and measurability [PDF]

We consider the reverse math strength of the statement $\mathsf{CD}$-$\mathsf M$: ``Every completely determined Borel set is measurable.'' Over $\mathsf{WWKL}$, we obtain the following results analogous to the previously studied category case. First, $\mathsf{CD}$-$\mathsf M$ lies strictly between $\mathsf{ATR}_0$ and $\mathsf{L}_{\omega_1,\omega}$-$\mathsf{CA}$. Second, any $\omega$-model of $\mathsf{CD}$-$\mathsf{M}$ must be closed under hyperarithmetic reduction. Finally, whenever $M\subseteq 2^\omega$ is the second-order part of an $\omega$-model of $\mathsf{CD}$-$\mathsf M$, then for every $Z \in M$, there is a $G \in M$ such that $G$ is $\Delta^1_1$-random relative to $Z$.

JACK YOON, University of Hawaii at Manoa Reverse Mathematical Strength of Grätzer-Schmidt Theorem [PDF]

Grätzer-Schmidt theorem is a representation-theoretic result in lattice theory stating that every complete and compactly-generated lattice is isomorphic to the congruence lattice of an algebra. We assess the strength of this theorem in the context of reverse mathematics.

haut de la page