UW Logic Seminar 2016-17

• Tuesday, Sept. 6th, 4PM, Joseph S. Miller, UW
  Title: A derivation on the field of d.c.e. reals
  Barmpalias and Lewis-Pye recently proved that if $\alpha$ and $\beta$ are (Martin-Löf) random left-c.e. reals with left-c.e. approximations $\{\alpha_s\}_{s\in\omega}$ and $\{\beta_s\}_{s\in\omega}$, then \[ \newcommand{\d}{\partial\kern 0.05em} \frac{\d\alpha}{\d\beta} = \lim_{s\to\infty} \frac{\alpha-\alpha_s}{\beta-\beta_s}. \] converges and is independent of the choice of approximations. Furthermore, they showed that $\d\alpha/\d\beta = 1$ if and only if $\alpha-\beta$ is nonrandom; $\d\alpha/\d\beta>1$ if and only if $\alpha-\beta$ is a random left-c.e. real; and $\d\alpha/\d\beta<1$ if and only if $\alpha-\beta$ is a random right-c.e. real.
  
  We extend their results to the d.c.e. reals, which clarifies what is happening. The extension is straightforward. Fix a random left-c.e. real $\Omega$ with approximation $\{\Omega_s\}_{s\in\omega}$. If $\alpha$ is a d.c.e. real with d.c.e. approximation $\{\alpha_s\}_{s\in\omega}$, let \[ \d\alpha = \frac{\d\alpha}{\d\Omega} = \lim_{s\to\infty} \frac{\alpha-\alpha_s}{\Omega-\Omega_s}. \] As above, the limit exists and is independent of the choice of approximations. Now $\d\alpha=0$ if and only if $\alpha$ is nonrandom; $\d\alpha>0$ if and only if $\alpha$ is a random left-c.e. real; and $\d\alpha<0$ if and only if $\alpha$ is a random right-c.e. real.
  
  As we have telegraphed by our choice of notation, $\d$ is a derivation on the field of d.c.e. reals. In other words, $\d$ preserves addition and satisfies the Leibniz law: \[ \d(\alpha\beta) = \alpha\,\d\beta + \beta\,\d\alpha. \] (However, $\d$ maps outside of the d.c.e. reals, so it does not make them a differential field.) We will see how the properties of $\d$ encapsulate much of what we know about randomness in the left-c.e. and d.c.e. reals. We also show that if $f\colon\mathbb{R}\to\mathbb{R}$ is a computable function that is differentiable at $\alpha$, then $\d f(\alpha) = f'(\alpha)\,\d\alpha$. This allows us to apply basic identities from calculus, so for example, $\d\alpha^n = n\alpha^{n-1}\,\d\alpha$ and $\d e^\alpha = e^\alpha\,\d\alpha$. Since $\d\Omega=1$, we have $\d e^\Omega = e^\Omega$.
  
  Given a derivation on a field, the elements that it maps to zero also form a field: the field of constants. In our case, these are the nonrandom d.c.e. reals. We show that, in fact, the nonrandom d.c.e. reals form a real closed field. Note that it was not even known that the nonrandom d.c.e. reals are closed under addition, and indeed, it is easy to prove the convergence of $\d\alpha/\d\beta$ from this fact. In contrast, it has long been known that the nonrandom left-c.e. reals are closed under addition ([Demuth 1975] and [Downey, Hirschfeldt, and Nies 2002]). While also nontrivial, this fact seems to be easier to prove. Towards understanding this difference, we show that the real closure of the nonrandom left-c.e. reals is strictly smaller than the field of nonrandom d.c.e. reals. In particular, there are nonrandom d.c.e. reals that cannot be written as the difference of nonrandom left-c.e. reals; despite being nonrandom, they carry some kind of intrinsic randomness.


• Tuesday, Sept. 13th, 4PM, Noah Schweber, UW
  Title: Computable structure theory of ordinals
  Let $\mathcal{A}$ and $\mathcal{B}$ be countable structures in (possibly different) finite languages. If we want to compare the computability-theoretic complexity of $\mathcal{A}$ and $\mathcal{B}$, one natural way to do so is via Muchnik (weak) reducibility: $\mathcal{A}\ge_w\mathcal{B}$ if every copy of $\mathcal{A}$ computes a copy of $\mathcal{B}$. This notion has a number of nice properties, and has been studied reasonably extensively. Although Muchnik reducibility in general is quite complicated, it is well understood in certain cases. For instance, the question of which countable ordinals are Muchnik-above which others is completely understood. Say that an ordinal $\alpha$ is admissible if $L_\alpha$ satisfies the theory $KP$ (roughly: set theory with replacement and separation weakened to “effective” formulas). Then $\alpha\ge_w\beta$ iff $\beta$ is less than the least admissible above $\alpha$. This is a consequence of a theorem of Sacks: that for every admissible $\alpha$, there is some real $r$ such that $\alpha$ is the least ordinal with no $r$-computable copy, and conversely any such ordinal is admissible.
  
  However, although the Muchnik picture is completely understood, there are still many interesting questions about the computability-theoretic behavior of ordinals which are left open. For example, here are two broad directions one can take:
  
  

  • What if I want to compute several ordinals simultaneously?
  • What if I want to compute ordinals uniformly - that is, I specify a Turing reduction independently of which copy I am given?

  
  It turns out that these questions bring in ideas from set theory - the second, in particular, interacts fruitfully with ideas about the computability of uncountable structures. The goal of this talk is to motivate these set-theoretic methods by presenting their applications to down-to-earth problems in computable structure theory.


• Tuesday, Sept. 20th, 4PM Uri Andrews, UW
  Title: Joins and meets in the structures of ceers
  (All work is joint with Andrea Sorbi) A ceer is a computably enumerable equivalence relation on $\omega$. We consider a ceer $R$ to be computably reducible ($\leq_c$) to a ceer $S$ if there is a total computable function $f:\omega\rightarrow\omega$ so that $nRm$ if and only if $f(n)Sf(m)$ for every $n,m\in\omega$. There is a uniform join operator on ceers, given by defining $R\oplus S$ by: $nR\oplus S m$ iff both $n$ and $m$ are even and $\frac{n}{2}R\frac{m}{2}$ or both are odd and $\frac{n-1}{2}S\frac{m-1}{2}$. This uniform join operation does not always give a least upper bound (under $\leq_c$) of $R$ and $S$.
  
  I will ostensibly be talking about which pairs of ceers have and which pairs of ceers do not have joins and meets in the structure of ceers. In reality, this goal will lead us to define several interesting classes of ceers, considering structures formed by modding out the ceers by particular ideals of ceers, and will lead us as far afield as showing the non-definability of the jump operation (pending enough time to wander quite that far afield).


• Tuesday, Sept. 27th, 4PM, Mariya Soskova, Sofia University
  Title: Rado's path decomposition theorem
  I will present joint work with Cholak, Igusa, Patey, and Turetsky. Let $c$ be a coloring of the pairs of natural numbers in $r$ colors. A path of color $j$ is a sequence $P = (n_0, n_1, \dots)$ of natural numbers such that every pair of adjacent elements $\{n_i, n_{i+1}\}$ has color $j$. Rado's path decomposition theorem states that the natural numbers can be partitioned into $r$ distinct paths $P_0$, $\dots$, $P_{r-1}$, such that $P_j$ is a path of color $j$. We will investigate the effective properties of this theorem.


• Tuesday, Oct. 4th, 4PM, Sherwood Hachtman, UIC
  Title: Determinacy and reflecting to admissible sets
  Borel determinacy, while a simple statement about definable sets of reals, cannot be proven without appeal to some form of higher set theoretic infinity; namely, to the axioms of Replacement and Power Set. Famous results of D. A. Martin and H. Friedman give level-by-level bounds on the strength of Borel determinacy: Finding winning strategies in games with $\Sigma^0_{1+\alpha+3}$ payoff requires (roughly) the existence of $V_{\alpha+1}$, the $\alpha+1$st level of the von Neumann hierarchy.
  
  Our work on improving these bounds led to an equivalence in terms of a novel family of weak reflection principles, the $\Pi_1$-Reflection to Admissibles principles. These turn out to be useful in obtaining precise calibrations of the consistency strength of determinacy hypotheses in a variety of settings. In this talk, we define these principles and give some applications to games on higher types; in particular, we describe a separation of Open and Clopen determinacy for games with uncountably many allowed moves, e.g. with each move a real number (re-proving a result of Schweber) or with a proper class of allowed moves (answering a question of Gitman and Hamkins).


• Tuesday, Oct. 11th, 4PM, Gabriel Conant, Notre Dame
  Title: On tame expansions of the group of integers
  We discuss some recent work concerning expansions of the group $\mathbb Z$ of integers, which are tame with respect to model theoretic dp-rank. Our focus is on the ordered group of integers (also called Presburger arithmetic), which is a well-known example of a dp-minimal expansion of $\mathbb Z$. It was asked by Aschenbrenner et. al. whether every dp-minimal expansion of $\mathbb Z$ is a reduct of Presburger. We present a result in the opposite direction: there are no intermediate structures strictly between the group of integers and Presburger arithmetic. The proof of this result uses Cluckers' cell decomposition for Presburger sets, as well as work of Kadets on the geometry of convex polyhedra.


• Tuesday, Oct. 25th, 4PM, Linda Brown Westrick, University of Connecticut
  Title: Effectiveness for Hindman's theorem with bounded sums
  Hindman's theorem ($HT$) states that for every $\ell$-coloring of the natural numbers, there is an infinite set $X \subseteq \omega$ and a color $i<\ell$ such that for every finite non-empty $F\subseteq X$, $\sum F$ receives color $i$. We consider the effective content and reverse math of the bounded variants $HT^{\leq k}_\ell$ in which only those $F$ with $|F|\leq k$ are required to have $\sum F$ colored monochromatically. The results are: $HT^{\leq 2}_2$ is not computably true; $HT^{\leq 2}_2+B\Pi^0_1$ implies $SRT^2_2$, and $HT^{\leq 3}_3$ implies $ACA$. But it is open whether these variants are strictly weaker than $HT$. This is joint work with Dzhafarov, Jockusch, and Solomon.


• Tuesday, Nov. 1st, No seminar in honor of Midwest Model Theory Day
  


• Tuesday, Nov. 8th, 4PM, James Freitag, University of Illinois at Chicago
  Title: Ranks of Painleve equations and vector fields


• Tuesday, Nov. 15th, 4PM, Chris Shaw, Columbia College Chicago
  Title: Definable choice for a class of weakly o-minimal structure
  For an o-minimal structure ${\mathcal M}$ expanding a group and a new convex predicate $U$, we show that the structure $({\mathcal M}, U)$ cannot satisfy definable choice. In the case that $({\mathcal M}, U)$ is nonvaluational, we show that the expanded structure cannot have definable Skolem functions even after naming constants. In the case that $({\mathcal M},U)$ is valuational, the failure of full definable choice is easy to see, but we use the work of van den Dries and Lewenberg on $T$-convexity to show that, modulo adding constants, the expanded structure in fact does have definable Skolem functions. In addition we present some insight about a particular algorithm for computing these functions when they are present.


• Tuesday, Nov. 22nd, No seminar in honor of the eating of turkeys
  

• 1/24/2017 4PM, Takayuki Kihara, Berkeley
  Title: The second-level Borel isomorphism problem
  Two spaces are second-level Borel isomorphic if there exists a bijection between these spaces which preserves $G_\delta\sigma$. The second level Borel isomorphism problem asks whether every uncountable Polish space is second-level Borel isomorphic either to the real line or to the Hilbert cube. We show that there are continuum many second-level Borel isomorphism types of uncountable compact metrizable spaces.


• 2/7/2017 4PM, Noah Schweber, UW
  Title: Higher reverse mathematics
  I will discuss the framework of higher reverse mathematics, and some results and open problems in the subject.


• 2/14/2017 4PM, Turbo Ho, UW
  Title: On the Scott sentence of finitely generated structures
  Scott showed that for every countable structure $A$, there is an $L_{\omega_1, \omega}$ sentence, called the Scott sentence, whose models are isomorphic copies of $A$. Thus, the quantifier complexity of a Scott sentence of a structure is one invariant that measures the complexity of the "description" of the structure. Knight et al. have studied the Scott sentences of many structures, in particular, Knight and Saraph showed that a finitely generated structure always have a $\Sigma_3$ Scott sentence. In this talk, we will discuss a joint work with Matthew Harrison-Trainor, and another independent work by Alvir, Knight, and McCoy, where we give characterizations of finitely generated structures where the $\Sigma_3$ Scott sentence is optimal. Using these results, we also give a construction of a finitely generated group where the $\Sigma_3$ Scott sentence is optimal.


• 2/21/2017 No seminar in honor of Schloss Dagstuhl
  


• 2/28/2017 No seminar in honor of Mardi Gras
  


• 3/14/2017 4PM, Gregory Igusa, Notre Dame
  Title: Trains (and an old claim concerning Ramsey's theorem)
  In 1972, Carl Jockusch initiated a computability theoretic study of Ramsey’s theorem, which proved to be very fruitful for effective combinatorics, and even more so for reverse mathematics. In his paper, he proved that for any $k$-coloring of pairs of integers, there is an infinite $\Pi^0_2$ homogeneous set. The proof used a nonuniform step, and in a remark preceding the proof, he claimed that there was no uniform way to prove the result, even using a finite number of $\Pi^0_2$ indices for sets. In 2013, Tahina Rakotoniaina asked for a proof of this claim, and Jockusch withdrew his claim, asking for a proof or refutation. We provide a proof of the claim.
  
  In proving this claim, we introduce "trains" as combinatorial objects whose purpose is to approximate $\Pi^0_2$ sets, while also being more combinatorially convenient to work with than a naive approximation.


• 3/16/2017 Midwest Computability Seminar
  


• 3/21/2017 No seminar in honor of Spring Break
  


• 3/28/2017 4PM, Matthew Harrison-Trainor, Berkeley
  Title: There is no classification of the decidably presentable structures
  Often, we want to know whether there is a characterization of the structures satisfying some property. Such a characterization would be simpler than the naive definition of that property. We can use an index set result to show that a characterization is as simple as possible, or to show that there is no characterization is possible. I will show that there is no reasonable classification of the computable structures which have decidable presentations. Formally, we do this by showing that the index set of the decidably presentable structures is $\Sigma^1_1$-complete.


• 4/4/2017 No seminar in honor of Midwest Model Theory Day
  


• 4/11/2017 4PM, Jack Lutz, Iowa State
  Title: Real-time computability of real numbers by chemical reaction networks
  In this talk I will review the emergence of chemical reaction networks as a mathematical model of computation. I will then discuss recent work with Xiang Huang, Titus H. Klinge, James I. Lathrop, and Xiaoyuan Li exploring the class of real numbers that are computed in real time by chemical reaction networks.


• 4/18/2017 4PM, Wim Ruitenburg, Marquette University
  Title: Latarres on complete lattices
  We establish a "decomposition" theorem of a latarre on a complete lattice into a Heyting latarre and a Löb fixed point latarre.


• 4/25/2017 4PM, Alex Kruckman, Indiana University
  Title: Generic expansion and Skolemization in NSOP1 theories
  Any model-complete theory T which eliminates the quantifier "there exist infinitely many" has generic expansions and generic Skolemizations: after adding new constant, function, and relation symbols, T has a model companion in the expanded language, and the same holds for T together with axioms asserting that new function symbols are Skolem functions. It is a classic result of Chatzidakis and Pillay that the generic expansion of a simple theory by new relation symbols is simple, but a generic binary function gives an instance of TP2. Recently, Kaplan and Ramsey have developed a theory of independence in the class of NSOP1 theories, which contain the simple theories, in which the new notion of Kim independence plays the role of forking independence in simple theories. Using this theory of independence, we show that if T is NSOP1 and satisfies a mild assumption on algebraic independence (which holds in every simple theory and every known NSOP1 theory), all generic expansions and generic Skolemizations of T are NSOP1. The simplest case of this construction is the model companion of the empty theory in an arbitrary language, and we study this theory in detail, characterizing forking and Kim independence and providing a "geometric" proof of weak elimination of imaginaries. This is joint work with Nick Ramsey.


• 5/2/2017 4PM, Carl Jockusch, University of Illinois at Urbana–Champaign
  Title: The strength and effective content of restricted forms of Hindman's Theorem
  Hindman's Theorem asserts that if the natural numbers are colored with finitely many colors there is an infinite set X of natural numbers such that all finite nonempty sums of elements of X have the same color. I will briefly review some results discussed by Linda Brown Westrick in a seminar here last fall on the effective content of Hindman's Theorem for sums of bounded length. The main part of the talk will discuss the result, due to Csima and Hirschfeldt, that Hindman's Theorem for sums of length exactly two has a computable instance with no $\Sigma^0_2$ solution. The proof of this result uses a computable version of the Lovász Local Lemma due to A. Rumyantsev and A. Shen to construct the required computable coloring. I will not assume that listeners are already familiar with Hindman's Theorem or the Lovász Local Lemma.