جلسهی 29: برهانِ خلف Proof by Contradiction
فرض کن ادعا غلط است و ببین به چیزِ غیرممکنی میرسی. اگر رسیدی، ادعا درست است. عددهای اولِ بیشمار، زوج بودنِ n از زوج بودنِ n²، و دو نفر با تعدادِ دوستِ برابر.
در این جلسه یاد میگیری
- یک اثباتِ خلف را با «فرض کنید چنین نباشد…» شروع میکنی.
- تناقض را دقیق نشان میدهی و نتیجه میگیری.
- لانهی کبوتری را به شکلِ برهانِ خلف مینویسی.
درس
برهانِ خلف: برای ثابت کردنِ P، فرض کن P غلط است. قدمبهقدم جلو برو تا به چیزی برسی که نمیشود (تناقض)، مثلاً «عددی هم زوج است هم فرد» یا «۵ < ۴». چون فرضِ تو به تناقض رسید، فرض غلط بوده و P درست است.
مثال: «بزرگترین عددِ طبیعی وجود ندارد.» فرض کن N بزرگترین باشد. ولی N + ۱ هم طبیعی است و از N بزرگتر: تناقض.
عددهای اول بیشمارند (اقلیدس، بیش از دو هزار سال پیش): فرض کن فقط تعدادِ محدودی عددِ اول هست: p₁، p₂، …، pₖ. عددِ M = p₁ × p₂ × … × pₖ + ۱ را بساز. M بر هیچکدام از pها بخشپذیر نیست (باقیماندهی ۱ میدهد). ولی هر عددِ بزرگتر از ۱ یک مقسومعلیهِ اول دارد؛ پس M یک مقسومعلیهِ اولِ تازه دارد که در فهرست نیست: تناقض.
لانهی کبوتری همان برهانِ خلف است: «اگر هیچ لانهای دو کبوتر نداشت، حداکثر k کبوتر جا میشد؛ ولی k + ۱ کبوتر داریم: تناقض.»
اشتباه رایج: فرض را برعکس نکردن. خلافِ «همهی …ها زوجاند» این است که «دستکم یکی فرد است»، نه اینکه «همه فردند».
چالشها
- The First Line (آسان)
- Negating Correctly (آسان)
- If n Squared Is Even (متوسط)
- Euclid's Primes (متوسط)
- Same Number of Friends (سخت)
- Five Points in a Square (سخت)
← جلسهی 28: اثبات یعنی چه؟ جلسهی 30: نوشتنِ اثباتِ استقرایی →