Computable processes can produce arbitrary outputs in nonstandard models

Models of PAWednesday, April 13, 20166:15 pmGC 4214-03

Victoria Gitman

Computable processes can produce arbitrary outputs in nonstandard models

The City University of New York

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.

Posted by on March 29th, 2016