Доказателство от противното

Доказателството от противното е популярна техника за доказване. Ако искаме да докажем, че някое съждение е в сила, го отричаме, предполагаме, че неговото отрицание е вярно, и се опитваме да стигнем до някакво противоречие. Целта е да докажем, че избраното от нас предположение води до някаква безсмислица.

Тривиален пример

Нека имаме твърдението „не съществува най-малко положително рационално число“. Това твърдение доказваме от противното така, че първо го отричаме: „съществува най-малко положително рационално число“ и означаваме това число с q. Ако q е най-малкото положително рационално число, то не можем да намерим по-малко положително рационално число – защото тогава числото q не би било най-малкото.

Това ще използваме при търсенето на противоречие. Ако все пак намерим число, което е по-малко от q, което можем да изберем произволно, значи сме стигнали до противоречие и отреченото съждение не е в сила. Ако за най-малко число изберем например 0,1, виждаме, че числото 0,01 е по-малко. След това 0,001 е още по-малко, 0,0001 е пак по-малко и така нататък. Достатъчно е да разделим даденото число q на десет и получаваме по-малко число. По принцип е достатъчно да го разделим на което и да е число, по-голямо от едно, например на две – половината на числото q със сигурност ще е по-малка от цялото число q.

Тоест числото q/2 със сигурност е по-малко от q и същевременно е положително рационално число. Така стигнахме до противоречие с отреченото твърдение, тоест отреченото твърдение не е в сила и следователно е в сила първоначалното неотречено твърдение.

Интересни числа

Класически забавен пример, който илюстрира принципа на противоречието, е следният. Нека предположим, че съществуват естествени числа, които по някакъв начин са интересни. Например числото 2 е интересно, защото е в сила 2 · 2 = 2 + 2, това е доста нетипично свойство. Числото 42 е интересно, защото е отговорът на всичко. И така нататък. Въпросът е: съществуват ли безброй много интересни числа?

Нека предположим обратното, тоест че съществуват само краен брой интересни числа и някои числа са неинтересни. Тези неинтересни естествени числа събираме в множество от неинтересни числа. Сега избираме най-малкото неинтересно число. Момент, най-малкото неинтересно число? Това звучи доста интересно, нали? :-)

Така стигнахме до противоречие, защото най-малкото неинтересно число всъщност е доста интересно, тоест не може да съществува най-малко неинтересно число, следователно множеството от неинтересни числа непременно трябва да е празно.

Това, разбира се, е безсмислица, не сме определили както трябва какво е интересно число, но самият начин на доказване е в ред.

Доказателство, че простите числа са безброй много

В този пример ще покажем подобен подход като в предишния раздел, но този път вече ще е правилно от всякаква гледна точка.

Просто число е число, което се дели само на две различни числа – на себе си и на единица. Забележи, че единицата не отговаря на определението, а числото 2 отговаря.

Разлагането на прости множители, или факторизацията, е разлагане на естествено число, различно от единица, на произведение на прости числа. Това е доста интересно свойство на естествените числа. Което и да е естествено число да вземеш (освен единицата), то може да се разложи на произведение на няколко (и еднакви) прости числа. Примери:

$$\begin{array}{rcl}8& =& 2\cdot 2\cdot 2\\ 15& =& 3\cdot 5\\ 26& =& 2\cdot 13\\ 1800& =& 2^3\cdot 3^2\cdot 5^2\end{array}$$

Твърдението за разлагането на прости множители се нарича основна теорема на аритметиката. Освен всичко друго ни казва, че такова разлагане е единствено, тоест не можем да намерим две различни разлагания на прости множители на едно естествено число. Освен това само простите числа имат разлагане на прости множители, образувано от едно-единствено число – от самите тях. Тоест разлагането на седем на прости множители би било числото седем. Тези факти ще използваме при построяването на доказателството на следното твърдение.

Сега ще докажем твърдението, че „простите числа са безброй много“. Отново отричаме твърдението: „простите числа са краен брой“. Нека предположим, че редицата от числа

$$a_1,a_2,a_3,\dots ,a_n$$

представлява всички съществуващи прости числа. Ако в тази редица са всички прости числа, то със сигурност вече няма да можем да намерим число, което да е просто и същевременно да не е в тази редица. Всички прости числа са в редицата, извън редицата вече не бива да се среща никое просто число.

Ако искаме да стигнем до противоречие, трябва да съставим някакво просто число, което не е в тази редица. За това ще ни помогне числото q. Съставяме го, като умножим всички прости числа в редицата и прибавим единица:

$$q=a_1\cdot a_2\cdot a_3\cdot \dots \cdot a_n+1$$

Сега трябва да покажем, че това число или е просто, или по някакъв начин поражда просто число. Знаем, че q е естествено число и че всяко естествено число може да се изрази като произведение на прости числа. Никое просто число a_i обаче не дели без остатък числото q, винаги след делението остава единица. Ако се опитаме да разделим числото q например на простото число a₂, ще се получи така:

$$\frac{a_1\cdot a_2\cdot a_3\cdot \dots \cdot a_n+1}{a_2}=\frac{a_1\cdot a_2\cdot a_3\cdot \dots \cdot a_n}{a_2}+\frac{1}{a_2}=$$

$$=a_1\cdot a_3\cdot a_4\cdot \dots \cdot a_n+\frac{1}{a_2}$$

Първо разделяме дробта на две. В първата дроб съкращаваме a₂ и остава някакво произведение на прости числа, което е просто някакво друго маловажно цяло число. Във втората дроб няма какво да се съкрати, тази дроб винаги ще е някакво нецяло число (защото знаменателят не може да е едно, единицата не е просто число). В сбора следователно получаваме число, което не е цяло, тоест простото число a₂ не дели числото q.

С това доказахме, че никое от простите числа от редицата a_n не дели числото q. (Забележка: показахме го само за a₂, но лесно може да се обобщи, ако заменим a₂ с общо a_i.) Но тъй като всяко естествено число може да се разложи на произведение на прости числа, трябва да съществуват други прости числа, които не са в редицата a_n, но са във факторизацията на числото q. При това самото число q може спокойно да е просто и тогава разлагането на прости множители ще включва само числото q. Така че още веднъж последният ход на мисълта:

1. Всяко естествено число може да се изрази като някакво произведение на прости числа.
2. Според предположението редицата a_n съдържа всички съществуващи прости числа.
3. Преобразуваме първото твърдение така, че всяко естествено число може да се изрази като произведение на избрани членове на редицата a_n, защото тя съдържа всички прости числа.
4. Доказахме, че никое число от редицата a_n не дели числото q.
5. Така възниква противоречие с предположението → ако трябва да можем да разложим всяко естествено число на произведение на прости числа и редицата a_n не съдържа никое число, което дели q, то трябва да съществуват други прости числа, които делят q и са разлагането на числото q на прости множители.

С това стигнахме до противоречие. Разлагането на числото q на прости множители включва прости числа, които не се съдържат в редицата, за която предположихме, че съдържа всички прости числа. Тоест не е в сила отреченото твърдение, в сила е първоначалното неотречено твърдение. Простите числа са безброй много.