संरचनात्मक प्रेरण

संरचनात्मक प्रेरण एक प्रमाण विधि है जिसका उपयोग गणितीय तर्क में किया जाता है (उदाहरण के लिए, Ultraproduct#Łoś's प्रमेय|Łoś' प्रमेय के प्रमाण में), कंप्यूटर विज्ञान, ग्राफ सिद्धांत और कुछ अन्य गणितीय क्षेत्रों में। यह गणितीय प्रेरण का एक सामान्यीकरण है और इसे मनमाने नोथेरियन प्रेरण के लिए आगे सामान्यीकृत किया जा सकता है। संरचनात्मक पुनरावर्तन एक पुनरावर्तन विधि है जिसका संरचनात्मक प्रेरण से वही संबंध होता है जो सामान्य पुनरावर्तन का सामान्य गणितीय प्रेरण से होता है।

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

एक संरचनात्मक रूप से पुनरावर्ती फ़ंक्शन एक पुनरावर्ती फ़ंक्शन को परिभाषित करने के लिए एक ही विचार का उपयोग करता है: आधार मामले प्रत्येक न्यूनतम संरचना और पुनरावृत्ति के लिए एक नियम को संभालते हैं। संरचनात्मक पुनरावर्तन आमतौर पर संरचनात्मक प्रेरण द्वारा सही साबित होता है; विशेष रूप से आसान मामलों में, आगमनात्मक चरण को अक्सर छोड़ दिया जाता है। नीचे दिए गए उदाहरण में लंबाई और ++ फ़ंक्शन संरचनात्मक रूप से पुनरावर्ती हैं।

उदाहरण के लिए, यदि संरचनाएँ सूचियाँ हैं, तो आमतौर पर आंशिक क्रम < का परिचय दिया जाता है, जिसमें L < M जब भी सूची L सूची की पूंछ है M. इस आदेश के अंतर्गत, रिक्त सूची [] अद्वितीय न्यूनतम तत्व है. किसी प्रस्ताव का संरचनात्मक प्रेरण प्रमाण P(L) तो इसमें दो भाग होते हैं: एक प्रमाण P([]) सत्य है और इसका प्रमाण है कि यदि P(L) कुछ सूची के लिए सत्य है L, और अगर L सूची की पूंछ है M, तब P(M) भी सत्य होना चाहिए.

अंततः, एक से अधिक आधार मामले और/या एक से अधिक आगमनात्मक मामले मौजूद हो सकते हैं, यह इस बात पर निर्भर करता है कि फ़ंक्शन या संरचना का निर्माण कैसे किया गया था। उन मामलों में, किसी प्रस्ताव का संरचनात्मक प्रेरण प्रमाण P(L) फिर इसमें शामिल हैं:

1. a proof that P(BC) is true for each base case BC,
2. a proof that if P(I) is true for some instance I, and M can be obtained from I by applying any one recursive rule once, then P(M) must also be true.

उदाहरण

प्राचीन पूर्वज वृक्ष, 5 पीढ़ियों में 31 व्यक्तियों को दर्शाता है

पारिवारिक वृक्ष एक सामान्य रूप से ज्ञात डेटा संरचना है, जहां तक ​​ज्ञात हो किसी व्यक्ति के माता-पिता, दादा-दादी आदि को दर्शाता है (उदाहरण के लिए चित्र देखें)। इसे पुनरावर्ती रूप से परिभाषित किया गया है:

• सबसे सरल मामले में, एक पूर्वज वृक्ष केवल एक व्यक्ति को दर्शाता है (यदि उनके माता-पिता के बारे में कुछ भी ज्ञात नहीं है);
• वैकल्पिक रूप से, एक पूर्वज वृक्ष एक व्यक्ति को दर्शाता है और, शाखाओं से जुड़ा हुआ, उनके माता-पिता के दो पूर्वज उपवृक्ष (प्रमाण की संक्षिप्तता के लिए सरल धारणा का उपयोग करते हुए कि यदि उनमें से एक ज्ञात है, तो दोनों हैं)।

उदाहरण के तौर पर, संपत्ति एक पूर्वज वृक्ष का विस्तार है gपीढ़ियाँ अधिक से अधिक दिखाती हैं 2^g − 1व्यक्तियों को संरचनात्मक प्रेरण द्वारा निम्नानुसार सिद्ध किया जा सकता है:

• सबसे सरल मामले में, पेड़ केवल एक व्यक्ति और इसलिए एक पीढ़ी को दर्शाता है; ऐसे पेड़ के लिए संपत्ति सत्य है, क्योंकि 1 ≤ 2¹ − 1.
• वैकल्पिक रूप से, पेड़ एक व्यक्ति और उनके माता-पिता के पेड़ को दर्शाता है। चूंकि उत्तरार्द्ध में से प्रत्येक पूरे पेड़ का एक उपसंरचना है, इसलिए यह माना जा सकता है कि यह सिद्ध की जाने वाली संपत्ति को संतुष्ट करता है (जैसे कि प्रेरण परिकल्पना)। वह है, p ≤ 2^g − 1 और q ≤ 2^h − 1 माना जा सकता है, कहां g और h क्रमशः पिता और माता के उपवृक्ष में फैली पीढ़ियों की संख्या को दर्शाता है, और p और q उनके द्वारा दिखाए गए व्यक्तियों की संख्या को निरूपित करें।
  • यदि g ≤ h, पूरा पेड़ फैला हुआ है 1 + h पीढ़ियाँ और शो p + q + 1 व्यक्ति, और
    $$p+q+1\leq (2^{g}-1)+(2^{h}-1)+1\leq 2^{h}+2^{h}-1=2^{1+h}-1,$$
    अर्थात संपूर्ण वृक्ष संपत्ति को संतुष्ट करता है।
  • यदि h ≤ g, पूरा पेड़ फैला हुआ है 1 + g पीढ़ियाँ और शो p + q + 1 ≤ 2^{g + 1} − 1 समान तर्क से व्यक्ति, यानी पूरा पेड़ इस मामले में भी संपत्ति को संतुष्ट करता है।

इसलिए, संरचनात्मक प्रेरण द्वारा, प्रत्येक पूर्वज वृक्ष संपत्ति को संतुष्ट करता है।

एक अन्य, अधिक औपचारिक उदाहरण के रूप में, सूचियों की निम्नलिखित संपत्ति पर विचार करें:

${\text{EQ:}}\quad \operatorname {len} (L+\!+\ M)=\operatorname {len} (L)+\operatorname {len} (M)$

यहाँ ++ सूची संयोजन ऑपरेशन को दर्शाता है, len() सूची की लंबाई, और L और M सूचियाँ हैं.

इसे सिद्ध करने के लिए, हमें लंबाई और संयोजन संक्रिया के लिए परिभाषाओं की आवश्यकता है। होने देना (h:t) उस सूची को निरूपित करें जिसका शीर्ष (पहला तत्व) है h और पूँछ (शेष तत्वों की सूची) किसकी है t, और जाने []रिक्त सूची को निरूपित करें। लंबाई और संयोजन संक्रिया की परिभाषाएँ हैं:

${\begin{array}{ll}{\text{LEN1:}}&\operatorname {len} ([\ ])=0\\{\text{LEN2:}}&\operatorname {len} (h:t)=1+\operatorname {len} (t)\\&\\{\text{APP1:}}&[\ ]+\!+\ list=list\\{\text{APP2:}}&(h:t)+\!+\ list=h:(t+\!+\ list)\end{array}}$

हमारा प्रस्ताव P(l) यह है कि EQ सभी सूचियों के लिए सत्य है M कब L है l. हम वो दिखाना चाहते हैं P(l) सभी सूचियों के लिए सत्य है l. हम इसे सूचियों में संरचनात्मक प्रेरण द्वारा सिद्ध करेंगे।

पहले हम इसे साबित करेंगे P([]) क्या सच है; वह है, EQ सभी सूचियों के लिए सत्य है M कब L ख़ाली सूची होती है []. विचार करना EQ:

${\begin{array}{rll}\operatorname {len} (L+\!+\ M)&=\operatorname {len} ([\ ]+\!+\ M)\\&=\operatorname {len} (M)&({\text{by APP1}})\\&=0+\operatorname {len} (M)\\&=\operatorname {len} ([\ ])+\operatorname {len} (M)&({\text{by LEN1}})\\&=\operatorname {len} (L)+\operatorname {len} (M)\\\end{array}}$

अतः प्रमेय का यह भाग सिद्ध हो गया है; EQ सभी के लिए सत्य है M, कब L है [], क्योंकि बायां पक्ष और दायां पक्ष बराबर हैं।

इसके बाद, किसी भी गैर-रिक्त सूची पर विचार करें I. तब से I गैर-रिक्त है, इसमें एक मुख्य आइटम है, x, और एक पूंछ सूची, xs, अतः हम इसे इस प्रकार व्यक्त कर सकते हैं (x:xs). प्रेरण परिकल्पना वह है EQ के सभी मानों के लिए सत्य है M कब L है xs:

${\text{HYP:}}\quad \operatorname {len} (xs+\!+\ M)=\operatorname {len} (xs)+\operatorname {len} (M)$

हम यह दिखाना चाहेंगे कि यदि ऐसा है तो EQ के सभी मानों के लिए भी सत्य है M कब L = I = (x:xs). हम पहले की तरह आगे बढ़ते हैं:

${\begin{array}{rll}\operatorname {len} (L)+\operatorname {len} (M)&=\operatorname {len} (x:xs)+\operatorname {len} (M)\\&=1+\operatorname {len} (xs)+\operatorname {len} (M)&({\text{by LEN2}})\\&=1+\operatorname {len} (xs+\!+\ M)&({\text{by HYP}})\\&=\operatorname {len} (x:(xs+\!+\ M))&({\text{by LEN2}})\\&=\operatorname {len} ((x:xs)+\!+\ M)&({\text{by APP2}})\\&=\operatorname {len} (L+\!+\ M)\end{array}}$

इस प्रकार, संरचनात्मक प्रेरण से, हम उसे प्राप्त करते हैं P(L) सभी सूचियों के लिए सत्य है L.

सुव्यवस्थित

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

इस प्रकार के तर्क के उदाहरण के रूप में, सभी बाइनरी पेड़ों के सेट पर विचार करें। हम दिखाएंगे कि एक पूर्ण बाइनरी पेड़ में पत्तियों की संख्या आंतरिक नोड्स की संख्या से एक अधिक है। मान लीजिए कि एक प्रति उदाहरण है; तो आंतरिक नोड्स की न्यूनतम संभव संख्या वाला एक मौजूद होना चाहिए। यह प्रति उदाहरण, C, है n आंतरिक नोड्स और l पत्ते, कहाँ n + 1 ≠ l. इसके अतिरिक्त, C गैर-तुच्छ होना चाहिए, क्योंकि तुच्छ वृक्ष के पास है n = 0 और l = 1 और इसलिए यह एक प्रतिउदाहरण नहीं है। C इसलिए कम से कम एक पत्ती होती है जिसका मूल नोड एक आंतरिक नोड होता है। इस पत्ते और उसके मूल नोड को पेड़ से हटा दें, पत्ती के सहोदर नोड को उस स्थान पर पदोन्नत करें जिस पर पहले उसके मूल नोड का कब्ज़ा था। इससे दोनों कम हो जाते हैं n और l 1 से, तो नया पेड़ भी है n + 1 ≠ l और इसलिए यह एक छोटा प्रति उदाहरण है। लेकिन परिकल्पना से, C पहले से ही सबसे छोटा प्रति उदाहरण था; इसलिए, यह धारणा कि शुरुआत में कोई प्रति-उदाहरण मौजूद थे, ग़लत रहा होगा। यहाँ 'छोटा' द्वारा निहित आंशिक क्रम वही है जो यही कहता है S < T जब कभी भी S से कम नोड्स हैं T.

यह भी देखें

• संयोजन
• प्रारंभिक बीजगणित
• लूप अपरिवर्तनीय, लूप के लिए एनालॉग

संदर्भ

• Hopcroft, John E.; Rajeev Motwani; Jeffrey D. Ullman (2001). Introduction to Automata Theory, Languages, and Computation (2nd ed.). Reading Mass: Addison-Wesley. ISBN 978-0-201-44124-6.
• "Mathematical Logic - Video 01.08 - Generalized (Structural) Induction" on YouTube

Early publications about structural induction include:

• Burstall, R. M. (1969). "Proving Properties of Programs by Structural Induction". The Computer Journal. 12 (1): 41–48. doi:10.1093/comjnl/12.1.41.
• Aubin, Raymond (1976), Mechanizing Structural Induction, EDI-INF-PHD, vol. 76–002, University of Edinburgh, hdl:1842/6649
• Huet, G.; Hullot, J. M. (1980). "Proofs by Induction in Equational Theories with Constructors" (PDF). 21st Ann. Symp. on Foundations of Computer Science. IEEE. pp. 96–107.
• Rózsa Péter, Über die Verallgemeinerung der Theorie der rekursiven Funktionen für abstrakte Mengen geeigneter Struktur als Definitionsbereiche, Symposium International, Varsovie septembre (1959) (On the generalization of the theory of recursive functions for abstract quantities with suitable structures as domains).