ความชัดเจนของคำสั่งในลายเซ็นต่างๆ
เมื่อเร็ว ๆ นี้ฉันได้ศึกษาว่าส่วนย่อยที่กำหนดได้ของลำดับที่นับได้ "มีลักษณะอย่างไร" จากมุมมองของตรรกะลำดับที่หนึ่งของกระดูกเปลือย (ไม่ใช่ทฤษฎีเซต) พร้อมกับวิธีต่างๆในการ "เข้าถึง" โครงสร้างของลำดับ
ตัวอย่างเช่นเราอาจมีลายเซ็นที่ประกอบด้วยสัญลักษณ์เชิงสัมพันธ์ 2 อาร์เรย์เท่านั้น $S$ ซึ่งเราตีความในโครงสร้าง $\mathcal{A}$ พร้อมชุดพื้นฐาน $\omega_1$ เป็นชุดของ $(\alpha,\beta)$ ดังนั้น $\beta$ เป็นผู้สืบทอดของ $\alpha$. จากนั้นเราสามารถถามคำถามเกี่ยวกับชุดย่อยของ$\mathcal{A}$ สามารถกำหนดได้ด้วยประโยคลอจิกลำดับที่หนึ่งที่มีลายเซ็นนี้ซึ่งเป็นส่วนย่อย $S\subset\mathcal{A}$ ถือว่าสามารถกำหนดได้หากมีประโยคลอจิกลำดับแรก $\phi(x)$ ซึ่งชุดของการมอบหมายที่น่าพอใจของ $x$ คือ $S$. ในตัวอย่างของเราเราสามารถกำหนดเซตของลำดับตัวต่อที่นับได้ทั้งหมดผ่านทางสูตร$\exists y:S(y,x)$.
เรายังสามารถถามคำถามเช่น "ลำดับที่เล็กที่สุดคืออะไร $\alpha$ ดังนั้น $\alpha$ ไม่สามารถกำหนดได้ในแง่ที่ว่า $\{\alpha\}$ ไม่สามารถกำหนดได้ "และในตัวอย่างข้างต้นเห็นได้ชัดว่าในความเป็นจริงไม่มีลำดับใดที่สามารถกำหนดได้ดังนั้นลำดับที่ไม่สามารถกำหนดได้ที่เล็กที่สุดจึงเป็นศูนย์ฉันสนใจเป็นพิเศษว่าลำดับที่เล็กที่สุดที่ไม่สามารถกำหนดได้เติบโตขึ้นอย่างไรเมื่อเรามีลายเซ็นที่แข็งแกร่งและแข็งแกร่งขึ้น ตัวอย่างเช่นฉันสามารถโน้มน้าวตัวเองด้วยลายเซ็น $\{<\}$ ด้วยการตีความที่ชัดเจนใน $\omega_1$ ในฐานะ "น้อยกว่าความสัมพันธ์" ลำดับที่เล็กที่สุดที่ไม่สามารถกำหนดได้คือ $\omega^\omega$ (แม้ว่าฉันจะยังไม่ได้เขียนข้อโต้แย้งอย่างเป็นทางการ)
คำถามของฉันคือมีใครศึกษาคำถามแบบนี้บ้าง? เป็นที่รู้กันว่าลำดับที่เล็กที่สุดที่กำหนดได้คืออะไรสำหรับลายเซ็นอื่น ๆ เช่น$\{ADD(x,y,z)\}$ ซึ่งเป็นความจริงกับทุกคน $x,y,z$ ดังนั้น $x+y=z$หรือแม้แต่ลายเซ็นอื่น ๆ ที่มีการคูณการยกกำลังฟังก์ชัน veblen หรืออื่น ๆ มีความรู้ทั่วไปของแนวคิดเหล่านี้หรือไม่? ขอความช่วยเหลือหรือวรรณกรรมที่เกี่ยวข้อง
คำตอบ
ฉันไม่มีชื่อเสียงมากพอที่จะเพิ่มความคิดเห็น กระดาษต่อไปนี้อาจเป็นประโยชน์สำหรับคุณ มันมีผลลัพธ์ที่ขยายการทำงานของ Tarski, Mostowski และ Doner ตลอดจนภาพรวมและข้อมูลอ้างอิงทางประวัติศาสตร์ที่ดีมาก
Buchi, Siefkes - ส่วนขยายที่สมบูรณ์ของทฤษฎี Monadic Second Order of Countable Ordinals
ตรรกะลำดับที่สองของ monadic ที่อ่อนแอปรากฏอยู่แล้วในงานต้นฉบับของ Ehrenfeucht แม้ว่าคุณจะสนใจเฉพาะในผลลัพธ์ของลำดับที่หนึ่ง แต่ตรรกะของลำดับที่สองแบบ monadic ก็สามารถมีบทบาทได้
ตัวอย่างเช่นทฤษฎีลำดับแรกของการบวกลำดับเกิดขึ้นพร้อมกับทฤษฎีลำดับแรกของการบวกลำดับที่อยู่ภายใน $\omega^{\omega^{\omega}}$ (โดย Ehrenfeuct) ในขณะที่ $(\omega^{\omega^{\omega}},+)$ เป็นการลดทอนอำนาจโดยทั่วไปของ $(\omega,+)$ โดย 'เลขชี้กำลัง' เป็นเวอร์ชันลำดับที่สองที่อ่อนแอของ $(\omega^{\omega},<)$(ทฤษฎีบท Feferman-Vaught เป็นเครื่องมือที่ถูกต้องในการทำความเข้าใจเรื่องนี้) สำหรับรายละเอียดเพิ่มเติมมีThomas - Ehrenfeucht, Vaught และความสามารถในการตัดสินใจของทฤษฎีผู้สืบทอดที่อ่อนแอรายละเอียดที่นี่ถูกต้องทั้งหมด แต่ฉันคิดว่าข้อสรุปมีประเด็นบางอย่าง
นอกจากนี้ยังมีงานล่าสุดเกี่ยวกับด้านออโตมาตะเช่นCachat - Tree Automata Make Ordinal Theory Easy ฉันไม่รู้อะไรเกี่ยวกับเนื้อหานี้ แต่ถ้าคุณต้องการภาพรวมที่ครอบคลุมของพื้นที่นี่อาจเป็นจุดเริ่มต้น