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

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

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

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

0! = 1.

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

यह परिभाषा प्रत्येक प्राकृतिक संख्या n के लिए मान्य है, क्योंकि पुनरावर्तन अंततः 0 के आधार स्थिति (रिकर्सन) तक पहुँचता है। परिभाषा को n = 0 से शुरू होकर n = 1, n = 2, n = 3 आदि के साथ आगे बढ़ने के लिए फ़ंक्शन n! के मान की गणना करने के लिए एक प्रक्रिया देने के बारे में भी सोचा जा सकता है।

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

समुच्चय की आगमनात्मक परिभाषा समुच्चय के तत्वों का समुच्चय के अन्य तत्वों के संदर्भ में वर्णन करती है। उदाहरण के लिए, प्राकृतिक संख्याओं के समुच्चय 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 को धारण करता है, तो गुण सभी प्राकृतिक संख्याओं (एक्सेल 1977:742) को धारण करता है।

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

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

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

इसके विपरीत, परिपत्र परिभाषा में कोई आधार स्थिति नहीं हो सकता है, और यहां तक ​​​​कि फलन के मान को उस मान के संदर्भ में भी परिभाषित कर सकता है - फलन के अन्य मानों के अतिरिक्त। ऐसी स्थिति अनंत प्रतिगमन की ओर ले जाएगी।

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

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

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

माना A समुच्चय हो और a₀ को A का तत्व होने दें। यदि ρ एक ऐसा फलन है जो धनात्मक पूर्णांकों के एक गैर-रिक्त खंड को A में A के एक तत्व में मैप करने वाले प्रत्येक फलन f को असाइन करता है, तो एक अद्धितीय फलन उपस्थित $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 के बीच प्रत्येक पूर्णांक की मौलिकता को जानना आवश्यक है, जो इस परिभाषा द्वारा अच्छी तरह से परिभाषित है। उस अंतिम बिंदु को X पर प्रेरण द्वारा सिद्ध किया जा सकता है, जिसके लिए यह आवश्यक है कि दूसरा खंड कहता है कि यदि और केवल यदि; यदि उसने अभी कहा होता तो, उदाहरण के लिए, संख्या 4 की प्रारंभिकता स्पष्ट नहीं होगी, और दूसरे खंड का आगे आवेदन असंभव होगा।

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

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

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

सुगठित सूत्र

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

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

चार बाइनरी संयोजकों में से कोई भी (C, A, K, या E) जिसके बाद दो wff होते हैं। प्रतीक K का अर्थ है "दोनों सत्य हैं", इसलिए Kpq का अर्थ हो सकता है "कॉनर एक वकील है, और मैरी को संगीत पसंद है।"

• Kpq अच्छी तरह से बनता है, क्योंकि यह K के बाद परमाणु wffs p और q होता है।
• NKpq अच्छी तरह से बना है, क्योंकि यह N के बाद Kpq है, जो बदले में wff है।
• KNpNq K के बाद Np और Nq है; और Np 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.