Çelişki ile İspat

Çelişki ile ispat, sevilen bir ispat tekniğidir. Bir önermenin doğru olduğunu göstermek istiyorsak önce onun değilini alırız, bu değilin doğru olduğunu varsayarız ve bir çelişkiye ulaşmaya çalışırız. Amaç, seçtiğimiz varsayımın saçma bir sonuca yol açtığını göstermektir.

Basit Bir Örnek

“En küçük pozitif rasyonel sayı yoktur” önermesini ele alalım. Bu önermeyi çelişki ile ispatlamak için önce değilini alırız: “en küçük pozitif rasyonel sayı vardır” ve bu sayıya q diyelim. q en küçük pozitif rasyonel sayı ise ondan daha küçük bir pozitif rasyonel sayı bulamayız — çünkü bulabilseydik q en küçük olmazdı.

Çelişkiyi bulmak için bundan yararlanacağız. q sayısını istediğimiz gibi seçebiliriz. Eğer ondan daha küçük bir sayı bulursak çelişkiye ulaşmış oluruz ve değili alınmış önerme doğru olamaz. En küçük sayı olarak örneğin 0,1’i seçtiysek 0,01’in daha küçük olduğunu görürüz. 0,001 daha da küçüktür, 0,0001 yine daha küçüktür ve böyle devam eder. q sayısını ona bölmek yeterlidir, daha küçük bir sayı elde ederiz. Aslında 1’den büyük herhangi bir sayıya bölmek yeter, örneğin 2’ye — q sayısının yarısı elbette q sayısının kendisinden küçüktür.

Demek ki q/2 sayısı q sayısından küçüktür ve aynı zamanda pozitif bir rasyonel sayıdır. Böylece değili alınmış önermeyle çelişkiye ulaştık; yani değili alınmış önerme doğru değildir, dolayısıyla değili alınmamış ilk önerme doğrudur.

İlginç Sayılar

Çelişki ilkesini gösteren klasik, esprili bir ispat şudur. Bir şekilde ilginç olan pozitif tam sayıların bulunduğunu varsayalım. Örneğin 2 sayısı ilginçtir, çünkü 2 · 2 = 2 + 2 eşitliği sağlanır ve bu oldukça alışılmadık bir özelliktir. 42 sayısı ilginçtir, çünkü o her şeyin cevabıdır. Ve böyle devam eder. Soru şu — sonsuz çoklukta ilginç sayı var mıdır?

Tersini varsayalım: yalnızca sonlu sayıda ilginç sayı olsun ve bazı sayılar ilginç olmasın. İlginç olmayan bu pozitif tam sayıları ilginç olmayan sayılar kümesinde toplayalım. Şimdi en küçük ilginç olmayan sayıyı seçelim. Dur bakalım, en küçük ilginç olmayan sayı mı? Bu epey ilginç geliyor, değil mi? :-)

Böylece çelişkiye ulaştık, çünkü en küçük ilginç olmayan sayı aslında oldukça ilginçtir. Demek ki en küçük ilginç olmayan sayı var olamaz, dolayısıyla ilginç olmayan sayılar kümesi mutlaka boş olmalıdır.

Bu elbette saçmalıktır, çünkü ilginç sayının ne olduğunu düzgünce tanımlamadık. Ama ispatın izlediği yol kendi içinde doğrudur.

Asal Sayıların Sonsuzluğunun İspatı

Bu örnekte bir önceki bölümdekine benzer bir yol izleyeceğiz, ama bu kez her bakımdan doğru olacak.

Asal sayı, yalnızca iki farklı sayıya bölünebilen sayıdır — kendisine ve bire. Dikkat et: 1 bu tanıma uymaz, 2 ise uyar.

Asal çarpanlara ayırma, kısaca çarpanlara ayırma, 1 dışındaki bir pozitif tam sayının asal sayıların çarpımı olarak yazılmasıdır. Bu, pozitif tam sayıların oldukça ilginç bir özelliğidir. 1 dışında hangi pozitif tam sayıyı alırsan al, onu birkaç (aynı da olabilen) asal sayının çarpımı olarak yazabilirsin. Örnekler:

$$\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}$$

Asal çarpanlara ayırma hakkındaki bu önermeye Aritmetiğin Temel Teoremi denir. Bu teorem bize, diğer şeylerin yanı sıra, böyle bir ayrılışın tek olduğunu söyler: bir pozitif tam sayının iki farklı asal çarpanlara ayrılışını bulamayız. Ayrıca yalnızca asal sayıların asal çarpanlara ayrılışı tek bir sayıdan oluşur — kendilerinden. Yani 7’nin asal çarpanlara ayrılışı yalnızca 7 sayısıdır. Bu gerçeklerden, aşağıdaki önermenin ispatını kurarken yararlanacağız.

Şimdi “asal sayılar sonsuz çoklukta vardır” önermesini ispatlayalım. Önermenin değilini yine alalım: “asal sayıların sayısı sonludur”. Bütün asal sayıları

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

dizisinin oluşturduğunu varsayalım. Bu dizide bütün asal sayılar varsa, hem asal olan hem de bu dizide bulunmayan bir sayı bulamayız. Bütün asal sayılar dizidedir, dizinin dışında artık hiçbir asal sayı bulunmamalıdır.

Çelişkiye ulaşmak istiyorsak bu dizide olmayan bir asal sayı oluşturmamız gerekir. Bunun için q sayısından yararlanacağız. Onu şöyle oluştururuz: dizideki bütün asal sayıları çarpar ve 1 ekleriz:

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

Şimdi bu sayının ya asal olduğunu ya da bir şekilde asal sayı ürettiğini göstermeliyiz. q sayısının bir pozitif tam sayı olduğunu ve her pozitif tam sayının asal sayıların çarpımı olarak yazılabildiğini biliyoruz. Ancak hiçbir a_i asal sayısı q sayısını kalansız bölmez, bölmeden hep 1 kalır. q sayısını örneğin a₂ asal sayısına bölmeye çalışsaydık şöyle olurdu:

$$\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}$$

Önce kesri ikiye ayırırız. İlk kesirde a₂ sadeleşir ve geriye bir asal sayı çarpımı kalır, bu da önemsiz, başka bir tam sayıdır. İkinci kesirde sadeleşecek bir şey yoktur, bu kesir her zaman tam sayı olmayan bir sayı olacaktır (çünkü payda 1 olamaz, 1 asal sayı değildir). Toplamda tam sayı olmayan bir sayı elde ederiz, yani a₂ asal sayısı q sayısını bölmez.

Böylece a_n dizisindeki asal sayıların hiçbirinin q sayısını bölmediğini ispatlamış olduk. (Not: bunu yalnızca a₂ için gösterdik, ama a₂ yerine genel bir a_i yazarsak kolayca genelleştirilebilir.) Fakat her pozitif tam sayı asal sayıların çarpımına ayrılabildiği için a_n dizisinde bulunmayan, ama q sayısının asal çarpanlara ayrılışında yer alan başka asal sayılar olmalıdır. Üstelik q sayısının kendisi de asal olabilir ve bu durumda asal çarpanlara ayrılış yalnızca q sayısını içerir. Şimdi düşünce zincirini son bir kez toparlayalım:

1. Her pozitif tam sayı, asal sayıların bir çarpımı olarak yazılabilir.
2. Varsayıma göre a_n dizisi var olan bütün asal sayıları içerir.
3. İlk önermeyi şöyle değiştiririz: her pozitif tam sayı, a_n dizisinin seçilmiş terimlerinin çarpımı olarak yazılabilir, çünkü bu dizi bütün asal sayıları içerir.
4. a_n dizisindeki sayıların hiçbirinin q sayısını bölmediğini ispatladık.
5. Böylece varsayımla çelişki oluştu → her pozitif tam sayıyı asal sayıların çarpımına ayırabilmemiz gerekiyorsa ve a_n dizisi q sayısını bölen hiçbir sayı içermiyorsa, o zaman q sayısını bölen ve q sayısının asal çarpanlara ayrılışında yer alan başka asal sayılar olmalıdır.

Bununla çelişkiye ulaştık. q sayısının asal çarpanlara ayrılışı, bütün asal sayıları içerdiğini varsaydığımız dizide bulunmayan asal sayılar içeriyor. Demek ki değili alınmış önerme doğru değildir, değili alınmamış ilk önerme doğrudur. Asal sayılar sonsuz çoklukta vardır.