Frage im Zusammenhang mit Hilberts 10. Problem

Mit und kann man die folgende Formel in der Sprache der formalen Arithmetik definieren $n \in \mathbb{N}$ $p,q \in \mathbb{N}[x_1,\ldots,x_n]$

φ (n, p, q) = \forall x_{1} \dots \forall x_{n} : \neg (p (x_{1}, \dots, x_{n}) = q (x_{1}, \dots, x_{n}))

$\varphi(n,p,q) = \forall x_1 \cdots \forall x_n : \neg (p(x_1,\ldots,x_n) = q(x_1,\ldots,x_n))$

Ich möchte zeigen, dass es unendlich viele Tripel so dass weder noch ein Satz der formalen Arithmetik ist. $(n,p,q)$ $\varphi(n,p,q)$ $\neg \varphi(n,p,q)$

Um dies zu zeigen, kann ich die Tatsache nutzen, dass das Problem der Entscheidung, ob ein Polynom eine natürliche Null hat, unentscheidbar ist. $r \in \mathbb{Z}[x_1,\ldots,x_n]$

Wenn wir die obige Tatsache kennen, wissen wir, dass es ein Polynom so dass weder noch ist ein Satz. (Hier sind die Quantifizierer über den Naturwerten, von denen ich nicht sicher bin, ob ich sie absichtlich verwenden kann?) $r \in \mathbb{Z}[x_1,\ldots,x_n]$

φ^{'} = \forall x_{1} \dots \forall x_{n} : \neg (r (x) = 0)

$\varphi' = \forall x_1 \cdots \forall x_n : \neg (r(x) = 0)$

\neg φ^{'}

$\neg \varphi'$

Sobald wir ein solches haben, können wir es schreiben als für und damit und sind ebenfalls keine Theoreme, da logisch und wir dies gezeigt haben Dies ist kein Satz. $r$

r (x_{1}, \dots, x_{n}) = p (x_{1}, \dots, x_{r}) - q (x_{1}, \dots, x_{n})

$r(x_1,\ldots,x_n) = p(x_1,\ldots,x_r) - q(x_1,\ldots,x_n)$

p, q \in N [x_{1}, \dots, x_{n}]

$p,q \in \mathbb{N}[x_1,\ldots,x_n]$

φ (n, p, q)

$\varphi(n,p,q)$

\neg φ (n, p, q)

$\neg \varphi(n,p,q)$

φ

$\varphi$

φ^{'}

$\varphi'$

Sobald wir ein solches Tripel haben, haben wir unendlich viele davon, da wir einfach für $(n,p,q)$ $(n,p+k,q+k)$ $k \in \mathbb{N}.$

Da ich solche Dinge noch nie zuvor gemacht habe, frage ich mich, ob die obige Argumentation richtig ist?

computability logic undecidability Jernej
quelle

Sie können auch beide Seiten mit einem konstanten Faktor multiplizieren ...

Cody

Es wäre interessanter, unendliche Paare von (p, q) zu finden, die nicht durch "affine Transformationen" verwandt sind. Ich vermute, dass es ein relativ einfaches Argument gibt, um dies ebenfalls zu zeigen.

Cody

Sie können eine Variable durch oder , um ein "anderes" Paar .

a + b

$a+b$

a^{2} + b^{2} + c^{2} + d^{2}

$a^2+b^2+c^2+d^2$

x_{i}

$x_i$

(p, q)

$(p,q)$

Yuval Filmus

Wie Yuval und Cody gezeigt haben, gibt es einfache Lösungen, um unendlich viele diophantinische Gleichungen zu erhalten, die weder beweisbar noch widerlegbar sind (sagen wir in PA).

Diese syntaktische Lösung führt jedoch zu nachweislich äquivalenten Mengen, dh Mengen, die die Theorie beweisen kann, dass sie äquivalent sind. Sie können diese als Füllargumente betrachten. Eine andere Möglichkeit ist das Hinzufügen einer Variablen, die überhaupt nicht verwendet wird.

Sie können auch explizit mit dem Hinzufügen oder Entfernen einiger Zeichenfolgen spielen (endliche Variationen des Satzes).

Wenn Sie diophantinische Gleichungen erhalten möchten, die "wesentlich" unterschiedlich sind (z. B. sind die Mengen nicht Turing-äquivalent), dann ist dies eine größere Herausforderung, und ich denke, dass es nicht ausreicht, zu wissen, dass es eine unabhängige diophantinische Gleichung gibt, müssen Sie die Tatsache berücksichtigen, dass jedes re set kann als diophantinische Gleichung (oder ähnliches) codiert werden.

ps: da Sie sich nur um die Unabhängigkeit kümmern, ist es natürlicher, diese Formeln als diophantinische Gleichungen darzustellen, nicht als ihre Negationen.

Kaveh
quelle

Frage im Zusammenhang mit Hilberts 10. Problem

Antworten: