Skip to main content
added 312 characters in body
Source Link

Work in the first order language $L$ of number theory, consisting of the symbols $\mathbf{0}$, $\mathbf{S}$, $\boldsymbol{+}$, and $\boldsymbol{\cdot}$, and let $Q$ denote Robinson's arithmetic.

By a diophantine formula we mean a formula in this language having the form $\exists y_1 \dots \exists y_m(f(x_1, \dots, x_n, y_1,\dots, y_m) = g(x_1, \dots, x_n, y_1,\dots, y_m))$, where each of $f(x_1, \dots, x_n, y_1,\dots, y_m)$ and $g(x_1, \dots, x_n, y_1,\dots, y_m)$ is a term in this language having the form of a polynomial whose variables are among $x_1, \dots, x_n, y_1, \dots, y_m$, and whose coefficients are terms of the form $\mathbf{S}\mathbf{S} \dots \mathbf{S}\mathbf{0}$.

We of course know (Rosser-Kleene-Mostowski) that there is a $\Sigma_1$-formula $\phi(x)$ with one free variable $x$ such that for every consistent recursively axiomatizable theory $T$ extending $Q$, there is some $n$ such that the sentence $\phi(\mathbf{S}^n\mathbf{0})$ is undecidable in $T$.

Question: Is there a diophantine formula $\phi(x)$ for which the above will be true (i.e. for every consistent recursively axiomatizable theory $T$ extending $Q$, there is some $n$ such that the sentence $\phi(\mathbf{S}^n\mathbf{0})$ is undecidable in $T$)?

Note that we are only requiring that $T$ be a consistent recursively axiomatizable theory extending $Q$, and so are allowing $T$ to be $\omega$-inconsistent.

An alternative way of asking the same question: Can some recursively inseparable pair of r.e. sets $A$ and $B$ be "represented" in $Q$ by some diophantine formula $\phi(x)$ (so that if $n \in A$ then $Q \vdash \phi(\mathbf{S}^n\mathbf{0})$ and if $n \in B$ then $Q \vdash \neg\phi(\mathbf{S}^n\mathbf{0})$)?

Work in the first order language $L$ of number theory, consisting of symbols $\mathbf{0}$, $\mathbf{S}$, $\boldsymbol{+}$, and $\boldsymbol{\cdot}$, and let $Q$ denote Robinson's arithmetic.

By a diophantine formula we mean a formula in this language having the form $\exists y_1 \dots \exists y_m(f(x_1, \dots, x_n, y_1,\dots, y_m) = g(x_1, \dots, x_n, y_1,\dots, y_m))$, where each of $f(x_1, \dots, x_n, y_1,\dots, y_m)$ and $g(x_1, \dots, x_n, y_1,\dots, y_m)$ is a term in this language having the form of a polynomial whose variables are among $x_1, \dots, x_n, y_1, \dots, y_m$, and whose coefficients are terms of the form $\mathbf{S}\mathbf{S} \dots \mathbf{S}\mathbf{0}$.

We of course know (Rosser-Kleene-Mostowski) that there is a $\Sigma_1$-formula $\phi(x)$ with one free variable $x$ such that for every consistent recursively axiomatizable theory $T$ extending $Q$, there is some $n$ such that the sentence $\phi(\mathbf{S}^n\mathbf{0})$ is undecidable in $T$.

Question: Is there a diophantine formula $\phi(x)$ for which the above will be true (i.e. for every consistent recursively axiomatizable theory $T$ extending $Q$, there is some $n$ such that the sentence $\phi(\mathbf{S}^n\mathbf{0})$ is undecidable in $T$)?

Note that we are only requiring that $T$ be a consistent recursively axiomatizable theory extending $Q$, and so are allowing $T$ to be $\omega$-inconsistent.

Work in the first order language of number theory, consisting of the symbols $\mathbf{0}$, $\mathbf{S}$, $\boldsymbol{+}$, and $\boldsymbol{\cdot}$, and let $Q$ denote Robinson's arithmetic.

By a diophantine formula we mean a formula in this language having the form $\exists y_1 \dots \exists y_m(f(x_1, \dots, x_n, y_1,\dots, y_m) = g(x_1, \dots, x_n, y_1,\dots, y_m))$, where each of $f(x_1, \dots, x_n, y_1,\dots, y_m)$ and $g(x_1, \dots, x_n, y_1,\dots, y_m)$ is a term in this language having the form of a polynomial whose variables are among $x_1, \dots, x_n, y_1, \dots, y_m$, and whose coefficients are terms of the form $\mathbf{S}\mathbf{S} \dots \mathbf{S}\mathbf{0}$.

We of course know (Rosser-Kleene-Mostowski) that there is a $\Sigma_1$-formula $\phi(x)$ with one free variable $x$ such that for every consistent recursively axiomatizable theory $T$ extending $Q$, there is some $n$ such that the sentence $\phi(\mathbf{S}^n\mathbf{0})$ is undecidable in $T$.

Question: Is there a diophantine formula $\phi(x)$ for which the above will be true (i.e. for every consistent recursively axiomatizable theory $T$ extending $Q$, there is some $n$ such that the sentence $\phi(\mathbf{S}^n\mathbf{0})$ is undecidable in $T$)?

Note that we are only requiring that $T$ be a consistent recursively axiomatizable theory extending $Q$, and so are allowing $T$ to be $\omega$-inconsistent.

An alternative way of asking the same question: Can some recursively inseparable pair of r.e. sets $A$ and $B$ be "represented" in $Q$ by some diophantine formula $\phi(x)$ (so that if $n \in A$ then $Q \vdash \phi(\mathbf{S}^n\mathbf{0})$ and if $n \in B$ then $Q \vdash \neg\phi(\mathbf{S}^n\mathbf{0})$)?

edited tags
Link
Source Link

Essential incompleteness via diophantine formulas?

Work in the first order language $L$ of number theory, consisting of symbols $\mathbf{0}$, $\mathbf{S}$, $\boldsymbol{+}$, and $\boldsymbol{\cdot}$, and let $Q$ denote Robinson's arithmetic.

By a diophantine formula we mean a formula in this language having the form $\exists y_1 \dots \exists y_m(f(x_1, \dots, x_n, y_1,\dots, y_m) = g(x_1, \dots, x_n, y_1,\dots, y_m))$, where each of $f(x_1, \dots, x_n, y_1,\dots, y_m)$ and $g(x_1, \dots, x_n, y_1,\dots, y_m)$ is a term in this language having the form of a polynomial whose variables are among $x_1, \dots, x_n, y_1, \dots, y_m$, and whose coefficients are terms of the form $\mathbf{S}\mathbf{S} \dots \mathbf{S}\mathbf{0}$.

We of course know (Rosser-Kleene-Mostowski) that there is a $\Sigma_1$-formula $\phi(x)$ with one free variable $x$ such that for every consistent recursively axiomatizable theory $T$ extending $Q$, there is some $n$ such that the sentence $\phi(\mathbf{S}^n\mathbf{0})$ is undecidable in $T$.

Question: Is there a diophantine formula $\phi(x)$ for which the above will be true (i.e. for every consistent recursively axiomatizable theory $T$ extending $Q$, there is some $n$ such that the sentence $\phi(\mathbf{S}^n\mathbf{0})$ is undecidable in $T$)?

Note that we are only requiring that $T$ be a consistent recursively axiomatizable theory extending $Q$, and so are allowing $T$ to be $\omega$-inconsistent.