निगमन: सारांश और चुनौतियाँ

इकाई की उपलब्धियाँ

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

लुकासिएविच प्रणाली और उसकी सीमा

औपचारिक निगमन प्रणालियों वाले पाठ ने एक प्रणाली को एक भाषा, कुछ अभिगृहीतों और कुछ नियमों के रूप में परिभाषित किया, जिनमें से सब केवल शृंखलाओं को देखकर जाँचे जा सकते हैं, और पाठ्यक्रम की प्रणाली का पहला चरण, लुकासिएविच प्रणाली, निर्धारित किया: योजनाएँ A1, A2 और A3, और एकमात्र नियम के रूप में मोडस पोनेन्स, जिसे अद्वितीय पठनीयता बिना संदिग्धता के लागू करने योग्य बनाती है। उसने आधार-वाक्यों के किसी समुच्चय $\Gamma$ से निगमन और संबंध $\Gamma \vdash \varphi$ को परिभाषित किया, $\vdash (\varphi \rightarrow \varphi)$ को पाँच पंक्तियों में निगमित किया और संरचनात्मक गुण सिद्ध किए: स्वतुल्यता, एकदिष्टता, निगमनों के बीच मोडस पोनेन्स, कर्तन और परिमितता। इनसे और पंक्तियों की संख्या पर प्रबल आगमन से उसने निगमन प्रमेय सिद्ध किया, जिसकी दूसरी स्थिति के लिए आवश्यक है कि $(\varphi \rightarrow \varphi)$ पहले से निगमित हो, और उसका विलोम भी; इनसे उसने निगमनतः तुल्यता प्राप्त की, जो स्वतुल्य, सममित और संक्रामक है। अंत में, उसने उस प्रणाली की सीमा स्थापित की: $0$ और $1$ मानों वाला एक अंकन, जो मूल रूप $(\alpha \downarrow \beta)$ पर पुनरावर्तन द्वारा परिभाषित है, निषेध और सोपाधिक के साथ सदा की तरह व्यवहार करता है, A1, A2, A3 और मोडस पोनेन्स द्वारा संरक्षित रहता है, और $(v_{1} \downarrow v_{2})$ जैसे सूत्रों का मान मुक्त छोड़ देता है। इससे निकलता है कि $((v_{1} \downarrow v_{2}) \rightarrow \neg v_{1})$ लुकासिएविच प्रणाली का प्रमेय नहीं है, और कि $(v_{1} \downarrow v_{2})$ से $(\neg\neg v_{1} \downarrow v_{2})$ निगमित नहीं होता, न ही उलटा। चूँकि हर अंकन $\theta$ और $\neg\neg\theta$ को एक ही मान देता है, पाठ ने यह भी बताया कि दोहरा निषेध भी, सिद्ध हो जाने पर, इस सीमा को दूर नहीं करेगा।

चार तकनीकें और नया नियम

निगमन की चार तकनीकों वाले पाठ ने पहले “परिणाम से नियम तक” प्रमेयिका सिद्ध की: यदि $\{\alpha_{1}, \ldots, \alpha_{n}\} \vdash \beta$, तो वही निष्कर्ष किसी भी समुच्चय $\Gamma$ से प्राप्त होता है, बशर्ते वह प्रत्येक $\alpha_{i}$ को निगमित करे, और इसके अतिरिक्त $\vdash (\alpha_{1} \rightarrow (\alpha_{2} \rightarrow \cdots (\alpha_{n} \rightarrow \beta) \cdots))$। यही प्रमेयिका हर तकनीक को तीन प्रस्तुतियों में (आधार-वाक्यों से, प्रमेय के रूप में और नियम के रूप में) प्रयोग करने देती है, और सममितियों वाला तथा डी मॉर्गन वाला पाठ, जो तुल्यताओं की शृंखलाओं को कर्तन से जोड़ते हैं, इसके लिए पहले पाठ की निगमनतः तुल्यता के गुणों पर टिके हैं, जो एक ही आधार-वाक्य पर लागू वही विचार हैं; शृंखला में हर परिणाम केवल एक बार आता है, वहाँ जहाँ वह सिद्ध होता है। इसके साथ, पाठ ने A1 और A2 से सात पंक्तियों में प्राकल्पिक न्यायवाक्य निगमित किया, निगमन प्रमेय से आधार-वाक्यों का विनिमय, दोहरा निषेध (जिसकी पहली दिशा A1 से गढ़े गए एक सोपाधिक पर A3 को दो बार लागू करती है, और दूसरी दिशा पहली दिशा को $\neg\varphi$ पर लागू करती है और A3 का उपयोग करती है) और प्रतिपरिवर्तन उसके तीनों रूपों में, जो किसी सोपाधिक के निषेधों को तीन ढंग से बाँटते हैं; चारों लुकासिएविच प्रणाली में ही मान्य हैं।

दोहरा निषेध सिद्ध होने के बाद, पाठ ने पाठ्यक्रम की प्रणाली को एक दूसरे मूल नियम, दोहरे निषेध के प्रतिस्थापन (RDN), से पूरा किया: $\chi$ से $\chi'$ का अनुमान किया जाता है जब $\chi'$, $\chi$ में किसी उपसूत्र $\theta$ की एक उपस्थिति को $\neg\neg\theta$ से, या $\neg\neg\theta$ की एक उपस्थिति को $\theta$ से प्रतिस्थापित करने पर प्राप्त होता है। नियम को अभिधारणा के रूप में रखना पड़ता है, क्योंकि अंकन $m_{1}$ दोहरे निषेध के प्रमेयों को $1$ देता है और फिर भी $(v_{1} \downarrow v_{2})$ को $(\neg\neg v_{1} \downarrow v_{2})$ से अलग करता है; RDN, $m_{1}$ को संरक्षित नहीं रखता, और इसलिए निगम्य को विस्तृत करता है, पर ईमानदार अंकन को संरक्षित रखता है, और इसलिए उसे बहुत अधिक विस्तृत नहीं करता। नियम आधार-भाषा की शृंखला पर कार्य करता है, जहाँ निषेध अपने संकार्य को दोहरा देता है: $(\varphi \rightarrow \psi)$ में उपसूत्र $\neg\varphi$ दो बार है, और उसके पूर्वपद के आगे दोहरा निषेध लगाने के लिए दो अनुप्रयोग चाहिए। यही अवलोकन निगमन प्रमेय के विस्तार का आधार है: यदि कोई पंक्ति नियम से प्राप्त होती है, तो आगमन परिकल्पना वह सोपाधिक देती है जिसका उत्तरपद पिछली पंक्ति है, और नियम के दो अनुप्रयोग, उस उत्तरपद की प्रत्येक प्रति में एक, वांछित सोपाधिक देते हैं; शेष संरचनात्मक गुण उसी उपपत्ति से मान्य हैं। पहले परिणाम ये हैं कि कोई सूत्र हर उस सूत्र के तुल्य है जो उससे नियम द्वारा प्राप्त होता है, विशेषकर $(\varphi \downarrow \psi) \dashv\vdash (\neg\neg\varphi \downarrow \psi)$ और $(\varphi \downarrow \psi) \dashv\vdash (\varphi \downarrow \neg\neg\psi)$, और कि संगत सोपाधिक, जिन्हें दूसरी प्रणालियाँ अभिगृहीत मानती हैं, यहाँ प्रमेय हैं।

संयोजक और प्रतिस्थापन

संयोजकों की सममितियों वाले पाठ ने वृत्तों और चक्रिकाओं की भाषा की विशिष्ट कठिनाई का सामना किया: लुकासिएविच के अभिगृहीत केवल निषेधों और सोपाधिकों की बात करते हैं, और लगभग कोई भी संयुक्त निषेध इन दोनों में से कोई नहीं है। मूल प्रमेयिका, $(\varphi \downarrow \psi) \dashv\vdash \neg(\neg\varphi \rightarrow \psi)$, पुल बनाती है: क्योंकि $\neg(\neg\varphi \rightarrow \psi)$, $\neg\neg(\neg\neg\varphi \downarrow \psi)$ है, नियम RDN भीतरी दोहरा निषेध लगाता है और दोहरा निषेध बाहरी; उलटी दिशा में, दोहरा निषेध और नियम उन्हें हटाते हैं। इसके साथ, तुल्यों का प्रतिस्थापन, जो पहले निषेध के अंतर्गत और सोपाधिक के दोनों ओर प्रतिपरिवर्तन और प्राकल्पिक न्यायवाक्य से सिद्ध हुआ, संयुक्त निषेध के दोनों संकार्यों तक और वहाँ से वियोजन और संयोजन तक बढ़ाया गया। नियम और प्रतिस्थापन एक-दूसरे को अनावश्यक नहीं बनाते: नियम केवल $\theta$ और $\neg\neg\theta$ की अदला-बदली करता है, जबकि प्रतिस्थापन कोई भी तुल्य सूत्र स्वीकार करता है; और प्रतिस्थापन, जो मूल प्रमेयिका से सिद्ध हुआ, स्वयं नियम पर टिका है। फिर पाठ ने सिद्ध किया कि जिन रूपों को दूसरे ग्रंथ परिभाषाएँ मानते हैं वे तुल्यताएँ हैं: $(\varphi \vee \psi) \dashv\vdash (\neg\varphi \rightarrow \psi)$, जिसके लिए नियम के दो अनुप्रयोग चाहिए, बाहरी निषेध द्वारा बनाई गई प्रत्येक प्रति में एक, और $(\varphi \wedge \psi) \dashv\vdash (\neg\varphi \downarrow \neg\psi)$, जिसके लिए दोहरा निषेध चाहिए; इसके विपरीत, $(\varphi \wedge \psi)$ और $\neg(\varphi \rightarrow \neg\psi)$ एक ही शृंखला हैं। अंत में, उसने पाँचों सममितियाँ उस क्रम में सिद्ध कीं जो परिभाषाएँ निर्धारित करती हैं: संयुक्त निषेध की सममिति मूल प्रमेयिका और प्रतिपरिवर्तन से, और शेष में से हर एक पिछली से, जिसे आवश्यकता होने पर निषेध के अंतर्गत प्रतिस्थापन से आगे ले जाया जाता है।

शास्त्रीय नियम और डी मॉर्गन तथा वितरण के नियम

शास्त्रीय तर्क की तकनीकों वाले पाठ ने, सबको आधार-वाक्यों के एक समुच्चय $\Gamma$ के साथ जो पंक्ति-दर-पंक्ति साथ चलता है, वियोजन और संयोजन का प्रवेश और निरसन, मध्य-परिहार नियम और अव्याघात नियम, विस्फोट सिद्धांत, असंभवापत्ति उसके दोनों रूपों में और स्थिति-भेद से उपपत्ति सिद्ध की, एक सूत्र और उसके निषेध के साथ और किसी भी वियोजन के साथ। निर्भरताओं का क्रम सख्त है: विस्फोट सिद्धांत वियोजन के नियमों पर टिका है; शास्त्रीय असंभवापत्ति विस्फोट सिद्धांत और A3 पर; स्थिति-भेद से उपपत्ति प्रतिपरिवर्तन और असंभवापत्ति पर। इनमें से कोई उपपत्ति नियम RDN का सीधे सहारा नहीं लेती: नियम तुल्य रूपों और तुल्यों के प्रतिस्थापन के माध्यम से कार्य करता है। डी मॉर्गन के नियमों और वितरण नियमों वाले पाठ ने इन नियमों से साथ-साथ काम लिया: डी मॉर्गन का पहला नियम संयोजन की परिभाषा और दोहरे निषेध से निकलता है; दूसरे के लिए संयुक्त निषेध के भीतर जाना पड़ता है, जहाँ नियम RDN दो बार हस्तक्षेप करता है, प्रत्येक संकार्य में एक बार और सममिति की आवश्यकता के बिना, और उससे निकलता है कि $(\varphi \downarrow \psi)$, $(\neg\varphi \wedge \neg\psi)$ के तुल्य है, अर्थात् वह पठन “न $\varphi$ न $\psi$” जिसे पिछली इकाई ने परिपाटी से निर्धारित किया था; रूपांतरों में $\neg(\varphi \rightarrow \psi) \dashv\vdash (\varphi \wedge \neg\psi)$ भी है। दोनों वितरण नियम अपनी दोनों दिशाओं में स्थिति-भेद से सिद्ध किए गए, हर दिशा में स्थिति-भेद से उपपत्ति का उपयुक्त रूप चुनकर।

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

औचित्यों के संक्षेपण

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

• पहला पाठ: A1, A2 और A3 (अभिगृहीत-योजनाएँ); MP$(i, j)$ (मोडस पोनेन्स); Def (परिभाषा: किसी संक्षेपण का विस्तार या संकोचन, खोले जाने वाले संयोजक के साथ: “Def $\vee$”, “Def $\dashv\vdash$”); Id (तादात्म्य, प्रमेय $\vdash (\varphi \rightarrow \varphi)$); Refl (स्वतुल्यता: यदि $\varphi \in \Gamma$, तो $\Gamma \vdash \varphi$); Mon (एकदिष्टता); Cut (कर्तन: जो निगमित हो चुका है उसे आधार-वाक्य के रूप में प्रयोग किया जा सकता है); Fin (परिमितता); DT (निगमन प्रमेय) और CDT (उसका विलोम)।
• दूसरा पाठ: HS (प्राकल्पिक न्यायवाक्य); IP (आधार-वाक्यों का विनिमय); DN (दोहरा निषेध); RDN$(i)$ (पंक्ति $i$ में दोहरे निषेध का प्रतिस्थापन; बिना संख्या के RDN किसी सूत्र और उस सूत्र के बीच की तुल्यता का उल्लेख करता है जो उससे नियम द्वारा प्राप्त होता है); CP (प्रतिपरिवर्तन, उसके तीनों रूपों में से किसी में भी); “हल प्रश्न $n$” (उसी पाठ के हल प्रश्न $n$ का कोई परिणाम, पंक्ति के रूप में लिखा गया)।
• तीसरा पाठ: FL (मूल प्रमेयिका, $(\varphi \downarrow \psi) \dashv\vdash \neg(\neg\varphi \rightarrow \psi)$); Repl (तुल्यों का प्रतिस्थापन, उसके किसी भी रूप में, जिसके बाद लागू की जाने वाली तुल्यता आती है: “Repl, DM$(i)$”); Eq (वियोजन और संयोजन के तुल्य रूप, $(\varphi \vee \psi) \dashv\vdash (\neg\varphi \rightarrow \psi)$ और $(\varphi \wedge \psi) \dashv\vdash (\neg\varphi \downarrow \neg\psi)$); Sym (किसी संयोजक की सममिति)।
• चौथा पाठ: $\vee$I और $\vee$E (वियोजन का प्रवेश और निरसन); $\wedge$I और $\wedge$E (संयोजन का प्रवेश और निरसन); EM (मध्य-परिहार नियम); NC (अव्याघात नियम, संक्षेपण जो प्रमेय का नाम है, पर इकाई की किसी पंक्ति का औचित्य नहीं देता); Exp (विस्फोट सिद्धांत); स्थितियाँ$(i, j)$ और स्थितियाँ$(i, j, k)$ (स्थिति-भेद से उपपत्ति, एक सूत्र और उसके निषेध के साथ या एक वियोजन के साथ); “आधार-वाक्य रहित स्थितियाँ” (समुच्चय $\Gamma$ के बिना स्थिति-भेद से उपपत्ति, जो केवल एक प्रश्न में आती है); RAA (असंभवापत्ति, उसके दोनों रूपों में)।
• पाँचवाँ पाठ: DM (डी मॉर्गन के नियम); Dist (वितरणता); Assoc (वियोजन की साहचर्यता); दृष्टांत$(i)$ (पंक्ति $i$, जो किसी भी सूत्र के लिए मान्य है, उसके अधिचरों के स्थान पर दूसरे सूत्र रखकर फिर से लिखी गई; बताया जाता है कि किसके स्थान पर क्या रखा गया)।
• इस पाठ की चुनौतियाँ: M3 (वह योजना जिसे तीसरी चुनौती A3 के स्थान पर रखती है)।