Blog Archives

Topic Archive: computable model theory

Notre Dame University
Dan Turetsky received his doctorate from the University of Wisconsin-Madison in 2010, under the supervision of Steffen Lempp, and has since held positions at Victoria University in Wellington, the Kurt Gödel Research Center in Vienna, and (currently) Notre Dame University. He studies many aspects of computability theory.
CUNY Logic WorkshopFriday, February 10, 20172:00 pmGC 6417

Russell Miller

Functors and infinitary interpretations of structures

City University of New York

It has long been recognized that the existence of an interpretation of one countable structure B in another one A yields a homomorphism from the automorphism group Aut(A) into Aut(B). Indeed, it yields a functor from the category Iso(A) of all isomorphic copies of A (under isomorphisms) into the category Iso(B). In traditional model theory, the converse is false. However, when we extend the concept of interpretation to allow interpretations by Lω1ω formulas, we find that now the converse essentially holds: every Borel functor arises from an infinitary interpretation of B in A, and likewise every Borel-measurable homomorphism from Aut(A) into Aut(B) arises from such an interpretation. Moreover, the complexity of an interpretation matches the complexities of the corresponding functor and homomorphism. We will discuss the concepts and the forcing necessary to prove these results and other corollaries.

University of Wisconsin
Noah Schweber received his doctorate from the University of California-Berkeley in 2016, under the supervision of Antonio Montalban. He now holds a postdoctoral position at the University of Wisconsin.
NERDS: New England Recursion & Definability SeminarSunday, November 6, 20163:30 pmScience Center, Room E104​, Wellesley College, Wellesley, MA

Linda Brown Westrick

Uncountable free abelian groups via κ-computability

University of Connecticut

One way to study structures of uncountable cardinality κ is to generalize the notion of computation. Saying that a subset of κ is κ-c.e. if it is Σ01 definable (with parameters, in the language of set theory) over Lκ provides the notion of κ-computability. We may also quantify over subsets of Lκ, providing a notion of a κ-analytic set (here we assume V=L). In this setting, we consider the difficulty of recognizing free groups and the complexity of their bases. For example, if κ is a successor cardinal, the set of free abelian groups of size κ is Σ11-complete. If κ is the successor of a regular cardinal which is not weakly compact, there is a computable free abelian group of cardinality κ, all of whose bases compute ∅”, and this is the best coding result possible. The resolution of questions of this type is more complex for other κ, and a few questions remain open. This is joint work with Greenberg and Turetsky.

Cornell University
Richard Shore is the Goldwin Smith Professor of Mathematics at Cornell University, and is a past president of the Association for Symbolic Logic. He received his doctorate from the Massachusetts Institute of Technology in 1972, under the supervision of Gerald Sacks. At Cornell he has directed 16 doctoral theses and mentored a dozen postdoctoral scholars.
NERDS: New England Recursion & Definability SeminarSaturday, April 2, 20162:30 pmLocklin Hall, Room 232, Springfield College

Marie Nicholson

Computable categoricity, linear orders and permitting

University of Connecticut

Remmel showed that a computable linear order L is computably categorical if and only if the order type of L has only a finite number of successivities. As part of the proof, Remmel assumes that L has infinitely many successivities and constructs another computable linear order R, which is not computably isomorphic to L, and a Δ02-isomorphism f such that f is an isomorphism from L onto R. Hence showing that L is not computably categorical. In this talk I will discuss the conditions under which we can use permitting arguments to construct f below certain types of Δ02 degrees.

NERDS: New England Recursion & Definability SeminarSaturday, April 2, 20169:45 amLocklin Hall, Room 232, Springfield College

Karen Lange

Climbing (or finding paths) through trees

Wellesley College

You can make a simple family tree by starting with a person at the root and then adding two branches for her parents, and then adding two branches for the parents of each of her two parents, and so on. Such a family tree is an example of a binary tree because each level of the tree has at most two branches. We’ll see that every binary tree with infinitely many nodes has an infinite path. But can we actually *compute* a path, given that we can prove one exists? Answering this question requires us to carefully define the verb “to compute.” This talk will highlight ideas from graph theory, theoretical computer science, and logic, but no background in any of these subjects is necessary.

This talk is aimed primarily at undergraduates.

Monday, February 22, 20164:00 pmGC 4102 (Science Center)This talk is part of the Graduate Student Colloquium, and is aimed at doctoral students in mathematics.

Russell Miller

Factoring polynomials and finding roots

City University of New York

We will use computability theory to investigate the difficulty of two standard questions from algebra. First, given a field F and a polynomial p∈ F[X], does the equation p=0 have a solution in F? And second, is p(X) irreducible in F[X]? Obviously these two questions are related, but it is not immediately clear which one is more difficult to answer. Indeed, it is not clear how one should measure the “difficulty” of answering these questions.

To address this problem, we will consider computable fields, which are countable fields in which we have algorithms for listing all the field elements and for the basic field operations. It has been known since 1960 that in this context, the two questions are equivalent under the standard notion of Turing reducibility: an algorithm for answering either question can be used to give an algorithm for answering the other one. However, computability theory also provides more precise measures of difficulty, and using one of these measures, known as 1-reducibility, we will show that one of the two questions can definitively be said to be more difficult in general than the other. To find out which is which, come to the talk!

NERDS: New England Recursion & Definability SeminarSaturday, April 2, 2016

NERDS on April 2, 2016

Springfield College

The Spring 2016 New England Recursion and Definability Seminar (“NERDS”) will take place on Saturday, April 2, 2016 at Springfield College, in Springfield, MA. Further details and abstracts of talks will be posted on as they become available.

CUNY Logic WorkshopFriday, December 4, 20152:00 pmGC 6417

Russell Miller

Hilbert’s Tenth Problem inside the rationals

City University of New York

For a ring R, Hilbert’s Tenth Problem is the set HTP(R) of polynomials f ∈ R[X1,X2,…] for which f=0 has a solution in R. Matiyasevich, completing work of Davis, Putnam, and Robinson, showed that HTP(Z) is Turing-equivalent to the Halting Problem. The Turing degree of HTP(Q) remains unknown. Here we consider the problem for subrings of Q. One places a natural topology on the space of such subrings, which is homeomorphic to Cantor space. This allows consideration of measure theory and also Baire category theory. We prove, among other things, that HTP(Q) computes the Halting Problem if and only if HTP(R) computes it for a nonmeager set of subrings R.

Tuesday, December 1, 201512:00 pmBronx Community College, room CP 305Research Seminar, Mathematics and Computer Science Department of BCC.

Russell Miller

Computability problems in number theory

City University of New York

We will consider several number-theoretic questions which arise from computable model theory. One of these, recently solved by Poonen, Schoutens, Shlapentokh, and the speaker, involves attempting to “embed” a graph into a field: given a graph, one wishes to construct a field with the exact same computable-model-theoretic properties as the graph. (For instance, the automorphisms of the graph should correspond to the automorphisms of the field, by a bijective functorial correspondence which preserves the Turing degree of each automorphism.) Another arises out of consideration of Hilbert’s Tenth Problem for subrings of the rationals: we ask for subrings in which Hilbert’s Tenth Problem is no harder than it is for the rationals themselves. This is known for semilocal subrings, and Eisenträger, Park, Shlapentokh and the speaker have shown that it holds for certain non-semilocal subrings as well, but it remains open whether one can invert “very few” primes and still have it hold. We will explain this problem and discuss the number-theoretic question which arises out of it.

Model theory seminarFriday, December 11, 201512:30 pmGC 6417

Matthew Harrison-Trainor

Scott ranks of models of a theory

University of California Berkeley

I will talk about a few different results about the Scott ranks of models of a theory. (By a theory, I mean a sentence of Lω1ω.) These results are all related in that they all follow from the same general construction; this construction takes a pseudo-elementary class C of linear orders and produces a theory T such that the Scott ranks of models of T are related to the well-founded parts of linear orders in C.

The main result is a descriptive-set-theoretic classification of the collections of ordinals which are the Scott spectrum of a theory. We also answer some open questions. First, we show that for each ordinal β, there is a Π20 theory which has no models of Scott rank less than β. Second, we find the Scott height of computable infinitary sentences. Third, we construct a computable model of Scott rank ω1CK+1 which is not approximated by models of low Scott rank.

Matthew Harrison-Trainor
University of California Berkeley
Matthew Harrison-Trainor is a doctoral student at the University of California at Berkeley, studying computability, computable model theory, and model theory. His advisor is Prof. Antonio Montalban.
NERDS: New England Recursion & Definability SeminarSaturday, October 17, 20152:00 pmCarriage House, Assumption College, Worcester, MA

Valentina Harizanov

Computably enumerable sets and vector spaces with thin complements

George Washington University

Simple, hypersimple, hyperhypersimple, and maximal sets play an important role in computability theory. Maximal sets are co-atoms in the lattice of computably enumerable sets modulo finite sets. Soare established that they are automorphic in this lattice. Similarly, maximal vector spaces play an important role in the study of the lattice of computably enumerable vector spaces modulo finite dimension. We will investigate principal filters determined by maximal spaces and how algebraic structure interacts with computability-theoretic properties. We will discuss the problem of finding orbits of maximal spaces under lattice automorphisms, the development of various notions of maximality for vector spaces, and recent progress that is joint work with R. Dimitrov.

Valentina Harizanov
George Washington University
Valentina Harizanov is a professor of mathematics at George Washington University, studying computable model theory. She did her graduate work at the University of Wisconsin-Madison, where her Ph.D. advisor was Terry Millar.
NERDS: New England Recursion & Definability SeminarSaturday, October 17, 201510:15 amCarriage House, Assumption College, Worcester, MA

Tyler Markkanen

A-Computable Graphs

Springfield College

A locally finite computable graph G is called A-computable if A can compute the neighbors of the vertices of G. William Gasarch and Andrew Lee introduced this notion to study graphs that are “between” computable and highly computable (i.e., ∅-computable). For any noncomputable c.e. set A, they proved that the A-computable graphs behave just like computable graphs when it comes to colorings. In this talk, we will see that their result also works for Euler paths and domatic partitions. Although it does not extend to arbitrary sets A (that are not necessarily c.e.), we will classify the sets for which it does.

NERDS: New England Recursion & Definability SeminarSaturday, October 17, 2015

NERDS October 17, 2015 at Assumption College

Carriage House, Assumption College, Worcester, MA

The 2015 autumn meeting of the New England Recursion & Definability Seminar will be held on the campus of Assumption College, in Worcester Massachusetts, on Saturday, October 17, from 10:00 until 4:15. Titles and abstracts are now posted at the link for NERDS, under the Seminars tab. Directions and visitor information are available here.

Model theory seminarFriday, September 11, 201512:30 pmGC 6417

Russell Miller

Degree spectra of real closed fields

City University of New York

The degree spectrum of a countable structure is the set of all Turing degrees of isomorphic copies of that structure. This topic has been widely studied in computable model theory. Here we examine the possible degree spectra of real closed fields, finding them to offer far more complexity than the related theory of algebraically closed fields. The co-author of this project, Victor Ocasio Gonzalez, showed in his dissertation that, for every linear order L, there exists a real closed field whose spectrum is the pre-image under jump of the spectrum of L. We add further results, distinguishing the cases of archimedean and non-archimedean real closed fields, and splitting the latter into two subcases based on the existence of a least multiplicative class of positive nonstandard elements. If such a class exists, then finiteness in the field is always decidable, but the case with no such class proves more interesting.

CUNY Logic WorkshopFriday, May 15, 20152:00 pmGC 6417

Rebecca M. Steiner

Effective symmetry breaking

Vanderbilt University

Symmetry breaking involves the coloring of elements of a structure so that the only automorphism of the structure which respects the coloring is the trivial one. We investigate how much information we would need to be able to compute a 2-coloring of a computable finite-branching tree under the predecessor function which eliminates all automorphisms except the trivial one; we also generalize to n-colorings for fixed n and for variable n. Then, we suppose the tree is no longer finite branching, and we observe what happens to the difficulty of computing a 2-coloring.

Rebecca M. Steiner
Vanderbilt University
Rebecca Steiner is a CUNY Graduate Center product, having received her Ph.D. here in 2012 as a student of Russell Miller. She then assumed a postdoctoral position at Vanderbilt University, studying computability and computable model theory, with a focus on algebraic structures. In the fall of 2015 she will join the mathematics department of Virginia Commonwealth University.