Skip to main content
missing escapes
Source Link
François G. Dorais
  • 44.4k
  • 6
  • 150
  • 233
Post Undeleted by François G. Dorais
major cleanup
Source Link
François G. Dorais
  • 44.4k
  • 6
  • 150
  • 233

Here is something very close which might be adaptable to get a suitable $f$ and ${\leq_f}$. I apologize for the relative complexity of the argument but I couldn't find any way to simplify it...

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 set theory$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$"known by stage $s$ that $ZFC + \{\phi_{f(i)} : i \leq t_s \land i \preceq m_s\}$$T + \{\phi_{f(i)} : i \leq t_s \land i \preceq m_s\}$ is inconsistent. By the phrase "known by stage $s$"known by stage $s$ I mean that $\perp$ appears by stage $s$ in the "standard computable enumeration"standard computable enumeration of the consequences of $ZFC + \{\phi_{f(i)} : i \leq t_s \land i \preceq m_s\}$$T + \{\phi_{f(i)} : i \leq t_s \land i \preceq m_s\}$. This standard computable enumeration is only 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 set theory$T$, then all elements of $F$ appear at stage $0$ of the enumeration of the consequences of $ZFC + F$$T + F$.

  2. If $F \subseteq G$ are finite sets of sentences in the language of set theory$T$, then all elements which appear by stage $s$ of the enumeration of the consequences of $ZFC + F$$T + F$ also appear by stage $s$ of the enumeration of the consequences of $ZFC + G$$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

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 $ZFC + \{\phi_{f(i)} : i \leq t_s \land i \preceq \ell_s\}$$T + \{\phi_{f(i)} : i \leq t_s \land i \preceq \ell_s\}$ is known to be inconsistent by stage $s+1$ to be inconsistent. Note that $\ell_s$ necessarily exists since $m_s$ is in the set being searched.

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 $$ZFC + \phi_n + \{\phi_{f(i)} : i \leq t_s \land f(i) < n \land i \prec m_s\}$$$$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$.)

    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.

    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.

It is straightforward to checkVerifications

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

ObserveProof. 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 $ZFC + \{\phi_{f(i)} : i \preceq n\}$$T + \{\phi_{f(i)} : i \preceq n\}$ is consistent or not.

Proof sketch. First, suppose that $ZFC + \{\phi_{f(i)} : i \preceq n\}$$T + \{\phi_{f(i)} : i \preceq n\}$ is inconsistent. Then, there is some stage $s$ such that $n \leq t_s$ and $$ZFC + \{\phi_{f(i)} : i \leq t_s \land i \preceq n\}$$ is $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.

IfNext, suppose that $ZFC + \{\phi_{f(i)} : i \preceq n\}$$T + \{\phi_{f(i)} : i \preceq n\}$ is consistent. Then noteFor 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$ and sosuch 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 $ZFC + \{\phi_{f(i)}:i \in I\}$$T_I = T + \{\phi_{f(i)}:i \in I\}$ is complete.

Proof sketch. Show by inductionLet $n_0 \in \omega$ be minimal such that for each $n$, there$n_0 \notin \{f(i) : i \in I\}$ and $T_I + \phi_{n_0}$ is a stageconsistent. Find $s \geq n$$i_0 \in I$ such that either $\phi_n \in \{\phi_{f(i)} : i \leq t_s \land i \in I\}$, or$n_0 < f(i_0)$ and let $ZFC + \phi_n + \{\phi_{f(i)} : i \leq t_s \land i \in I\}$ is known to$s_0 \geq n_0$ be inconsistent by stage $s$.

Suppose we know the desired fact for allsuch that $m < n$$\max\{i : i \preceq i_0\} \leq t_{s_0}$. If $ZFC + \phi_n + \{\phi_{f(i)} : i \in I\}$ is inconsistent$s \geq s_0$, then simply find a stage $s$ such that $$\{i : i \prec i_0\} = \{i \leq t_s : f(i) < f(i_0) \land i \prec m_s\}$$ because $t_s$ is large enough to witness this. Otherwise, find a stage$i \prec i_0$ iff $s_0 \geq m$ large enough to witness the desired fact simultaneously$f(i) < f(i_0)$ for all $m < n$$i \prec m_s$. Then, find a stage $s_1 \geq s_0$ such that

Since $\{ i \leq t_{s_0} : i \in I \} = \{i \leq t_{s_0} : i \prec m_{s_1} \}$. Note$T_I + \phi_{n_0}$ is consistent, it follows that for every stageif $s \geq s_1$, we$s \geq s_0$ then have that $$ZFC + \phi_n + \{\phi_{f(i)} : i \leq t_s \land f(i) < n \land i \prec m_s\}$$$$T + \phi_{n_0} + \{\phi_{f(i)} : i \leq t_s \land f(i) < n_0 \land i \prec m_s\}$$ is consistent (hence not known to be inconsistent by stage $s$)$s+1$. Furthermore Indeed, if $$\{\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 $n \notin \{f(i) : i \leq t_s \land i \prec m_s\}$$s \geq s_0$ and $\ell_s = m_s$, then $n$ is necessarily the first element of$n_0$ belongs to the set of all $$\{0,1,\ldots,s+1\} \setminus \{f(i) : i \leq t_s \land i \prec m_s\}$$$$n \in \{0,1,\ldots,s+1\} \setminus \{f(i) : i \leq t_s \land i \prec m_s\}$$ such that $$ZFC + \phi_n + \{\phi_{f(i)} : i \leq t_s \land f(i) < n \land i \prec m_s\}$$$$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$. Waiting a few more stages if necessaryLet $n_1 \leq n_0$ be the minimal such $n$. Then, by the construction, we will eventually have $\ell_s = m_s$$f(t_s+1) = n_1$ and then $n = f(t_s+1)$$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}$. Moreover

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 hypotheses onlanguage of $n$ guarantee$T$, it follows that we will then have $t_s+1 \in I$$T_I$ is complete. QED

Here is something very close which might be adaptable to get a suitable $f$ and ${\leq_f}$. I apologize for the relative complexity of the argument but I couldn't find any way to simplify it...

Let $\phi_0,\phi_1,\ldots$ be a computable enumeration of all sentences in the language of set theory. I will assume that $\phi_0$ is your favorite contradiction, which I will also denote $\perp$.

I will define a 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 $ZFC + \{\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 $ZFC + \{\phi_{f(i)} : i \leq t_s \land i \preceq m_s\}$. This standard computable enumeration is only 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 set theory, then all elements of $F$ appear at stage $0$ of the enumeration of the consequences of $ZFC + F$.

  2. If $F \subseteq G$ are finite sets of sentences in the language of set theory, then all elements which appear by stage $s$ of the enumeration of the consequences of $ZFC + F$ also appear by stage $s$ of the enumeration of the consequences of $ZFC + G$.

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 $ZFC + \{\phi_{f(i)} : i \leq t_s \land i \preceq \ell_s\}$ is known by stage $s+1$ to be inconsistent. Note that $\ell_s$ necessarily exists since $m_s$ is in the set being searched.

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 $$ZFC + \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.

It is straightforward to check that $\sup_{s<\omega} t_s = \omega$. Thus $f:\omega\to\omega$ is well-defined and ${\preceq}$ is a linear ordering of $\omega$.

Observe that every $n \in \omega$ has either finitely many ${\preceq}$-predecessors or finitely many ${\preceq}$-successors. The dividing line is whether the theory $ZFC + \{\phi_{f(i)} : i \preceq n\}$ is consistent or not.

Proof sketch. First suppose that $ZFC + \{\phi_{f(i)} : i \preceq n\}$ is inconsistent. Then, there is some stage $s$ such that $n \leq t_s$ and $$ZFC + \{\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.

If $ZFC + \{\phi_{f(i)} : i \preceq n\}$ is consistent. Then note that $f(i) < f(j) < f(n)$ for all $i \prec j \prec n$ and so $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 $ZFC + \{\phi_{f(i)}:i \in I\}$ is complete.

Proof sketch. Show by induction that for each $n$, there is a stage $s \geq n$ such that either $\phi_n \in \{\phi_{f(i)} : i \leq t_s \land i \in I\}$, or $ZFC + \phi_n + \{\phi_{f(i)} : i \leq t_s \land i \in I\}$ is known to be inconsistent by stage $s$.

Suppose we know the desired fact for all $m < n$. If $ZFC + \phi_n + \{\phi_{f(i)} : i \in I\}$ is inconsistent, then simply find a stage $s$ such that $t_s$ is large enough to witness this. Otherwise, find a stage $s_0 \geq m$ large enough to witness the desired fact simultaneously for all $m < n$. Then, find a stage $s_1 \geq s_0$ such that $\{ i \leq t_{s_0} : i \in I \} = \{i \leq t_{s_0} : i \prec m_{s_1} \}$. Note that for every stage $s \geq s_1$, we then have that $$ZFC + \phi_n + \{\phi_{f(i)} : i \leq t_s \land f(i) < n \land i \prec m_s\}$$ is consistent (hence not known to be inconsistent by stage $s$). Furthermore, if $n \notin \{f(i) : i \leq t_s \land i \prec m_s\}$ then $n$ is necessarily the first element of the set $$\{0,1,\ldots,s+1\} \setminus \{f(i) : i \leq t_s \land i \prec m_s\}$$ such that $$ZFC + \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$. Waiting a few more stages if necessary, we will eventually have $\ell_s = m_s$ and then $n = f(t_s+1)$. Moreover, the hypotheses on $n$ guarantee that we will then have $t_s+1 \in I$. QED

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

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

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

Post Deleted by François G. Dorais
typos
Source Link
François G. Dorais
  • 44.4k
  • 6
  • 150
  • 233

At stage $s+1$, let $\ell_s$ be the first${\preceq}$-first element of the set $\{i \leq t_s : i \preceq m_s\}$ (in the usual ordering) such that $ZFC + \{\phi_{f(i)} : i \leq t_s \land i \preceq \ell_s\}$ is known by stage $s+1$ to be inconsistent. Note that $\ell_s$ necessarily exists since $m_s$ is in the set being searched.

  • 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 \lneq_f m_s\}$$\{i \leq t_s : f(i) < n \land i \prec m_s\}$ in the ${\preceq}$-ordering.

Proof sketch. First suppose that $ZFC + \{\phi_{f(i)} : i \preceq n\}$ is inconsistent. Then, there is some stage $s$ such that $n \leq t_s$ and $$ZFC + \{\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 after stage $s$.

At stage $s+1$, let $\ell_s$ be the first element of the set $\{i \leq t_s : i \preceq m_s\}$ (in the usual ordering) such that $ZFC + \{\phi_{f(i)} : i \leq t_s \land i \preceq \ell_s\}$ is known by stage $s+1$ to be inconsistent. Note that $\ell_s$ necessarily exists since $m_s$ is in the set being searched.

  • 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 \lneq_f m_s\}$ in the ${\preceq}$-ordering.

Proof sketch. First suppose that $ZFC + \{\phi_{f(i)} : i \preceq n\}$ is inconsistent. Then, there is some stage $s$ such that $n \leq t_s$ and $$ZFC + \{\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 after stage $s$.

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 $ZFC + \{\phi_{f(i)} : i \leq t_s \land i \preceq \ell_s\}$ is known by stage $s+1$ to be inconsistent. Note that $\ell_s$ necessarily exists since $m_s$ is in the set being searched.

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

Proof sketch. First suppose that $ZFC + \{\phi_{f(i)} : i \preceq n\}$ is inconsistent. Then, there is some stage $s$ such that $n \leq t_s$ and $$ZFC + \{\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.

Source Link
François G. Dorais
  • 44.4k
  • 6
  • 150
  • 233
Loading