2 Niceleyiciler ve İspat Yöntemleri

Önceki bölümde önermeleri bağlaçlarla birleştirmeyi öğrendik. Ne var ki analizdeki cümlelerin neredeyse hiçbiri “\(2 + 2 = 4\)” gibi tek bir yargı değildir; “her \(\varepsilon > 0\) için öyle bir \(N\) vardır ki …” biçimindedir. Bu cümleleri kesin olarak yazabilmek ve özellikle olumsuzlayabilmek için iki yeni sembole ihtiyacımız var: “her” anlamındaki \(\forall\) ve “vardır” anlamındaki \(\exists\).

Bölümün ikinci yarısında matematiğin asıl işine, teorem ispatlamaya geçiyoruz. Doğrudan ispat, karşıt tersle ispat, olmayana ergi, iki yönlü ispat, karşıt örnekle çürütme ve durumlara ayırma yöntemlerinin her birini önce mantıksal olarak gerekçelendirip sonra örneklerle uygulayacağız. Bu bölümden sonra kitaptaki her ispat, burada adı konan kalıplardan birine ya da birkaçına oturacaktır.

2.1 Açık Önermeler ve Niceleyiciler

“\(x > 4\)” ifadesini düşünelim. Bu, tek başına bir önerme değildir; doğruluğu \(x\)’in değerine bağlıdır. \(x = 5\) alırsak “\(5 > 4\)” doğru, \(x = 2\) alırsak “\(2 > 4\)” yanlış bir önermedir. Üstelik ifadenin anlamlı olması için \(x\)’in hangi kümeden seçildiğini de söylemek gerekir: \(x\) bir reel sayı mı, bir doğal sayı mı?

Tanım 2.1 (Açık Önerme) İçinde bir ya da daha çok değişken bulunan ve değişkenlere belirli bir \(X\) kümesinden (evren kümesi) değer verildiğinde bir önermeye dönüşen ifadeye açık önerme (predicate, open sentence) denir. Değişkeni \(x\) olan bir açık önerme \(p(x)\), değişkenleri \(x, y\) olan bir açık önerme \(p(x, y)\) ile gösterilir.

Örneğin \(p(x)\): “\(x > 4\)” ifadesi, evren kümesi \(\mathbb{R}\) olan bir açık önermedir; \(p(5)\) doğru, \(p(2)\) yanlış bir önermedir. \(q(n)\): “\(n\) asaldır” ifadesi, evren kümesi \(\mathbb{N}\) olan bir açık önermedir; \(q(7)\) doğru, \(q(8)\) yanlıştır.

Bir açık önermeyi önermeye çevirmenin iki yolu vardır: ya değişkene somut bir değer veririz ya da “bütün \(x\)’ler için” veya “en az bir \(x\) için” diyerek değişkeni niceleriz. İkinci yol için kullanılan sembollere niceleyici denir.

Tanım 2.2 (Tümel ve Varlıksal Niceleyici) \(p(x)\), evren kümesi \(X\) olan bir açık önerme olsun.

Tümel niceleyici (universal quantifier) \(\forall\): “\(\forall x \in X,\ p(x)\)” önermesi, “\(X\)’in her \(x\) elemanı için \(p(x)\) doğrudur” anlamına gelir. Bu önerme ancak ve ancak \(X\)’in bütün elemanları \(p\) özelliğini sağlıyorsa doğrudur; özelliği sağlamayan tek bir eleman bile varsa yanlıştır. “Her \(x\) için”, “bütün \(x\)’ler için”, “keyfi bir \(x\) için” diye okunur.
Varlıksal niceleyici (existential quantifier) \(\exists\): “\(\exists x \in X,\ p(x)\)” önermesi, “\(X\)’te \(p(x)\)’i doğru yapan en az bir \(x\) elemanı vardır” anlamına gelir. Bu önerme ancak ve ancak \(X\)’in en az bir elemanı \(p\) özelliğini sağlıyorsa doğrudur. “Öyle bir \(x\) vardır ki”, “bazı \(x\)’ler için”, “en az bir \(x\) için” diye okunur.
Teklik niceleyicisi \(\exists!\): “\(\exists!\, x \in X,\ p(x)\)” önermesi, “\(p(x)\)’i doğru yapan tam olarak bir \(x \in X\) vardır” anlamına gelir.

Tanımdaki farkı bir kez daha vurgulayalım: \(\forall x \in X,\ p(x)\) için özelliğin herkeste olması gerekir; \(\exists x \in X,\ p(x)\) için birinde olması yeter. Şu örnekleri inceleyelim:

\(\forall x \in \mathbb{R},\ x^2 \ge 0\): “Her reel sayının karesi sıfırdan büyük ya da sıfıra eşittir.” Hangi reel sayıyı seçersek seçelim karesi negatif olmadığından bu önerme doğrudur.
\(\forall x \in \mathbb{R},\ x^2 > 0\): Yanlıştır, çünkü \(x = 0\) için \(0^2 > 0\) sağlanmaz. Tek bir istisna tümel önermeyi yanlış yapar.
\(\exists x \in \mathbb{R},\ x^2 = 2\): Doğrudur; \(x = \sqrt{2}\) böyle bir sayıdır. (Böyle bir reel sayının gerçekten var olduğunu ileride aksiyomlardan ispatlayacağız: Teorem 13.1.)
\(\exists x \in \mathbb{R},\ x^2 = -1\): Yanlıştır; hiçbir reel sayının karesi negatif değildir.
\(\forall n \in \mathbb{N},\ n \ge 1\): Doğrudur.
\(\exists!\, x \in \mathbb{R},\ 2x + 1 = 7\): Doğrudur; denklemi sağlayan tek reel sayı \(x = 3\)’tür.
\(\exists!\, x \in \mathbb{R},\ x^2 = 4\): Yanlıştır; \(x = 2\) ve \(x = -2\) olmak üzere iki çözüm vardır. \(\exists x \in \mathbb{R},\ x^2 = 4\) ise doğrudur.

Teklik niceleyicisi diğer ikisiyle yazılabilir

“Tam olarak bir \(x\) vardır” demek, “en az bir \(x\) vardır ve özelliği sağlayan her \(y\), bu \(x\)’e eşittir” demektir:

\[\exists!\, x \in X,\ p(x) \quad\equiv\quad \exists x \in X,\ \big[p(x) \wedge \forall y \in X,\ (p(y) \Rightarrow y = x)\big].\]

Bu yüzden bir “teklik” teoremi (limitin tekliği, supremumun tekliği gibi) her zaman iki adımda ispatlanır: önce varlık, sonra teklik. Teklik için de standart yol, özelliği sağlayan iki aday \(x\) ve \(y\) alıp \(x = y\) olmak zorunda olduğunu göstermektir.

Niceleyiciler, aslında “ve” ile “veya” bağlaçlarının sonsuz kümelere genellenmesidir. Evren kümesi sonlu, diyelim \(X = \{x_1, x_2, \dots, x_n\}\) ise

\[\forall x \in X,\ p(x) \ \equiv\ p(x_1) \wedge p(x_2) \wedge \dots \wedge p(x_n), \qquad \exists x \in X,\ p(x) \ \equiv\ p(x_1) \vee p(x_2) \vee \dots \vee p(x_n).\]

Bu gözlem, niceleyicilerin olumsuzlama kuralının neden De Morgan yasalarına bu kadar benzediğini açıklar.

2.2 Niceleyicilerin Olumsuzlanması

“Herkes sınavı geçti” cümlesinin yanlış olması için ne gerekir? Herkesin kalması değil; bir kişinin kalması yeter. “Birisi sınavı geçti” cümlesinin yanlış olması içinse herkesin kalmış olması gerekir. Kural budur: niceleyiciyi çevir, içerideki önermeyi olumsuzla.

Teorem 2.1 (Niceleyicilerin Olumsuzlanması) \(p(x)\), evren kümesi \(X\) olan bir açık önerme olsun.

\(\neg\big(\forall x \in X,\ p(x)\big) \ \equiv\ \exists x \in X,\ \neg p(x)\).
\(\neg\big(\exists x \in X,\ p(x)\big) \ \equiv\ \forall x \in X,\ \neg p(x)\).

İspat

(1) İki önermenin tam olarak aynı koşulda doğru olduğunu gösterelim; bu, doğruluk tablolarının aynı olması demektir.

\(\neg(\forall x \in X,\ p(x))\) önermesi doğrudur \(\Leftrightarrow\) \(\forall x \in X,\ p(x)\) önermesi yanlıştır (Tanım 1.2) \(\Leftrightarrow\) “\(X\)’in bütün elemanları \(p\) özelliğini sağlar” iddiası doğru değildir, yani \(p(x)\)’in yanlış olduğu en az bir \(x \in X\) vardır (Tanım 2.2, tümel niceleyicinin “tek istisna yeter” kuralı) \(\Leftrightarrow\) \(\neg p(x)\)’in doğru olduğu en az bir \(x \in X\) vardır \(\Leftrightarrow\) \(\exists x \in X,\ \neg p(x)\) önermesi doğrudur (Tanım 2.2, varlıksal niceleyici).

Zincirin her halkası bir “ancak ve ancak” olduğundan iki önerme birlikte doğru, birlikte yanlıştır; yani denktirler.

(2) Birinci kuralı \(q(x) = \neg p(x)\) açık önermesine uygulayalım:

\[\neg\big(\forall x \in X,\ \neg p(x)\big) \ \equiv\ \exists x \in X,\ \neg(\neg p(x)) \ \equiv\ \exists x \in X,\ p(x),\]

son adımda Önerme 1.1 kullanıldı. Denk iki önermenin olumsuzlamaları da denktir; her iki tarafı olumsuzlayıp sol tarafta tekrar çift olumsuzlama yasasını kullanırsak

\[\forall x \in X,\ \neg p(x) \ \equiv\ \neg\big(\exists x \in X,\ p(x)\big)\]

elde ederiz; bu da (2)’dir.

\(X\) sonlu olduğunda bu kuralların, \(\forall\)’yı \(\wedge\) zinciri ve \(\exists\)’yı \(\vee\) zinciri olarak yazıp Teorem 1.1 (6) De Morgan yasalarını uygulamaktan başka bir şey olmadığına dikkat edin.

\(\blacksquare\)

Teorem, analizdeki tanımların olumsuzlamalarını mekanik olarak yazmamızı sağlar; “yakınsak değil”, “sınırlı değil”, “sürekli değil” gibi ifadelerin ne demek olduğunu hep bu kuralla bulacağız. Birkaç örnek:

“Her öğrenci sınavı geçti.” önermesinin olumsuzlaması “Sınavı geçemeyen bir öğrenci vardır.” önermesidir.
“Bazı asal sayılar çifttir.” önermesinin olumsuzlaması “Hiçbir asal sayı çift değildir.” önermesidir.
\(\forall x \in \mathbb{R},\ x^2 > 0\) önermesinin olumsuzlaması \(\exists x \in \mathbb{R},\ x^2 \le 0\)’dır. Olumsuzlama doğrudur (\(x = 0\)), dolayısıyla özgün önerme yanlıştır.
\(\exists x \in \mathbb{R},\ x^2 = -1\) önermesinin olumsuzlaması \(\forall x \in \mathbb{R},\ x^2 \neq -1\)’dir; olumsuzlama doğru, özgün önerme yanlıştır.

Evren kümesi değişmez

Olumsuzlama alırken değişkenin evren kümesi (örneğin \(x \in \mathbb{N}\)) olduğu gibi kalır; işlem yalnızca niceleyiciyi ve içerideki önermeyi etkiler.

\(\forall x \in \mathbb{N},\ p(x)\) önermesinin olumsuzlaması \(\exists x \notin \mathbb{N},\ \dots\) değildir.
Doğrusu: \(\neg(\forall x \in \mathbb{N},\ p(x)) \equiv \exists x \in \mathbb{N},\ \neg p(x)\).

“\(\forall x \in \mathbb{N}\)” ifadesi, “\(x\) doğal sayıysa” koşulunu içerir; olumsuzlamada aradığımız istisna da yine bir doğal sayı olmalıdır.

Olumsuzlama kuralı, aynı zamanda ispat stratejilerimizi belirler.

Niceleyicili önermeler nasıl ispatlanır?

\(\forall x \in X,\ p(x)\) biçiminde bir önermeyi ispatlamak için: \(X\)’ten keyfi bir \(x\) alınır (“\(x \in X\) olsun”) ve bu \(x\) hakkında \(X\)’e ait olmasından başka hiçbir şey varsaymadan \(p(x)\)’in doğru olduğu gösterilir. \(x\) keyfi olduğundan sonuç bütün elemanlar için geçerlidir. Tek tek örnekler denemek ispat değildir; sonsuz kümede örnekler asla tükenmez.
\(\exists x \in X,\ p(x)\) biçiminde bir önermeyi ispatlamak için: \(p(x)\)’i sağlayan tek bir \(x \in X\) bulmak (ve gerçekten sağladığını doğrulamak) yeter. Buna varlık ispatı denir. Elemanı açıkça yazmak şart değildir; var olduğunu dolaylı yoldan göstermek de kabul edilir.
\(\forall x \in X,\ p(x)\) biçiminde bir önermeyi çürütmek için: Teorem 2.1 gereği \(\neg p(x)\)’i sağlayan tek bir \(x\) bulmak yeter; buna karşıt örnek denir.
\(\exists!\, x \in X,\ p(x)\) için: önce varlık, sonra teklik gösterilir.

Örnek 2.1 (Bir Varlık ve Bir Tümel İspat) Aşağıdaki önermelerin doğru olduğunu gösteriniz.

\(\exists x \in \mathbb{R},\ x > x^2\).
\(\forall x \in \mathbb{R},\ x^2 - 2x + 2 > 0\).

Çözüm

(1) Varlık ispatı: tek bir örnek yeter. \(x = \dfrac{1}{2}\) alalım. \(x^2 = \dfrac{1}{4}\) ve \(\dfrac{1}{2} > \dfrac{1}{4}\) olduğundan \(x > x^2\) sağlanır. Demek ki önerme doğrudur. (\(0\) ile \(1\) arasındaki her sayı işe yarar; ama bir tanesi yeter.)

(2) Tümel ispat: keyfi bir eleman alıp özelliği gösterelim. \(x \in \mathbb{R}\) keyfi olsun. Kareyi tamamlayalım:

\[x^2 - 2x + 2 = (x^2 - 2x + 1) + 1 = (x - 1)^2 + 1.\]

Bir reel sayının karesi negatif olamaz (bu okul bilgisini şimdilik kabul ediyoruz; sıralama aksiyomlarından ispatı Önerme 7.12’nde verilecek): \((x-1)^2 \ge 0\). Her iki tarafa \(1\) ekleyince \((x-1)^2 + 1 \ge 1 > 0\) bulunur. \(x\) keyfi olduğundan eşitsizlik her reel sayı için doğrudur.

Dikkat: (2)’de \(x = 0, 1, 2, 3\) için denklemi hesaplayıp “hep pozitif çıkıyor” demek ispat değildir; keyfi \(x\) ile yapılan hesap ispattır.

\(\blacksquare\)

2.3 İç İçe Niceleyiciler ve Sıranın Önemi

Analizdeki tanımlar çoğunlukla birden çok niceleyici içerir ve niceleyicilerin sırası anlamı tamamen değiştirebilir. \(p(x, y)\), \(x \in X\) ve \(y \in Y\) değişkenlerine bağlı bir açık önerme olsun. İki temel durum vardır.

Durum 1: \(\forall x \in X,\ \exists y \in Y,\ p(x, y)\). Anlamı: “Her \(x\) için, ona bağlı en az bir \(y\) vardır.” Burada \(y\)’nin seçimi \(x\)’e bağlıdır; \(x\) değişince \(y\) de değişebilir. Bu bağımlılığı vurgulamak için bazen \(y\) yerine \(y_x\) yazılır. Örnek: “Her insanın bir annesi vardır.” Anne (\(y\)), kişiye (\(x\)) göre değişir.

Durum 2: \(\exists y \in Y,\ \forall x \in X,\ p(x, y)\). Anlamı: “Bütün \(x\)’ler için aynı anda işe yarayan tek bir \(y\) vardır.” Burada \(y\), \(x\)’ten tamamen bağımsızdır; sabit bir \(y\) değeri, her \(x\) için \(p(x, y)\)’yi doğru yapar. Örnek: “Herkesin annesi olan tek bir insan vardır.” Bu önerme açıkça yanlıştır.

Sıra neden bu kadar önemli?

Aynı \(p(x, y)\) açık önermesi için Durum 1 doğru, Durum 2 yanlış olabilir. \(\forall\) ile \(\exists\)’nın yerini değiştirmek, “herkese uygun ayrı ayrı bir şey bulabilirim” iddiasını “herkese uyan tek bir şey var” iddiasına dönüştürür; ikincisi çok daha güçlü bir iddiadır. Genel olarak Durum 2, Durum 1’i gerektirir (herkese uyan tek \(y\) varsa her \(x\) için bir \(y\) vardır: hep o), ama tersi doğru değildir.

Solda ∀x ∃y: her x için ona uygun bir y seçilir ve seçim x'ten x'e değişebilir. Sağda ∃y ∀x: önce tek bir y sabitlenir ve bu y bütün x'ler için işe yarar. İkincisi birinciyi gerektirir; tersi doğru değildir.

Öte yandan aynı türden iki niceleyicinin sırası önemsizdir: \(\forall x\, \forall y\) ile \(\forall y\, \forall x\) aynı şeyi söyler, \(\exists x\, \exists y\) ile \(\exists y\, \exists x\) de öyle.

Analizden üç örnek, bu ayrımın ne kadar temel olduğunu gösterir:

\(\forall \varepsilon > 0,\ \exists N \in \mathbb{N},\ \forall n \ge N,\ |a_n - a| < \varepsilon\). Bu, “\((a_n)\) dizisi \(a\)’ya yakınsar” ifadesinin tanımıdır (Tanım 20.1). Her \(\varepsilon\) için ona bağlı bir \(N\) (çoğu zaman \(N_\varepsilon\) yazılır) bulunur; \(\varepsilon\) küçüldükçe \(N\) genellikle büyür. Sıra \(\exists N,\ \forall \varepsilon\) olsaydı, bütün \(\varepsilon\)’lar için tek bir \(N\) istenirdi; bu, \(N\)’den sonraki bütün terimlerin \(a\)’ya eşit olması demektir ve bambaşka, çok daha güçlü bir koşuldur.
\(\exists M > 0,\ \forall n \in \mathbb{N},\ |a_n| \le M\). Bu, “\((a_n)\) dizisi sınırlıdır” demektir (Tanım 19.3; sınırlılık orada üst ve alt sınırla tanımlanır, buradaki mutlak değerli biçime denkliği Önerme 19.1’de gösterilecek): dizinin bütün terimlerini birden bastıran tek bir \(M\) vardır; \(M\), \(n\)’den bağımsızdır. Sıra \(\forall n,\ \exists M\) olsaydı her terim için ayrı bir \(M\) seçebilirdik (\(M = |a_n| + 1\) gibi) ve önerme her dizi için doğru, yani içeriksiz olurdu.
\(\forall x \in \mathbb{N},\ \exists y \in \mathbb{N},\ 3y > x\): “Her doğal sayıdan büyük bir \(3\) katı vardır.” Doğrudur: \(x\) verilince \(y = x\) alınırsa \(3x > x\) olur. Sırası değiştirilmiş \(\exists y \in \mathbb{N},\ \forall x \in \mathbb{N},\ 3y > x\) önermesi ise “bütün doğal sayılardan büyük bir \(3\) katı vardır” der ve yanlıştır: \(y\) ne olursa olsun \(x = 3y\) için \(3y > 3y\) sağlanmaz.

İç içe niceleyicilerin olumsuzlanması için kural değişmez: Teorem 2.1 dıştan içe doğru art arda uygulanır.

Sonuç 2.1 (İç İçe Niceleyicilerin Olumsuzlanması) \(p(x, y)\), \(x \in X\) ve \(y \in Y\) değişkenli bir açık önerme olsun.

\(\neg\big(\forall x \in X,\ \exists y \in Y,\ p(x, y)\big) \ \equiv\ \exists x \in X,\ \forall y \in Y,\ \neg p(x, y)\).
\(\neg\big(\exists x \in X,\ \forall y \in Y,\ p(x, y)\big) \ \equiv\ \forall x \in X,\ \exists y \in Y,\ \neg p(x, y)\).

Genel kural: bütün niceleyiciler sırası korunarak çevrilir (\(\forall \leftrightarrow \exists\)), sondaki önerme olumsuzlanır.

İspat

(1) \(q(x)\) ile \(\exists y \in Y,\ p(x, y)\) açık önermesini gösterelim; olumsuzlanacak önerme \(\forall x \in X,\ q(x)\)’tir. Teorem 2.1 (1) ile

\[\neg\big(\forall x \in X,\ q(x)\big) \ \equiv\ \exists x \in X,\ \neg q(x).\]

Şimdi \(\neg q(x) = \neg(\exists y \in Y,\ p(x, y))\) ifadesine Teorem 2.1 (2)’yi uygulayalım: \(\neg q(x) \equiv \forall y \in Y,\ \neg p(x, y)\). Yerine yazınca (1) elde edilir.

(2) Aynı biçimde: önce dıştaki \(\exists\) için kural (2), sonra içteki \(\forall\) için kural (1) uygulanır.

\(\blacksquare\)

Örnek olarak yakınsaklık tanımını olumsuzlayalım; “\((a_n)\) dizisi \(a\)’ya yakınsamaz” ne demektir?

\[\neg\Big(\forall \varepsilon > 0,\ \exists N \in \mathbb{N},\ \forall n \ge N,\ |a_n - a| < \varepsilon\Big) \ \equiv\ \exists \varepsilon > 0,\ \forall N \in \mathbb{N},\ \exists n \ge N,\ |a_n - a| \ge \varepsilon.\]

Sözle: öyle bir \(\varepsilon > 0\) vardır ki, \(N\)’yi ne kadar büyük seçersek seçelim, \(N\)’den sonra \(a\)’dan en az \(\varepsilon\) uzakta kalan bir terim bulunur. Burada iki küçük noktaya dikkat edin. Birincisi, “\(\forall n \ge N\)” ifadesi aslında “\(\forall n \in \mathbb{N},\ (n \ge N \Rightarrow \dots)\)” kısaltmasıdır; olumsuzlaması Sonuç 1.1 ile “\(\exists n \in \mathbb{N},\ (n \ge N \wedge \neg\dots)\)”, yani “\(\exists n \ge N,\ \neg\dots\)” olur. İkincisi, “\(\forall \varepsilon > 0\)” ifadesi de “\(\forall \varepsilon \in \mathbb{R},\ (\varepsilon > 0 \Rightarrow \dots)\)” kısaltmasıdır ve aynı nedenle olumsuzlaması “\(\exists \varepsilon > 0,\ \neg \dots\)”dır: evren değişmez, \(\varepsilon\) yine pozitiftir.

Bir örnek daha: \(\forall x \in \mathbb{N},\ \exists y \in \mathbb{N},\ 3y > x\) önermesinin olumsuzlaması \(\exists x \in \mathbb{N},\ \forall y \in \mathbb{N},\ 3y \le x\)’tir: “bütün \(3\) katlarından büyük ya da onlara eşit bir doğal sayı vardır.” Bu yanlıştır; dolayısıyla özgün önerme doğrudur, zaten yukarıda doğrudan göstermiştik.

2.4 Sözel İfadeleri Sembollere Çevirme

Matematikte uzun sözel cümleleri kısa ve kesin sembollerle yazmak yaygın bir alışkanlıktır: belirsizliği önler ve önerme üzerinde işlem yapmayı (özellikle olumsuzlama almayı) kolaylaştırır. Tersi de aynı derecede önemlidir; sembolik bir ifadeyi okuyup sözle ne dediğini anlayabilmek gerekir. Bağlama göre iki biçim de kullanılır.

“Bazı reel sayılar karelerinden büyüktür.” \(\ \longrightarrow\ \exists x \in \mathbb{R},\ x > x^2\).
“Her reel sayının karesi negatif değildir.” \(\ \longrightarrow\ \forall x \in \mathbb{R},\ x^2 \ge 0\).
“\(U\)’nun her \(a\) elemanı için öyle bir pozitif \(\delta\) sayısı vardır ki, \(|x - a| < \delta\) koşulunu sağlayan her \(x\) reel sayısı \(U\)’nun elemanıdır.” \(\ \longrightarrow\)

\[\forall a \in U,\ \exists \delta > 0,\ \forall x \in \mathbb{R},\ \big(|x - a| < \delta \Rightarrow x \in U\big).\]

Son ifade ileride “açık küme” tanımı olarak karşımıza çıkacak (Tanım 15.4); \(\delta\)’nın \(a\)’ya bağlı olduğunu vurgulamak için \(\delta_a\) yazıldığı da olur.

Sembolik yazım, bir koşullu önermenin karşıtını ve karşıt tersini bulmayı da kolaylaştırır. Bir önceki bölümde gördüğümüz gibi, bir önermenin karşıtı (converse), tersi (inverse), karşıt tersi (contrapositive) ve olumsuzlaması (negation) birbirinden farklı şeylerdir; bunları ayırt edebilmek gerekir.

Örnek 2.2 (Niceleyicili Koşullu Önermenin Karşıtı ve Karşıt Tersi) “Her \(x \in \mathbb{R}\) için, \(x > 4\) ise \(x^2 > 16\)’dır.” önermesinin karşıtını ve karşıt tersini yazınız; hangileri doğrudur?

Çözüm

Önerme sembolle \(\forall x \in \mathbb{R},\ (x > 4 \Rightarrow x^2 > 16)\) biçimindedir. Karşıt ve karşıt ters, niceleyicinin içindeki koşullu önermeye uygulanır (Tanım 1.9):

Karşıtı: \(\forall x \in \mathbb{R},\ (x^2 > 16 \Rightarrow x > 4)\); sözle “her reel \(x\) için, \(x^2 > 16\) ise \(x > 4\)’tür.”
Karşıt tersi: \(\forall x \in \mathbb{R},\ (\neg(x^2 > 16) \Rightarrow \neg(x > 4))\), yani \(\forall x \in \mathbb{R},\ (x^2 \le 16 \Rightarrow x \le 4)\); sözle “her reel \(x\) için, \(x^2 \le 16\) ise \(x \le 4\)’tür.”

Özgün önerme doğrudur: \(x > 4\) ise \(x^2 > 4x > 16\) olur. Karşıt ters, özgün önermeye denk olduğundan (Teorem 1.1 (7)) o da doğrudur. Karşıt ise yanlıştır: \(x = -5\) için \((-5)^2 = 25 > 16\) sağlanır ama \(-5 > 4\) sağlanmaz. Yani \(x = -5\) karşıt için bir karşıt örnektir. (Karşıtın doğru olan biçimi “\(x^2 > 16 \Rightarrow x > 4 \vee x < -4\)” olurdu.)

Bu arada \(x \le 4\) olan bir \(x\) için koşullu önerme “boşlukla doğru”dur: hipotez sağlanmadığından koşul sınanmaz. Tümel önermenin bütün \(x\)’ler üzerinde doğru olması işte bu yüzden yalnızca \(x > 4\) olanları kontrol etmeyi gerektirir.

\(\blacksquare\)

2.5 İspat Yöntemleri

Matematikte bir teorem, ispatlanmış bir gerçeği ifade eder; ispatı da bu gerçeğin neden doğru olduğunun adım adım, mantıksal açıklamasıdır. Teoremlerin büyük çoğunluğu \(p \Rightarrow q\) yapısındadır: \(p\) hipotez (verilen, varsayılan), \(q\) sonuç (ispatlanacak) kısımdır. İspatın amacı, \(p\)’nin doğru olduğu varsayımı altında \(q\)’nun da zorunlu olarak doğru olduğunu göstermektir. Tanım 1.7 gereği \(p \Rightarrow q\) yalnızca “\(p\) doğru, \(q\) yanlış” durumunda yanlış olduğundan, bu durumun oluşamayacağını göstermek yeter.

Çoğu teorem ayrıca gizli bir tümel niceleyici taşır: “\(n^2\) çift ise \(n\) çifttir” aslında “her \(n\) tam sayısı için, \(n^2\) çift ise \(n\) çifttir” demektir. Bu yüzden ispat, keyfi bir \(n\) ile başlar.

Aşağıdaki örneklerde tam sayılarla ilgili şu bilgileri kullanacağız: bir \(n\) tam sayısı, bir \(k\) tam sayısı için \(n = 2k\) biçimindeyse çift, \(n = 2k + 1\) biçimindeyse tek sayıdır; her tam sayı bunlardan tam biridir. Tam sayıların toplamı ve çarpımı yine tam sayıdır. Bu kavramların aksiyomlardan kuruluşunu ileride Tam Sayılar ve Rasyonel Sayılar bölümünde (Tanım 11.2) vereceğiz; şimdilik ispat tekniğine odaklanıyoruz.

Doğrudan İspat

En doğal yöntem budur: hipotezi kabul eder, tanımları ve bilinen sonuçları kullanarak adım adım sonuca yürürüz.

\(p\)’nin doğru olduğunu varsay.
Mantıksal bir zincir kur: \(p \Rightarrow r\), \(r \Rightarrow s\), …, \(z \Rightarrow q\) (her adım bir tanım, bir aksiyom ya da ispatlanmış bir sonuçtur).
Geçişlilik (Teorem 1.1 (5)) ile \(p \Rightarrow q\) sonucuna var.

Teoremlerin çoğu bu yöntemle ispatlanır.

Örnek 2.3 (İki Tek Sayının Çarpımı Tektir) İki tek tam sayının çarpımının tek olduğunu ispatlayınız.

Çözüm

\(m\) ve \(n\) keyfi iki tek tam sayı olsun (hipotez). Tek sayı tanımı gereği \(m = 2k_1 + 1\) ve \(n = 2k_2 + 1\) olacak biçimde \(k_1, k_2\) tam sayıları vardır. Çarpımı hesaplayalım:

\[m \cdot n = (2k_1 + 1)(2k_2 + 1) = 4k_1 k_2 + 2k_1 + 2k_2 + 1 = 2(2k_1 k_2 + k_1 + k_2) + 1.\]

\(k_1\) ve \(k_2\) tam sayı olduğundan \(k = 2k_1 k_2 + k_1 + k_2\) de bir tam sayıdır; dolayısıyla \(mn = 2k + 1\) biçimindedir, yani tek sayı tanımını sağlar. \(m\) ve \(n\) keyfi olduğundan iddia bütün tek sayı çiftleri için doğrudur.

\(\blacksquare\)

Bir doğrudan ispat örneği daha: bölünebilme, tanımı kullanılarak zincir kurmanın güzel bir örneğidir. \(a\) ve \(b\) tam sayılar ve \(a \neq 0\) olmak üzere, \(b = ak\) olacak biçimde bir \(k\) tam sayısı varsa “\(a\), \(b\)’yi böler” der ve \(a \mid b\) yazarız.

Örnek 2.4 (Bölünebilme Geçişlidir) \(a, b, c\) tam sayılar olsun. \(a \mid b\) ve \(b \mid c\) ise \(a \mid c\) olduğunu ispatlayınız.

Çözüm

\(a \mid b\) ve \(b \mid c\) olsun (hipotez). Tanım gereği \(b = ak\) ve \(c = bl\) olacak biçimde \(k, l\) tam sayıları vardır. İkinci eşitlikte \(b\) yerine \(ak\) yazalım:

\[c = bl = (ak)l = a(kl).\]

\(kl\) bir tam sayı olduğundan \(c\), \(a\)’nın bir tam sayı katıdır; yani \(a \mid c\). Zincir şuydu: hipotez \(\Rightarrow\) \(b = ak,\ c = bl\) \(\Rightarrow\) \(c = a(kl)\) \(\Rightarrow\) sonuç.

\(\blacksquare\)

Karşıt Tersle İspat

\(p \Rightarrow q\) yerine, ona denk olan (Teorem 1.1 (7)) \(\neg q \Rightarrow \neg p\) önermesini doğrudan ispatlarız. Bazı durumlarda bu çok daha kolaydır; özellikle sonuç \(q\) “değil”li ya da hipotezden geri gitmesi zor bir ifadeyse.

\(\neg q\)’nun doğru olduğunu varsay (sonucun yanlış olduğunu).
Mantıksal adımlarla \(\neg p\)’nin doğru olduğunu göster (hipotezin de yanlış olduğunu).
\(\neg q \Rightarrow \neg p\) ispatlandığından, ona denk olan \(p \Rightarrow q\) da ispatlanmıştır.

Örnek 2.5 (Karesi Çift Olan Tam Sayı Çifttir) \(n\) bir tam sayı olsun. \(n^2\) çift ise \(n\)’nin çift olduğunu ispatlayınız.

Çözüm

Doğrudan ispat denersek \(n^2 = 2k\) eşitliğinden \(n\) hakkında bir şey söylemek zordur: \(n = \sqrt{2k}\) yazmak bize \(n\)’nin çift olduğunu göstermez. Karşıt tersi deneyelim: “\(n\) çift değilse (yani tekse) \(n^2\) çift değildir (yani tektir).”

\(n\) tek olsun. O hâlde bir \(k\) tam sayısı için \(n = 2k + 1\)’dir. Karesini alalım:

\[n^2 = (2k + 1)^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1.\]

\(2k^2 + 2k\) bir tam sayı olduğundan \(n^2\) tek sayı biçimindedir. Böylece karşıt ters, “\(n\) tek \(\Rightarrow\) \(n^2\) tek”, ispatlanmıştır; Teorem 1.1 (7) gereği özgün önerme “\(n^2\) çift \(\Rightarrow\) \(n\) çift” de doğrudur. (Aslında bu, Örnek 2.3’in \(m = n\) özel hâlidir.)

\(\blacksquare\)

Örnek 2.6 (Üç n Artı İki Tek İse n Tektir) \(n\) bir tam sayı olsun. \(3n + 2\) tek ise \(n\)’nin tek olduğunu ispatlayınız.

Çözüm

Karşıt tersi ispatlayalım: “\(n\) tek değilse (çiftse) \(3n + 2\) tek değildir (çifttir).”

\(n\) çift olsun; bir \(k\) tam sayısı için \(n = 2k\). O zaman

\[3n + 2 = 3(2k) + 2 = 6k + 2 = 2(3k + 1).\]

\(3k + 1\) bir tam sayı olduğundan \(3n + 2\) çifttir. Karşıt ters ispatlandığından özgün önerme de doğrudur.

Neden karşıt ters daha kolaydı? Hipotez “\(3n + 2\) tek” bize \(3n + 2 = 2k + 1\) verir; buradan \(n\)’yi çekmek, \(n = (2k - 1)/3\)’ün tam sayı olup olmadığını tartışmayı gerektirirdi. Karşıt terste ise hipotez doğrudan \(n\) hakkındadır ve hesap kendiliğinden ilerler.

\(\blacksquare\)

Olmayana Ergi (Çelişkiyle İspat)

Bu yöntem, ispatlanmak istenen önermenin yanlış olduğunu varsayıp mantıksal bir olanaksızlığa (çelişkiye) ulaşmaya dayanır. Çelişmezlik ilkesi gereği çelişki olamaz; demek ki varsayım yanlıştır ve üçüncü hâlin olmazlığı ilkesi gereği önerme doğrudur.

\(p \Rightarrow q\) biçimindeki bir önerme için adımlar şöyledir:

Önermenin yanlış olduğunu varsay. Sonuç 1.1 gereği \(p \Rightarrow q\)’nun yanlış olması, \(p\)’nin doğru ve \(q\)’nun yanlış olması demektir.
Yani \(p\) ve \(\neg q\)’nun ikisinin de doğru olduğunu varsayarak başla.
Bu iki varsayımdan bir çelişki türet: hem \(r\) hem \(\neg r\) olan bir \(r\) önermesi (ya da \(1 = 2\) gibi açıkça yanlış bir şey).
Adımlar geçerli olduğundan çelişkinin kaynağı başlangıç varsayımıdır.
Demek ki “\(p \Rightarrow q\) yanlıştır” varsayımı yanlıştır; önerme doğrudur.

Niceleyicili bir önerme için de aynı şey yapılır: “\(\forall x,\ p(x)\)” yanlış olsun, yani \(\neg p(x_0)\) olan bir \(x_0\) olsun, deyip çelişki aranır.

Örnek 2.7 (Kök İki İrrasyoneldir) \(\sqrt{2}\)’nin irrasyonel olduğunu, yani \(a, b\) tam sayılar ve \(b \neq 0\) olmak üzere \(\sqrt{2} = \dfrac{a}{b}\) biçiminde yazılamayacağını ispatlayınız.

Çözüm

Olmayana ergi ile ispatlayalım. Önermenin yanlış olduğunu, yani \(\sqrt{2}\)’nin rasyonel olduğunu varsayalım. O hâlde \(a, b\) tam sayılar ve \(b \neq 0\) olmak üzere

\[\sqrt{2} = \frac{a}{b}\]

yazılabilir. Kesri sadeleştirilmiş kabul edebiliriz (pay ile paydanın ortak böleni varsa ikisini de ona böleriz; kesrin değeri değişmez): \(a\) ile \(b\)’nin \(1\)’den başka ortak pozitif böleni yoktur (aralarında asaldır). Özel olarak \(a\) ve \(b\) ikisi birden çift olamaz; çift olsalardı ortak bölen \(2\) olurdu.

Her iki tarafın karesini alalım: \(2 = \dfrac{a^2}{b^2}\), yani

\[a^2 = 2b^2.\]

Sağ taraf \(2\)’nin bir tam sayı katı olduğundan \(a^2\) çifttir. Örnek 2.5 gereği \(a\) çifttir; bir \(k\) tam sayısı için \(a = 2k\) yazalım. Yerine koyunca

\[(2k)^2 = 2b^2 \ \Rightarrow\ 4k^2 = 2b^2 \ \Rightarrow\ b^2 = 2k^2.\]

Demek ki \(b^2\) de çifttir ve yine Örnek 2.5 gereği \(b\) çifttir.

Böylece hem \(a\) hem \(b\) çift çıktı; bu, “\(a\) ve \(b\) ikisi birden çift olamaz” bilgisiyle çelişir. Çelişkiye, “\(\sqrt{2}\) rasyoneldir” varsayımından geçerli adımlarla ulaştığımız için bu varsayım yanlıştır: \(\sqrt{2}\) irrasyoneldir.

\(\blacksquare\)

Bu ispat, Pisagorcuların “her uzunluk iki tam sayının oranıdır” inancını yıkan, matematik tarihinin en ünlü ispatlarından biridir. Burada “\(\sqrt{2}\)” ile karesi \(2\) olan pozitif reel sayıyı kastettik ve varlığını kabul ettik; varlığın ispatı ve bu sonucun sıralı cisim aksiyomlarına dayanan sürümü için bkz. Teorem 13.1 ve Teorem 13.3.

İkinci bir olmayana ergi örneği, Öklid’e ait bir başka klasiktir.

Örnek 2.8 (Sonsuz Çoklukta Asal Sayı Vardır) \(1\)’den büyük ve \(1\) ile kendisinden başka pozitif böleni olmayan doğal sayılara asal sayı denir. Sonsuz çoklukta asal sayı olduğunu ispatlayınız.

Çözüm

Önce bir yardımcı gözlem: \(1\)’den büyük her \(N\) doğal sayısının bir asal böleni vardır. Gerçekten, \(N\)’nin \(1\)’den büyük bölenleri kümesi boş değildir (\(N\) kendisi bu kümededir), dolayısıyla en küçük elemanı \(p\) vardır (doğal sayıların her boş olmayan alt kümesinin en küçük elemanı olduğunu ileride ispatlayacağız: Teorem 9.2). Bu \(p\) asaldır: \(p\)’nin \(1 < d < p\) koşulunu sağlayan bir \(d\) böleni olsaydı, \(d \mid p\) ve \(p \mid N\) olduğundan Örnek 2.4 gereği \(d\) de \(N\)’yi bölerdi; o zaman \(d\), \(N\)’nin \(1\)’den büyük bölenleri kümesinde \(p\)’den küçük bir eleman olurdu ve bu, \(p\)’nin bu kümenin en küçük elemanı seçilmesiyle çelişir.

Şimdi olmayana ergi. Sonlu çoklukta asal sayı olduğunu varsayalım ve hepsini listeleyelim: \(p_1, p_2, \dots, p_n\). Şu sayıyı kuralım:

\[N = p_1 p_2 \cdots p_n + 1.\]

\(N > 1\) olduğundan yardımcı gözlem gereği \(N\)’nin bir asal böleni \(p\) vardır. Bütün asallar listede olduğuna göre \(p\), listedeki \(p_i\)’lerden biridir. O hâlde \(p\), hem \(N\)’yi hem de \(p_1 p_2 \cdots p_n\) çarpımını böler (çarpanlardan biridir); dolayısıyla farklarını da böler: \(N = pu\) ve \(p_1 p_2 \cdots p_n = pv\) ise \(N - p_1 p_2 \cdots p_n = p(u - v)\) olur, yani

\[p \mid N - p_1 p_2 \cdots p_n = 1.\]

Ama \(p > 1\) olan bir sayı \(1\)’i bölemez. Bu bir çelişkidir. Demek ki asal sayılar sonlu çoklukta değildir.

Dikkat: ispat, \(N\)’nin kendisinin asal olduğunu iddia etmez; yalnızca listede olmayan bir asal bölenin var olduğunu gösterir. Örneğin \(2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 + 1 = 30031 = 59 \cdot 509\) asal değildir.

\(\blacksquare\)

Karşıt tersle ispat ile olmayana ergi arasındaki fark

İkisi de \(\neg q\) varsayımıyla başladığından sık sık karıştırılır. Karşıt tersle ispatta yalnızca \(\neg q\) varsayılır ve hedef bellidir: \(\neg p\)’ye ulaşmak. Olmayana ergide hem \(p\) hem \(\neg q\) varsayılır ve hedef herhangi bir çelişkidir; \(\neg p\)’ye ulaşmak bunlardan yalnızca biridir (çünkü \(p \wedge \neg p\) bir çelişkidir). Bu yüzden olmayana ergi daha esnektir; ama elde daha çok varsayım olduğundan hangi adımın gerçekten gerekli olduğunu görmek bazen zorlaşır. Bir ispat “\(\neg q\) varsay … \(\neg p\) elde ettik, oysa \(p\) doğruydu, çelişki” biçimindeyse aslında bir karşıt ters ispatıdır ve öyle yazılması daha temizdir.

İki Yönlü İspat

\(p \Leftrightarrow q\) (“\(p\) ancak ve ancak \(q\)”) biçimindeki bir teorem, Örnek 1.2 gereği iki koşullu önermenin birleşimidir ve iki ayrı ispat gerektirir:

Yeterlilik (\(\Rightarrow\) yönü): \(p \Rightarrow q\)’nun ispatı.
Gereklilik (\(\Leftarrow\) yönü): \(q \Rightarrow p\)’nin ispatı.

Her yön için yukarıdaki yöntemlerden uygun olanı seçilebilir; iki yön farklı yöntemlerle ispatlanabilir. Teorem, iki yön de bitmeden ispatlanmış sayılmaz.

Örnek 2.9 (Bir Tam Sayı Çifttir Ancak ve Ancak Karesi Çiftse) \(n\) bir tam sayı olsun. \(n\)’nin çift olması için gerek ve yeter koşulun \(n^2\)’nin çift olması olduğunu ispatlayınız.

Çözüm

(\(\Rightarrow\)) \(n\) çift olsun; \(n = 2k\) olacak biçimde bir \(k\) tam sayısı vardır. O zaman \(n^2 = 4k^2 = 2(2k^2)\) ve \(2k^2\) tam sayı olduğundan \(n^2\) çifttir. (Doğrudan ispat.)

(\(\Leftarrow\)) \(n^2\) çift olsun. Örnek 2.5’te karşıt tersle gösterildiği gibi \(n\) çifttir.

İki yön de ispatlandığından \(n\) çift \(\Leftrightarrow\) \(n^2\) çift.

\(\blacksquare\)

Bazen iki yön birden, her adımı bir denklik olan bir zincirle ispatlanır: \(p \Leftrightarrow r \Leftrightarrow s \Leftrightarrow \dots \Leftrightarrow q\). Örneğin “\(x^2 = x\) ancak ve ancak \(x = 0\) veya \(x = 1\)” iddiası

\[x^2 = x \ \Leftrightarrow\ x^2 - x = 0 \ \Leftrightarrow\ x(x - 1) = 0 \ \Leftrightarrow\ x = 0 \vee x - 1 = 0 \ \Leftrightarrow\ x = 0 \vee x = 1\]

zinciriyle ispatlanır; üçüncü adımda “çarpım sıfırsa çarpanlardan biri sıfırdır” özelliği (Önerme 6.13) kullanılır. Böyle bir zincirde her okun gerçekten çift yönlü olduğundan emin olmak gerekir; tek yönlü bir adım sızarsa yalnızca bir yön ispatlanmış olur.

Tümevarım (Tanıtım)

Doğal sayılarla ilgili “her \(n \in \mathbb{N}\) için \(P(n)\)” biçimindeki önermeler için çok güçlü bir yöntem vardır. Domino taşları gibi düşünün: ilk taş devriliyorsa ve her taş devrildiğinde bir sonrakini deviriyorsa, bütün taşlar devrilir. Buna karşılık gelen ilke şudur: \(P(1)\) doğruysa ve her \(k \in \mathbb{N}\) için “\(P(k)\) doğru ise \(P(k+1)\) doğru” gerektirmesi sağlanıyorsa, \(P(n)\) her doğal sayı için doğrudur.

Bu ilkenin neden geçerli olduğu, doğal sayıların nasıl tanımlandığına bağlıdır ve ayrı bir bölümü hak eder. Tümevarım ilkesinin ispatını, uygulama örneklerini (toplam formülleri, eşitsizlikler, bölünebilme) ve güçlü tümevarımı Doğal Sayılar ve Tümevarım bölümünde (Teorem 9.1) ele alacağız. Şimdilik yalnızca varlığını ve ne tür önermeler için kullanıldığını bilmek yeter.

Karşıt Örnekle Çürütme

Bu yöntem bir önermenin yanlış olduğunu ispatlamak içindir ve özellikle \(\forall x,\ p(x)\) biçimindeki tümel önermeler için idealdir. Teorem 2.1 gereği \(\forall x,\ p(x)\) önermesinin olumsuzlaması \(\exists x,\ \neg p(x)\)’tir; dolayısıyla \(p(x)\)’in yanlış olduğu tek bir \(x\) değeri bulmak, “her \(x\) için \(p(x)\)” iddiasını çürütmeye yeter. Bu, bir tür varlık ispatıdır: aradığımız şey, iddianın bozulduğu bir örnektir.

Örnek 2.10 (Asal Üreten Formül Sanısı) “Her \(n\) doğal sayısı için \(f(n) = n^2 + n + 41\) bir asal sayıdır.” önermesinin yanlış olduğunu ispatlayınız.

Çözüm

Tek bir karşıt örnek yeter. Küçük değerler umut vericidir: \(f(1) = 43\), \(f(2) = 47\), \(f(3) = 53\) hep asaldır; hatta \(n = 1, 2, \dots, 39\) için \(f(n)\) asaldır. Ama \(n = 40\) alalım:

\[f(40) = 40^2 + 40 + 41 = 1600 + 40 + 41 = 1681 = 41^2.\]

\(1681 = 41 \cdot 41\) asal değildir. Dolayısıyla \(n = 40\) bir karşıt örnektir ve önerme yanlıştır. (\(n = 41\) de işe yarar: \(f(41) = 41^2 + 41 + 41 = 41 \cdot 43\).)

Bu örnek ayrıca “39 doğru örnek bir ispat değildir” dersini verir: kaç örnek denersek deneyelim, tümel bir önerme örneklerle ispatlanamaz.

\(\blacksquare\)

Örnek 2.11 (Dört Katı Çift Olan Her Sayı Çift midir?) “Her \(x\) tam sayısı için, \(4x\) çift ise \(x\) çifttir.” önermesinin yanlış olduğunu ispatlayınız.

Çözüm

Önerme \(\forall x \in \mathbb{Z},\ (4x \text{ çift} \Rightarrow x \text{ çift})\) biçimindedir. Olumsuzlaması, Teorem 2.1 ve Sonuç 1.1 ile, \(\exists x \in \mathbb{Z},\ (4x \text{ çift} \wedge x \text{ tek})\)’tir; yani hipotezin sağlandığı ama sonucun sağlanmadığı bir \(x\) arıyoruz.

\(x = 3\) alalım. \(4 \cdot 3 = 12\) çifttir (hipotez doğru) ama \(3\) tektir (sonuç yanlış). Demek ki \(x = 3\) bir karşıt örnektir ve önerme yanlıştır. (Aslında \(4x\) her \(x\) için çift olduğundan, hipotez her zaman sağlanır ve her tek \(x\) karşıt örnektir.)

\(\blacksquare\)

Örnek ispatlamaz, karşıt örnek çürütür

Bu bakışımsızlık niceleyicilerden gelir. “Her \(x\) için \(p(x)\)” iddiasını ispatlamak için bütün \(x\)’ler gerekir; örnekler yetmez. Aynı iddiayı çürütmek için tek bir \(x\) yeter. Tersine, “öyle bir \(x\) vardır ki \(p(x)\)” iddiasını ispatlamak için tek bir örnek yeter; çürütmek içinse bütün \(x\)’ler için \(\neg p(x)\) göstermek gerekir.

Durumlara Ayırma

Bazen bir teoremi tek bir akıl yürütmeyle ispatlamak zordur. Bunun yerine önerme, bütün olasılıkları kapsayan birkaç duruma ayrılır ve her durum ayrı ayrı ispatlanır. Mantıksal temeli şudur: \(p \equiv p_1 \vee p_2 \vee \dots \vee p_k\) ise (durumlar hipotezi tüketiyorsa) \(p \Rightarrow q\)’yu göstermek için \(p_1 \Rightarrow q\), …, \(p_k \Rightarrow q\)’nun her birini göstermek yeter. Örneğin “her \(x \in \mathbb{R}\) için \(p(x)\)” ispatlanacaksa \(x > 0\), \(x < 0\) ve \(x = 0\) durumları ayrı ayrı ele alınabilir; üçlem yasası (Bölüm 7.1) bu üç durumun bütün reel sayıları kapsadığını garanti eder. Durumların eksiksiz olduğunu belirtmek ispatın parçasıdır.

Örnek 2.12 (n Kare Artı n Her Zaman Çifttir) Her \(n\) tam sayısı için \(n^2 + n\)’nin çift olduğunu ispatlayınız.

Çözüm

\(n\) keyfi bir tam sayı olsun. \(n^2 + n = n(n + 1)\) olduğuna dikkat edelim. Her tam sayı ya çift ya tektir; bu iki durum bütün olasılıkları kapsar.

Durum 1: \(n\) çift. Bir \(k\) tam sayısı için \(n = 2k\). O zaman \(n(n+1) = 2k(2k+1) = 2\big(k(2k+1)\big)\) ve \(k(2k+1)\) tam sayı olduğundan \(n^2 + n\) çifttir.

Durum 2: \(n\) tek. Bir \(k\) tam sayısı için \(n = 2k + 1\). O zaman \(n + 1 = 2k + 2 = 2(k+1)\) ve \(n(n+1) = (2k+1) \cdot 2(k+1) = 2\big((2k+1)(k+1)\big)\); yine çifttir.

Her iki durumda da \(n^2 + n\) çift olduğundan ve başka durum olmadığından iddia her \(n\) için doğrudur.

\(\blacksquare\)

Yöntemleri toparlayalım: hepsi, önceki bölümdeki bir mantıksal gerçeğe dayanır.

Yöntem	Ne yapılır	Dayandığı mantık
Doğrudan ispat	\(p\) varsayılır, zincirle \(q\)’ya gidilir	Geçişlilik, Teorem 1.1 (5)
Karşıt tersle ispat	\(\neg q\) varsayılır, \(\neg p\) gösterilir	\(p \Rightarrow q \equiv \neg q \Rightarrow \neg p\), Teorem 1.1 (7)
Olmayana ergi	\(p\) ve \(\neg q\) varsayılır, çelişki bulunur	Sonuç 1.1 ve üçüncü hâlin olmazlığı
İki yönlü ispat	\(p \Rightarrow q\) ve \(q \Rightarrow p\) ayrı ayrı	Örnek 1.2
Karşıt örnek	\(\neg p(x_0)\) olan bir \(x_0\) bulunur	Teorem 2.1
Durumlara ayırma	Hipotez tüketici durumlara bölünür	\((p_1 \vee p_2) \Rightarrow q \equiv (p_1 \Rightarrow q) \wedge (p_2 \Rightarrow q)\)

Son satırdaki denklik de doğruluk tablosuyla kolayca doğrulanır: sol taraf yalnızca “\(p_1\) ya da \(p_2\) doğru ve \(q\) yanlış” iken yanlıştır; sağ taraf da tam olarak o zaman yanlıştır.

İspat olmayan şeyler

Aşağıdakiler ispat değildir:

Şekil ya da diyagram çizmek. Şekiller problemi anlamak ve bir yol haritası çıkarmak için çok yararlıdır; ama tek başlarına asla ispatın yerini tutmazlar, kesin bir mantıksal akıl yürütme sunmazlar.
Örnek vermek. Örnek, iddiayı anlamaya yardım eder; iddianın kendisini ispatlamaz (karşıt örnek ise yalnızca çürütür).
Atlama, ihmal, eksik bırakma. “Buradan kolayca görülür” denip geçilen adımlar çoğu zaman ispatın en zor yeridir.
İddiayı küçümsemek ya da apaçık göstermek. “İspat aşikârdır” cümlesi bir ispat değildir.
Süslü dil, karmaşık formüller, ilgisiz sözcükler. Anlaşılmaz olmak sağlam olmak demek değildir (bulanıklaştırma ile ispat).
Birinin ya da bir otoritenin söylediğine güvenmek. “Hocam öyle demişti” bir gerekçe değildir (otoriteye başvurma).
Doğru gerekçelerle, makul görünen ama yanlış gerekçeleri karıştırmak. Kulağa doğru gelen her adım geçerli değildir; her adımın hangi tanıma, aksiyoma ya da teoreme dayandığı söylenebilmelidir.

2.6 Alıştırmalar

Alıştırma 2.1 (Niceleyiciler ve İspat Yöntemleri Alıştırmaları)

Aşağıdaki önermelerin doğruluk değerini belirleyiniz, olumsuzlamalarını sembolle yazınız ve olumsuzlamanın doğruluk değerini kontrol ediniz.

(i) \(\forall x \in \mathbb{R},\ \exists y \in \mathbb{R},\ y > x\).

(ii) \(\exists y \in \mathbb{R},\ \forall x \in \mathbb{R},\ y > x\).

(iii) \(\forall x \in \mathbb{R},\ \exists y \in \mathbb{R},\ xy = 1\).

Aşağıdaki sözel ifadeleri niceleyicilerle yazınız.

(i) “Her pozitif reel sayının pozitif bir karekökü vardır.”

(ii) “Her doğal sayıdan büyük bir asal sayı vardır.”

(iii) “\(A\) kümesi üzerinde tanımlı \(f\) fonksiyonu sınırlıdır” ifadesi \(\exists M > 0,\ \forall x \in A,\ |f(x)| \le M\) demektir. “\(f\) sınırlı değildir” ifadesini niceleyicilerle yazınız.

\(m\) ve \(n\) tam sayılar olsun. “\(mn\) çift ise \(m\) çifttir veya \(n\) çifttir.” önermesini karşıt tersle ispatlayınız.
Önce “her \(n\) tam sayısı için, \(n^2\) üçe bölünüyorsa \(n\) üçe bölünür” önermesini karşıt ters ve durumlara ayırma yöntemleriyle ispatlayınız. Sonra bunu kullanarak \(\sqrt{3}\)’ün irrasyonel olduğunu olmayana ergi ile ispatlayınız.
Aşağıdaki önermelerin yanlış olduğunu karşıt örnekle gösteriniz.

(i) “Her \(n \in \mathbb{N}\) için \(2^n + 1\) asaldır.”

(ii) “Her \(n \in \mathbb{N}\) için \(n^2 \ge 2n\).”

(iii) “Her \(x \in \mathbb{R}\) için \(x^2 \ge x\).”

Çözüm

a) (i) Doğrudur: \(x\) verilince \(y = x + 1\) alınırsa \(y > x\) olur; \(y\)’nin \(x\)’e bağlı olması Durum 1’e uygundur. Olumsuzlaması (Sonuç 2.1): \(\exists x \in \mathbb{R},\ \forall y \in \mathbb{R},\ y \le x\); “bütün reel sayılardan büyük ya da onlara eşit bir reel sayı vardır”, yani “\(\mathbb{R}\)’nin en büyük elemanı vardır”. Bu yanlıştır; özgün önermenin doğru olmasıyla tutarlı.

(ii) Yanlıştır: hangi \(y\) seçilirse seçilsin \(x = y\) (ya da \(x = y + 1\)) için \(y > x\) sağlanmaz. Olumsuzlaması: \(\forall y \in \mathbb{R},\ \exists x \in \mathbb{R},\ y \le x\); “her reel sayıdan büyük ya da ona eşit bir reel sayı vardır” ki doğrudur (\(x = y\)). (i) ile (ii) yalnızca niceleyici sırasıyla ayrılır ve doğruluk değerleri farklıdır.

(iii) Yanlıştır: \(x = 0\) için hiçbir \(y\) ile \(0 \cdot y = 1\) sağlanmaz. Olumsuzlaması: \(\exists x \in \mathbb{R},\ \forall y \in \mathbb{R},\ xy \neq 1\); doğrudur, \(x = 0\) tanığıdır. (\(x \neq 0\) olan her \(x\) için \(y = 1/x\) işe yarardı; tümel önermeyi tek istisna yanlış yapar.)

b) (i) \(\forall x \in \mathbb{R},\ \big(x > 0 \Rightarrow \exists y \in \mathbb{R},\ (y > 0 \wedge y^2 = x)\big)\); kısaca \(\forall x > 0,\ \exists y > 0,\ y^2 = x\).

(ii) \(\forall n \in \mathbb{N},\ \exists p \in \mathbb{N},\ (p \text{ asal} \wedge p > n)\). Örnek 2.8 bunun doğru olduğunu gösterir: önerme yanlış olsaydı, kendisinden büyük asal bulunmayan bir \(n\) olurdu; o zaman bütün asallar \(\{1, 2, \dots, n\}\) kümesinde kalır ve sonlu çoklukta olurdu, bu ise Örnek 2.8 ile çelişir.

(iii) Sınırlılık tanımını Sonuç 2.1 ile olumsuzlayalım: \(\forall M > 0,\ \exists x \in A,\ |f(x)| > M\). Sözle: hangi \(M\) pozitif sayısı verilirse verilsin, \(A\)’da \(|f(x)|\)’in \(M\)’yi aştığı bir \(x\) vardır. Evren değişmedi: \(M\) yine pozitif, \(x\) yine \(A\)’da.

c) Karşıt ters: “\(m\) çift değil ve \(n\) çift değil ise \(mn\) çift değildir.” Burada “\(m\) çift veya \(n\) çift” sonucunun olumsuzlaması De Morgan (Teorem 1.1 (6)) ile “\(m\) çift değil ve \(n\) çift değil”dir; tam sayılar için de “çift değil” demek “tek” demektir. Yani ispatlanacak olan: \(m\) tek ve \(n\) tek ise \(mn\) tektir. Bu tam olarak Örnek 2.3’dir. Karşıt ters doğru olduğundan özgün önerme doğrudur.

d) Yardımcı önerme: \(3 \mid n^2 \Rightarrow 3 \mid n\). Karşıt tersini ispatlayalım: \(3 \nmid n \Rightarrow 3 \nmid n^2\). \(n\) üçe bölünmüyorsa, bir \(k\) tam sayısı için \(n = 3k + 1\) ya da \(n = 3k + 2\)’dir (üçe bölümden kalan \(1\) ya da \(2\)’dir; bölme algoritması Teorem 12.4). İki durum:

\(n = 3k + 1\) ise \(n^2 = 9k^2 + 6k + 1 = 3(3k^2 + 2k) + 1\); kalan \(1\), yani \(3 \nmid n^2\).
\(n = 3k + 2\) ise \(n^2 = 9k^2 + 12k + 4 = 3(3k^2 + 4k + 1) + 1\); kalan yine \(1\), yani \(3 \nmid n^2\).

Her iki durumda da \(n^2\) üçe bölünmez; karşıt ters, dolayısıyla yardımcı önerme ispatlanmıştır.

\(\sqrt{3}\) irrasyoneldir: \(\sqrt{3}\)’ün rasyonel olduğunu varsayalım: \(a, b\) tam sayılar, \(b \neq 0\), kesir sadeleştirilmiş (\(a\) ve \(b\)’nin \(1\)’den başka ortak pozitif böleni yok) olmak üzere \(\sqrt{3} = a/b\). Karesini alınca \(a^2 = 3b^2\); demek ki \(3 \mid a^2\) ve yardımcı önerme gereği \(3 \mid a\). \(a = 3k\) yazıp yerine koyalım: \(9k^2 = 3b^2\), yani \(b^2 = 3k^2\). O hâlde \(3 \mid b^2\) ve yine yardımcı önerme gereği \(3 \mid b\). Böylece \(3\), hem \(a\)’yı hem \(b\)’yi böler; bu, kesrin sadeleştirilmiş olmasıyla çelişir. Demek ki varsayım yanlıştır: \(\sqrt{3}\) irrasyoneldir.

e) (i) \(n = 3\): \(2^3 + 1 = 9 = 3 \cdot 3\) asal değildir. (\(n = 1, 2\) için \(3\) ve \(5\) asaldır; ilk iki örnek yanıltıcıdır.)

(ii) \(n = 1\): \(1^2 = 1\) ama \(2 \cdot 1 = 2\) ve \(1 \ge 2\) yanlıştır. (\(n \ge 2\) için önerme doğrudur; ama “her \(n\)” iddiasını tek istisna yıkar.)

(iii) \(x = \dfrac{1}{2}\): \(\dfrac{1}{4} \ge \dfrac{1}{2}\) yanlıştır. Genel olarak \(0 < x < 1\) olan her \(x\) karşıt örnektir; Örnek 2.1 (1) zaten böyle bir \(x\)’in var olduğunu göstermişti.

\(\blacksquare\)

Mantık ve ispat dilimiz tamamlandı. Bundan sonra bu dili, matematiğin bütün nesnelerinin kurulduğu temel yapıya, kümelere uygulayacağız: Kümeler ve Küme İşlemleri.