Üs alma ve çarpma için ilkel yinelemeli yüklemler
Aşağıdaki gayri resmi olarak ifade edilmiş ve zayıf bir şekilde sahip olunan inançlara sahibim, bunların bazıları daha fazla düşündüğümde bana tutarsız görünüyor. Düşüncemdeki hataların kaynağının nerede olabileceğini merak ediyorum; temel tanımlardaki hatalar kesin bir olasılıktır.
Toplama ve çarpma ile tamsayıların birinci dereceden teorisinde niceleyici eliminasyonu yapmak imkansızdır. (Bu, söyleyebileceğim kadarıyla, ilk eksiklik teoreminin biraz daha güçlü bir versiyonudur.)
Toplama ve çarpma ile tamsayıların birinci dereceden teorisinde, üs alma için ilkel özyinelemeli bir yüklem tanımlamak mümkündür. (Üs alma için bir yüklem derken, sadece "$Fabc\text{ just when }a^b = c.$")
İse iki operasyonları ile tamsayılar birinci dereceden teoride niceleyici yokedilmesine yapmak mümkün$a \oplus b = \min(a, b)$ ve $a \otimes b = a + b$(yani, tam sayıların olağan toplamı). Aslında niceleyici eliminasyonu yapmak için asalların bölünebilirlik tahminlerine ve çarpma operatörlerine ihtiyacımız olduğunun farkındayım.
İşlemlerle tamsayıların birinci dereceden teorisinde $\oplus$ ve $\otimes$, çarpma için ilkel özyinelemeli bir yüklem tanımlamak mümkündür (yukarıdaki üs alma koşulu ile hemen hemen aynı şekilde).
Kabaca konuşursak, "sıradan operasyonlar kulesi" arasındaki analojide bir bozulma var gibi görünüyor. $(+, \times, \hat{\phantom{n}}, \cdots)$ ve "tropikal operasyonlar kulesi" $(\min, +, \times, \cdots)$.
Daha spesifik olarak, eğer (4) ve (3) doğruysa, neden çarpım koşulunu özgürce kullanıp sonra hem niceliksel eliminasyonu yapıp ((3) aracılığıyla) hem de yapamayacağımız bir duruma sahip olduğumuzu anlamıyorum nicelik belirteci eliminasyonu ((1) aracılığıyla). (2) doğru olsa da (4) doğru olmasaydı beni çok şaşırtabilirdi ve (2) yanlış olsaydı beni daha da şaşırtardı.
Üs alma yükleminin ne anlama geldiğini tam olarak anlayamadığımdan şüpheleniyorum (yani benim gayri resmi tanımım $Fabc$ yanlıştır, yoksa "çarpma koşulunu serbestçe kullanma" ile ilgili farkında olmadığım biraz daha ayrıntı var.
Yanıtlar
İddialarınız $(1), (2)$, ve $(3)$her biri doğru. İddia$(4)$ancak yanlıştır ; gerçekten, çarpma üzerinden tanımlanabilir olsaydı$(\mathbb{N};\max,+)$ sonra teori $Th(\mathbb{N};\max,+)$ kadar karmaşık olurdu $Th(\mathbb{N};+,\times)$. Ancak ilki özyinelemelidir, ikincisi ise aritmetik olarak tanımlanamaz.
Sorun, çarpma işleminin toplama açısından "açık" tanımının aslında birinci dereceden olmamasıdır: özyinelemeli tanımlar, birinci dereceden mantığın yapabileceği bir şey değildir. Yeterince zengin yapılarda, özyinelemeli tanımları birinci dereceden bir şekilde gerçekleştirmenin yollarını bulabiliriz ve aslında bu,$Th(\mathbb{N};+,\times)$Bu anlamda Gödel'in eoremini mümkün kılar, ancak toplama tek başına bu işi yapacak kadar güçlü değildir. Önemli olan, hem toplamaya hem de çarpmaya sahipsek, sonlu doğal dizilerini bireysel doğal maddelerle "kodlayabiliriz" (ör.$\beta$fonksiyonu ) ve bunların kodlama dizileri hakkında konuşarak özyinelemeli yapılar hakkında bu kadar konuşmak "adım-adım davranışları," ama eklenmesiyle yalnız biz bile kod çiftleri tek tek sayılarla numaralar .
Bu son cümleyi detaylandırmak ve iddianıza geri dönmek $(2)$İşte birinci dereceden bir şekilde toplama ve çarpma kullanarak üs almanın nasıl tanımlanacağına dair bir özet:
Sahibiz $a^b=c$ bir dizi olarak yorumlandığında uzunluğu olan bir sayı varsa $b$, ilk dönem $a$, son dönem $c$, ve $i+1$terim eşittir $a$ kere $i$inci terim.
Bunun "özyinelemeli" bir tanımdan ziyade "tek seferde" bir tanım olduğuna dikkat edin: sonlu dizileri sayılarla kodlamanın ayrıntılarını modulo, sadece tek tek sayılar üzerinden nicelemeyi ve temel özellikleri kontrol etmeyi içerir, ki bu tam olarak ilk şeydir. sipariş mantığı yapabilir. Sonlu dizileri birinci dereceden bir şekilde bireysel sayılar olarak kodlama yeteneği olmadan - ki$(\mathbb{N};\max,+)$ eksik - olağan birinci dereceden olmayan tanıma bağlı kalırdık.
- Bir kenara, bunun teoride "doğrulanabilir bir tanım" olması önemlidir: $\mathsf{Q}$, tam teorinin küçük bir parçası olan $Th(\mathbb{N};+,\times)$her biri için buna sahibiz $a,b,c$ kısaltılmış cümle $$\underline{a}^{\underline{b}}=\underline{c}$$ (nerede $\underline{k}$ sayı doğal sayının karşılığıdır $k$) kanıtlanabilir $\mathsf{Q}$ Eğer $a^b=c$ ve inkar edilemez $\mathsf{Q}$ Eğer $a^b\not=c$. Bu, temsil edilebilirlik olarak adlandırılır ve Gödel'in ispatının anahtar fikirlerinden biridir; aslında, her özyinelemeli işlev gösterilebilir .