บทนิยามเวียนเกิด

บทนิยามเวียนเกิด (อังกฤษ: recursive definition) หรือบทนิยามแบบอุปนัย (อังกฤษ: inductive definition) เป็นคณิตตรรกศาสตร์และวิทยาการคอมพิวเตอร์ที่ใช้นิยามสมาชิกในเซตหนึ่งในพจน์สมาชิกอื่นในเซต

บทนิยามเวียนเกิดของฟังก์ชันนิยามค่าของฟังก์ชันสำหรับค่าป้อนเข้าบางค่าในพจน์ค่าของฟังก์ชันเดิมสำหรับค่าป้อนเข้าอื่น ตัวอย่างเช่น ฟังก์ชันแฟกทอเรียล n! นิยามด้วยกฎดังนี้

0! = 1.

(n+1)! = (n+1)·n!.

บทนิยามนี้สมเหตุสมผลสำหรับทุก n เพราะการเวียนกลับสุด้ายจะถึงกรณีฐาน 0 บทนิยามนี้อาจยังคิดได้เป็นการให้กระบวนงานอธิบายการสร้างฟังก์ชัน n! โดยเริ่มจาก n = 0 แล้วต่อไปเป็น n = 1, n = 2, n = 3 เป็นต้น

ทฤษฎีบทเวียนเกิดระบุว่า บทนิยามดังนี้นิยามฟังก์ชันหนึ่ง ข้อพิสูจน์ใช้การอุปนัยทางคณิตศาสตร์

บทนิยามแบบอุปนัยของเซตอธิบายสมาชิกในเซตในพจน์สมาชิกอื่นในเซต ตัวอย่างเช่น บทนิยามหนึ่งของเซต N ของจำนวนธรรมชาติเป็นดังนี้

1. 1 อยู่ใน N.
2. หากสมาชิก n อยู่ใน N แล้ว n+1 อยู่ใน N
3. N เป็นส่วนร่วมของทุกเซตที่เป็นไปตามข้อ (1) และ (2)

มีเซตจำนวนมากที่เป็นไปตามข้อ (1) และ (2) ตัวอย่างเช่นเซต {1, 1.649, 2, 2.649, 3, 3.649, ...} เข้าได้กับบนิยาม ทว่า เงื่อนไข (3) เจาะจงเซตจำนวนธรมชาติโดยตัดสมาชิกภายนอก

คุณสมบัติของฟังก์ชันและเซตที่นิยามเวียนเกิดสามารถพิสูจน์ได้โดยหลักการอุปนัยซึ่งเป็นไปตามบทนิยามเวียนเกิด ตัวอย่างเช่น บทนิยามของจำนวนธรรมชาติที่แสดงในที่นี้ส่อความหลักการอุปนัยทางคณิตศาสตร์สำหรับจำนวนธรรมชาติ คือ หากคุณสมบัติเข้าได้กับจำนวนธรรมชาติ 0 และคุณสมบัติเข้าได้กับ n+1 ต่อเมื่อเข้าได้กับ n แล้วคุณสมบัติจะเข้าได้กับทุกจำนวนธรรมชาติ

อ้างอิง

1. (Aczel 1978:740ff).
2. (Aczel 1978:742)

บรรณานุกรม

• P. Aczel (1977), "An introduction to inductive definitions", Handbook of Mathematical Logic, J. Barwise (ed.),