مقدمه
در بسیاری از مسائل ریاضی، رسیدن مستقیم از فرض مسئله به نتیجه ساده‌ترین مسیر نیست. گاهی یک گزاره بسته به وضعیت متغیرها، علامت عبارت‌ها، زوج یا فرد بودن اعداد، یا باقی‌مانده حاصل از تقسیم، رفتارهای متفاوتی دارد. در چنین شرایطی می‌توان مسئله را به چند حالت تقسیم کرد و هر حالت را جداگانه بررسی کرد.
این روش اثبات با تفکیک حالات نام دارد. ایده اصلی آن ساده است: اگر بتوانیم نشان دهیم همه حالت‌های ممکن در مجموعه‌ای از حالت‌ها قرار می‌گیرند و گزاره موردنظر در هر یک از آن حالت‌ها درست است، آنگاه گزاره در حالت کلی نیز درست خواهد بود.
در منابع دانشگاهی، اثبات با تفکیک حالات به‌عنوان یکی از روش‌های استاندارد اثبات معرفی می‌شود. در این روش، حالت‌ها باید همه امکانات ممکن را پوشش دهند و استدلال در هر حالت به نتیجه موردنظر منتهی شود. این روش در درس‌های مبانی ریاضیات، منطق، ریاضیات گسسته و دوره‌های آموزش روش‌های اثبات کاربرد گسترده‌ای دارد.
برای آشنایی با جایگاه این روش در مباحث بنیادی ریاضیات، می‌توانید به مبانی ریاضیات مراجعه کنید.
پیش‌نیازهای اثبات با تفکیک حالات
برای استفاده از این روش، آشنایی با مفهوم گزاره و استدلال منطقی کافی است. همچنین باید بتوانیم مجموعه‌ای از حالت‌ها را به‌گونه‌ای انتخاب کنیم که دست‌کم یکی از آن‌ها برای هر وضعیت ممکن برقرار باشد.
اگر \(P\) گزاره‌ای باشد، ممکن است بتوانیم آن را به چند حالت \(C_1,C_2,\ldots,C_n\) تقسیم کنیم، به‌گونه‌ای که:
$$ C_1\lor C_2\lor\cdots\lor C_n $$
همیشه درست باشد. در این صورت، اگر نشان دهیم:
$$ C_1\rightarrow P,\quad C_2\rightarrow P,\quad \ldots,\quad C_n\rightarrow P $$
می‌توان نتیجه گرفت که \(P\) درست است.
برای مطالعه بیشتر درباره مفاهیم منطقی مورد استفاده در این استدلال، موضوعات گزاره، عطف و فصل و شرطی و دوشرطی مرتبط هستند.
تعریف دقیق اثبات با تفکیک حالات
فرض کنید می‌خواهیم گزاره \(P\) را ثابت کنیم و می‌دانیم یکی از حالت‌های \(C_1,C_2,\ldots,C_n\) باید برقرار باشد. اگر برای هر \(i\) نشان دهیم:
$$ C_i\rightarrow P $$
و همچنین ثابت باشد که:
$$ C_1\lor C_2\lor\cdots\lor C_n $$
آنگاه می‌توان نتیجه گرفت:
$$ P $$
بنابراین ساختار عمومی اثبات با تفکیک حالات را می‌توان چنین خلاصه کرد:
$$ \left(C_1\lor C_2\lor\cdots\lor C_n\right) \land \bigwedge_{i=1}^{n}(C_i\rightarrow P) \;\Longrightarrow\; P $$
به زبان ساده، ابتدا نشان می‌دهیم که حالت‌های انتخاب‌شده تمام امکانات را پوشش می‌دهند؛ سپس در هر حالت، گزاره موردنظر را ثابت می‌کنیم.
ایده شهودی
فرض کنید می‌خواهیم وارد ساختمانی شویم و می‌دانیم تنها سه درِ ممکن وجود دارد: درِ اول، درِ دوم و درِ سوم. اگر نشان دهیم از هر سه در می‌توان به مقصد رسید، بدون اینکه بدانیم دقیقاً کدام در مورد استفاده قرار می‌گیرد، می‌توانیم نتیجه بگیریم که در هر حالت به مقصد خواهیم رسید.
در ریاضیات نیز همین ایده وجود دارد. لازم نیست یک استدلال واحد برای همه وضعیت‌ها پیدا کنیم؛ می‌توانیم وضعیت‌های ممکن را جدا کنیم و در هر کدام استدلال مناسبی ارائه دهیم.
شرط اساسی: پوشش همه حالت‌های ممکن
مهم‌ترین شرط در اثبات با تفکیک حالات این است که حالت‌ها باید تمام امکانات مسئله را پوشش دهند. اگر حتی یک حالت ممکن از قلم بیفتد، نتیجه فقط برای حالت‌های بررسی‌شده ثابت شده است، نه برای کل مسئله.
برای مثال، هر عدد صحیح یا زوج است یا فرد. بنابراین دو حالت زیر همه اعداد صحیح را پوشش می‌دهند:
$$ n\text{ زوج}\quad\lor\quad n\text{ فرد} $$
در نتیجه، اگر گزاره‌ای را برای همه اعداد صحیح می‌خواهیم ثابت کنیم، می‌توانیم دو حالت «\(n\) زوج» و «\(n\) فرد» را بررسی کنیم.
همین ایده را می‌توان برای باقی‌مانده تقسیم بر یک عدد مثبت نیز به کار برد. اگر \(n\) را بر \(m\) تقسیم کنیم، با توجه به الگوریتم تقسیم، یک عدد صحیح \(q\) و یک باقی‌مانده \(r\) وجود دارند که:
$$ n=mq+r $$
و:
$$ 0\leq r