Blog Archives

Topic Archive: automorphism group

CUNY Logic WorkshopFriday, February 28, 20142:00 pmGC 6417

Russell Miller

The theory of fields is complete for isomorphisms

City University of New York

We give a highly effective coding of countable graphs into countable fields. For each countable graph $G$, we build a countable field $F(G)$, uniformly effectively from an arbitrary presentation of $G$. There is a uniform effective method of recovering the graph $G$ from the field $F(G)$. Moreover, each isomorphism $g$ from $G$ onto any $G’$ may be turned into an isomorphism $F(g)$ from $F(G)$ onto $F(G’)$, again by a uniform effective method so that $F(g)$ is computable from $g$. Likewise, an isomorphism $f$ from $F(G)$ onto any $F(G’)$ may be turned back into an isomorphism $g$ with $F(g)=f$. Not every field $F$ isomorphic to $F(G)$ is actually of the form $F(G’)$, but for every such $F$, there is a graph $G’$ isomorphic to $G$ and an isomorphism $f$ from $F$ onto $F(G’)$, both computable in $F$.

It follows that many computable-model-theoretic properties which hold of some graph $G$ will carry over to the field $F(G)$, including spectra, categoricity spectra, automorphism spectra, computable dimension, and spectra of relations on the graph. By previous work of Hirschfeldt, Khoussainov, Shore, and Slinko, all of these properties can be transferred from any other countable, automorphically nontrivial structure to a graph (and then to various other standard classes of structures), so our result may be viewed as saying that, like these other classes, fields are complete for such properties.

This work is properly joint with Jennifer Park, Bjorn Poonen, Hans Schoutens, and Alexandra Shlapentokh. The slides for the talk are available here.

Models of PAWednesday, October 23, 20136:30 pmGC 4214.03

Erez Shochat

Schmerl’s Lemma and Boundedly Saturated Models

St. Francis College

We prove a slight modification of Schmerl’s Lemma for saturated models, and show how it can be applied to prove Kaye’s Theorem for boundedly saturated models of PA.

CUNY Logic WorkshopFriday, October 25, 20132:00 pmGC 6417

Jim Schmerl

Automorphism Groups of Countable, Recursively Saturated Models of Peano Arithmetic

University of Connecticut

It is still unknown whether there are nonisomorphic countable recursively saturated models M and N whose automorphism groups Aut(M) and Aut(N) are isomorphic. I will discuss what has happened over the last 20 years towards showing that such models do not exist, including some very recent results.

Models of PAWednesday, May 8, 20135:00 pmGC 4214.03

Ermek Nurkhaidarov

The automorphism group of a model of arithmetic: recognizing standard system

Penn State Mont Alto

Let M be countable recursively saturated model of Peano Arithmetic. In the talk I will discuss ongoing research on recognizing standard system of M in the automorphism group of M.