विरोधाभास द्वारा गणितीय प्रमाण

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

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

विरोधाभास द्वारा प्रमाण को नियोजित करने वाला एक गणितीय प्रमाण सामान्यतः निम्नानुसार विस्तृत होता है:

1. सिद्ध होने वाला प्रस्ताव P है।
2. माना P असत्य हैं अर्थात P को हम ¬P के रूप मान लेते हैं।
3. तब यह प्रदर्शित किया जाता है कि ¬P का तात्पर्य असत्य से है यह सामान्यतः दो परस्पर विरोधाभासी अभिकथनों Q और ¬Q को प्राप्त करके और गैर-विरोधाभास के कानून की याचना करके पूर्ण किया जाता है।
4. चूँकि P को असत्य मानने से विरोधाभास उत्पन्न होता है जिससे यह निष्कर्ष निकाला जाता है कि P वास्तव में सत्य है।

एक महत्वपूर्ण विशेष स्थिति विरोधाभास द्वारा अस्तित्व प्रमाण है जिसमे यह प्रदर्शित करने के लिए कि किसी दिए गए संपत्ति के साथ एक वस्तु सम्मिलित है, हम इस धारणा से एक विरोधाभास प्रम द्वारा प्राप्त करते हैं कि सभी वस्तुएं संपत्ति की अस्वीकृति को संतुष्ट करती हैं।

औपचारिककरण

सिद्धांत को औपचारिक रूप से प्रस्ताविक सूत्र ¬¬P ⇒ P समतुल्य (¬P ⇒ ⊥) ⇒ P के रूप में व्यक्त किया जा सकता है "यदि P को असत्य मानने का अर्थ असत्य है, तो P सत्य है।" जो प्राकृतिक निगमन सिद्धांत अनुमान के नियम का रूप प्राप्त करता है

${\cfrac {\vdash \lnot \lnot P}{\vdash P}}$

जिसका अर्थ है: यदि $\lnot \lnot P$ सिद्ध होता है, तब $P$ का निष्कर्ष निकाला जा सकता है।

अनुक्रमिक कैलकुलस में सिद्धांत को निम्न अनुक्रम द्वारा व्यक्त किया जाता है:

$\Gamma ,\lnot \lnot P\vdash P,\Delta$

जिसका अर्थ है: परिकल्पना $\Gamma$ और $\lnot \lnot P$ निष्कर्ष पर $P$ या $\Delta$ में प्रवेश करते हैं।

औचित्य

पारम्परिक तर्क में सिद्धांत को प्रस्ताव ¬¬P ⇒ P की सत्य तालिका के परीक्षण से उपयुक्त सिद्ध जा सकता है जो इसे एक सत्यता सूचक के रूप में प्रदर्शित करता है:

p	¬p	¬¬p	¬¬p ⇒ p
T	F	T	T
F	T	F	T

सिद्धांत को सत्य सिद्ध करने का एक और तरीका यह है कि इसे बहिष्कृत मध्य के सिद्धान्त से प्राप्त किया जाए, जैसा कि निम्नानुसार है। हम ¬¬P मान लेते हैं और P को सिद्ध करना चाहते हैं। बहिष्कृत मध्य P के सिद्धान्त द्वारा या तो यह धारण करता है या यह नहीं करता है:

1. यदि P धारण करता है, तो निश्चित रूप से P धारण करता है।
2. यदि ¬P धारण करता है, तो हम ¬P और ¬¬P पर गैर-विरोधाभास के नियम को प्रयुक्त करके असत्य को प्राप्त करते हैं, जिसके बाद बाहुल्य सिद्धांत हमें P निष्कर्ष निकालने की स्वीकृति देता है।

किसी भी स्थिति में, हमने P स्थापित किया। जिससे यह पता चला है कि, इसके विपरीत, विरोधाभास द्वारा प्रमाण का उपयोग बहिष्कृत मध्य के सिद्धान्त को प्राप्त करने के लिए किया जा सकता है।

पारंपरिक अनुक्रम कैलकुलस एलके प्रमाण में विरोधाभास द्वारा निषेध के लिए अनुमान नियमों से प्राप्त किया जा सकता है:

${\cfrac {{\cfrac {{\cfrac {\ }{\Gamma ,P\vdash P,\Delta }}\;(I)}{\Gamma ,\vdash \lnot P,P,\Delta }}\;({\lnot }R)}{\Gamma ,\lnot \lnot P\vdash P,\Delta }}\;({\lnot }L)$

अन्य प्रमाण तकनीकों के साथ संबंध

विरोधाभास द्वारा प्रतिनियुक्ति

विरोधाभास द्वारा गणितीय प्रमाण विरोधाभास द्वारा खंडन के समान होता है जिसे निषेध के प्रमाण के रूप में भी जाना जाता है, जिसमें कहा गया है कि ¬P इस प्रकार सिद्ध होता है:

1. सिद्ध किया जाने वाला तर्कवाक्य ¬P है।
2. P को मान ले।
3. असत्यता प्राप्त करें।
4. ¬P का समापन करें।

इसके विपरीत, विरोधाभास द्वारा प्रमाण निम्नानुसार है:

1. सिद्ध किया जाने वाला तर्कवाक्य P है।
2. ¬P को मान ले।
3. असत्यता प्राप्त करें।
4. P का समापन करें।

औपचारिक रूप से ये समान नहीं होते हैं क्योंकि विरोधाभास द्वारा खंडन केवल तभी प्रयुक्त होता है जब सिद्ध किए जाने वाले प्रस्ताव को अस्वीकृत कर दिया जाता है, जबकि विरोधाभास द्वारा प्रमाण किसी भी प्रस्ताव पर प्रयुक्त किया जा सकता है। पारम्परिक तर्क में, जहां $P$ और $\neg \neg P$ को स्वतंत्र रूप से परिवर्तित कर दिया जा सकता है विशिष्टता अपेक्षाकृत रूप से अस्पष्ट है। इस प्रकार गणितीय अभ्यास में, दोनों सिद्धांतों को विरोधाभास द्वारा प्रमाण के रूप में संदर्भित किया जाता है।

बहिष्कृत मध्य का कानून

Main article: बहिष्कृत मध्य का कानून

विरोधाभास द्वारा गणितीय प्रमाण बहिष्कृत मध्य के कानून के बराबर होता है, जो पहले अरस्तू द्वारा तैयार किया गया था जो बताता है कि या तो एक अभिकथन या उसका अस्वीकृत सत्य P ∨ ¬P है।

गैर-विरोधाभास का कानून

गैर-विरोधाभास के नियम को सबसे पहले अरस्तू द्वारा एक तत्वमीमांसा सिद्धांत के रूप में बताया गया था। यह मानता है कि एक प्रस्ताव और इसकी अस्वीकृति दोनों सत्य या समकक्ष नहीं हो सकते हैं, कि एक प्रस्ताव सही और गलत दोनों नहीं हो सकता है। औपचारिक रूप से गैर-विरोधाभास के नियम को ¬(P ∧ ¬P) के रूप में लिखा जाता है और इसे "ऐसा नहीं है कि प्रस्ताव सत्य और असत्य दोनों है" के रूप में पढ़ा जाता है। गैर-विरोधाभास का नियम न तो अनुसरण करता है और न ही अंतर्विरोध द्वारा प्रमाण के सिद्धांत का अनुसरण करता है।

बहिष्कृत मध्य और गैर-विरोधाभास के नियमों का एक साथ अर्थ है कि P और ¬P में से कोई एक सत्य है।

अंतर्ज्ञानवादी तर्क में विरोधाभास द्वारा प्रमाण

अंतर्ज्ञानवादी तर्क में विरोधाभास द्वारा प्रमाणसामान्य रूप से मान्य नहीं होता है, हालांकि कुछ विशेष उदाहरण प्राप्त किए जा सकते हैं। इसके विपरीत, निषेध का प्रमाण और गैर-विरोधाभास का सिद्धांत दोनों ही सहज रूप से मान्य होते हैं।

ब्रौवर-हेटिंग-कोल्मोगोरोव विरोधाभास द्वारा प्रमाण की व्याख्या निम्नलिखित अंतर्ज्ञानवादी वैधता की स्थिति प्रदान करती है यदि यह स्थापित करने की कोई विधि नहीं है कि कोई तर्कवाक्य असत्य है, तो यह स्थापित करने की एक विधि है जिससे कि तर्कवाक्य सत्य होता है।

यदि हम इस सिद्धांत को एल्गोरिथम के रूप में मानते हैं तो स्थिति स्वीकार्य नहीं होती है क्योंकि यह हमें हाल्टिंग समस्या को हल करने की स्वीकृति प्रदान करता है। यह देखने के लिए कि कैसे कथन H(M) पर विचार करें जिसमें कहा गया है कि "ट्यूरिंग मशीन M पर स्थगित होती है या नहीं स्थगित होती है" इसका निषेध ¬H(M) कहता है कि "M न तो स्थगित होता है और नही स्थगित होता है, जो कि गैर-विरोधाभास के कानून द्वारा असत्य है जो अंतर्ज्ञानवादी रूप से मान्य है। यदि विरोधाभास द्वारा प्रमाण अंतर्ज्ञानवादी रूप से मान्य थे तो हम यह तय करने के लिए एक एल्गोरिदम प्राप्त करेंगे कि क्या एक अपेक्षाकृत ट्यूरिंग मशीन M स्थगित है, जिससे हॉल्टिंग समस्या की गैर-हल क्षमता के प्रमाण (सहजता से मान्य) का उल्लंघन होता है। और यह एक प्रस्ताव $\lnot \lnot P\Rightarrow P$ को संतुष्ट करता है जिसे स्थिर प्रस्ताव के रूप में जाना जाता है।

इस प्रकार अन्तर्ज्ञानवादी तर्क में विरोधाभास द्वारा प्रमाण सम्पूर्ण रूप से मान्य नहीं होता है, लेकिन केवल ¬¬-स्थिर प्रस्तावों पर प्रयुक्त किया जा सकता है। इस प्रकार के प्रस्ताव का एक उदाहरण निर्णायक होता है, अर्थात्, $P\lor \lnot P$ वास्तव में, उपरोक्त प्रमाण कि बहिष्कृत मध्य का नियम विरोधाभास द्वारा प्रमाण का तात्पर्य है, यह दिखाने के लिए पुन: प्रस्तुत किया जा सकता है कि एक निर्णायक प्रस्ताव ¬¬-स्थिर होता है। यह प्रदर्शित करने के लिए पुनर्निर्मित किया जा सकता है कि एक निर्णय लेने योग्य प्रस्ताव स्थिर होता है। एक निर्णायक प्रस्ताव का एक विशिष्ट उदाहरण ($n$ अभाज्य है जो $a$ या $b$ विभाजित करता है।) तर्क है जिसकी गणना द्वारा प्रत्यक्ष परीक्षण किया जा सकता है।

विरोधाभास द्वारा प्रमाणों के उदाहरण

यूक्लिड के तत्व

विरोधाभास द्वारा प्रमाण की एक प्रारंभिक घटना यूक्लिड के तत्वों, पुस्तक 1, प्रस्ताव 6 में पाई जा सकती है: यदि एक त्रिभुज में दो कोण एक दूसरे के बराबर हैं, तो समान कोणों के विपरीत पक्ष भी एक दूसरे के बराबर होते हैं। प्रमाण यह मानकर आगे बढ़ता है कि विपरीत कोण समान नहीं हैं और एक विरोधाभास प्राप्त करते हैं।

हिल्बर्ट का नलस्टेलनसैट्ज

विरोधाभास द्वारा एक प्रभावशाली प्रमाण डेविड हिल्बर्ट द्वारा दिया गया था। जिसको हिल्बर्ट का नलस्टेलनसैट्ज प्रमाण कहा जाता है।

यदि $f_{1},\ldots ,f_{k}$ में [[बहुपद|बहुपद n]] हैं समिश्र संख्या गुणांक के साथ अनिश्चितता है जिसमें एक कारक का कोई सामान्य समिश्र शून्य नहीं है, फिर बहुपद $g_{1},\ldots ,g_{k}$ ऐसा होता है कि $f_{1}g_{1}+\ldots +f_{k}g_{k}=1.$

हिल्बर्ट ने यह मानकर तर्क प्रमाणित किया कि ऐसे कोई बहुपद $g_{1},\ldots ,g_{k}$ नहीं हैं जिससे कि एक विरोधाभास प्राप्त किया जा सकता है।

अभाज्य संख्याओं की अनंतता

यूक्लिड के प्रमेय में कहा गया है कि अपरिमित रूप से अनेक अभाज्य संख्याएँ हैं। यूक्लिड के तत्वों में प्रमेय को पुस्तक IX, प्रस्ताव 20 में कहा गया है:

अभाज्य संख्याएँ अभाज्य संख्याओं की किसी भी निर्धारित यूक्लिड के तत्वों से अधिक होती हैं।

उपरोक्त कथन को हम औपचारिक रूप से कैसे लिखते हैं, इस पर निर्भर करते हुए, सामान्य प्रमाण या तो विरोधाभास द्वारा प्रमाण का रूप ले लेता है या विरोधाभास द्वारा खंडन करता है। हम यहां पूर्व को प्रस्तुत करते हैं, नीचे देखें कि विरोधाभास द्वारा खंडन के रूप में प्रमाण कैसे प्राप्त किया जाता है।

यदि हम औपचारिक रूप से यूक्लिड के प्रमेय को यह कहते हुए व्यक्त करते हैं कि प्रत्येक प्राकृतिक संख्या के लिए $n$ इससे भी बड़ा है, फिर हम विरोधाभास द्वारा प्रमाण को नियुक्त करते हैं, जो निम्नानुसार हैं।

किसी भी संख्या $n$ को देखते हुए, हम यह सिद्ध करना चाहते हैं कि $n$ से बड़ा एक अभाज्य है। इसके विपरीत मान लीजिए कि ऐसा कोई P (विरोधाभास द्वारा गणितीय प्रमाण का अनुप्रयोग) सम्मिलित नहीं है। तब सभी अभाज्य संख्याएँ $n$ से छोटी या उसके बराबर होती हैं और हम उन सभी की सूची $p_{1},\ldots ,p_{k}$ बना सकते हैं। मान लीजिए कि $P=p_{1}\cdot \ldots \cdot p_{k}$ सभी अभाज्य संख्याओं का गुणनफल $Q=P+1$ है क्योंकि $Q$ सभी अभाज्य संख्याओं से बड़ा है और यह अभाज्य नहीं है इसलिए यह उनमें से एक $p_{i}$ से विभाज्य होना चाहिए,अब $P$ और $Q$ दोनों $p_{i}$ से विभाज्य हैं, इसलिए उनका अंतर $Q-P=1$ है लेकिन ऐसा नहीं हो सकता है क्योंकि 1 किसी भी अभाज्य संख्या से विभाज्य नहीं होता है। इसलिए हमारे पास एक विरोधाभास है और इसलिए $n$ से बड़ी एक अभाज्य संख्या होता है।

विरोधाभास द्वारा खंडन के उदाहरण

निम्नलिखित उदाहरणों को सामान्यतः विरोधाभास द्वारा प्रमाण के रूप में संदर्भित किया जाता है लेकिन औपचारिक रूप से विरोधाभास द्वारा खंडन को नियोजित किया जाता है और इसलिए सहज रूप से मान्य हैं।

अभाज्य संख्याओं की अनंतता

यूक्लिड के तत्वों की प्रमेय पुस्तक IX, प्रस्ताव 20 पर दोबारा प्रकाश पप्रकाशित किया गया है जिसमे अभाज्य संख्याएँ अभाज्य संख्याओं की किसी भी निर्धारित यूक्लिड के तत्वों से अधिक होती हैं।

हम कथन को यह कहते हुए पढ़ सकते हैं कि अभाज्य संख्याओं की प्रत्येक परिमित सूची के लिए, उस सूची में नहीं एक अन्य अभाज्य संख्या है जो यूक्लिड के मूल सूत्रीकरण के समान और उसी भावना के निकट होती है। इस स्थिति में यूक्लिड का प्रमाण विरोधाभास द्वारा खंडन प्रयुक्त करता है जैसा कि नीचे दिया गया है।

अभाज्य संख्याओं की कोई परिमित $p_{1},\ldots ,p_{n}$ सूची दी गई है यह प्रदर्शित किया गया है कि कम से कम एक अतिरिक्त अभाज्य संख्या इस सूची में सम्मिलित नहीं है। मान लीजिए कि $P=p_{1}\cdot p_{2}\cdots p_{n}$ सभी सूचीबद्ध अभाज्य संख्याओं का गुणनफल है और $p$ संभवतः $P+1$ का एक अभाज्य कारक है। हम निश्चित करते हैं कि $p$ दी गई अभाज्य संख्याओं की सूची में नहीं है। इसके विपरीत मान लीजिए कि यह विरोधाभास द्वारा प्रतिनियुक्ति का एक अनुप्रयोग था। तब $p$, $P$ और $P+1$ दोनों को विभाजित करता है इसलिए उनका अंतर भी, जो 1 है यह 1 विरोधाभास देता है क्योंकि कोई भी अभाज्य संख्या 1 को विभाजित नहीं करती है।

2 के वर्गमूल की अपरिमेयता

पारम्परिक प्रमाण यह है कि 2 का वर्गमूल तर्कहीन होता है क्योकि यह विरोधाभास द्वारा खंडन है। वास्तव में, हम निषेध ¬ ∈ a, b, $\mathbb {N}$ को सिद्ध करने के लिए a/b = √2 यह मानते हुए कि प्राकृतिक संख्याएँ a और b उपस्थित हैं जिनका अनुपात दो का वर्गमूल है और एक विरोधाभास प्राप्त करता है।

अपरिमित अवरोह द्वारा प्रमाण

अपरिमित अवरोह द्वारा प्रमाण की एक विधि है जिससे वांछित संपत्ति के साथ एक सबसे छोटी वस्तु को निम्नानुसार नहीं प्रदर्शित किया गया है:

• माना कि वांछित संपत्ति के साथ सबसे छोटी वस्तु है।
• प्रदर्शित करें कि वांछित संपत्ति के साथ एक और भी छोटी वस्तु सम्मिलित है जिससे एक विरोधाभास उत्पन्न होता है।

ऐसा प्रमाण फिर से विरोधाभास द्वारा खंडन है। एक विशिष्ट उदाहरण "कोई सबसे छोटी धनात्मक परिमेय संख्या नहीं है" प्रस्ताव का प्रमाण है: माना कि एक सबसे छोटी धनात्मक परिमेय संख्या q है और यह देखते हुए एक विरोधाभास प्राप्त करें कि q/2 से भी छोटा है और फिर भी धनात्मक है।

रसेल का विरोधाभास

रसेल का विरोधाभास, एक समुच्चय-सैद्धांतिक रूप से कहा गया है कि "ऐसा कोई समुच्चय नहीं है जिसके तत्व ठीक वही प्रयुक्त हैं जो स्वयं को सम्मिलित नहीं करते हैं", एक निषेध कथन है जिसका सामान्य प्रमाण का विरोधाभास द्वारा खंडन होता है।

संकेतन

विरोधाभास द्वारा प्रमाण कभी-कभी "विरोधाभास" शब्द के साथ समाप्त होते हैं। इसहाक बैरो और बर्मन ने क्यूईडी के तर्क पर "क्वॉड इस्ट एब्सर्डम" (जो निरर्थक है) के लिए क्यूईए संकेतन का उपयोग किया, लेकिन आज इस संकेतन का अपेक्षाकृत रूप से कम ही कभी उपयोग किया जाता है। विरोधाभासों के लिए कभी-कभी इस्तेमाल किया जाने वाला एक ग्राफिकल प्रतीक एक नीचे की ओर ज़िगज़ैग तीर विद्युत प्रतीक (यू + 21एएफ: ↯) उदाहरण के लिए डेवी और प्रिस्टले में है। कभी -कभी उपयोग किए जाने वाले दूसरों में एरिस के हाथ की एक जोड़ी सम्मिलित होती है जैसा कि $\rightarrow \!\leftarrow$ या $\Rightarrow \!\Leftarrow$, ($\nleftrightarrow$), हैश का एक शैलीबद्ध रूप (जैसे कि u+2a33: ⨳), या संदर्भ चिह्न (u+203b: ※), या $\times \!\!\!\!\times$ और इसी प्रकार के विभिन्न प्रतीक सम्मिलित होते है।

जीएच हार्डी के विचार

जीएच हार्डी ने विरोधाभास द्वारा गणितीय प्रमाण को गणितज्ञ के अपेक्षाकृत सिद्धान्त में से एक के रूप में वर्णित किया है यह किसी भी शतरंज के खिलाड़ी की तुलना में कहीं अधिक सूक्ष्म खेल है एक शतरंज खिलाड़ी संकेतन या एक टुकड़े का परित्याग कर सकता है लेकिन एक गणितज्ञ खेल को प्रस्तावित करता है।

यह भी देखें

• बहिष्कृत मध्य का कानून
• गैर-विरोधाभास का कानून
• निःशेषण प्रमाण
• अपरिमित अवरोहण प्रमाण
• निषेधक हेतु फलानुमान

आगे पढ़ने और बाहरी लिंक

• Franklin, James; Daoud, Albert (2011). गणित में प्रमाण: एक परिचय. chapter 6: Kew. ISBN 978-0-646-54509-7. {{cite book}}: |archive-date= requires |archive-url= (help)CS1 maint: location (link)
• विरोधाभास द्वारा लैरी डब्ल्यू। क्यूसिक के कैसे लिखें
• reductio ad absurdum इंटरनेट इनसाइक्लोपीडिया ऑफ फिलॉसफी;ISSN 2161-0002

श्रेणी: गणितीय प्रमाण श्रेणी: प्रमाण के तरीके श्रेणी: प्रपोजल लॉजिक में प्रमेय