การเหนี่ยวนำอนันต์เป็นการขยายการเหนี่ยวนำทางคณิตศาสตร์ไปยังจำนวนเชิงอันดับความถูกต้องของมันเป็นทฤษฎีบทของZFและอาศัยข้อเท็จจริงที่ว่าจำนวนเชิงอันดับมีลำดับที่ดีดังนั้นข้อความที่ไม่เป็นจริงโดยทั่วไปสำหรับจำนวนเชิงอันดับทั้งหมดจะต้องมีตัวอย่างค้านขั้นต่ำในความเป็นจริง หลักการนี้ยังเป็นจริงสำหรับเซตที่มีลำดับที่ดีใดๆ แต่เนื่องจากเซตที่มีลำดับที่ดีใดๆ สามารถจัดทำดัชนีโดยจำนวนเชิงอันดับในลักษณะที่รักษาลำดับไว้ได้ จึงเพียงพอที่จะสร้างหลักการสำหรับจำนวนเชิงอันดับ^{[ 1 ]}

หลักการของการเหนี่ยวนำอนันต์มีดังนี้:

ให้เป็นคุณสมบัติที่กำหนดไว้สำหรับลำดับทั้งหมดสมมติว่าเมื่อใดก็ตามที่ เป็นจริงสำหรับ⁠ ⁠ ทั้งหมด แล้วก็เป็นจริงเช่นกัน^{[ 2 ]}ดังนั้น จึงเป็นจริงสำหรับลำดับทั้งหมด${\displaystyle P(\alpha )}$${\displaystyle \alpha }$${\displaystyle P(\beta )}$${\displaystyle \beta <\alpha }$${\displaystyle P(\alpha )}$${\displaystyle P}$

หลักการนี้สามารถพิสูจน์ได้ง่ายๆ โดยพิจารณาจาก รูปแบบ ข้อความแย้ง :

ถ้า⁠ ⁠${\displaystyle P}$ไม่เป็นจริงสำหรับลำดับทั้งหมดแล้ว จะมีลำดับ⁠ ⁠${\displaystyle \alpha }$ อยู่ตัวหนึ่ง ซึ่ง⁠ ⁠${\displaystyle P(\beta )}$เป็นจริงสำหรับ ⁠ ⁠ ทุกตัวแต่${\displaystyle \beta <\alpha }$ ⁠ ⁠ เป็น${\displaystyle P(\alpha )}$เท็จ

ตัวอย่าง${\displaystyle \alpha }$เช่นนี้เป็นเพียงตัวอย่างค้านขั้นต่ำซึ่งการมีอยู่ของมันได้รับการรับประกันโดยข้อเท็จจริงที่ว่ากลุ่มของจำนวนเชิงอันดับนั้นมีลำดับที่ดี

การพิสูจน์โดยใช้การเหนี่ยวนำแบบอนันต์มักแบ่งออกเป็นสามกรณี:

• กรณีศูนย์:พิสูจน์ว่าสิ่งนั้นเป็นจริง${\displaystyle P(0)}$
• กรณีตัวสืบทอด:พิสูจน์ว่าสำหรับลำดับที่สืบทอด ใดๆ จะได้มาจาก(และถ้าจำเป็นสำหรับทุกๆ)${\displaystyle \alpha +1}$${\displaystyle P(\alpha +1)}$${\displaystyle P(\alpha )}$${\displaystyle P(\beta )}$${\displaystyle \beta <\alpha }$
• กรณีลิมิต:พิสูจน์ว่าสำหรับลำดับลิมิต ใดๆ ถ้า เป็น จริงสำหรับทุกแล้ว${\displaystyle \lambda }$${\displaystyle P(\beta )}$${\displaystyle \beta <\แลมบ์ดา }$${\displaystyle P(\lambda )}$

ทั้งสามกรณีเหมือนกันทุกประการ ยกเว้นประเภทของลำดับที่พิจารณา ในทางทฤษฎีแล้วไม่จำเป็นต้องพิจารณาแยกกัน แต่ในทางปฏิบัติแล้ว การพิสูจน์มักแตกต่างกันมากจนต้องนำเสนอแยกกัน ศูนย์บางครั้งถูกพิจารณาว่าเป็นลำดับลิมิตและบางครั้งอาจถูกพิจารณาในการพิสูจน์ในลักษณะเดียวกับลำดับลิมิต

การเรียกซ้ำแบบอนันต์คล้ายกับการอุปนัยแบบอนันต์ อย่างไรก็ตาม แทนที่จะพิสูจน์ว่าบางสิ่งบางอย่างเป็นจริงสำหรับจำนวนเชิงอันดับทั้งหมด เราจะสร้างลำดับของวัตถุขึ้นมาหนึ่งชิ้นสำหรับแต่ละจำนวนเชิงอันดับ

ตัวอย่างเช่นฐาน สำหรับ ปริภูมิเวกเตอร์ (ซึ่งอาจมีมิติอนันต์) สามารถสร้างได้โดยเริ่มจากเซตว่าง และสำหรับแต่ละลำดับα > 0เลือกเวกเตอร์ที่ไม่ปรากฏอยู่ในปริภูมิที่เกิดจากการรวมเวกเตอร์กระบวนการนี้จะหยุดลงเมื่อไม่สามารถเลือกเวกเตอร์ได้อีกต่อไป ${\displaystyle \{v_{\beta }\mid \beta <\alpha \}}$

กล่าวอย่างเป็นทางการมากขึ้น เราสามารถกล่าวถึงทฤษฎีบทการเรียกซ้ำแบบอนันต์ได้ดังนี้:

ทฤษฎีบทการเรียกซ้ำแบบอนันต์ (เวอร์ชัน 1)กำหนดให้ฟังก์ชันคลาส ^{[ 3 ]} G : V → V (โดยที่ Vคือคลาสของเซตทั้งหมด) จะมีลำดับอนันต์ที่ไม่ซ้ำ กัน F : Ord → V (โดยที่ Ord คือคลาสของลำดับทั้งหมด) เช่นนั้น

${\displaystyle F(\alpha )=G(F\upharpoonright \alpha )}$สำหรับลำดับทั้งหมดαโดยที่หมายถึงการจำกัดโดเมนของF ให้เหลือเฉพาะลำดับ < α${\displaystyle \upharpoonright }$

เช่นเดียวกับกรณีของการอุปนัย เราอาจพิจารณาลำดับประเภทต่างๆ แยกกันได้: รูปแบบอื่นของการเรียกซ้ำแบบอนันต์มีดังต่อไปนี้:

ทฤษฎีบทการเรียกซ้ำอนันต์ (เวอร์ชัน 2)กำหนดให้เซตg ₁และฟังก์ชันชั้นG ₂ , G ₃จะมีฟังก์ชันF : Ord → V ที่ไม่ซ้ำกันเพียงฟังก์ชันเดียวเท่านั้น ซึ่งทำให้

• F (0) = g ₁ ,
• F ( α + 1) = G ₂ ( F ( α )) สำหรับα ∈ Ord ทั้งหมด
• ${\displaystyle F(\lambda )=G_{3}(F\upharpoonright \lambda )}$สำหรับค่าลิมิตλ ≠ 0 ทั้งหมด

โปรดทราบว่าเราต้องการให้โดเมนของG ₂และG ₃กว้างพอที่จะทำให้คุณสมบัติข้างต้นมีความหมาย ความเป็นเอกภาพของลำดับที่สอดคล้องกับคุณสมบัติเหล่านี้สามารถพิสูจน์ได้โดยใช้การเหนี่ยวนำแบบอนันต์

โดยทั่วไปแล้ว เราสามารถกำหนดนิยามของวัตถุได้โดยใช้การเรียกซ้ำแบบอนันต์บนความสัมพันธ์ที่มีรากฐานที่ดี ใดๆ R ( Rไม่จำเป็นต้องเป็นเซตด้วยซ้ำ อาจเป็นคลาสที่เหมาะสมก็ได้ ตราบใดที่เป็นความสัมพันธ์ที่คล้ายเซตกล่าวคือ สำหรับx ใดๆ การรวบรวมy ทั้งหมด ที่ทำให้yRxเป็นเซต)

การพิสูจน์หรือการสร้างโดยใช้การเหนี่ยวนำและการเรียกซ้ำมักใช้สัจพจน์ของการเลือกเพื่อสร้างความสัมพันธ์ที่มีลำดับที่ดีซึ่งสามารถจัดการได้ด้วยการเหนี่ยวนำแบบอนันต์ อย่างไรก็ตาม หากความสัมพันธ์ที่กล่าวถึงมีลำดับที่ดีอยู่แล้ว มักจะสามารถใช้การเหนี่ยวนำแบบอนันต์ได้โดยไม่ต้องอ้างถึงสัจพจน์ของการเลือก^{[ 4 ]}ตัวอย่างเช่น ผลลัพธ์มากมายเกี่ยวกับเซต Borelได้รับการพิสูจน์โดยการเหนี่ยวนำแบบอนันต์บนอันดับลำดับของเซต อันดับเหล่านี้มีลำดับที่ดีอยู่แล้ว ดังนั้นจึงไม่จำเป็นต้องใช้สัจพจน์ของการเลือกเพื่อจัดลำดับให้ดี

การสร้าง เซต Vitaliต่อไปนี้แสดงให้เห็นถึงวิธีหนึ่งที่สามารถใช้สัจพจน์ของการเลือกในการพิสูจน์โดยการอุปมานแบบอนันต์ได้:

ขั้นแรกเรียงลำดับจำนวนจริงให้เหมาะสม ( นี่คือจุดที่สัจพจน์ของการเลือกเข้ามาเกี่ยวข้องผ่านทฤษฎีบทการเรียงลำดับที่เหมาะสม ) ทำให้ได้ลำดับโดยที่ β เป็นจำนวนเชิงอันดับที่มีขนาดเท่ากับจำนวนต่อเนื่องให้v ₀เท่ากับr ₀จากนั้นให้v ₁เท่ากับr _{α 1}โดยที่α _{1 เป็น} จำนวนจริงที่น้อยที่สุดที่ทำให้r _{α 1}  −  v ₀ไม่ใช่ จำนวนตรรกยะ ทำเช่นนี้ ต่อไป ในแต่ละขั้นตอน ให้ใช้จำนวนจริงที่น้อยที่สุดจาก ลำดับ rที่ไม่มีผลต่างเชิงตรรกยะกับสมาชิกใดๆ ที่สร้างขึ้นใน ลำดับ v ทำเช่นนี้ ต่อไปจนกว่าจำนวนจริงทั้งหมดใน ลำดับ r จะหมดไป ลำดับ vสุดท้ายจะแจงนับเซต Vitali${\displaystyle \langle r_{\alpha }\mid \alpha <\beta \rangle }$

ข้อโต้แย้งข้างต้นใช้สัจพจน์ของการเลือกในลักษณะสำคัญตั้งแต่เริ่มต้น เพื่อจัดลำดับจำนวนจริงให้ถูกต้อง หลังจากนั้นแล้ว สัจพจน์ของการเลือกก็ไม่ได้ถูกนำมาใช้อีก

การใช้สัจพจน์ของการเลือกในรูปแบบอื่นๆ นั้นมีความซับซ้อนกว่า ตัวอย่างเช่น การสร้างโดยการเรียกซ้ำแบบอนันต์มักจะไม่ระบุ ค่า ที่ไม่ซ้ำกันสำหรับA _{α +1}เมื่อกำหนดลำดับจนถึงαแต่จะระบุเพียงเงื่อนไขที่A _{α +1}ต้องเป็นไปตาม และโต้แย้งว่ามีอย่างน้อยหนึ่งเซตที่ตรงตามเงื่อนไขนี้ หากไม่สามารถกำหนดตัวอย่างที่ไม่ซ้ำกันของเซตดังกล่าวในแต่ละขั้นตอนได้ อาจจำเป็นต้องใช้สัจพจน์ของการเลือก (ในรูปแบบใดรูปแบบหนึ่ง) เพื่อเลือกเซตดังกล่าวในแต่ละขั้นตอน สำหรับการอุปมานและการเรียกซ้ำที่มี ความ ยาวที่นับได้ สัจพจน์ ของการเลือกแบบพึ่งพา ที่อ่อนกว่า ก็เพียงพอแล้ว เนื่องจากมีแบบจำลองของทฤษฎีเซต Zermelo–Fraenkelที่น่าสนใจสำหรับนักทฤษฎีเซตซึ่งตรงตามสัจพจน์ของการเลือกแบบพึ่งพาแต่ไม่ตรงตามสัจพจน์ของการเลือกแบบเต็ม ความรู้ที่ว่าการพิสูจน์เฉพาะนั้นต้องการเพียงการเลือกแบบพึ่งพาเท่านั้นจึงมีประโยชน์

• การเหนี่ยวนำทางคณิตศาสตร์
• การเหนี่ยวนำ ∈
• จำนวนอนันต์
• การเหนี่ยวนำที่มีเหตุผลที่ดี
• ทฤษฎีบทของซอร์น

• เอเมอร์สัน, โจนาธาน ; เลซามา, มาร์คและไวส์สไตน์, เอริค ดับเบิลยู. "การเหนี่ยวนำอนันต์" . MathWorld .