Blog Archives

Topic Archive: computable model theory

Uri Andrews
University of Wisconsin
Uri Andrews received his Ph.D. from the University of California-Berkeley in 2010, as a student of Tom Scanlon, and subsequently took up an assistant professorship (now tenure-track) at the University of Wisconsin. He studies computable model theory, blending techniques from model theory and computability theory.
CUNY Logic WorkshopFriday, May 1, 20152:00 pmGC 6417

Uri Andrews

A Local Characterization of VC-minimality

University of Wisconsin

(Work joint with Vincent Guingona.) I’ll talk about a problem in the intersection of computable model theory and classical model theory. The notion of VC-minimality, though intriguing, has proven very difficult to work with. It has even been difficult to check whether familiar examples are VC-minimal. This has led model theorists (chiefly my co-author) to ask whether there was a “local” (read “simpler”) characterization of VC-minimality. I suggested a computable model theoretic version of this question in terms of the index set of VC-minimality. We answered this question by giving a local characterization of VC-minimality, and we showed that VC-minimality is a Π04-complete notion.

CUNY Logic WorkshopFriday, March 13, 201512:30 pmGC 6417

Andrey Morozov

Σ-Presentable structures over HF(R)

Sobolev Institute of Mathematics, Novosibirsk State University

If we replace in the definition of computable structures the concept of classical computability over ω with Σ-definability over the structure HF(R) (the hereditarily finite superstructure over the ordered field R of reals), we obtain its generalization, namely, the notion of Σ-presentable structures over HF(R). This generalization could correspond to the hypothetical situation when we have an opportunity to use algorithms written in a powerful programming language with “real” reals, elements of R, not approximations, where we in addition have opportunity to find roots of polynomials and use them in further computations.

In the talk, a survey will be given of the results on the existence of Σ-presentations for various structures, on the number of non Σ-isomorphic presentations, and on the existence of Σ-parameterizations for classes of presentations.

Andrey Morozov
Sobolev Institute of Mathematics, Novosibirsk State University
Prof. Andrey Morozov received his doctorate in 1983, as a student of Sergey Goncharov at Novosibirsk State University, Russia. Since then he has risen to serve as Head of the Laboratory of Logical Systems at Novosibirsk, and has held assorted visiting positions in other countries during that time as well. He studies computability theory, with a focus on Sigma-definability and computable model theory.
Friday, February 6, 20154:50 pmGC 4102 (Science Center)

Computability, computational complexity and geometric group theory

University of Illinois at Urbana-Champaign

The three topics in the title have been inextricably linked since the famous 1912 paper of Max Dehn. In recent years the asymptotic-generic point of view of geometric group theory has given rise to new areas of computability and computational complexity. I will discuss how this arose and then focus on one recent development in computability theory, namely, coarse computability and the coarse computability bound.

Model theory seminarFriday, May 8, 201512:30 pmGC 6417

Leah Marshall

Computable Functors between Nested Equivalence Structures and Full Trees of Finite Height

George Washington University

Trees have long been used throughout mathematics to better understand and represent many different types of objects and structures. In this talk we examine finitely nested equivalence structures. Such structures consist of a set of natural numbers and a finite number of equivalence relations which are nested inside of each other. (That is, their resulting equivalence classes are subsets of each other.) We utilize the notions of category theory to build functors between nested equivalence structures and full trees of finite height. These functors behave quite nicely, and we build them in a computable way so that the various computability-theoretic properties of the structures are preserved. We discuss computable isomorphisms and the Turing degree spectrum of a structure – defining and giving examples of each, and showing how, once our computable functors are constructed, such properties transfer readily between nested equivalence structures and trees.

CUNY Logic WorkshopFriday, March 6, 20152:00 pmGC 6417

Karen Lange

Lengths of roots of polynomials over k((G))

Wellesley College

Mourgues and Ressayre showed that any real closed field $R$ can be mapped isomorphically onto a truncation-closed subfield of the Hahn field $k((G))$, where $G$ is the natural value group of $R$ and $k$ is the residue field. If we fix a section of the residue field and a well ordering < of $R$, then the procedure of Mourgues and Ressayre yields a canonical section of $G$ and a unique embedding $d: R$ → $k((G))$. Julia Knight and I believed we had shown that for a real closed field $R$ with a well ordering < of type ω, the series in $d(R)$ have length less than ωωω, but we found a mistake in our proof. We needed a better understanding of what happens to lengths under root-taking. In this talk, we give a partial answer, which allows us to prove the original statement and generalize it. We make use of unpublished notes of Starchenko on the Newton-Puiseux method for taking roots of polynomials.

CUNY Logic WorkshopFriday, December 5, 20142:00 pmGC 6417

Russell Miller

Computable functors and effective interpretations

City University of New York

We give an overview of a number of recent results in computable model theory, by various researchers (not necessarily including the speaker). The results are not all directly connected to each other, but they serve to illustrate the principle that much of the work in this discipline can be viewed through the prism of functors, on categories C and D whose elements are countable (or computable) structures and whose morphisms are isomorphisms (not necessarily computable). Ideally, such a functor F from C to D should be effective: given a structure M from C as an oracle, it should compute the structure F(M) in D, and given a C-morphism g from M to N as an oracle, it should compute the D-morphism F(g) from F(M) to F(N). Moreover, one would hope for F to be full and faithful, as a functor, and to have a computable inverse functor. In practice, it is unusual for an F to have all of these properties, and for particular applications in computable model theory, only certain of the properties are needed. Many familiar examples will be included to help make these concepts clear.

Recent joint work by Harrison-Trainor, Melnikov, Montalbán, and the speaker has established that computable functors are closely connected to Montalban’s notion of effective interpretation of one class C of countable structures in another class D. We will explain the connections and discuss the extent to which they realize the model-theorist’s suspicion that functors are really just another version of interpretations.

NERDS: New England Recursion & Definability SeminarSaturday, October 18, 201411:40 amAssumption College, Worcester, MA

Caleb Martin

The degree spectra of orders on a computable Abelian group

University of Connecticut

For any computable abelian group, the collection of possible linear orderings on the group can be represented as a Π01 class. However, not all Π01 classes can occur in this way, and we investigate the possible Turing degrees of their members. First, we describe the connection between orders for a group and bases for the group. Additionally, we extend a previously known result regarding the Turing degrees not represented in the space of orders of some group.

NERDS: New England Recursion & Definability SeminarSaturday, October 18, 20142:40 pmAssumption College, Worcester, MA

Jacob Suggs

Low for omega and equivalence class isomorphism properties

University of Connecticut

We look at the property of being low for isomorphism, restricted to certain classes of structures – if C is a class of structures, a set D is low for C isomorphism iff for any two structures in C, if D computes an isomorphism between them then there is a computable isomorphism between them. In particular we will show that exactly those sets which cannot compute non-zero Δ2 degrees are low for ω-isomorphism (when ω is viewed purely as an order), and we will show that no set which computes a non-zero Δ2 set or which computes a separating set for any two computably inseparable c.e. degrees is low for equivalence class isomorphism.

Reed Solomon
University of Connecticut
Reed Solomon is a Professor in the Department of Mathematics at the University of Connecticut, studying computability theory. He received his doctorate from Cornell University in 1998, under the supervision of Richard Shore, and subsequently held postdoctoral positions at the University of Wisconsin and Notre Dame University.
NERDS: New England Recursion & Definability SeminarSaturday, October 18, 20142:00 pmAssumption College, Worcester, MA

Leah Marshall

Computability theoretic properties of isomorphisms between partial computable injection structures

George Washington University

A partial computable injection structure consists of a computable set of natural numbers and a partial computable, injective (1-1) function. Clearly, the isomorphism type of such a structure is determined by the kinds and number of orbits of the elements under the function application. First, we investigate partial computable injection structures always having computable isomorphisms to other isomorphic structures, and we analyze what goes wrong in structures without such computable isomorphisms. Additionally, we do the same for partial computable injection structures under Δ2-isomorphisms and Δ3-isomorphisms.

Leah Marshall
George Washington University
Leah Marshall is a graduate student at George Washington University, working on a doctorate in computability theory under the supervision of Valentina Harizanov.
NERDS: New England Recursion & Definability SeminarSaturday, October 18, 2014Assumption College, Carriage House

NERDS

The Autumn 2014 meeting of NERDS, the New England Recursion & Definability Seminar, will take place on Saturday, October 18 at Assumption College, in Worcester, MA, beginning at 10:30 a.m. The principal organizers are Brooke Andersen, Damir Dzhafarov, and Reed Solomon. All talks are posted on nylogic.org (find NERDS under the “Conferences” tab), and they will take place in the Carriage House building on the campus of Assumption College. Directions.

CUNY Logic WorkshopFriday, September 12, 20142:00 pmGC 6417

Chris Conidis

Computable algebra: a personal perspective

College of Staten Island - CUNY

I will give a brief overview of some of my recent research in the field of Computable Algebra, emphasizing connections between Computability Theory and Algebra. Some of the topics that I hope to cover include Artinian and Euclidean rings, as well as infinite dimensional vector spaces. There will be no proofs, just statements of theorems along with discussions on their logical and algebraic significance.

Tuesday, May 13, 20142:30 pm750 Schapiro CEPSR, Columbia University Morningside CampusThe Schapiro Center (CEPSR) is located on the Morningside Campus of Columbia University.

Russell Miller

Generalizing Turing machines: $\omega_1$-computation

City University of New York

While Turing machines are well established as the principal framework for theoretical computation on the natural numbers, no machine model for computation on uncountable domains has achieved any similarly dominant status. We will give an overview of various methods that have been explored, including computable analysis, the Blum-Shub-Smale model of computation on the real numbers, local computability, α-recursion theory, and certain models of computation over ordinal time (one of which turns out to be equivalent to α-recursion). Each of these has strengths and weaknesses, for which reason no one of them has come to dominate the discussion. Much of the talk will be expository, describing these different notions of computation, but we will finish with a specific example from ω1-recursive model theory which shows how phenomena that were unknown under Turing computation on ω can arise in the context of ω1-computable model theory.

NERDS: New England Recursion & Definability SeminarSunday, March 30, 20142:00 pmAcademic Center, Room 113, Olin College

Jesse Johnson

Quasiminimality and computability

Westfield State University

We briefly define computability on uncountable domains via Σ1-recursion, with an emphasis on ω1-computability. We will then apply this notion of uncountable computability to quasiminimal excellent classes. We will concentrate on the pseudo-exponential fields and the topological group covers of the complex numbers. We show that the group covers are relatively ω1-computably categorical while the pseudo-exponential fields are not even ω1-computably categorical.

Jesse Johnson
Westfield State University
Jesse Johnson received his Ph.D. from Notre Dame University in 2013, under the supervision of Prof. Julia Knight, and is now an Assistant Professor at Westfield State University in Westfield, MA.