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

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].

References

  1. W. H. Woodin, “A potential subtlety concerning the distinction between determinism and nondeterminism,” in Infinity, Cambridge Univ. Press, Cambridge, 2011, pp. 119–129.
  2. R. Blanck and A. Enayat, “Marginalia on a theorem of Woodin,” J. Symb. Log., vol. 82, no. 1, pp. 359–374, 2017.