Skip to main content
added 761 characters in body
Source Link
Noah Schweber
  • 20.7k
  • 8
  • 104
  • 321

Yet another one, very belatedly - this time proving the second incompleteness theorem! Below I assume some reasonable bijective (for simplicity) Godel numbering system. This is due to Adamowicz and Bigorajska, Existentially closed structures and Godel's second incompleteness theorem.

Fix an r.e. theory $T\supseteq I\Delta_0+\mathit{exp}$. Say that $M\models T$ is 1-closed (with respect to $T$) iff for every extension $M\prec_0 N\models T$, every $\overline{a}\in M$, and every $\Sigma_1$ formula $\varphi$, we have $\varphi(\overline{a})^M\leftrightarrow\varphi(\overline{a})^N$. If $T\subseteq\Pi_2$ then $T$ has a 1-closed model via a union of chains construction. If $T$ isn't $\Pi_2$-axiomatizable, we can always shift attention to its set $T_2$ of $\Pi_2$ consequences; note that $T_2\vdash \mathit{Con}(T_2)$ iff $T\vdash \mathit{Con}(T)$ iff [etc.], so this is a benign shift for our purposes.

OK, so WLOG assume $T\subseteq \Pi_2$. The usual proof of Tarski's undefinability theorem in fact does more; it applies to nonstandard models via taking standard parts, and it restricts to complexity classes, in the following sense:

(Extended TUT) Let $\Gamma$ be a syntactic class and $\mathcal{M}\models T$. Then there is no formula $\varphi\in\check{\Gamma}$ (= the set of negations of formulas in $\Gamma$) such that, for all standard sentences $\gamma\in\Gamma$, we have $$\mathcal{M}\models\gamma\iff\mathcal{M}\models\varphi\left(\underline{\ulcorner\gamma\urcorner}\right).$$

The classical TUT takes $\mathcal{M}=\mathbb{N}$ and $\Gamma=\check{\Gamma}=\mathit{Fmla}$, but the proof is the same.

The claim is now that any 1-closed model of $T$ must satisfy $\neg \mathit{Con}(T)$. To see this, suppose $\mathcal{M}\models T+\mathit{Con}(T)$ is $1$-closed and consider the formula $$\psi(\varphi,x)\equiv \mathit{Con}(T+\varphi(\underline{x}))$$ (the right hand side is phrased "internally" - of course, the thing plugged in for $x$ might be nonstandard, but $\mathcal{M}$ will still think that it has a numeral). Fix $\varphi\in\Sigma_1$ and $m\in\mathcal{M}$.

  • If $\mathcal{M}\models\varphi(m)$, then by internal $\Sigma_1$-completeness and $\mathcal{M}\models\mathit{Con}(T)$ we get $\mathcal{M}\models\psi(\varphi, m)$. Note that this does not use 1-closedness.

  • Now suppose $\mathcal{M}\models\psi(\varphi,m)$. Adding constants to the language to name all elements of $\mathcal{M}$, let $T'$ be the theory consisting of $T$, the $\Sigma_1$ diagram of $\mathcal{M}$, and $\varphi(m)$. By $\Sigma_1$-completeness we get that $T'$ is (externally) finitely consistent, and so (externally) satisfiable. Fix an extension $\mathcal{M}\prec_0\mathcal{N}\models T'$, we get $\mathcal{N}\models\varphi(m)$ and so by 1-closedness $\mathcal{M}\models\varphi(m)$.

At this point we have a contradiction with the extended TUT above!


As an amusing aside, note that in fact every model of a "reasonable" theory can be extended to one that thinks that that theory is inconsistent. The simplest proof of that uses GIT2, but we can also attack it as follows: letting $T$ be "appropriate" with $\mathcal{M}\models T$ and $T'$ be the $\Pi^0_2$-consequences of $T$, we can find extensions $\mathcal{M}\prec_0\mathcal{N}\prec_0\mathcal{S}$ with $\mathcal{N}\models T'$ 1-closed with respect to $T'$ and $\mathcal{S}\models T$. But then $\mathcal{N}\models \neg Con(T')$ and hence $\mathcal{N}\models\neg Con(T)$, and this is upwards-absolute to $\mathcal{S}$.

Yet another one, very belatedly - this time proving the second incompleteness theorem! Below I assume some reasonable bijective (for simplicity) Godel numbering system. This is due to Adamowicz and Bigorajska, Existentially closed structures and Godel's second incompleteness theorem.

Fix an r.e. theory $T\supseteq I\Delta_0+\mathit{exp}$. Say that $M\models T$ is 1-closed (with respect to $T$) iff for every extension $M\prec_0 N\models T$, every $\overline{a}\in M$, and every $\Sigma_1$ formula $\varphi$, we have $\varphi(\overline{a})^M\leftrightarrow\varphi(\overline{a})^N$. If $T\subseteq\Pi_2$ then $T$ has a 1-closed model via a union of chains construction. If $T$ isn't $\Pi_2$-axiomatizable, we can always shift attention to its set $T_2$ of $\Pi_2$ consequences; note that $T_2\vdash \mathit{Con}(T_2)$ iff $T\vdash \mathit{Con}(T)$ iff [etc.], so this is a benign shift for our purposes.

OK, so WLOG assume $T\subseteq \Pi_2$. The usual proof of Tarski's undefinability theorem in fact does more; it applies to nonstandard models via taking standard parts, and it restricts to complexity classes, in the following sense:

(Extended TUT) Let $\Gamma$ be a syntactic class and $\mathcal{M}\models T$. Then there is no formula $\varphi\in\check{\Gamma}$ (= the set of negations of formulas in $\Gamma$) such that, for all standard sentences $\gamma\in\Gamma$, we have $$\mathcal{M}\models\gamma\iff\mathcal{M}\models\varphi\left(\underline{\ulcorner\gamma\urcorner}\right).$$

The classical TUT takes $\mathcal{M}=\mathbb{N}$ and $\Gamma=\check{\Gamma}=\mathit{Fmla}$, but the proof is the same.

The claim is now that any 1-closed model of $T$ must satisfy $\neg \mathit{Con}(T)$. To see this, suppose $\mathcal{M}\models T+\mathit{Con}(T)$ is $1$-closed and consider the formula $$\psi(\varphi,x)\equiv \mathit{Con}(T+\varphi(\underline{x}))$$ (the right hand side is phrased "internally" - of course, the thing plugged in for $x$ might be nonstandard, but $\mathcal{M}$ will still think that it has a numeral). Fix $\varphi\in\Sigma_1$ and $m\in\mathcal{M}$.

  • If $\mathcal{M}\models\varphi(m)$, then by internal $\Sigma_1$-completeness and $\mathcal{M}\models\mathit{Con}(T)$ we get $\mathcal{M}\models\psi(\varphi, m)$. Note that this does not use 1-closedness.

  • Now suppose $\mathcal{M}\models\psi(\varphi,m)$. Adding constants to the language to name all elements of $\mathcal{M}$, let $T'$ be the theory consisting of $T$, the $\Sigma_1$ diagram of $\mathcal{M}$, and $\varphi(m)$. By $\Sigma_1$-completeness we get that $T'$ is (externally) finitely consistent, and so (externally) satisfiable. Fix an extension $\mathcal{M}\prec_0\mathcal{N}\models T'$, we get $\mathcal{N}\models\varphi(m)$ and so by 1-closedness $\mathcal{M}\models\varphi(m)$.

At this point we have a contradiction with the extended TUT above!

Yet another one, very belatedly - this time proving the second incompleteness theorem! Below I assume some reasonable bijective (for simplicity) Godel numbering system. This is due to Adamowicz and Bigorajska, Existentially closed structures and Godel's second incompleteness theorem.

Fix an r.e. theory $T\supseteq I\Delta_0+\mathit{exp}$. Say that $M\models T$ is 1-closed (with respect to $T$) iff for every extension $M\prec_0 N\models T$, every $\overline{a}\in M$, and every $\Sigma_1$ formula $\varphi$, we have $\varphi(\overline{a})^M\leftrightarrow\varphi(\overline{a})^N$. If $T\subseteq\Pi_2$ then $T$ has a 1-closed model via a union of chains construction. If $T$ isn't $\Pi_2$-axiomatizable, we can always shift attention to its set $T_2$ of $\Pi_2$ consequences; note that $T_2\vdash \mathit{Con}(T_2)$ iff $T\vdash \mathit{Con}(T)$ iff [etc.], so this is a benign shift for our purposes.

OK, so WLOG assume $T\subseteq \Pi_2$. The usual proof of Tarski's undefinability theorem in fact does more; it applies to nonstandard models via taking standard parts, and it restricts to complexity classes, in the following sense:

(Extended TUT) Let $\Gamma$ be a syntactic class and $\mathcal{M}\models T$. Then there is no formula $\varphi\in\check{\Gamma}$ (= the set of negations of formulas in $\Gamma$) such that, for all standard sentences $\gamma\in\Gamma$, we have $$\mathcal{M}\models\gamma\iff\mathcal{M}\models\varphi\left(\underline{\ulcorner\gamma\urcorner}\right).$$

The classical TUT takes $\mathcal{M}=\mathbb{N}$ and $\Gamma=\check{\Gamma}=\mathit{Fmla}$, but the proof is the same.

The claim is now that any 1-closed model of $T$ must satisfy $\neg \mathit{Con}(T)$. To see this, suppose $\mathcal{M}\models T+\mathit{Con}(T)$ is $1$-closed and consider the formula $$\psi(\varphi,x)\equiv \mathit{Con}(T+\varphi(\underline{x}))$$ (the right hand side is phrased "internally" - of course, the thing plugged in for $x$ might be nonstandard, but $\mathcal{M}$ will still think that it has a numeral). Fix $\varphi\in\Sigma_1$ and $m\in\mathcal{M}$.

  • If $\mathcal{M}\models\varphi(m)$, then by internal $\Sigma_1$-completeness and $\mathcal{M}\models\mathit{Con}(T)$ we get $\mathcal{M}\models\psi(\varphi, m)$. Note that this does not use 1-closedness.

  • Now suppose $\mathcal{M}\models\psi(\varphi,m)$. Adding constants to the language to name all elements of $\mathcal{M}$, let $T'$ be the theory consisting of $T$, the $\Sigma_1$ diagram of $\mathcal{M}$, and $\varphi(m)$. By $\Sigma_1$-completeness we get that $T'$ is (externally) finitely consistent, and so (externally) satisfiable. Fix an extension $\mathcal{M}\prec_0\mathcal{N}\models T'$, we get $\mathcal{N}\models\varphi(m)$ and so by 1-closedness $\mathcal{M}\models\varphi(m)$.

At this point we have a contradiction with the extended TUT above!


As an amusing aside, note that in fact every model of a "reasonable" theory can be extended to one that thinks that that theory is inconsistent. The simplest proof of that uses GIT2, but we can also attack it as follows: letting $T$ be "appropriate" with $\mathcal{M}\models T$ and $T'$ be the $\Pi^0_2$-consequences of $T$, we can find extensions $\mathcal{M}\prec_0\mathcal{N}\prec_0\mathcal{S}$ with $\mathcal{N}\models T'$ 1-closed with respect to $T'$ and $\mathcal{S}\models T$. But then $\mathcal{N}\models \neg Con(T')$ and hence $\mathcal{N}\models\neg Con(T)$, and this is upwards-absolute to $\mathcal{S}$.

Source Link
Noah Schweber
  • 20.7k
  • 8
  • 104
  • 321

Yet another one, very belatedly - this time proving the second incompleteness theorem! Below I assume some reasonable bijective (for simplicity) Godel numbering system. This is due to Adamowicz and Bigorajska, Existentially closed structures and Godel's second incompleteness theorem.

Fix an r.e. theory $T\supseteq I\Delta_0+\mathit{exp}$. Say that $M\models T$ is 1-closed (with respect to $T$) iff for every extension $M\prec_0 N\models T$, every $\overline{a}\in M$, and every $\Sigma_1$ formula $\varphi$, we have $\varphi(\overline{a})^M\leftrightarrow\varphi(\overline{a})^N$. If $T\subseteq\Pi_2$ then $T$ has a 1-closed model via a union of chains construction. If $T$ isn't $\Pi_2$-axiomatizable, we can always shift attention to its set $T_2$ of $\Pi_2$ consequences; note that $T_2\vdash \mathit{Con}(T_2)$ iff $T\vdash \mathit{Con}(T)$ iff [etc.], so this is a benign shift for our purposes.

OK, so WLOG assume $T\subseteq \Pi_2$. The usual proof of Tarski's undefinability theorem in fact does more; it applies to nonstandard models via taking standard parts, and it restricts to complexity classes, in the following sense:

(Extended TUT) Let $\Gamma$ be a syntactic class and $\mathcal{M}\models T$. Then there is no formula $\varphi\in\check{\Gamma}$ (= the set of negations of formulas in $\Gamma$) such that, for all standard sentences $\gamma\in\Gamma$, we have $$\mathcal{M}\models\gamma\iff\mathcal{M}\models\varphi\left(\underline{\ulcorner\gamma\urcorner}\right).$$

The classical TUT takes $\mathcal{M}=\mathbb{N}$ and $\Gamma=\check{\Gamma}=\mathit{Fmla}$, but the proof is the same.

The claim is now that any 1-closed model of $T$ must satisfy $\neg \mathit{Con}(T)$. To see this, suppose $\mathcal{M}\models T+\mathit{Con}(T)$ is $1$-closed and consider the formula $$\psi(\varphi,x)\equiv \mathit{Con}(T+\varphi(\underline{x}))$$ (the right hand side is phrased "internally" - of course, the thing plugged in for $x$ might be nonstandard, but $\mathcal{M}$ will still think that it has a numeral). Fix $\varphi\in\Sigma_1$ and $m\in\mathcal{M}$.

  • If $\mathcal{M}\models\varphi(m)$, then by internal $\Sigma_1$-completeness and $\mathcal{M}\models\mathit{Con}(T)$ we get $\mathcal{M}\models\psi(\varphi, m)$. Note that this does not use 1-closedness.

  • Now suppose $\mathcal{M}\models\psi(\varphi,m)$. Adding constants to the language to name all elements of $\mathcal{M}$, let $T'$ be the theory consisting of $T$, the $\Sigma_1$ diagram of $\mathcal{M}$, and $\varphi(m)$. By $\Sigma_1$-completeness we get that $T'$ is (externally) finitely consistent, and so (externally) satisfiable. Fix an extension $\mathcal{M}\prec_0\mathcal{N}\models T'$, we get $\mathcal{N}\models\varphi(m)$ and so by 1-closedness $\mathcal{M}\models\varphi(m)$.

At this point we have a contradiction with the extended TUT above!

Post Made Community Wiki by Noah Schweber