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

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

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

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

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 में पाई जा सकती है:

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

प्रमाण यह मानकर आगे बढ़ता है कि विपरीत कोण समान नहीं हैं, और एक विरोधाभास प्राप्त करते हैं।

हिल्बर्ट के Nullstellensatz

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

अगर $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}$ और एक विरोधाभास प्राप्त किया।

primes का अचूक

यूक्लिड के प्रमेय में कहा गया है कि असीम रूप से कई प्राइम हैं।यूक्लिड के तत्वों में प्रमेय को बुक IX में कहा गया है, प्रस्ताव 20:

प्राइम नंबर प्राइम नंबरों के किसी भी असाइन किए गए भीड़ से अधिक हैं।

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

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

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

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

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

primes का अचूक

आइए हम यूक्लिड के प्रमेय पर एक दूसरी नज़र डालें - पुस्तक IX, प्रस्ताव 20:

प्राइम नंबर प्राइम नंबरों के किसी भी असाइन किए गए भीड़ से अधिक हैं।

हम यह कहते हुए बयान को पढ़ सकते हैं कि प्राइम्स की हर परिमित सूची के लिए, उस सूची में एक और प्राइम नहीं है, जो यकीनन यूक्लिड के मूल सूत्रीकरण के रूप में और उसी आत्मा के करीब है।इस मामले में Euclid के प्रमेय#EUCLID का प्रमाण | Euclid का प्रमाण एक कदम पर विरोधाभास द्वारा प्रतिनियुक्ति लागू करता है, निम्नानुसार है।

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

=== 2 === के वर्गमूल की तर्कहीनता

अनंत वंश द्वारा 2#प्रूफ का क्लासिक वर्गमूल विरोधाभास द्वारा एक प्रतिनियुक्ति है। दरअसल, हम नकारात्मक साबित करने के लिए सेट करते हैं ¬ ∈ a, b, $\mathbb {N}$ ।a/b = √2यह मानकर कि प्राकृतिक संख्याएं ए और बी मौजूद हैं जिनका अनुपात दो का वर्गमूल है, और एक विरोधाभास प्राप्त करता है।

अनंत वंश द्वारा प्रमाण

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

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

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

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

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

संकेतन

विरोधाभास द्वारा प्रमाण कभी -कभी शब्द विरोधाभास के साथ समाप्त होते हैं!।इसहाक बैरो और बर्मन ने Q.E.D की तर्ज पर, क्वोड एस्ट एस्टरबर्डम (जो बेतुका है) के लिए नोटेशन Q.E.A. का उपयोग किया, लेकिन इस संकेतन का आज शायद ही कभी उपयोग किया जाता है। कभी -कभी विरोधाभासों के लिए उपयोग किया जाने वाला एक ग्राफिकल प्रतीक एक नीचे की ओर ज़िगज़ैग एरो लाइटनिंग सिंबल (यू+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

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