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

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

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

विरोधाभास द्वारा प्रमाण को नियोजित करने वाला एक गणितीय प्रमाण आमतौर पर निम्नानुसार आगे बढ़ता है:

1. साबित करने का प्रस्ताव पी। पी।
2. हम मानते हैं कि पी को गलत माना जाता है, यानी, हम मान लेते हैं।
3. तब दिखाया गया है कि ¬p का अर्थ है झूठ।यह आम तौर पर दो पारस्परिक रूप से विरोधाभासी दावे, क्यू और, क्यू प्राप्त करके पूरा किया जाता हैअविश्वास नियम के कानून के लिए अपील करता है।
4. Since मान को गलत मानते हुए एक विरोधाभास की ओर जाता है, यह निष्कर्ष निकाला जाता है कि 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
T	F	T	T
F	T	F	T

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

1. यदि P धारण करता है, तो निश्चित रूप से P धारण करता है।
2. यदि, पी है, तो हम ¬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. साबित करने का प्रस्ताव। पी है।
2. मान लें पी।
3. झूठ को प्राप्त करें।
4. समापन। पी।

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

1. साबित करने का प्रस्ताव पी।
2. मान लें।
3. झूठ को प्राप्त करें।
4. समापन पी।

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

बाहर के मध्य का कानून

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

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

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

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

एक साथ मध्य और गैर-विरोधाभास के कानूनों के कानूनों का मतलब है कि वास्तव में पी और ofp में से एक सच है।

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

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

Brouwer -heyting -kolmogorov विरोधाभास द्वारा प्रमाण की व्याख्या निम्नलिखित अंतर्ज्ञानवादी वैधता की स्थिति देती है:

यदि यह स्थापित करने के लिए कोई विधि नहीं है कि एक प्रस्ताव गलत है, तो यह स्थापित करने के लिए एक विधि है कि प्रस्ताव सत्य है।

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

एक प्रस्ताव पी जो संतुष्ट करता है $\lnot \lnot P\Rightarrow P$ एक-स्थिर प्रस्ताव के रूप में जाना जाता है।इस प्रकार विरोधाभास द्वारा अंतर्ज्ञानवादी तर्क प्रमाण सार्वभौमिक रूप से मान्य नहीं है, लेकिन केवल and-स्थिर प्रस्तावों पर लागू किया जा सकता है।इस तरह के प्रस्ताव का एक उदाहरण एक निर्णायक है, अर्थात्, संतोषजनक $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

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