اثبات با بررسی حالت‌ها

اثبات با بررسی حالت‌ها (به انگلیسی: Proof by cases) روشی برای اثبات ریاضی است که در آن گزاره‌ای که باید اثبات شود به تعداد متناهی حالت تقسیم می‌شود و هر حالت اثبات می‌شود تا ببینیم که آیا گزارهٔ مورد نظر صادق است یا خیر. این یک روش اثبات مستقیم است. اثبات با بررسی حالت‌ها معمولاً شامل دو مرحله است:

1. اثبات اینکه مجموعهٔ حالت‌ها جامع است؛ یعنی هر مثال از گزاره‌ای که باید ثابت شود، با شرایط (حداقل) یکی از حالت‌ها مطابقت دارد.
2. اثبات هر یک از حالت‌ها.

رواج رایانه‌های دیجیتال، راحتی استفاده از این روش اثبات را بسیار افزایش داده‌است (به عنوان مثال، اولین اثبات قضیهٔ چهار رنگ به کمک رایانه در سال ۱۹۷۶ انجام گرفت)، اگرچه چنین رویکردهایی نیز می‌توانند بر اساس زیبایی ریاضی به چالش کشیده شوند. همچنین سامانه‌های خبره می‌توانند برای رسیدن به پاسخ بسیاری از سؤالات مطرح شده برای آن‌ها استفاده شوند. از لحاظ تئوری، این روش اثبات هر زمان که تعداد حالت‌ها متناهی باشد، قابل استفاده است. با این حال، از آنجایی که اکثر مجموعه‌های ریاضی بی‌نهایت هستند، این روش به ندرت برای استخراج نتایج کلی ریاضی استفاده می‌شود.

مثال

برای اثبات اینکه «اگر یک عدد صحیح، مکعب کامل باشد، آنگاه مضربی از ۹، یک واحد بیشتر از مضرب ۹، یا یک واحد کمتر از مضرب ۹ می‌باشد» می‌توان از اثبات با بررسی حالت‌ها استفاده کرد.

اثبات: هر عدد صحیح مکعب کامل به‌صورت $n^{3}$ که $n$ عددی صحیح است، نوشته می‌شود. سه حالت زیر برای $n$ وجود دارد:

• حالت اول: اگر $n=3p$، آنگاه $n^{3}=27p^{3}$ که مضربی از ۹ است.
• حالت دوم: اگر $n=3p+1$، آنگاه $n^{3}=27p^{3}+27p^{2}+9p+1$ که یک واحد بیشتر از مضربی از ۹ است.
• حالت سوم: اگر $n=3p-1$، آنگاه $n^{3}=27p^{3}-27p^{2}+9p-1$ که یک واحد کمتر از مضربی از ۹ است.

چون درستی گزاره برای هر سه حالت ممکن اثبات شد، پس گزاره به‌طور کلی درست است. $\blacksquare$

ظرافت

ریاضی‌دانان ترجیح می‌دهند از اثبات‌هایی که از طریق بررسی تعداد زیادی از حالت‌ها گزارهٔ مورد نظر را به اثبات می‌رسانند (که به‌عنوان بی‌ظرافت تلقی می‌شوند)، اجتناب کنند. مثالی در مورد اینکه چگونه چنین اثبات‌هایی ممکن است بی‌ظرافت باشند، نگاهی به اثبات زیر است که نشان می‌دهد که همهٔ بازی‌های المپیک تابستانی مدرن در سال‌هایی برگزار می‌شوند که بر ۴ بخش‌پذیرند:

اثبات: اولین بازی‌های المپیک تابستانی مدرن در سال ۱۸۹۶ برگزار شد و پس از آن هر ۴ سال یک‌بار (با نادیده گرفتن استثناهایی مانند زمانی که بازی‌ها به دلیل جنگ جهانی اول و دوم برگزار نشد و در المپیک ۲۰۲۰ توکیو به دلیل دنیاگیری کووید-۱۹ به ۲۰۲۱ به تعویق افتاد). از آنجایی که $1896=474\cdot 4$ بر ۴ بخش‌پذیر است، المپیک بعدی در سال $474\cdot 4+4=(474+1)\cdot 4$ است که بر چهار نیز بخش‌پذیر است و به همین ترتیب (این یک اثبات با استقرای ریاضی است). بنابراین گزاره ثابت می‌شود.

این گزاره را نیز می‌توان با بررسی حالت‌ها با فهرست هر سالی که بازی‌های المپیک تابستانی در آن برگزار شد، اثبات کرد و بخش‌پذیری هر یک از آن‌ها را بر ۴ بررسی کرد. با مجموع ۲۸ بازی المپیک تابستانی تا سال ۲۰۱۶، این نشان از بررسی ۲۸ حالت برای اثبات گزاره است.

علاوه بر ظرافت کمتر، هر بار که بازی‌های المپیک تابستانی جدید برگزار می‌شود، اثبات با بررسی حالت‌ها نیز به یک حالت اضافی نیاز دارد اما استقرای ریاضی، این گزاره را در حالت کلی ثابت می‌کند.

تعداد حالت‌ها

هیچ محدودیتی برای تعداد حالت‌های مجاز در این نوع از اثبات وجود ندارد. گاهی اوقات فقط دو یا سه حالت وجود دارد و گاهی ممکن است هزاران یا حتی میلیون‌ها حالت وجود داشته باشد! برای مثال، حل دقیق یک پازل پایان بازی شطرنج، ممکن است شامل در نظر گرفتن تعداد بسیار زیادی موقعیت ممکن در درخت بازی آن مشکل باشد.

اولین اثبات قضیهٔ چهار رنگ، اثبات با بررسی حالت‌ها با ۱۸۳۴ حالت بود. این اثبات بحث‌برانگیز بود؛ زیرا اکثر حالت‌ها توسط یک برنامهٔ کامپیوتری بررسی می‌شد، نه با دست. کوتاه‌ترین اثبات شناخته شدهٔ قضیهٔ چهار رنگ، امروزه هنوز بیش از ۶۰۰ مورد دارد.

به‌طور کلی، احتمال خطا در کل اثبات با افزایش تعداد حالت‌ها افزایش می‌یابد. اثباتی با تعداد حالت‌های زیاد این تصور را به‌جای می‌گذارد که قضیه فقط از روی تصادف صادق است و نه به دلیل برخی از اصول یا پیوندهای اساسی. انواع دیگر اثبات‌ها - مانند استقرای ریاضی - زیباتر در نظر گرفته می‌شوند. با این حال، برخی از قضایای مهم وجود دارند که هیچ روش اثبات دیگری برای آن‌ها یافت نشده‌است، مانند:

• اثبات اینکه صفحه نمایشی محدود از مرتبهٔ ۱۰ وجود ندارد.
• طبقه‌بندی گروه‌های سادهٔ محدود
• حدس کپلر
• مسئلهٔ سه گانهٔ فیثاغورث بولی

جستارهای وابسته

• استقرا
• استقرای ریاضی
• برهان خلف