Pertanyaan terkait masalah 10 Hilbert

Dengan dan orang dapat mendefinisikan rumus berikut dalam bahasa aritmatika formal $n \in \mathbb{N}$ $p,q \in \mathbb{N}[x_1,\ldots,x_n]$

φ (n, hal, q) = \forall x_{1} \dots \forall x_{n} : \neg (hal (x_{1}, ..., x_{n}) = q (x_{1}, ..., 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))$

Saya ingin menunjukkan bahwa ada banyak tiga kali lipat sehingga tidak ada atau adalah teorema aritmatika formal. $(n,p,q)$ $\varphi(n,p,q)$ $\neg \varphi(n,p,q)$

Dalam menunjukkan ini saya dapat menggunakan fakta bahwa masalah memutuskan apakah polinomial memiliki nol alami tidak dapat diputuskan. $r \in \mathbb{Z}[x_1,\ldots,x_n]$

Mengetahui fakta di atas kita tahu bahwa ada polinomial sedemikian rupa sehingga tidak ada atau adalah teorema. (Di sini bilangan bulat melebihi naturals yang saya tidak yakin apakah saya bisa menggunakannya dengan sengaja?) $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'$

Setelah kita memiliki seperti itu, kita dapat menuliskannya sebagai untuk dan karenanya dan juga bukan teorema karena secara logis setara dengan dan kami telah menunjukkan bahwa ini bukan teorema. $r$

r (x_{1}, ..., x_{n}) = hal (x_{1}, ..., x_{r}) - q (x_{1}, ..., 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'$

Setelah kita memiliki satu triple kita memiliki banyak dari mereka karena kita dapat mengambil untuk $(n,p,q)$ $(n,p+k,q+k)$ $k \in \mathbb{N}.$

Karena saya tidak pernah melakukan hal seperti itu sebelum saya bertanya-tanya apakah alasan di atas benar?

computability logic undecidability Jernej
sumber

Anda juga dapat mengalikan kedua sisi dengan faktor konstan ...

cody

Akan lebih menarik untuk menemukan pasangan tak terbatas (p, q) yang tidak berhubungan dengan "transformasi affine". Saya menduga ada argumen yang relatif sederhana untuk menunjukkan ini juga.

cody

Anda dapat mengganti atau untuk variabel untuk mendapatkan pasangan "berbeda" .

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

Seperti yang ditunjukkan oleh Yuval dan cody ada solusi mudah untuk mendapatkan banyak persamaan Diophantine yang tidak dapat dibuktikan atau disangkal (katakanlah dalam PA).

Namun solusi sintaksis ini menghasilkan set yang dapat dibuktikan setara, yaitu set yang dapat dibuktikan oleh teori bahwa mereka setara. Anda dapat menganggap ini sebagai argumen padding. Cara lain adalah menambahkan variabel yang tidak digunakan sama sekali.

Anda juga dapat bermain dengan menambahkan atau menghapus beberapa string secara eksplisit (variasi set yang terbatas).

Jika Anda ingin mendapatkan persamaan Diophantine yang "pada dasarnya" berbeda (misalnya set tidak setara Turing) maka itu lebih menantang dan saya pikir mengetahui bahwa ada persamaan Diophantine independen tidak cukup, Anda akan memerlukan fakta bahwa setiap set dapat dikodekan sebagai persamaan Diophantine (atau yang serupa).

ps: karena Anda hanya peduli pada kemandirian, lebih alami untuk merepresentasikan formula ini sebagai persamaan Diophantine dan bukan negasinya.

Kaveh
sumber

Pertanyaan terkait masalah 10 Hilbert

Jawaban: