إثبات الاستحالة

يُعدّ البرهان بالتناقض أحد أكثر أنواع البراهين شيوعًا في إثبات الاستحالة . في هذا النوع من البراهين، يُبيّن أنه إذا افترضنا صحة قضية ما، كحلّ فئة معينة من المعادلات، فإنه يُمكن، بالاستدلال، إثبات صحة أمرين متناقضين، كأن يكون عدد ما زوجيًا وفرديًا في آنٍ واحد، أو سالبًا وموجبًا في آنٍ واحد. ولأن التناقض ينبع من الافتراض الأصلي، فهذا يعني أن الفرضية المفترضة مستحيلة.

في المقابل، يقوم البرهان غير البنّاء على ادعاء الاستحالة بإثبات أن كون جميع الأمثلة المضادة المحتملة غير صالحة يُعدّ تناقضًا منطقيًا: إذ يجب أن يكون عنصر واحد على الأقل في قائمة الأمثلة المضادة المحتملة مثالًا مضادًا صالحًا لفرضية الاستحالة. على سبيل المثال، تم دحض فرضية مفادها أنه من المستحيل أن تكون قوة غير عقلانية مرفوعة إلى قوة غير عقلانية عقلانية ، وذلك بإثبات أن أحد مثالين مضادين محتملين يجب أن يكون مثالًا مضادًا صالحًا، دون تحديد أيّهما هو.

الطريقة البديهية لدحض فرضية الاستحالة هي تقديم مثال مضاد واحد . على سبيل المثال، اقترح أويلر أنه يلزم وجود n قوة مختلفة على الأقل ^{من الرتبة} n لمجموعها يساوي قوة أخرى من ^الرتبة n . تم دحض هذه الفرضية في عام 1966، بمثال مضاد يتضمن حساب أربع قوى مختلفة فقط من الرتبة الخامسة مجموعها يساوي قوة أخرى من الرتبة الخامسة.

إن البرهان عن طريق المثال المضاد هو شكل من أشكال البرهان البنائي ، حيث يتم عرض شيء ينفي الادعاء.

في نظرية الاختيار الاجتماعي ، تُظهر نظرية استحالة آرو أنه من المستحيل ابتكار نظام تصويت بالاختيار المصنف يكون غير دكتاتوري ويلبي في نفس الوقت شرطًا أساسيًا للسلوك العقلاني يسمى استقلال البدائل غير ذات الصلة .

تُظهر نظرية جيبارد أن أي شكل من أشكال اللعبة المقاومة للاستراتيجية (أي تلك التي تحتوي على استراتيجية مهيمنة ) مع أكثر من نتيجتين هو شكل دكتاتوري .

تُعد نظرية جيبارد -ساترثويت حالة خاصة تُظهر أنه لا يمكن لأي نظام تصويت حتمي أن يكون محصنًا تمامًا ضد التصويت الاستراتيجي في جميع الظروف، بغض النظر عن كيفية تصويت الآخرين.

يمكن اعتبار مبدأ الكشف بمثابة نظرية استحالة تُظهر "عكس" نظرية جيبارد، بالمعنى الدارج: أي لعبة أو نظام تصويت يمكن جعله مقاومًا للاستراتيجية من خلال دمج الاستراتيجية في الآلية . وبالتالي، يستحيل تصميم آلية بحل أفضل مما يمكن الحصول عليه بواسطة آلية صادقة .

كان لبرهان فيثاغورس حوالي عام 500 قبل الميلاد أثر بالغ على الرياضيات. فقد أثبت أن الجذر التربيعي للعدد 2 لا يمكن التعبير عنه كنسبة بين عددين صحيحين. وقد قسم هذا البرهان "الأعداد" إلى مجموعتين غير متداخلتين: الأعداد النسبية والأعداد غير النسبية . 

هناك مقطع شهير في محاورة ثيائيتيتوس لأفلاطون ، يُذكر فيه أن ثيودوروس (معلم أفلاطون) أثبت عدم عقلانية

${\displaystyle {\sqrt {3}},{\sqrt {5}},...,}$

بأخذ جميع الحالات المنفصلة حتى جذر 17  قدم مربع  ... . ^{[ 6 ]}

يُظهر برهانٌ أكثر عمومية أن الجذر النوني لعدد صحيح N هو عدد غير نسبي، إلا إذا كان N هو القوة النونية لعدد صحيح n . ^{[ 7 ]} أي أنه من المستحيل التعبير عن الجذر النوني لعدد صحيح N كنسبة a / b لعددين صحيحين a و b ، لا يشتركان في أي عامل أولي مشترك ، إلا في الحالات التي يكون فيها b  =  1.

اعتمدت الهندسة اليونانية على استخدام الفرجار والمسطرة (مع أن المسطرة ليست ضرورية تمامًا). يسمح الفرجار للمهندس بإنشاء نقاط متساوية البعد عن بعضها، وهو ما يُعادل ضمنيًا في الفضاء الإقليدي حساب الجذور التربيعية . وقد طُرحت أربعة أسئلة شهيرة حول كيفية إنشاء هذه النقاط.

1. زوج من الخطوط يقسم زاوية معينة إلى ثلاثة أجزاء متساوية ؛
2. مكعب حجمه ضعف حجم مكعب معين ؛
3. مربع يساوي في مساحته مساحة دائرة معينة؛
4. مضلع متساوي الأضلاع بعدد عشوائي من الأضلاع.

على مدى أكثر من 2000 عام، بُذلت محاولات غير ناجحة لحل هذه المشكلات؛ وأخيرًا، في القرن التاسع عشر، ثبت أن الإنشاءات المطلوبة مستحيلة رياضيًا دون استخدام أدوات إضافية غير البوصلة. ^{[ 8 ]}

جميع هذه المشكلات تُعدّ من صعوبات الإنشاء الإقليدي ، ولا يُمكن إجراء الإنشاءات الإقليدية إلا إذا اقتصرت على الأعداد الإقليدية (بحسب تعريفها). ^{[ 9 ]} يُمكن أن تكون الأعداد غير النسبية أعدادًا إقليدية. ومن الأمثلة الجيدة على ذلك الجذر التربيعي للعدد 2 (وهو عدد غير نسبي). فهو ببساطة طول وتر مثلث قائم الزاوية، طول كل من ضلعيه وحدة واحدة، ويُمكن إنشاؤه باستخدام المسطرة والفرجار. ولكن بعد قرون من اكتشاف إقليدس، تبيّن أن الأعداد الإقليدية لا يُمكن أن تتضمن أي عمليات حسابية أخرى غير الجمع والطرح والضرب والقسمة واستخراج الجذور التربيعية.

يتطلب كل من تقسيم الزاوية العامة إلى ثلاثة أجزاء ومضاعفة المكعب أخذ الجذور التكعيبية ، وهي أعداد غير قابلة للإنشاء .

${\displaystyle \pi }$ليس عددًا إقليديًا ... وبالتالي يستحيل إنشاء طول يساوي محيط دائرة قطرها وحدة واحدة، باستخدام الطرق الإقليدية.

لأن${\displaystyle \pi }$ثبت في عام 1882 أنه عدد متسامٍ ، وليس عددًا إقليديًا؛ ومن هنا جاء بناء الطول${\displaystyle \pi }$من المستحيل الحصول على نتيجة من دائرة الوحدة. ^{[ 10 ] [ 11 ]}

تُعادل مسلمة التوازي من كتاب الأصول لإقليدس القول بأنه إذا وُجد خط مستقيم ونقطة لا تقع عليه، فلا يُمكن رسم سوى خط واحد موازٍ له يمر بتلك النقطة. وعلى عكس المسلمات الأخرى، اعتُبرت هذه المسلمة أقل وضوحًا. ويُجادل ناجل ونيومان بأن ذلك قد يعود إلى أن هذه المسلمة تتعلق بمناطق "بعيدة جدًا" في الفضاء؛ فعلى وجه الخصوص، تُعرَّف الخطوط المتوازية بأنها لا تلتقي حتى "عند اللانهاية"، على عكس خطوط التقارب . ^{[ 12 ]} وقد أدى هذا النقص الملحوظ في الوضوح إلى التساؤل عما إذا كان من الممكن إثباتها من بديهيات ومسلمات إقليدس الأخرى. ولم يتضح استحالة استنتاج مسلمة التوازي من المسلمات الأخرى إلا في القرن التاسع عشر، وذلك من خلال أعمال جاوس وبولياي ولوباتشيفسكي وريمان . وقد أظهرت هذه الأعمال أنه يُمكن استبدال مسلمة التوازي بمسلمات بديلة، مما يؤدي إلى هندسات غير إقليدية .

يعتبر ناجل ونيومان السؤال الذي أثارته مسلمة التوازي "...ربما أهم تطور من حيث آثاره بعيدة المدى على تاريخ الرياضيات اللاحق". ^{[ 12 ]} وعلى وجه الخصوص، يعتبران نتيجتها "ذات أهمية فكرية بالغة"، إذ أظهرت أنه " يمكن تقديم برهان على استحالة إثبات بعض القضايا [في هذه الحالة، مسلمة التوازي] ضمن نظام معين [في هذه الحالة، مسلمات إقليدس الأربع الأولى]". ^{[ 13 ]}

تنص نظرية فيرما الأخيرة، التي وضعها بيير دي فيرما في القرن السابع عشر، على استحالة إيجاد حلول في الأعداد الصحيحة الموجبة للمعادلة${\displaystyle x^{n}+y^{n}=z^{n}}$مع${\displaystyle n>2}$. قدم فيرما نفسه برهانًا لحالة n  =  4 باستخدام أسلوبه في النزول اللانهائي ، وتم إثبات حالات خاصة أخرى لاحقًا، ولكن لم يتم إثبات الحالة العامة حتى عام 1994 بواسطة أندرو وايلز .

إن السؤال "هل لأي معادلة ديوفانتية عشوائية حل صحيح؟" غير قابل للحسم . أي أنه من المستحيل الإجابة على هذا السؤال لجميع الحالات.

يُقدّم فرانزين المسألة العاشرة لهيلبرت ونظرية ماتياسيفيتش-روبنسون-ديفيس-بوتنام ( MRDP ) التي تنص على أنه "لا توجد خوارزمية قادرة على تحديد ما إذا كانت معادلة ديوفانتية لها حل أم لا " . تستخدم نظرية MRDP برهان عدم قابلية الحسم لتورينغ: "... مجموعة المعادلات الديوفانتية القابلة للحل هي مثال على مجموعة قابلة للتعداد الحسابي ولكنها غير قابلة للحسم، ومجموعة المعادلات الديوفانتية غير القابلة للحل ليست قابلة للتعداد الحسابي". ^{[ 14 ]}

أثرت هذه المفارقة العميقة التي طرحها جول ريتشارد عام 1905 على أعمال كورت غودل ^{[ 15 ]} وآلان تورينج. ويمكن إيجاد تعريف موجز لها في كتاب " برينسيبيا ماثيماتيكا" ^{[ 16 ].}

مفارقة ريتشارد... هي كما يلي. لنفترض جميع الأعداد العشرية التي يمكن تعريفها باستخدام عدد محدود من الكلمات ["الكلمات" هنا هي رموز؛ تم إضافة الخط الغامق للتأكيد] ؛ ولتكن E فئة هذه الأعداد العشرية. عندئذٍ، تمتلك E${\displaystyle \aleph _{0}}$عدد لا نهائي من الحدود؛ لذا يمكن ترتيب عناصرها كالتالي: الأول، الثاني، الثالث، ... ليكن X عددًا مُعرَّفًا كما يلي [يستخدم وايتهيد وراسل الآن طريقة كانتور القطرية] . إذا كان الرقم النوني في العدد العشري النوني هو p ، فليكن الرقم النوني في X هو p  +  1 (أو 0، إذا كان p  =  9). عندئذٍ، يختلف X عن جميع عناصر E ، لأنه مهما كانت القيمة المحدودة لـ n ، فإن الرقم النوني في X يختلف عن الرقم النوني في العدد العشري النوني المُكوِّن لـ E ، وبالتالي يختلف X عن العدد العشري النوني . مع ذلك، فقد عرَّفنا X بعدد محدود من الكلمات [أي هذا التعريف لـ "الكلمة" أعلاه]، وبالتالي ينبغي أن يكون X عنصرًا من E. إذن، X هو عنصر من E وليس عنصرًا منها في الوقت نفسه .

اعتبر كورت غودل برهانه بمثابة "تشبيه" لمفارقة ريتشارد، والتي أطلق عليها اسم " تناقض ريتشارد " ^{[ 17 ]} .

قام آلان تورينج بتكوين هذه المفارقة باستخدام آلة وأثبت أن هذه الآلة لا يمكنها الإجابة على سؤال بسيط: هل ستكون هذه الآلة قادرة على تحديد ما إذا كانت أي آلة (بما في ذلك نفسها) ستعلق في " حلقة لا نهائية " غير منتجة (أي أنها تفشل في مواصلة حساب العدد القطري).

كما ذكر ناجل ونيومان (ص  68): "إنّ ورقة غودل صعبة. إذ يجب استيعاب ستة وأربعين تعريفًا تمهيديًا، إلى جانب العديد من النظريات التمهيدية المهمة، قبل الوصول إلى النتائج الرئيسية". في الواقع، احتاج ناجل ونيومان إلى مقدمة من 67 صفحة لشرح برهانهما. ولكن إذا شعر القارئ بالقدرة الكافية على قراءة الورقة، يُشير مارتن ديفيس إلى أن "هذه الورقة الرائعة ليست مجرد علامة فارقة في الفكر، بل إنها مكتوبة بوضوح وحيوية تجعل قراءتها ممتعة" (ديفيس في كتاب "غير قابل للتقرير"، ص  4).

أثبت غودل، بكلماته الخاصة:

«من المعقول... أن نفترض أن... البديهيات [من كتابي Principia Mathematica و Peano ] كافية لحسم جميع المسائل الرياضية التي يمكن التعبير عنها شكليًا في الأنظمة المعطاة. وسنبين فيما يلي أن هذا ليس صحيحًا، بل إن... هناك مسائل بسيطة نسبيًا في نظرية الأعداد الصحيحة العادية لا يمكن حسمها بناءً على هذه البديهيات» (غودل في كتاب Undecidable، ص 4).

قارن غودل برهانه بـ "تناقض ريتشارد" ( التناقض هو تناقض أو مفارقة؛ لمزيد من المعلومات انظر مفارقة ريتشارد ):

إن تشابه هذه النتيجة مع تناقض ريتشارد واضحٌ جليّ؛ كما توجد علاقة وثيقة [14] بمفارقة الكاذب (حاشية غودل 14: يمكن استخدام كل تناقض معرفي لإثبات عدم قابلية الحسم بشكل مماثل)... وبالتالي، لدينا قضية أمامنا تؤكد عدم قابليتها للإثبات [15]. (حاشية غودل 15: على عكس ما يبدو، فإن هذه القضية ليست دائرية، لأنها، في البداية، تؤكد عدم قابلية إثبات صيغة محددة تمامًا). ^{[ 17 ]}

• تم حل مشكلة القرار ( Entscheidungsproblem ) لأول مرة من قبل تشيرش في أبريل 1935 وسبقت تورينج بأكثر من عام، حيث تم استلام ورقة تورينج للنشر في مايو 1936. ^{[ 18 ]}
• يُعدّ برهان تورينج صعباً نظراً لكثرة التعريفات المطلوبة ودقّته. انظر آلة تورينج وبرهان تورينج لمزيد من التفاصيل.
• يتبع برهان تورينج الأول (من ثلاثة) مخطط مفارقة ريتشارد: آلة تورينج الحاسوبية عبارة عن خوارزمية ممثلة بسلسلة من سبعة أحرف في "آلة حاسوبية". تتمثل "عمليتها الحسابية" في اختبار جميع الآلات الحاسوبية (بما فيها نفسها) بحثًا عن "دوائر"، وتكوين عدد قطري من حسابات الآلات غير الدائرية أو "الناجحة". تقوم بذلك، بدءًا من 1 بالتسلسل، عن طريق تحويل الأرقام (الأساس 8) إلى سلاسل من سبعة أحرف لاختبارها. عندما تصل إلى عددها الخاص، تُنشئ سلسلة أحرف خاصة بها . تقرر أنها سلسلة أحرف آلة ناجحة، ولكن عندما تحاول إجراء حساب هذه الآلة ( حسابها الخاص )، فإنها تتعطل في حلقة ولا تستطيع المتابعة. وهكذا، نكون قد وصلنا إلى مفارقة ريتشارد. (إذا كنت تشعر بالحيرة، فراجع برهان تورينج لمزيد من التفاصيل).

ظهر عدد من البراهين المماثلة المتعلقة بعدم قابلية الحسم قبل برهان تورينج وبعده بفترة وجيزة:

1. أبريل 1935: برهان ألونسو تشيرش ("مسألة غير قابلة للحل في نظرية الأعداد الأولية"). كان برهانه هو "...اقتراح تعريف للحساب الفعال ... وإظهار، من خلال مثال، أنه ليس كل مشكلة من هذه الفئة قابلة للحل" (غير قابلة للتقرير، ص  90).
2. 1946: مشكلة المراسلات البريدية (انظر هوبكروفت وأولمان ^{[ 19 ]} ص  193 وما بعدها، ص  407 كمرجع)
3. أبريل 1947: برهان إميل بوست ( عدم قابلية حل مشكلة ثو بشكل متكرر ) (غير قابل للتقرير، ص  293). عُرفت هذه المشكلة منذ ذلك الحين باسم "مشكلة ثو اللفظية" أو "مشكلة ثو اللفظية" ( اقترح أكسل ثو هذه المشكلة في ورقة بحثية عام 1914 (انظر مراجع ورقة بوست في غير قابل للتقرير، ص  303)).
4. نظرية رايس : صياغة معممة لنظرية تورينج الثانية (انظر هوبكروفت وأولمان ^{[ 19 ]} ص.  185 وما بعدها) ^{[ 20 ]}
5. نظرية جريباخ : عدم قابلية الحسم في نظرية اللغة (انظر هوبكروفت وأولمان ^{[ 19 ]} ص  205 وما بعدها، والإشارة في الصفحة  401 من المرجع نفسه: جريباخ [1963] "عدم قابلية حسم مشكلة الغموض للقواعد الخطية الدنيا"، المعلومات والتحكم 6:2، 117-125، وأيضًا الإشارة في الصفحة  402 من المرجع نفسه: جريباخ [1968] "ملاحظة حول خصائص عدم قابلية الحسم للغات الرسمية"، نظرية الأنظمة الرياضية 2:1، 1-6).
6. أسئلة حول تبليط بنروز .

للحصول على شرح مناسب لغير المتخصصين، انظر بلترامي، الصفحات  ١٠٨ وما بعدها. انظر أيضًا فرانزن، الفصل الثامن، الصفحات  ١٣٧-١٤٨، وديفيس، الصفحات  ٢٦٣-٢٦٦. مناقشة فرانزن أكثر تعقيدًا بكثير من مناقشة بلترامي، وتتعمق في Ω - ما يُسمى بـ"احتمالية التوقف" لغريغوري تشايتين . يتناول ديفيس، في معالجته الأقدم، المسألة من منظور آلة تورينغ . وقد ألّف تشايتين عددًا من الكتب حول مساعيه وما ترتب عليها من آثار فلسفية ورياضية.

تُسمى السلسلة (خوارزميًا) عشوائية إذا لم يكن بالإمكان إنتاجها من أي برنامج حاسوبي أقصر منها. مع أن معظم السلاسل عشوائية ، إلا أنه لا يمكن إثبات ذلك لأي سلسلة بعينها، باستثناء عدد محدود من السلاسل القصيرة.

"بتعبير آخر عن نتيجة تشايتين، لا يمكن تقديم دليل رسمي على أن السلسلة الطويلة بما فيه الكفاية عشوائية..." ^{[ 21 ]}

يلاحظ بلترامي أن "برهان تشايتين مرتبط بمفارقة طرحها أمين مكتبة أكسفورد جي. بيري في أوائل القرن العشرين، والتي تسأل عن 'أصغر عدد صحيح موجب لا يمكن تعريفه بجملة إنجليزية لا تتجاوز 1000 حرف'. من الواضح أن أقصر تعريف لهذا العدد يجب أن يتكون من 1000 حرف على الأقل. ومع ذلك، فإن الجملة بين علامتي الاقتباس، والتي هي في حد ذاتها تعريف للعدد المزعوم، لا تتجاوز 1000 حرف!" ^{[ 22 ]}