Wednesday, April 13, 20166:15 pmModels of PAGC 4214-03

Computable processes can produce arbitrary outputs in nonstandard models

Victoria Gitman

The City University of New York

Victoria Gitman

The focus of this talk is the question of what a computable process can output by passing to a nonstandard model of arithmetic. It is not difficult to see that a computable process can change its output by passing to a nonstandard model, but in fact, for some processes, we can thus affect any arbitrary desired change. I will discuss and prove a theorem of Woodin, recently generalized by Blanck and Enayat, showing that for every computably enumerable theory $T$ extending ${\rm PA}$, there is a corresponding index $e$ such that ${\rm PA}\vdash “W_e$ is finite” and whenever a model $M\models T$ satisfies that $W_e$ is contained in some $M$-finite set $s$, then $M$ has an end-extension $N\models T$ in which $W_e=s$. Indeed, the hypotheses can be relaxed to say that $T$ extends ${\rm I}\Sigma_1$, but I will not discuss this in the talk.

An extended abstract can be found here on my blog.

Victoria Gitman received her Ph.D. in 2007 from the CUNY Graduate Center, as a student of Joel Hamkins, and is presently a visiting scholar at the CUNY Graduate Center. Her research is in Mathematical Logic, in particular in the areas of Set Theory and Models of Peano Arithmetic.