İspat yöntemlerine giriş: doğrudan, contrapositive, çelişki

Ayrık matematik vizesinin en korkulan kısmı ispat soruları. Aslında çoğu şablon soru: “Give a direct proof”, “Prove by contraposition”, “Prove by contradiction”. Bu sayfada her yöntemin İngilizce iskeletini öğreneceksin. İspatların yarısı tanımı doğru yazmaktır. Tanımı yazmadan başlayan ispat genelde dağılır.

Altın kurallar:

1. Tanımla başla. ”$n$ is odd” yazdığın an hemen “so $n = 2k + 1$ for some integer $k$” yaz.
2. Her yeni sayıya yeni harf. $m$ ve $n$ tekse $m = 2a + 1$, $n = 2b + 1$.
3. Hedefin tanımıyla bitir. ”$= 2m + 1$, where $m = \dots$ is an integer. Therefore … is odd.”
4. Örnek ispat değildir, ama tek karşı örnek bir $\forall$ iddiasını çürütür.
5. Hipotez kullanışsızsa contrapositive’e geç.

Terimler ve tanımlar

• Theorem: doğru olduğu ispatlanmış önemli bir iddia. Lemma: büyük bir ispatta kullanılan yardımcı iddia. Corollary: bir teoremden hemen çıkan sonuç. Conjecture: doğru olduğu düşünülen ama ispatlanmamış iddia. Axiom: ispatsız kabul edilen başlangıç doğrusu.
• Çoğu teorem “for all” ile başlar ama bunu yazmaz: “If $n$ is odd, then $n^2$ is odd” aslında $\forall n\,(P(n) \to Q(n))$ demektir. İspatta keyfi bir $n$ alırsın ve sonunda universal generalization ile bütün $n$‘ler için geçerli olur.

Ezber tanımlar:

Doğrudan ispat (direct proof)

$p \to q$‘yu ispatlamak için $p$‘yi varsay, tanımlar ve cebirle $q$‘ya ulaş.

Teorem. If $m$ is even and $n$ is odd, then $m + n$ is odd.

Proof. Let m be even and n be odd.            hipotezi yaz
Then m = 2a and n = 2b + 1 for some            tanımlar, İKİ farklı harf
integers a and b.
So m + n = 2a + 2b + 1 = 2(a + b) + 1.         cebir, 2 parantezine al
Since a + b is an integer, m + n is odd        hedefin tanımı
by definition.  ∎

TUZAK · Aynı harfi iki sayıya vermek. $m = 2k$, $n = 2k + 1$ yazarsan $n = m + 1$ demiş olursun; ispat sadece ardışık sayılar için geçerli olur. Her sayı kendi harfini alır.

Contraposition ile ispat

$p \to q \equiv \lnot q \to \lnot p$ olduğu için contrapositive’i ispatlamak yeter. Ne zaman? Hipotez sana kullanışlı bir eşitlik vermiyorsa: ”$3n + 7$ is even”, ”$n^2$ is odd”, ”$xy$ is irrational” gibi.

Teorem. If $n$ is an integer and $3n + 7$ is even, then $n$ is odd.

Doğrudan denesen: $3n + 7 = 2k \Rightarrow n = \tfrac{2k - 7}{3}$. Bu işe yaramaz, $n$‘nin tek olduğunu göremezsin.

Proof. We prove the contrapositive:
"If n is even, then 3n + 7 is odd."
Let n be even, so n = 2k for some integer k.
Then 3n + 7 = 6k + 7 = 6k + 6 + 1 = 2(3k + 3) + 1.
Since 3k + 3 is an integer, 3n + 7 is odd.
Since the contrapositive is true, the original statement is true.  ∎

Contrapositive’i açıkça cümle olarak yazmak puan getirir. “Ve/veya” içeren sonuçlarda De Morgan’a dikkat: ”$x \ge 1$ or $y \ge 1$“‘in olumsuzu ”$x < 1$ and $y < 1$”.

Çelişki ile ispat (proof by contradiction)

İddianın yanlış olduğunu varsay, bir saçmalığa ($r \land \lnot r$) ulaş. $p \to q$ için varsayım ”$p$ doğru ve $q$ yanlış”. Ne zaman? “irrational”, “there is no …”, “infinitely many” gibi olumsuz iddialarda.

Teorem. $\sqrt{2}$ is irrational.

Proof. Assume, for contradiction, that √2 is rational.
Then √2 = a/b where a, b are integers, b ≠ 0, and the
fraction is in lowest terms (a and b have no common factor > 1).
Squaring: 2 = a²/b², so a² = 2b². Hence a² is even,
so a is even (if a were odd, a² would be odd).
Write a = 2c. Then 4c² = 2b², so b² = 2c², and b² is even,
so b is even.
Now a and b are both even, so 2 is a common factor.
This contradicts "lowest terms". Hence √2 is irrational.  ∎

Burada “a² even ⇒ a even” lemması kullanıldı; onu contraposition ile ispatlamıştın (soru 1). Büyük ispatlar küçük lemmalardan kurulur.

İPUCU · Çelişkiyi adlandır. Son satırda neyin neyle çeliştiğini yaz: “This contradicts the assumption that $a/b$ is in lowest terms.” “Contradiction” kelimesi tek başına zayıf kalır.

Durum ayırma (proof by cases)

Hipotez birkaç duruma ayrılıyorsa her durumu ayrı ispatla. Durumlar bütün olasılıkları kapsamalı (exhaustive).

Teorem. For every integer $n$, $n^2 + n$ is even.

Proof. Case 1: n is even, n = 2k.
  n² + n = 4k² + 2k = 2(2k² + k), even.
Case 2: n is odd, n = 2k + 1.
  n² + n = 4k² + 4k + 1 + 2k + 1 = 4k² + 6k + 2 = 2(2k² + 3k + 1), even.
Every integer is even or odd, so n² + n is even for all n.  ∎

Daha kısa yol: $n^2 + n = n(n+1)$, ardışık iki sayının çarpımı ve biri mutlaka çift. Ama bu cümleyi de gerekçelendirmen lazım; sınavda iki durumlu ispat daha güvenli.

Varlık ispatı ve karşı örnek

Existence proof (constructive): “There exists $x$ with $P(x)$” demek için somut bir $x$ göster. Örnek: “There is a positive integer that can be written as the sum of two cubes in two different ways.” $1729 = 1^3 + 12^3 = 9^3 + 10^3$. Bitti.

Nonconstructive: örneği göstermeden var olduğunu kanıtlamak (mesela iki durumdan birinin işe yaradığını gösterip hangisi olduğunu söylememek). Bu derste daha az çıkar.

Counterexample: $\forall x\, P(x)$‘in yanlış olduğunu göstermek için $P(c)$‘nin yanlış olduğu tek bir $c$ yeter. Tehlike tersi: kaç örnek denersen dene, $\forall$ iddiası örnekle ispatlanmaz. $n^2 - n + 11$ ilk on değerde asal, $n = 11$‘de çöküyor.

Diğer küçük şablonlar

• Vacuous proof: $p$ hiç doğru olamıyorsa $p \to q$ otomatik doğru. “If $n$ is an integer with $n^2 < 0$, then $n = 7$.” Hipotez hiçbir zaman sağlanmaz.
• Trivial proof: $q$ her zaman doğruysa $p \to q$ doğru.
• iff ispatı: $p \leftrightarrow q \equiv (p \to q) \land (q \to p)$. İki yönü ayrı başlıklarla yaz: ”(⇒)” ve ”(⇐)”. İkinci yön için contrapositive kullanmak serbest.

Hangi yöntemi seçeyim?

Sık yapılan hatalar