เพรดิเคตแบบเรียกซ้ำดั้งเดิมสำหรับการยกกำลังและการคูณ
ฉันมีความเชื่อต่อไปนี้ที่ระบุไว้อย่างไม่เป็นทางการและถือไว้อย่างไม่เป็นทางการซึ่งบางส่วนดูเหมือนจะไม่สอดคล้องกับฉันเมื่อไตร่ตรองเพิ่มเติม ฉันสงสัยว่าต้นตอของข้อผิดพลาดในความคิดของฉันอาจอยู่ที่ใด ข้อผิดพลาดในคำจำกัดความพื้นฐานเป็นไปได้ที่แน่นอน
เป็นไปไม่ได้ที่จะทำการกำจัดตัวระบุในทฤษฎีลำดับที่หนึ่งของจำนวนเต็มด้วยการบวกและการคูณ (นี่คือเท่าที่ฉันสามารถบอกได้ว่าเป็นทฤษฎีบทที่ไม่สมบูรณ์แบบแรกที่แข็งแกร่งกว่าเล็กน้อย)
ในทฤษฎีลำดับที่หนึ่งของจำนวนเต็มด้วยการบวกและการคูณเป็นไปได้ที่จะกำหนดเพรดิเคตแบบเรียกซ้ำแบบดั้งเดิมสำหรับการยกกำลัง (โดยเพรดิเคตสำหรับการยกกำลังฉันแค่หมายถึงสิ่งที่มีพฤติกรรมเหมือน "$Fabc\text{ just when }a^b = c.$")
มันเป็นไปได้ที่จะกำจัดปริมาณในทฤษฎีลำดับแรกของจำนวนเต็มกับทั้งสองดำเนินการ$a \oplus b = \min(a, b)$ และ $a \otimes b = a + b$(กล่าวคือการบวกจำนวนเต็มธรรมดา) ฉันทราบดีว่าเราต้องการเพรดิเคตความสามารถในการหารและตัวดำเนินการคูณด้วยสำหรับไพรม์ในการกำจัดตัวบ่งชี้
ในทฤษฎีลำดับที่หนึ่งของจำนวนเต็มกับการดำเนินการ $\oplus$ และ $\otimes$เป็นไปได้ที่จะกำหนดเพรดิเคตแบบเรียกซ้ำแบบดั้งเดิมสำหรับการคูณ (เกือบจะเหมือนกับเพรดิเคตสำหรับการยกกำลังด้านบน)
พูดอย่างคร่าวๆดูเหมือนว่ามีการเปรียบเทียบระหว่าง "หอคอยปฏิบัติการธรรมดา" $(+, \times, \hat{\phantom{n}}, \cdots)$ และ "หอปฏิบัติการเขตร้อน" $(\min, +, \times, \cdots)$.
โดยเฉพาะอย่างยิ่งถ้า (4) และ (3) เป็นจริงฉันไม่เข้าใจว่าทำไมเราไม่สามารถใช้เพรดิเคตการคูณได้อย่างอิสระจากนั้นมีสถานการณ์ที่เราทั้งคู่สามารถกำจัดตัวระบุปริมาณ (ผ่าน (3)) และไม่ทำ การกำจัดปริมาณ (ผ่าน (1)) มันจะทำให้ฉันประหลาดใจมากถ้า (2) เป็นจริง แต่ (4) ไม่ใช่และจะทำให้ฉันประหลาดใจมากยิ่งขึ้นถ้า (2) เป็นเท็จ
ฉันสงสัยว่าฉันไม่ค่อยเข้าใจความหมายของเพรดิเคตเลขชี้กำลัง (กล่าวคือคำจำกัดความที่ไม่เป็นทางการของฉันคือ $Fabc$ ไม่ถูกต้องหรือมีรายละเอียดเพิ่มเติมเกี่ยวกับ "การใช้เพรดิเคตการคูณอย่างอิสระ" ที่ฉันไม่ทราบ
คำตอบ
การอ้างสิทธิ์ของคุณ $(1), (2)$และ $(3)$ถูกต้องหรือไม่ อ้างสิทธิ์$(4)$แต่เป็นที่ไม่ถูกต้อง ; แน่นอนถ้าการคูณสามารถกำหนดได้$(\mathbb{N};\max,+)$ แล้วทฤษฎี $Th(\mathbb{N};\max,+)$ จะซับซ้อนพอ ๆ $Th(\mathbb{N};+,\times)$. แต่อดีตจะเกิดขึ้นซ้ำในขณะที่อย่างหลังนั้นไม่สามารถกำหนดเลขคณิตได้
ปัญหาคือคำจำกัดความที่ "ชัดเจน" ของการคูณในแง่ของการบวกนั้นไม่ใช่ลำดับแรกจริง ๆ แล้วคำจำกัดความแบบวนซ้ำไม่ใช่สิ่งที่ตรรกะลำดับแรกสามารถทำได้ ในโครงสร้างที่สมบูรณ์เพียงพอเราสามารถหาวิธีดำเนินการคำจำกัดความแบบวนซ้ำได้ในลำดับแรกและแท้จริงแล้วความสมบูรณ์ของ$Th(\mathbb{N};+,\times)$ในแง่นี้ซึ่งทำให้ eorem ของ Godel เป็นไปได้ แต่การเพิ่มเพียงอย่างเดียวไม่ได้มีพลังเพียงพอที่จะทำให้งานนี้ กุญแจสำคัญคือถ้าเรามีทั้งการบวกและการคูณเราสามารถ "โค้ด" ลำดับที่ จำกัด ของธรรมชาติตามธรรมชาติแต่ละตัว (เช่นผ่านทาง$\beta$ฟังก์ชั่น ) และเพื่อพูดคุยเกี่ยวกับการก่อสร้าง recursive โดยการพูดคุยเกี่ยวกับลำดับการเขียนโปรแกรมของพวกเขา "พฤติกรรมขั้นตอนโดยขั้นตอน" แต่เพียงอย่างเดียวด้วยนอกจากนี้เราไม่สามารถแม้กระทั่งรหัสคู่ของตัวเลขโดยตัวเลขของแต่ละบุคคล
การอธิบายประโยคสุดท้ายและกลับไปที่การอ้างสิทธิ์ของคุณ $(2)$ต่อไปนี้เป็นโครงร่างของวิธีกำหนดเลขชี้กำลังโดยใช้การบวกและการคูณตามลำดับแรก:
เรามี $a^b=c$ iff มีตัวเลขบางตัวซึ่งเมื่อตีความเป็นลำดับแล้วจะมีความยาวคือ $b$, ระยะแรก $a$, ระยะสุดท้าย $c$และ $i+1$เทอมเท่ากับ $a$ คูณ $i$ระยะที่.
โปรดทราบว่านี่เป็นคำจำกัดความ "ทั้งหมดในครั้งเดียว" แทนที่จะเป็นคำจำกัดความโดย "กระบวนการเรียกซ้ำ:" ปรับรายละเอียดของการเข้ารหัสลำดับ จำกัด ด้วยตัวเลขเพียงแค่เกี่ยวข้องกับการหาปริมาณจากตัวเลขแต่ละตัวและการตรวจสอบคุณสมบัติพื้นฐานซึ่งเป็นสิ่งแรก ตรรกะการสั่งซื้อสามารถทำได้ หากไม่มีความสามารถในการเขียนโค้ดลำดับที่ จำกัด เป็นตัวเลขแต่ละตัวในลำดับแรก - ซึ่ง$(\mathbb{N};\max,+)$ ขาด - เราจะติดอยู่กับคำจำกัดความที่ไม่ใช่ลำดับที่หนึ่งตามปกติ
- นอกจากนี้สิ่งสำคัญคือ "นิยามที่ตรวจสอบได้:" ในทางทฤษฎี $\mathsf{Q}$ซึ่งเป็นส่วนเล็ก ๆ ของทฤษฎีเต็ม $Th(\mathbb{N};+,\times)$เรามีสิ่งนั้นสำหรับแต่ละคน $a,b,c$ ประโยคย่อโดย $$\underline{a}^{\underline{b}}=\underline{c}$$ (ที่ไหน $\underline{k}$ คือตัวเลขที่ยืนอยู่สำหรับจำนวนธรรมชาติ $k$) สามารถพิสูจน์ได้ในรูปแบบ $\mathsf{Q}$ ถ้า $a^b=c$ และไม่สามารถพิสูจน์ได้ใน $\mathsf{Q}$ ถ้า $a^b\not=c$. สิ่งนี้เรียกว่าความสามารถในการเป็นตัวแทนและเป็นหนึ่งในแนวคิดหลักในการพิสูจน์ของ Godel ในความเป็นจริงฟังก์ชันการเรียกซ้ำทุกฟังก์ชันสามารถแสดงได้