Let $f : \omega \to \{\text{wffs of set theory}\}$ be a function. Let $\leq\_f$ be a total order on $\omega$.
  
  
  

Definition: $\langle f,\leq\_f \rangle$ is a computable quasi-completion of ZFC if and only if
  
  

1. $f$ and $\leq\_f$ are both computable
  

and
  

2. for all $m,n$ in $\omega$, if $m \leq\_f \; n$, then all theorems of $ZFC+f(m)$ are theorems of $ZFC+f(n)$
  

and
  

3. for all sentences $s$ in the language of set theory, there exists a member $n$ of $\omega$ such that $ZFC+f(n)$ is consistent and one of $\{s,\lnot s\}$ is a theorem of $ZFC+f(n)$
  
  
  




> 
> Is it known that there is no computable quasi-completion of ZFC?
> 
> 
> 


  

Basically, has the goal of [Ultimate L](https://mathoverflow.net/questions/46907/completion-of-zfc) been shown to be impossible?



computable "completion" of ZFC
Here is something very close which might be adaptable to get a suitable $f$ and ${\leq\_f}$.


**Outline**


Since there is nothing very special about ZFC in the construction, I will instead work with a consistent computably axiomatizable theory $T$ for which Goedel's First Incompleteness Theorem applies. Let $\phi\_0,\phi\_1,\ldots$ be a computable enumeration of all sentences in the language of $T$. I will assume that $\phi\_0$ is your favorite contradiction, which I will also denote $\perp$.


I will define a computable function $f:\omega\to\omega$ and computable linear ordering ${\preceq}$ of $\omega$ by stages. At each stage $s$, I will decide the restrictions of $f$ and ${\preceq}$ on the set $\{0,1,\dots,t\_s\}$. I will also keep track of a marker $m\_s$ which will mark the ${\preceq}$-first element of $\{0,1,\dots,t\_s\}$ for which it is *known by stage $s$* that $T + \{\phi\_{f(i)} : i \leq t\_s \land i \preceq m\_s\}$ is inconsistent. By the phrase *known by stage $s$* I mean that $\perp$ appears by stage $s$ in the *standard computable enumeration* of the consequences of $T + \{\phi\_{f(i)} : i \leq t\_s \land i \preceq m\_s\}$. This standard computable enumeration is allowed to enumerate finitely many consequences at each stage. I will also assume that this standard computable enumeration is such that:


1. If $F$ is a finite set of sentences in the language of $T$, then all elements of $F$ appear at stage $0$ of the enumeration of the consequences of $T + F$.
2. If $F \subseteq G$ are finite sets of sentences in the language of $T$, then all elements which appear by stage $s$ of the enumeration of the consequences of $T + F$ also appear by stage $s$ of the enumeration of the consequences of $T + G$.


The function $f:\omega\to\omega$ and the linear ordering ${\preceq}$ will have the following properties.


1. Every $n \in \omega$ has either finitely many ${\preceq}$-predecessors or finitely many ${\preceq}$-successors. The dividing line is whether or not the theory $T + \{\phi\_{f(i)} : i \preceq n\}$ is consistent.
2. If $I$ is the set of all $n \in \omega$ which have finitely many ${\preceq}$-predecessors, then $T\_I = T + \{\phi\_{f(i)} : i \in I\}$ is a complete theory.


So the only missing requirement is that $i \prec j$ implies that $T \vdash \phi\_{f(j)} \rightarrow \phi\_{f(i)}$.


**Construction**


Stage $s = 0$ is trivial: $t\_s = 0$, $f(0) = 0$, $0 \preceq 0$. (Note that $m\_0 = 0$ since $\phi\_0 = \perp$.) 


At stage $s+1$, let $\ell\_s$ be the ${\preceq}$-first element of the set $\{i \leq t\_s : i \preceq m\_s\}$ such that $T + \{\phi\_{f(i)} : i \leq t\_s \land i \preceq \ell\_s\}$ is known to be inconsistent by stage $s+1$. Note that $\ell\_s$ necessarily exists since $m\_s$ is in the set being searched.


Case $\ell\_s \neq m\_s$: Then simply let $t\_{s+1} = t\_s$. (Note that $m\_{s+1} = \ell\_s$.)


Case $\ell\_s = m\_s$: Then consider the first element $n$ of the set
$$\{0,1,\ldots,s+1\}\setminus\{f(i): i \leq t\_s \land i \prec m\_s\}$$
such that
$$T + \phi\_n + \{\phi\_{f(i)} : i \leq t\_s \land f(i) < n \land i \prec m\_s\}$$
is not known to be inconsistent by stage $s+1$.


* If there is no such $n$, then simply let $t\_{s+1} = t\_s$. (Note that $m\_{s+1} = m\_s$.)
* Otherwise, set $t\_{s+1} = t\_s + 1$ and $f(t\_{s+1}) = n$. Place $t\_{s+1}$ immediately after the maximum element of $\{i \leq t\_s : f(i) < n \land i \prec m\_s\}$ in the ${\preceq}$-ordering.


Note that we always have that if $i \prec j \prec m\_s$ and $i, j \leq t\_s$ then $f(i) < f(j)$.


**Verifications**


First, observe that $\sup\_{s<\omega} t\_s = \omega$. Thus $f:\omega\to\omega$ is well-defined and ${\preceq}$ is a linear ordering of $\omega$.


*Proof.* Suppose, for the sake of contradiction, that $t\_s = t\_{s\_0}$ for all $s \geq s\_0$. Note that there are only finitely many stages $s \geq s\_0$ such that $\ell\_s \neq m\_s$. So we can find a stage $s\_1 \geq s\_0$ such that $\ell\_s = m\_s$ for all $s \geq s\_1$. Let $t = t\_{s\_0}$ and $m = m\_{s\_1}$. Note that $T' = T + \{\phi\_{f(i)} : i \leq t \land i \prec m\}$ is necessarily consistent. Moreover, for every $n \notin \{f(i) : i \leq t \land i \prec m\}$, we must have that $T' + \phi\_n$ is inconsistent and hence $T' \vdash \lnot\phi\_n$. Since $\phi\_0,\phi\_1,\ldots$ enumerates all sentences of the language of $T$, it follows that $T'$ is a complete extension of $T$. However, $T'$ is computably axiomatizable and hence cannot be complete. *QED*


Next, observe that every $n \in \omega$ has either finitely many ${\preceq}$-predecessors or finitely many ${\preceq}$-successors. The dividing line is whether the theory $T + \{\phi\_{f(i)} : i \preceq n\}$ is consistent or not.


*Proof.* First, suppose that $T + \{\phi\_{f(i)} : i \preceq n\}$ is inconsistent. Then, there is some stage $s$ such that $n \leq t\_s$ and $T + \{\phi\_{f(i)} : i \leq t\_s \land i \preceq n\}$ is inconsistent and this is known by stage $s$. It follows that $m\_s \preceq n$ and after this stage no new elements will appear after $n$ in the ${\preceq}$-ordering.


Next, suppose that $T + \{\phi\_{f(i)} : i \preceq n\}$ is consistent. For any stage $s$ such that $n \leq t\_s$, the theory $T + \{\phi\_{f(i)} : i \leq t\_s \land i \preceq n\}$ is consistent and hence not known to be inconsistent by stage $s$. It follows that $n \prec m\_s$ and hence that $f(i) < f(j) < f(n)$ for all $i \prec j \prec n$ such that $i,j \leq t\_s$. Therefore, $n$ has no more than $f(n)$ predecessors in the ${\preceq}$-ordering by stage $s$. Since the bound $f(n)$ is independent of $s$, it follows that $n$ has no more than $f(n)$ predecessors in the ${\preceq}$-ordering. *QED*


Now let $I$ be the set of all $n \in \omega$ which have only finitely many ${\preceq}$-predecessors. I claim that $T\_I = T + \{\phi\_{f(i)}:i \in I\}$ is complete.


*Proof.* Let $n\_0 \in \omega$ be minimal such that $n\_0 \notin \{f(i) : i \in I\}$ and $T\_I + \phi\_{n\_0}$ is consistent. Find $i\_0 \in I$ such that $n\_0 < f(i\_0)$ and let $s\_0 \geq n\_0$ be such that $\max\{i : i \preceq i\_0\} \leq t\_{s\_0}$. If $s \geq s\_0$, then 
$$\{i : i \prec i\_0\} = \{i \leq t\_s : f(i) < f(i\_0) \land i \prec m\_s\}$$ 
because $i \prec i\_0$ iff $f(i) < f(i\_0)$ for all $i \prec m\_s$.


Since $T\_I + \phi\_{n\_0}$ is consistent, it follows that if $s \geq s\_0$ then 
$$T + \phi\_{n\_0} + \{\phi\_{f(i)} : i \leq t\_s \land f(i) < n\_0 \land i \prec m\_s\}$$
is not known to be inconsistent by stage $s+1$. Indeed, 
$$\{\phi\_{f(i)} : i \leq t\_s \land f(i) < n\_0 \land i \prec m\_s\} \subseteq \{\phi\_{f(i)} : i \leq t\_s \land f(i) < f(i\_0) \land i \prec m\_s\}$$ 
and 
$$\{i \leq t\_s : f(i) < f(i\_0) \land i \prec m\_s\} = \{i : i \prec i\_0\} \subseteq I.$$


If $s \geq s\_0$ and $\ell\_s = m\_s$, then $n\_0$ belongs to the set of all 
$$n \in \{0,1,\ldots,s+1\} \setminus \{f(i) : i \leq t\_s \land i \prec m\_s\}$$
such that
$$T + \phi\_n + \{\phi\_{f(i)} : i \leq t\_s \land f(i) < n \land i \prec m\_s\}$$
is not known to be inconsistent by stage $s+1$. Let $n\_1 \leq n\_0$ be the minimal such $n$. Then, by the construction, we have $f(t\_s+1) = n\_1$ and $t\_s+1$ comes immediately after the ${\preceq}$-maximal element of 
$$\{i \leq t\_s : f(i) < n\_1 \land i \prec m\_s\}.$$
Since $n\_1 \leq n\_0 < f(i\_0)$ it follows that $t\_s+1 \prec i\_0$, which contradicts the fact that $\max\{i : i \preceq i\_0\} \leq t\_{s\_0}$.


It follows that $n\_0$ does not exist and hence that $n \notin \{f(i) : i \in I\}$ entails that $T\_I + \phi\_n$ is inconsistent (i.e., $T\_I \vdash \lnot\phi\_n$). Since $\phi\_0,\phi\_1,\ldots$ enumerates all sentences in the language of $T$, it follows that $T\_I$ is complete. *QED* 


