บทนิยามเวียนเกิด
บทนิยามเวียนเกิด (อังกฤษ: recursive definition) หรือบทนิยามแบบอุปนัย (อังกฤษ: inductive definition) เป็นคณิตตรรกศาสตร์และวิทยาการคอมพิวเตอร์ที่ใช้นิยามสมาชิกในเซตหนึ่งในพจน์สมาชิกอื่นในเซต[1]
บทนิยามเวียนเกิดของฟังก์ชันนิยามค่าของฟังก์ชันสำหรับค่าป้อนเข้าบางค่าในพจน์ค่าของฟังก์ชันเดิมสำหรับค่าป้อนเข้าอื่น ตัวอย่างเช่น ฟังก์ชันแฟกทอเรียล n! นิยามด้วยกฎดังนี้
- 0! = 1.
- (n+1)! = (n+1)·n!.
บทนิยามนี้สมเหตุสมผลสำหรับทุก n เพราะการเวียนกลับสุด้ายจะถึงกรณีฐาน 0 บทนิยามนี้อาจยังคิดได้เป็นการให้กระบวนงานอธิบายการสร้างฟังก์ชัน n! โดยเริ่มจาก n = 0 แล้วต่อไปเป็น n = 1, n = 2, n = 3 เป็นต้น
ทฤษฎีบทเวียนเกิดระบุว่า บทนิยามดังนี้นิยามฟังก์ชันหนึ่ง ข้อพิสูจน์ใช้การอุปนัยทางคณิตศาสตร์
บทนิยามแบบอุปนัยของเซตอธิบายสมาชิกในเซตในพจน์สมาชิกอื่นในเซต ตัวอย่างเช่น บทนิยามหนึ่งของเซต N ของจำนวนธรรมชาติเป็นดังนี้
- 1 อยู่ใน N.
- หากสมาชิก n อยู่ใน N แล้ว n+1 อยู่ใน N
- N เป็นส่วนร่วมของทุกเซตที่เป็นไปตามข้อ (1) และ (2)
มีเซตจำนวนมากที่เป็นไปตามข้อ (1) และ (2) ตัวอย่างเช่นเซต {1, 1.649, 2, 2.649, 3, 3.649, ...} เข้าได้กับบนิยาม ทว่า เงื่อนไข (3) เจาะจงเซตจำนวนธรมชาติโดยตัดสมาชิกภายนอก
คุณสมบัติของฟังก์ชันและเซตที่นิยามเวียนเกิดสามารถพิสูจน์ได้โดยหลักการอุปนัยซึ่งเป็นไปตามบทนิยามเวียนเกิด ตัวอย่างเช่น บทนิยามของจำนวนธรรมชาติที่แสดงในที่นี้ส่อความหลักการอุปนัยทางคณิตศาสตร์สำหรับจำนวนธรรมชาติ คือ หากคุณสมบัติเข้าได้กับจำนวนธรรมชาติ 0 และคุณสมบัติเข้าได้กับ n+1 ต่อเมื่อเข้าได้กับ n แล้วคุณสมบัติจะเข้าได้กับทุกจำนวนธรรมชาติ[2]
อ้างอิง
[แก้]บรรณานุกรม
[แก้]- P. Aczel (1977), "An introduction to inductive definitions", Handbook of Mathematical Logic, J. Barwise (ed.),