Undecidability and Peano Arithmetic
Facts
$% shorthands \newcommand{\cl}{ \mathcal{#1} } \newcommand{\sc}{ \mathscr{#1} } \newcommand{\bb}{ \mathbb{#1} } \newcommand{\fk}{ \mathfrak{#1} } \renewcommand{\bf}{ \mathbf{#1} } \renewcommand{\sf}{ \mathsf{#1} } % category names \newcommand{\cat}{{ \sf{#1} }} % more shorthands \newcommand{\floor}{ { \lfloor {#1} \rfloor } } \newcommand{\ceil}{ { \lceil {#1} \rceil } } \newcommand{\ol}{ \overline{#1} } \newcommand{\t}{ \text{#1} } \newcommand{\norm}{ { \lvert {#1} \rvert } } % norm/magnitude \newcommand{\card}{ \t{cd} } % cardinality \newcommand{\dcup}{ \sqcup } % disjoint untion \newcommand{\tup}{ \langle {#1} \rangle } % tuples % turing machines \newcommand{\halts}{ {\downarrow} } \newcommand{\loops}{ {\uparrow} } % represents an anonymous parameter % eg. f(\apar) usually denotes the function x \mapsto f(x) \newcommand{\apar}{ {-} } % reverse-order composition %\newcommand{\then}{ \operatorname{\ ;\ } } \newcommand{\then}{ {\scriptsize\ \rhd\ } } % Like f' represents "f after modification", \pre{f} % represents "f before modification" \newcommand{\pre}{{ \small {#1} }} % hook arrows \newcommand{\injects}{ \hookrightarrow } \newcommand{\embeds}{ \hookrightarrow } \newcommand{\surjects}{ \twoheadrightarrow } \newcommand{\projects}{ \twoheadrightarrow } % good enough definition of yoneda \newcommand{\yo}{よ} \text{Th}((\bb N, +, \times))$ is not c.e. Proof sketch — if it were, then by embedding the partial recursive functions into $% shorthands \newcommand{\cl}{ \mathcal{#1} } \newcommand{\sc}{ \mathscr{#1} } \newcommand{\bb}{ \mathbb{#1} } \newcommand{\fk}{ \mathfrak{#1} } \renewcommand{\bf}{ \mathbf{#1} } \renewcommand{\sf}{ \mathsf{#1} } % category names \newcommand{\cat}{{ \sf{#1} }} % more shorthands \newcommand{\floor}{ { \lfloor {#1} \rfloor } } \newcommand{\ceil}{ { \lceil {#1} \rceil } } \newcommand{\ol}{ \overline{#1} } \newcommand{\t}{ \text{#1} } \newcommand{\norm}{ { \lvert {#1} \rvert } } % norm/magnitude \newcommand{\card}{ \t{cd} } % cardinality \newcommand{\dcup}{ \sqcup } % disjoint untion \newcommand{\tup}{ \langle {#1} \rangle } % tuples % turing machines \newcommand{\halts}{ {\downarrow} } \newcommand{\loops}{ {\uparrow} } % represents an anonymous parameter % eg. f(\apar) usually denotes the function x \mapsto f(x) \newcommand{\apar}{ {-} } % reverse-order composition %\newcommand{\then}{ \operatorname{\ ;\ } } \newcommand{\then}{ {\scriptsize\ \rhd\ } } % Like f' represents "f after modification", \pre{f} % represents "f before modification" \newcommand{\pre}{{ \small {#1} }} % hook arrows \newcommand{\injects}{ \hookrightarrow } \newcommand{\embeds}{ \hookrightarrow } \newcommand{\surjects}{ \twoheadrightarrow } \newcommand{\projects}{ \twoheadrightarrow } % good enough definition of yoneda \newcommand{\yo}{よ} (\bb N, +, \times)$ we can solve the halting problem.
For a theory $% shorthands \newcommand{\cl}{ \mathcal{#1} } \newcommand{\sc}{ \mathscr{#1} } \newcommand{\bb}{ \mathbb{#1} } \newcommand{\fk}{ \mathfrak{#1} } \renewcommand{\bf}{ \mathbf{#1} } \renewcommand{\sf}{ \mathsf{#1} } % category names \newcommand{\cat}{{ \sf{#1} }} % more shorthands \newcommand{\floor}{ { \lfloor {#1} \rfloor } } \newcommand{\ceil}{ { \lceil {#1} \rceil } } \newcommand{\ol}{ \overline{#1} } \newcommand{\t}{ \text{#1} } \newcommand{\norm}{ { \lvert {#1} \rvert } } % norm/magnitude \newcommand{\card}{ \t{cd} } % cardinality \newcommand{\dcup}{ \sqcup } % disjoint untion \newcommand{\tup}{ \langle {#1} \rangle } % tuples % turing machines \newcommand{\halts}{ {\downarrow} } \newcommand{\loops}{ {\uparrow} } % represents an anonymous parameter % eg. f(\apar) usually denotes the function x \mapsto f(x) \newcommand{\apar}{ {-} } % reverse-order composition %\newcommand{\then}{ \operatorname{\ ;\ } } \newcommand{\then}{ {\scriptsize\ \rhd\ } } % Like f' represents "f after modification", \pre{f} % represents "f before modification" \newcommand{\pre}{{ \small {#1} }} % hook arrows \newcommand{\injects}{ \hookrightarrow } \newcommand{\embeds}{ \hookrightarrow } \newcommand{\surjects}{ \twoheadrightarrow } \newcommand{\projects}{ \twoheadrightarrow } % good enough definition of yoneda \newcommand{\yo}{よ} T$, if $% shorthands \newcommand{\cl}{ \mathcal{#1} } \newcommand{\sc}{ \mathscr{#1} } \newcommand{\bb}{ \mathbb{#1} } \newcommand{\fk}{ \mathfrak{#1} } \renewcommand{\bf}{ \mathbf{#1} } \renewcommand{\sf}{ \mathsf{#1} } % category names \newcommand{\cat}{{ \sf{#1} }} % more shorthands \newcommand{\floor}{ { \lfloor {#1} \rfloor } } \newcommand{\ceil}{ { \lceil {#1} \rceil } } \newcommand{\ol}{ \overline{#1} } \newcommand{\t}{ \text{#1} } \newcommand{\norm}{ { \lvert {#1} \rvert } } % norm/magnitude \newcommand{\card}{ \t{cd} } % cardinality \newcommand{\dcup}{ \sqcup } % disjoint untion \newcommand{\tup}{ \langle {#1} \rangle } % tuples % turing machines \newcommand{\halts}{ {\downarrow} } \newcommand{\loops}{ {\uparrow} } % represents an anonymous parameter % eg. f(\apar) usually denotes the function x \mapsto f(x) \newcommand{\apar}{ {-} } % reverse-order composition %\newcommand{\then}{ \operatorname{\ ;\ } } \newcommand{\then}{ {\scriptsize\ \rhd\ } } % Like f' represents "f after modification", \pre{f} % represents "f before modification" \newcommand{\pre}{{ \small {#1} }} % hook arrows \newcommand{\injects}{ \hookrightarrow } \newcommand{\embeds}{ \hookrightarrow } \newcommand{\surjects}{ \twoheadrightarrow } \newcommand{\projects}{ \twoheadrightarrow } % good enough definition of yoneda \newcommand{\yo}{よ} T \supseteq \text{PA}$ is consistent then either $% shorthands \newcommand{\cl}{ \mathcal{#1} } \newcommand{\sc}{ \mathscr{#1} } \newcommand{\bb}{ \mathbb{#1} } \newcommand{\fk}{ \mathfrak{#1} } \renewcommand{\bf}{ \mathbf{#1} } \renewcommand{\sf}{ \mathsf{#1} } % category names \newcommand{\cat}{{ \sf{#1} }} % more shorthands \newcommand{\floor}{ { \lfloor {#1} \rfloor } } \newcommand{\ceil}{ { \lceil {#1} \rceil } } \newcommand{\ol}{ \overline{#1} } \newcommand{\t}{ \text{#1} } \newcommand{\norm}{ { \lvert {#1} \rvert } } % norm/magnitude \newcommand{\card}{ \t{cd} } % cardinality \newcommand{\dcup}{ \sqcup } % disjoint untion \newcommand{\tup}{ \langle {#1} \rangle } % tuples % turing machines \newcommand{\halts}{ {\downarrow} } \newcommand{\loops}{ {\uparrow} } % represents an anonymous parameter % eg. f(\apar) usually denotes the function x \mapsto f(x) \newcommand{\apar}{ {-} } % reverse-order composition %\newcommand{\then}{ \operatorname{\ ;\ } } \newcommand{\then}{ {\scriptsize\ \rhd\ } } % Like f' represents "f after modification", \pre{f} % represents "f before modification" \newcommand{\pre}{{ \small {#1} }} % hook arrows \newcommand{\injects}{ \hookrightarrow } \newcommand{\embeds}{ \hookrightarrow } \newcommand{\surjects}{ \twoheadrightarrow } \newcommand{\projects}{ \twoheadrightarrow } % good enough definition of yoneda \newcommand{\yo}{よ} T$ is not c.e. or is incomplete (here $% shorthands \newcommand{\cl}{ \mathcal{#1} } \newcommand{\sc}{ \mathscr{#1} } \newcommand{\bb}{ \mathbb{#1} } \newcommand{\fk}{ \mathfrak{#1} } \renewcommand{\bf}{ \mathbf{#1} } \renewcommand{\sf}{ \mathsf{#1} } % category names \newcommand{\cat}{{ \sf{#1} }} % more shorthands \newcommand{\floor}{ { \lfloor {#1} \rfloor } } \newcommand{\ceil}{ { \lceil {#1} \rceil } } \newcommand{\ol}{ \overline{#1} } \newcommand{\t}{ \text{#1} } \newcommand{\norm}{ { \lvert {#1} \rvert } } % norm/magnitude \newcommand{\card}{ \t{cd} } % cardinality \newcommand{\dcup}{ \sqcup } % disjoint untion \newcommand{\tup}{ \langle {#1} \rangle } % tuples % turing machines \newcommand{\halts}{ {\downarrow} } \newcommand{\loops}{ {\uparrow} } % represents an anonymous parameter % eg. f(\apar) usually denotes the function x \mapsto f(x) \newcommand{\apar}{ {-} } % reverse-order composition %\newcommand{\then}{ \operatorname{\ ;\ } } \newcommand{\then}{ {\scriptsize\ \rhd\ } } % Like f' represents "f after modification", \pre{f} % represents "f before modification" \newcommand{\pre}{{ \small {#1} }} % hook arrows \newcommand{\injects}{ \hookrightarrow } \newcommand{\embeds}{ \hookrightarrow } \newcommand{\surjects}{ \twoheadrightarrow } \newcommand{\projects}{ \twoheadrightarrow } % good enough definition of yoneda \newcommand{\yo}{よ} \text{PA}$ is the theory of Peano Arithmetic) This is a strengthening of (1) Proof sketch — roughly the same as the previous but we embed into $% shorthands \newcommand{\cl}{ \mathcal{#1} } \newcommand{\sc}{ \mathscr{#1} } \newcommand{\bb}{ \mathbb{#1} } \newcommand{\fk}{ \mathfrak{#1} } \renewcommand{\bf}{ \mathbf{#1} } \renewcommand{\sf}{ \mathsf{#1} } % category names \newcommand{\cat}{{ \sf{#1} }} % more shorthands \newcommand{\floor}{ { \lfloor {#1} \rfloor } } \newcommand{\ceil}{ { \lceil {#1} \rceil } } \newcommand{\ol}{ \overline{#1} } \newcommand{\t}{ \text{#1} } \newcommand{\norm}{ { \lvert {#1} \rvert } } % norm/magnitude \newcommand{\card}{ \t{cd} } % cardinality \newcommand{\dcup}{ \sqcup } % disjoint untion \newcommand{\tup}{ \langle {#1} \rangle } % tuples % turing machines \newcommand{\halts}{ {\downarrow} } \newcommand{\loops}{ {\uparrow} } % represents an anonymous parameter % eg. f(\apar) usually denotes the function x \mapsto f(x) \newcommand{\apar}{ {-} } % reverse-order composition %\newcommand{\then}{ \operatorname{\ ;\ } } \newcommand{\then}{ {\scriptsize\ \rhd\ } } % Like f' represents "f after modification", \pre{f} % represents "f before modification" \newcommand{\pre}{{ \small `{#1} }} % hook arrows \newcommand{\injects}{ \hookrightarrow } \newcommand{\embeds}{ \hookrightarrow } \newcommand{\surjects}{ \twoheadrightarrow } \newcommand{\projects}{ \twoheadrightarrow } % good enough definition of yoneda \newcommand{\yo}{よ} \text{PA}$