पुनरावर्ती परिभाषा

कोच स्नोफ्लेक्स के निर्माण में चार चरण। कई अन्य भग्नों की तरह, चरणों को पुनरावर्ती परिभाषा के माध्यम से प्राप्त किया जाता है।

गणित और कंप्यूटर विज्ञान में, एक पुनरावर्ती परिभाषा, या आगमनात्मक परिभाषा का उपयोग सेट (गणित) में तत्व (गणित) को सेट में अन्य तत्वों के संदर्भ में परिभाषित करने के लिए किया जाता है (पीटर एक्ज़ेल 1977: 740ff)। पुनरावर्ती-परिभाषित वस्तुओं के कुछ उदाहरणों में क्रमगुणित, प्राकृतिक संख्या, फाइबोनैचि संख्या और कैंटर सेट शामिल हैं।

एक फ़ंक्शन (गणित) की पुनरावर्ती परिभाषा कुछ इनपुट के लिए फ़ंक्शन के मानों को अन्य (आमतौर पर छोटे) इनपुट के लिए समान फ़ंक्शन के मानों के संदर्भ में परिभाषित करती है। उदाहरण के लिए, भाज्य फलन n! नियमों द्वारा परिभाषित किया गया है

0! = 1।

(एन + 1)! = (एन + 1)·एन!.

यह परिभाषा प्रत्येक प्राकृतिक संख्या n के लिए मान्य है, क्योंकि पुनरावर्तन अंततः 0 के आधार मामले (रिकर्सन) तक पहुँचता है। परिभाषा को फ़ंक्शन के मान की गणना करने के लिए एक प्रक्रिया देने के बारे में भी सोचा जा सकता है। '!, 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) बाहरी सदस्यों के सेट को हटाकर प्राकृतिक संख्याओं के सेट को निर्दिष्ट करती है। ध्यान दें कि यह परिभाषा मानती है कि N एक बड़े सेट (जैसे वास्तविक संख्याओं का सेट) में समाहित है - जिसमें ऑपरेशन + परिभाषित किया गया है।

पुनरावर्ती परिभाषित कार्यों और सेटों के गुणों को अक्सर एक प्रेरण सिद्धांत द्वारा सिद्ध किया जा सकता है जो पुनरावर्ती परिभाषा का अनुसरण करता है। उदाहरण के लिए, यहां प्रस्तुत प्राकृतिक संख्याओं की परिभाषा सीधे तौर पर प्राकृतिक संख्याओं के लिए गणितीय आगमन के सिद्धांत को दर्शाती है: यदि कोई संपत्ति प्राकृतिक संख्या 0 (या 1) रखती है, और संपत्ति n+1 रखती है जब भी यह n को धारण करता है, तो गुण सभी प्राकृतिक संख्याओं को धारण करता है (Aczel 1977:742)।

पुनरावर्ती परिभाषाओं का रूप

अधिकांश पुनरावर्ती परिभाषाओं के दो आधार होते हैं: एक आधार मामला (आधार) और एक आगमनात्मक खंड।

एक परिपत्र परिभाषा और एक पुनरावर्ती परिभाषा के बीच का अंतर यह है कि एक पुनरावर्ती परिभाषा में हमेशा आधार मामले होने चाहिए, ऐसे मामले जो परिभाषा के संदर्भ में परिभाषित किए बिना परिभाषा को संतुष्ट करते हैं, और आगमनात्मक खंड में अन्य सभी उदाहरण कुछ में छोटे होने चाहिए भाव (अर्थात्, उन मूल स्थितियों के निकट जो पुनरावर्तन को समाप्त करते हैं) — एक नियम जिसे केवल एक साधारण मामले के साथ पुनरावृत्ति के रूप में भी जाना जाता है। इसके विपरीत, एक परिपत्र परिभाषा में कोई आधार मामला नहीं हो सकता है, और यहां तक ​​​​कि फ़ंक्शन के मूल्य को उस मूल्य के संदर्भ में भी परिभाषित कर सकता है - फ़ंक्शन के अन्य मूल्यों के बजाय। ऐसी स्थिति अनंत प्रतिगमन की ओर ले जाएगी।

वह पुनरावर्ती परिभाषाएँ मान्य हैं - जिसका अर्थ है कि एक पुनरावर्ती परिभाषा एक अद्वितीय कार्य की पहचान करती है - सेट सिद्धांत का एक प्रमेय है जिसे रिकर्सन # पुनरावर्ती प्रमेय के रूप में जाना जाता है, जिसका प्रमाण गैर-तुच्छ है। जहां फ़ंक्शन का डोमेन प्राकृतिक संख्या है, परिभाषा के मान्य होने के लिए पर्याप्त शर्तें हैं कि का मान f(0) (यानी, बेस केस) दिया गया है, और उसके लिए n > 0, निर्धारण के लिए एक एल्गोरिथ्म दिया गया है f(n) के अनुसार n, f(0), f(1), …, f(n − 1) (यानी, आगमनात्मक खंड)।

अधिक आम तौर पर, कार्यों की पुनरावर्ती परिभाषाएं तब बनाई जा सकती हैं जब डोमेन एक अच्छी तरह से आदेश | सुव्यवस्थित सेट हो, जो ट्रांसफिनिट रिकर्सन के सिद्धांत का उपयोग कर रहा हो। वैध पुनरावर्ती परिभाषा का गठन करने के लिए औपचारिक मानदंड सामान्य मामले के लिए अधिक जटिल हैं। जेम्स मुनक्रेस की टोपोलॉजी में सामान्य प्रमाण और मानदंड की रूपरेखा पाई जा सकती है। हालांकि, सामान्य पुनरावर्ती परिभाषा का एक विशिष्ट मामला (डोमेन किसी भी सुव्यवस्थित सेट के बजाय धनात्मक पूर्णांकों तक सीमित है) नीचे दिया जाएगा।

पुनरावर्ती परिभाषा का सिद्धांत

होने देना A एक सेट हो और चलो a₀ का एक तत्व हो A. अगर ρ एक फ़ंक्शन है जो प्रत्येक फ़ंक्शन को असाइन करता है f सकारात्मक पूर्णांकों के एक गैर-रिक्त खंड को मैप करना A, का एक तत्व A, तो एक अनूठा कार्य मौजूद है $h:\mathbb {Z} _{+}\to A$ ऐसा है कि

$h(1)=a_{0}$

$h(i)=\rho (h|_{\{1,2,\ldots ,i-1\}}){\text{ for }}i>1.$

पुनरावर्ती परिभाषाओं के उदाहरण

प्राथमिक कार्य

जोड़ को पुनरावर्ती रूप से गिनती के आधार पर परिभाषित किया गया है

$0+a=a,$

$(1+n)+a=1+(n+a).$

गुणा को पुनरावर्ती रूप से परिभाषित किया गया है

$0a=0,$

$(1+n)a=a+na.$

घातांक को पुनरावर्ती रूप से परिभाषित किया गया है

$a^{0}=1,$

$a^{1+n}=aa^{n}.$

द्विपद गुणांक को पुनरावर्ती रूप से परिभाषित किया जा सकता है

${\binom {a}{0}}=1,$

${\binom {1+a}{1+n}}={\frac {(1+a){\binom {a}{n}}}{1+n}}.$

अभाज्य संख्याएँ

अभाज्य संख्याओं के समुच्चय को सकारात्मक पूर्णांकों के अद्वितीय समुच्चय के रूप में परिभाषित किया जा सकता है

• 1 (संख्या) अभाज्य संख्या नहीं है,
• कोई भी अन्य सकारात्मक पूर्णांक एक अभाज्य संख्या है यदि और केवल यदि यह अपने से छोटी किसी भी अभाज्य संख्या से विभाज्य नहीं है।

पूर्णांक 1 की प्रधानता आधार मामला है; इस परिभाषा द्वारा किसी भी बड़े पूर्णांक X की प्राथमिकता की जाँच करने के लिए 1 और X के बीच प्रत्येक पूर्णांक की मौलिकता को जानना आवश्यक है, जो इस परिभाषा द्वारा अच्छी तरह से परिभाषित है। उस अंतिम बिंदु को एक्स पर प्रेरण द्वारा सिद्ध किया जा सकता है, जिसके लिए यह आवश्यक है कि दूसरा खंड कहता है कि अगर और केवल अगर; अगर उसने अभी कहा होता तो, उदाहरण के लिए, संख्या 4 की प्रारंभिकता स्पष्ट नहीं होगी, और दूसरे खंड का आगे आवेदन असंभव होगा।

गैर-नकारात्मक सम संख्याएं

सम संख्याओं को मिलकर परिभाषित किया जा सकता है

• 0 गैर-ऋणात्मक सम (आधार खंड) के सेट ई में है,
• सेट E में किसी भी तत्व x के लिए, x + 2 E (आगमनात्मक खंड) में है,
• ई में कुछ भी नहीं है जब तक कि यह आधार और आगमनात्मक खंड (चरम खंड) से प्राप्त न हो।

सुगठित सूत्र

यह मुख्यतः तर्क या कंप्यूटर प्रोग्रामिंग में है कि पुनरावर्ती परिभाषाएँ पाई जाती हैं। उदाहरण के लिए, एक अच्छी तरह से निर्मित सूत्र (wff) को इस प्रकार परिभाषित किया जा सकता है:

1. a प्रतीक जो एक प्रस्ताव के लिए खड़ा है - जैसे p का अर्थ है कॉनर एक वकील है।
2. नकार का प्रतीक, जिसके बाद wff - जैसे Np का अर्थ है यह सच नहीं है कि कॉनर एक वकील है।
3. चार बाइनरी तार्किक संयोजक्स (सी, ए, के, या ई) में से कोई भी दो wffs के बाद। प्रतीक K का अर्थ है कि दोनों सत्य हैं, इसलिए Kpq का अर्थ हो सकता है कि कॉनर एक वकील है, और मैरी को संगीत पसंद है।

ऐसी पुनरावर्ती परिभाषा का मूल्य यह है कि इसका उपयोग यह निर्धारित करने के लिए किया जा सकता है कि प्रतीकों की कोई विशेष स्ट्रिंग अच्छी तरह से बनाई गई है या नहीं।

• Kpq अच्छी तरह से बनता है, क्योंकि यह K के बाद परमाणु wffs p और q होता है।
• NKpq अच्छी तरह से बना है, क्योंकि यह N के बाद Kpq है, जो बदले में एक wff है।
• KNpNq K के बाद Np और Nq है; और एनपी एक wff है, आदि।

यह भी देखें

• गणितीय प्रेरण
• पुनरावर्ती डेटा प्रकार
• प्रत्यावर्तन
• संरचनात्मक प्रेरण

संदर्भ

• Halmos, Paul (1960). Naive set theory. van Nostrand. OCLC 802530334.
• Aczel, Peter (1977). "An Introduction to Inductive Definitions". In Barwise, J. (ed.). Handbook of Mathematical Logic. Studies in Logic and the Foundations of Mathematics. Vol. 90. North-Holland. pp. 739–782. doi:10.1016/S0049-237X(08)71120-0. ISBN 0-444-86388-5.
• Hein, James L. (2010). Discrete Structures, Logic, and Computability. Jones & Bartlett. ISBN 978-0-7637-7206-2. OCLC 636352297.