Computable processes can produce arbitrary outputs in nonstandard models (continued)

In the previous post, I discussed a theorem of Woodin, extended recently by Blanck and Enayat, showing that for every computably enumerable theory $T$, there is in index $e$ such that if $M\models T$ satisfies that $W_e$ is contained in an $M$-finite set $s$, then $M$ has an end-extension $N\models T$ such that in $N$, $W_e=s$.

Theorem (Woodin [1], Blanck and Enayat [2]): For every computably enumerable theory $T$ extending ${\rm PA}$, there is an index $e$ (depending on $T$) such that

  • ${\rm PA}\vdash “W_e$ is finite”,
  • If $M\models T$ and $M$ satisfies that $W_e\subseteq s$ for some $M$-finite set $s$, then $M$ has an end-extension $N\models T$ that satisfies $W_e=s$.

Let me now sketch the proof of the theorem.

We start out by fixing some computably enumerable theory $T$ extending ${\rm PA}$. Let’s extend the language of arithmetic $\mathcal L_A$ by adding a constant symbol $\bar c$. What we would like to show is that there is an index $e$ such that whenever $(M,s)\models T+W_e\subseteq\bar c$ (meaning that $s$ interprets $\bar c$), then $M$ has an end-extension $N$ such that $(N,s)\models T+W_e=\bar c$. Standard techniques in models of arithmetic can be used to prove the following theorem.

Theorem: Suppose $T$ is a computably enumerable theory extending ${\rm PA}$. Then the following are equivalent for sentences $\varphi(\bar c)$ and $\psi(\bar c)$.

  1. Every model $(M,s)\models T+\varphi(\bar c)$ has an end-extension $(N,s)\models T+\psi(\bar c)$.
  2. Every model $(M,s)\models T+\varphi(\bar c)$ satisfies ${\rm Con}(n,T+\psi(\bar c)+{\rm Th}_{\Sigma_1(\bar c)})$ for all $n\in\mathbb N$.

Here ${\rm Tr}_{\Sigma_1(\bar c)}$ is the theory consisting of all true $\Sigma_1$-sentences that hold in $(M,s)$ and the statement ${\rm Con}(n,\bar T)$, for a theory $\bar T$, asserts that there is no proof of inconsistency of length less than $n$ from $\bar T$.

So to prove the theorem we need to find an index $e$ such that every model $$(M,s)\models T+W_e\subseteq\bar c$$ also satisfies for every $n\in\mathbb N$ that $${\rm Con}(n,T+\psi(\bar c)+{\rm Th}_{\Sigma_1(\bar c)})$$ holds. Let’s now find the required index $e$. First, to be precise, we define that $W_e$ is the $e$-th c.e. set, meaning that we have fixed some reasonable enumeration $\langle \varphi_e\mid e\in \mathbb N\rangle$ of all $\Sigma_1$-formulas and $$W_e:=\{i\in\mathbb N\mid \varphi_e(i)\}.$$

Fix a natural number $k$. We define the set $S_k$ to consist of ordered triples $(n,p,s)$ such that

  1. $p,s\leq n$,
  2. $p$ is a (code of a) proof of some formula of the form $\ulcorner\forall t\,(\sigma(t)\rightarrow W_k=t)\urcorner$,
  3. $\sigma(v):=\exists x\,\delta(x,y)$, where $\delta(x,y)$ is $\Delta_0$,
  4. $\exists x\leq n\,\delta(x,s)$ holds.

The set $S_k$ might be empty but it is clearly computable.

Let $\leq$ denote the lexicographical order on ordered triples of natural numbers. Consider the following Turing Machine program $p_k$. First $p_k$ searches for the $\leq$-least triple $(n_0,p_0,s_0)$ in $S_k$. If $p_k$ succeeds, it will write out the finite set coded by $s_0$ on the output tape. It will then search for the $\leq$-least triple $(n_1,p_1,s_1)$ in $S_k$ such that $p_1<p_0$ and $s_1\supseteq s_0$ (viewed as codes for finite sets). If it succeeds, $p_k$ will extend the output to $s_1$ and continue the process. Clearly ${\rm PA}$ proves that $p_k$ always has a finite output because the values $p_i$ are decreasing.

Next, we define a total computable function $f:\mathbb N\to \mathbb N$, which on input $k$ outputs an index $e$ such that $W_e$ is the output of $p_k$. It is not difficult to see that for every computable function the Second Recursion Theorem is provable in ${\rm PA}$, so that we get that there is an index $e$ such that ${\rm PA}\vdash W_{f(e)}=W_e$.

The challenge for the reader now is to prove that $e$ has the desired property. Namely, we want to show that whenever $$(M,s)\models T+W_e\subseteq \bar c,$$ then also for all $n\in \mathbb N$, $$(M,s)\models {\rm Con}(n,T+W_e=\bar c+{\rm Th}_{\Sigma_1(\bar c)}).$$ The details can be found in [2].

[1] H. W. Woodin, “A potential subtlety concerning the distinction between determinism and nondeterminism,” in Infinity, Cambridge Univ. Press, Cambridge, 2011, pp. 119-129.
[Bibtex]
@incollection {Woodin:PotentialSubtletyDeterminismNonDeterminism,
AUTHOR = {Woodin, W. Hugh},
TITLE = {A potential subtlety concerning the distinction between
determinism and nondeterminism},
BOOKTITLE = {Infinity},
PAGES = {119--129},
PUBLISHER = {Cambridge Univ. Press, Cambridge},
YEAR = {2011},
MRCLASS = {03A05 (03H15)},
MRNUMBER = {2767236},
MRREVIEWER = {Saeed Salehi},
}
[2] R. Blanck and A. Enayat, “Marginalia on a theorem of Woodin,” , 2016.
[Bibtex]
@ARTICLE{BlanckEnayat:WoodinTheorem,
AUTHOR= {Blanck, Rasmus and Enayat, Ali},
TITLE= {Marginalia on a theorem of {W}oodin},
Note ={Manuscript},
Year={2016}
}
This entry was posted in research and tagged . Bookmark the permalink.

One Response to Computable processes can produce arbitrary outputs in nonstandard models (continued)

  1. Pingback: Every function can be computable! | Joel David Hamkins

Leave a Reply

Your email address will not be published. Required fields are marked *