CONTOH-CONTOH TEKNIK PEMBUKTIAN DALAM MATEMATIKA

TUGAS 2

Disusun sebagai Tugas Kelompok Mata Kuliah Filsafat dan Sejarah Matematika

Oleh:

K A D I R 0706197 (S3) SYARIFAH FADILLAH A. 0706877 (S3) YONANDI 0707196 (S3) YANRY BUDIANINGSIH 0705740 (S2) JAPAR SIDIK 0706357 (S2) A M R I 0706412 (S2)

PROGRAM STUDI S2 DAN S3 PENDIDIKAN MATEMATIKA SEKOLAH PASCASARJANA UPI BANDUNG

JANUARI 2008

1

A. BUKTI MATEMATIKA

Salah satu ciri khas ilmu matematika adalah bukti matematika dan

pembuktian matematis. Filsafat matematika berurusan dengan peran

bahasa dan logika matematika dalam pembuktian, dan dengan ilmu

matematika yang dapat dipandang sebagai suatu bahasa. Bukti dan

pembuktian dalam matematika menggunakan logika matematika namun

tidak dapat lepas dari penggunaan bahasa sehari-hari yang biasanya

mengandung kekaburan makna.

Suatu bukti atau pembuktian adalah suatu cara untuk memastikan

kebenaran suatu pernyataan. Suatu bukti matematika adalah suatu hasil

upaya untuk menunjukkan bahwa, dengan bertumpu pada aksioma-

aksioma tertentu dan dengan aturan-aturan logika matematika, suatu

pernyataan adalah benar. Bukti matematika adalah argumen yang

menggunakan logika, bukan bukti yang empiris.

Suatu bukti matematika adalah suatu urutan berantai penarikan

kesimpulan yang didasarkan pada suatu kumpulan aksioma dan sejumlah

teorema yang sudah dibuktikan, tunduk kepada aturan-aturan logika

matematika, dan berakhir dengan pernyataan yang akan dibuktikan.

Pernyataan [matematika] adalah suatu kalimat matematika yang

memiliki nilai kebenaran Benar atau Salah. (Kalimat itu strukturnya

adalah kalimat berita.)

Aksioma adalah pernyataan yang tidak dapat atau tidak perlu

dibuktikan. Dalam banyak cabang matematika sistem aksioma yang

dipakai sebagai dasar pembuktian adalah sistem aksioma ZFC, yaitu

sistem aksioma untuk teori himpunan Zermelo-Fraenkel yang ditambah

dengan Aksioma Pemilihan (Axiom of Choice). Pendekatan aksioma-dan-

bukti, yang dimulai oleh Euclides, sekarang disebut metode aksiomatik.

2

Sekumpulan aksioma disebut lengkap jika ia dapat digunakan

untuk membuktikan kebenaran atau ketakbenaran tiap pernyataan.

Sekumpulan aksioma disebut konsisten jika tidak ada pernyataan yang

dapat dibuktikan benar dan sekaligus salah.

Suatu pernyataan yang belum dapat dibuktikan secara matematis

namun memiliki bukti-bukti empiris dalam bentuk kasus-kasus dan

contoh, dinamakan konjektur.

Pernyataan yang memiliki bukti matematis, artinya telah

dibuktikan benar dengan berdasarkan aksioma-aksioma saja dan teorema-

teorema lain yang memenuhi aturan logika matematika, disebut teorema.

Jika suatu pernyataan adalah suatu teorema, maka ia berlaku umum dan

dapat digunakan sebagai dasar untuk membuktikan pernyataan-

pernyataan lain.

Suatu lema adalah pernyataan pendahuluan yang memiliki bukti

(disebut juga "teorema kecil") dan berguna untuk membuktikan

pernyataan baru.

Suatu teorema akibat (corrolary) adalah suatu teorema yang dapat

diturunkan dari suatu teorema dalam beberapa langkah saja.

Aturan penarikan kesimpulan (inference rules), atau deduksi logika

matematika, adalah aturan yang meramu aksioma dan pernyataan yang

benar untuk membentuk lebih banyak pernyataan yang benar.

B. BEBERAPA MACAM BUKTI MATEMATIKA

Pernyataan-pernyataan matematika dapat dibuktikan dengan:

1. Pembuktian langsung;

2. Pembuktian dengan induksi matematika;

3. Pembuktian dengan transposisi atau pembuktian dengan

kontrapositif;

4. Pembuktian dengan kontradiksi atau reductio ad absordum;

3

5. Pembuktian dengan konstruksi atau pembuktian dengan contoh;

6. Pembuktian dengan exhaustion;

7. Pembuktian probabilistik;

8. Pembuktian kombinatorik;

9. Pembuktian nonkonstruktif;

10. Bukti atau bukan-bukti;

11. Pembuktian sederhana.

Selain kesebelas bukti di atas, dalam matematika juga dikenal

beberapa bukti lain, yaitu:

12. Pembuktian dengan contoh penyangkal (Counter example);

13. Pembuktian terdefinisi dengan baik (well defined);

14. Pembuktian Pigeon Hole;

15. Pembuktian jika dan hanya jika / biimplikasi (if and only if); dan

16. Pembuktian Unwinding definition.

C. CONTOH-CONTOH METODE PEMBUKTIAN MATEMATIKA

Contoh-contoh semua metode pembuktian pernyataan matematika

di atas disajikan sebagai berikut.

1. Pembuktian langsung

Dalam pembuktian langsung, kesimpulan dapat dicapai dengan

mengkombinasi pernyataan yang akan dibuktikan, dengan logika

matematika, aksioma-aksioma, definisi, dan teorema-teorema yang sudah

ada.

Contoh:

Teorema: Jika a membagi b dan b membagi c, maka a membagi c

Bukti:

Berdasarkan definisi keterbagian, maka ada bilangan asli k1 dan k2

sedemikian sehingga b = a k1 dan c = b k2. Karena c = b k2 dan b = a k1,

maka c = a k1 k2.

4

Misalkan k = k1 k2; maka k adalah bilangan asli dan c = a k, sehingga

dengan definisi keterbagian disimpulkan a membagi c. ����

2. Pembuktian dengan Induksi Matematika

Pembuktian dengan cara ini menggunakan himpunan bilangan

bulat positif, untuk pembuktian kasus dasar, kemudian menerapkan

aturan induksi untuk kasus-kasus yang berikutnya, acapkali untuk tak

berhingga banyaknya kasus.

Himpunan bilangan bulat positif adalah Z+ = {1, 2, 3, ...}.

Ditetapkan bahwa P(n) adalah pernyataan matematika yang menyangkut

bilangan bulat positif n. Harus dipastikan bahwa:

i. P(1) adalah benar, artinya P(n) benar untuk n = 1;

ii. Jika diandaikan P(m) adalah benar untuk bilangan m ∈ Z+ maka

harus diperoleh bahwa P(m + 1) adalah benar. (Bilangan m + 1

adalah pemberikut dari m.)

Jika kedua syarat itu sudah dipenuhi maka disimpulkan pernyataan P(n)

adalah benar, atau berlaku, untuk semua bilangan bulat positif.

Contoh:

Gunakan induksi matematik untuk membuktikan bahwa jumlah n buah

bilangan ganjil positif pertama adalah n2.

Bukti:

(i) Basis induksi: Untuk n = 1, jumlah satu buah bilangan ganjil positif

pertama adalah 12 = 1. Ini benar karena jumlah satu buah bilangan

ganjil positif pertama adalah 1.

(ii) Langkah induksi: Andaikan p(n) benar, yaitu pernyataan

1 + 3 + 5 + … + (2n – 1) = n2

adalah benar (hipotesis induksi) [catat bahwa bilangan ganjil positif

ke-n adalah 2n – 1]. Akan ditunjukkan bahwa p(n +1) juga benar, yaitu

1 + 3 + 5 + … + (2n – 1) + (2n + 1) = (n + 1)2

5

juga benar. Hal ini dapat ditunjukkan sebagai berikut:

1 + 3 + 5 + … + (2n – 1) + (2n + 1)

= [1 + 3 + 5 + … + (2n – 1)] + (2n + 1)

= n2 + (2n + 1)

= n2 + 2n + 1

= (n + 1)2.

Terbukti bahwa juga berlaku untuk n+1.

Karena langkah basis dan langkah induksi keduanya telah diperlihatkan

benar, maka terbukti bahwa jumlah n buah bilangan ganjil positif

pertama adalah n2. ����

3. Pembuktian dengan transposisi

Cara pembuktian ini juga dinamakan pembuktian dengan

kontrapositif. Pembuktian ini memastikan bahwa pernyataan "Jika P,

maka Q" adalah benar dengan menunjukkan kebenaran pernyataan

kontrapositifnya, yaitu pernyataan "Jika Q tidak benar, maka P tidak

benar". Dalam lambang-lambang, ditulis ¬ Q ⇒ ¬ P eq P ⇒ Q.

Contoh:

Teorema

Jika x dan y adalah dua bilangan bulat di mana x + y genap, maka x dan y

memiliki parity yang sama.

Sebelum membuktikan teorema tersebut terlebih dahulu dikemukakan

definisi bilangan bulat ganjil, bilangan bulat genap, dan parity.

Definisi:

1. Bilangan bulat x disebut genap (atau ganjil) jika ada bilangan bulat

k lain sehingga x = 2k (atau 2k + 1).

2. Dua bilangan bulat dikatakan mempunyai parity-nya sama jika

kedua-duanya genap atau kedua-duanya ganjil

Bukti Teorema:

6

Kontrapositif dari teorema tersebut adalah: ”Jika x dan y adalah dua

bilangan bulat yang memiliki parity yang berbeda, maka x + y ganjil”.

Misalkan x dan y memiliki parity yang berbeda. Karena salah satu

bilangan bulat tersebut genap dan yang lainnya ganjil, maka dengan tidak

mengurangi keumuman, misalkan x genap dan y ganjil. Jadi terdapat

bilangan bulat k dan m sedemikian sehingga x = 2k dan y = 2m+1. Jika x

dan y dijumlahkan, maka akan diperoleh

x + y = (2k) + (2m + 1) = 2(k+m) + 1

yang menurut definisi merupakan bilangan bulat ganjil. ����

4. Pembuktian dengan kontradiksi

Pembuktian dengan cara ini dinamakan juga pembuktian reductio

ad absordum (reduksi sehingga absurd). Suatu pernyataan ingin dibuktikan

benar. Jika diandaikan bahwa pernyataan itu tidak benar sehingga akan

pasti memunculkan kontradiksi, maka disimpulkan bahwa pernyataan

yang akan dibuktikan adalah benar. Contoh pembuktian dengan cara ini

adalah pembuktian bahwa 2 adalah bilangan irasional, akar bilangan

irasional adalah bilangan irasional juga, dan bahwa tidak ada bilangan

prima terbesar atau bilangan prima tidak berhingga.

Contoh:

Teorema : Terdapat tak berhingga banyak bilangan prima.

Bukti:

Asumsikan bilangan prima itu berhingga dan misalkan bilangan-bilangan

prima itu adalah p1, p2, ..., pn. Misalkan bilangan q = p1p2... pn + 1

Maka q adalah prima atau komposit. Jika q dibagi oleh sebarang bilangan

prima pi, maka hasilnya akan selalu bersisa 1 untuk setiap i = 1, 2, ..., n.

Jadi, q bukan komposit. Oleh karena itu disimpulkan bahwa q adalah

bilangan prima yang berbeda dengan bilangan prima p1, p2, ..., pn. Hal

7

ini kontradiksi dengan asumsi bahwa semua bilangan prima tersebut

adalah p1, p2 ..., pn. ����

5. Pembuktian dengan konstruksi

Cara pembuktian dengan konstruksi juga dinamakan pembuktian

dengan contoh. Pembuktian ini membangun suatu contoh kongkrit yang

memiliki sifat khusus untuk menunjukkan bahwa ada sesuatu yang lain

yang memiliki sifat itu. Pembuktian ini menetapkan bahwa suatu objek

tertentu itu ada dengan memberikan cara-cara menemukannya.

Contoh:

Teorema:

Terdapat bilangan rasional antara akar kuadrat dari 10100 dan akar

kuadrat dari 10100 + 1

Bukti:

Akar kuadrat dari 10100 adalah 1050. Dengan cara coba-coba, misalkan x =

10 50 + 10 -51, yang jelas merupakan bilangan rasional yang lebih besar dari

akar kuadrat dari 10100. Untuk membuktikan x lebih kecil dari akar

kuadrat dari 10100+1, kita hitung

x2 = (1050 + 10-51)2 = 10100 + (2) 10-1 + 10-102

yang jelas lebih kecil dari 10100+1. ����

6. Pembuktian dengan exhaustion

Dalam pembuktian dengan cara ini, kesimpulan pernyataan

dipastikan atau ditetapkan dengan membagi-baginya menjadi sejumlah

berhingga kasus dan tiap kasus dibuktikan kebenarannya. Seringkali

banyaknya kasus adalah besar sekali. Untuk pembuktian yang pertama

Masalah Empat Wama, pembuktian dengan cara exhaustion ini

menggunakan 1936 buah kasus dan tiap kasus harus dibuktikan

tersendiri. Pembuktian ini dipandang kontroversial karena sebagian besar

8

dari kasus itu dikerjakan dengan menggunakan komputer, bukan dengan

tangan. Pembuktian mutakhir masalah ini sekarang masih menggunakan

600 kasus.

Contoh:

Teorema:

Jika n adalah bilangan bulat positif, maka n7 - n dapat dibagi oleh 7.

Bukti:

Pertama faktorkan n7 – n sebagai berikut:

n7 - n = n(n6 - 1) = n(n3 - 1)(n3 + 1) = n(n - 1) (n2 + n + 1) (n + 1)(n2 - n + 1).

Terdapat 7 kasus yang harus dipertimbangkan, bergantung pada n = 7q+r

di mana r = 0, 1, 2, 3, 4, 5, 6, 7.

Kasus 1: n = 7q.

Maka n7 – n memiliki n faktor yang dapat dibagi oleh 7.

Kasus 2: n = 7q + 1.

Maka n7 - n memiliki n - 1 = 7q faktor yang dapat dibagi oleh 7.

Kasus 3: n = 7q + 2.

Maka faktor n2 + n + 1 = (7q + 2)2 + (7q+2) + 1 = 49 q2 + 35 q + 7 jelas

dapat dibagi oleh 7.

Kasus 4: n = 7q + 3.

Maka faktor n2 - n + 1 = (7q + 3)2 - (7q+3) + 1 = 49 q2 + 35 q + 7 jelas

dapat dibagi oleh 7.

Kasus 5: n = 7q + 4.

Maka faktor n2 + n + 1 = (7q + 4)2 + (7q+4) + 1 = 49 q2 + 63 q + 21 jelas

dapat dibagi oleh 7.

Kasus 6: n = 7q + 5.

Maka faktor n2 - n + 1 = (7q + 5)2 - (7q+5) + 1 = 49 q2 + 63 q + 21 jelas

dapat dibagi oleh 7.

Kasus 7: n = 7q + 6.

Maka faktor n + 1 = 7q+7 jelas dapat dibagi oleh 7. ����

9

7. Pembuktian probabilistik

Dalam cara pembuktian ini, suatu contoh dibuktikan dengan cara

teori probabilitas, bukan dengan argumen bahwa suatu teorema

"mungkin" benar. Pembuktian probabilistik, seperti halnya pembuktian

dengan konstruksi, adalah salah satu pendekatan untuk membuktikan

teorema eksistensi.

Contoh:

Misalkan kita mempunyai grup lengkap pada n titik sudut (vertices). Akan

ditunjukkan (untuk nilai n yang cukup kecil) bahwa kemungkinan untuk

mewarnai sisi-sisi graph dalam dua warna (misalnya merah dan biru)

sedemikian sehingga subgrup yang tidak lengkap pada r titik sudut

adalah monokrom (setiap sisi berwarna sama).

Bukti:

Untuk membuktikan hal tersebut, warnai graph secara acak. Warna setiap

sisi saling bebas dengan peluang ½ untuk yang berwarna biru dan ½

untuk yang berwarna merah. Banyaknya subgraph monokromatik yang

diharapkan pada r titik sudut sebagai berikut:

Untuk setiap himpunan S dari r titik sudut graph, definisikan variabel

X(S) = 1 jika setiap sisi memiliki r titik sudut berwarna sama, dan 0 untuk

hal lainnya. Banyaknya monokromatik r subgraph adalah jumlah X(S)

untuk semua subset yang mungkin. Untuk setiap S, nilai harapan dari

X(S) adalah peluang bahwa semua

2

r sisi dalam S berwarna sama,

−

⋅ 222r

(faktor dari 2 muncul karena terdapat dua kemungkinan warna).

Hal ini benar untuk setiap subset yang mungkin dari C(n, r) yang telah

dipilih, sehingga jumlah E[X(S)] untuk semua S adalah

−

212

r

r

n.

10

Jumlah dari suatu ekspektasi adalah espektasi dari jumlah (regardless of

whether the variables are independent), sehingga ekspektasi dari jumlah

(banyaknya espektasi dari r subgraph monokromatik) adalah

−

212

r

r

n.

Perhatikan apa yang terjadi jika nilai ini lebih kecil dari 1. Banyaknya r

subgraph monokromatik dalam pewarnaan acak kita akan selalu bernilai

bulat, sehingga paling sedikit satu warna yang kurang dari nilai yang

diharapkan. Tetapi hanya bilangan bulat 0 yang memenuhi kriteria ini.

Jadi jika 122

−

<r

)r,n(C , beberapa warna sesuai dengan kriteria yang

diinginkan. Berdasarkan definisi, R(r, r; 2) harus lebih besar dari n. Secara

khusus, R(r, r; 2) harus meningkat sedikitnya secara eksponensial

terhadap r. ����

8. Pembuktian kombinatorik

Pembuktian cara ini menentukan keekuivalenan berbagai

pernyataan dengan menunjukkan bahwa pernyataan-pernyataan itu

menghitung banyaknya objek yang sama dengan berbagai cara. Biasanya

digunakan pemetaan bijeksi (satu-satu-pada) untuk menunjukkan bahwa

dua interpretasi menghasilkan hasil yang sama.

Contoh: Perhitungan Ganda

Suatu sub komisi beranggota k dipilih dari suatu komisi beranggota n,

dan kemudian satu anggota k dari sub komisi dipilih untuk mendapatkan

kursi. Banyaknya cara untuk melakukan ini adalah kk

n

.

Sebagai alternatif, pertama pilih kursi dari semua n anggota komisi asal dan

kemudian pilih k – 1 anggota sub komisi lainnya di antara n - 1 anggota komisi

asal yang lainnya. Banyaknya cara untuk melakukan ini adalah

−−

1

1

k

nn .

11

Jadi dapat disimpulkan bahwa

−−

=

1

1

k

nnk

k

n. ����

Teknik serupa digunakan untuk membuktikan identitas Vandermonde.

Bukti Bijektif

Misalkan kita ingin menunjukkan bahwa banyaknya subset berukuran k

dari suatu himpuan berukuran n adaah sama dengan banyaknya subset

berukuran (n – k) dari suatu himpuan berukuran n, yaitu bahwa

−=

kn

n

k

n.

Hal ini dapat dicapai dengan memperlihatkan suatu bijeksi antara

himpunan dari semua subset berukuran k dan himpunan semua subset

berukuran (n - k). Bijeksi tersebut - mungkin paling sederhana - adalah

korespondensi antara setiap subset berukuran k dengan komplemennya

relatif terhadap himpunan berukuran n yang lebih besar. ����

9. Pembuktian nonkonstruktif

Pembuktian ini menetapkan bahwa suatu objek tertentu

matematika harus ada (harus eksis). misalnya "Ada S yang memenuhi

f(S)" tanpa menunjukkan bagaimana objek itu dapat ditemukan atau

dikonstruksi. Biasanya bentuk bukti ini seperti bukti dengan kontradiksi

yang menunjukkan bahwa ketiadaan suatu objek adalah tidak mungkin.

Contoh:

Akan dibuktikan dengan cara nonkonstruktif bahwa ”Terdapat bilangan

irasional a dan b sedemikian sehingga ab rasional”.

Bukti:

Ingat bahwa 2 adalah irasional dan 2 adalah rasional. Misalkan q =

2 2 . Akan diperiksa, apakah q rasional atau irasional.

Jika q rasional, maka teorema benar, dengan a dan b keduanya 2 .

12

Jika q irasional, maka teorema benar, dengan a 2 2 dan b 2 , karena

( ) 2222

2222 ==

⋅= 2. ����

Karena nilai a dan b tidak diketahui (sebab tidak diketahui kapan q

irasional), maka bukti ini nonkonstruktif. Pernyataan "Apakah q rasional

atau irasional", dari bukti di atas, adalah suatu penyederhanaan dari law of

excluded middle, yang tidak valid dalam pembuktian konstruktif. Dengan

kata lain, bukti konstruktif dari teorema yang sama akan memberikan

suatu contoh yang aktual, seperti: log29 adalah bilangan irasional menurut

faktorisasi tunggal dan 3 jelas merupakan bilangan rasional.

10. Bukti atau bukan-bukti

Dalam matematika ada pernyataan yang tidak dapat dibuktikan

dan tidak dapat disanggah dengan hanya menggunakan sistem aksioma

ZFC saja. Contohnya adalah Teorema Ketaklengkapan Pertama Godel

(Godel's First Incompleteness Theorem) yang berkaitan dengan Hipotesis

Kontinuum. Tidaklah selalu mudah suatu pernyataan dapat dibuktikan

dengan suatu sistem aksioma karena mungkin akan melibatkan banyak

langkah yang sangat teknis.

Ketidakmungkinan bukti dan bantahan (di ZFC). Cantor percaya

hipotesis continuum benar dan mencoba selama bertahun-tahun untuk

membuktikannya, tapi sia-sia. Hal ini menjadi utama pada daftar

pertanyaan terbuka yang penting dari David Hilbert yang diperkenalkan

pada International Mathematical Congress tahun 1900 di Paris. Axiomatic set

theory pada saat itu belum dirumuskan.

Kurt Gödel menunjukkan di tahun 1940 bahwa hipotesis

continuum (CH) tidak bisa dibuktikan-balik dari standar teori himpunan

Zermelo-Fraenkel (ZF), sekalipun aksioma pemilihan itu diadopsi (ZFC).

Paul Cohen menunjukkan di 1963 bahwa CH tidak bisa dibuktikan dari

13

aksioma-aksioma yang sama. Karenanya, CH independen pada ZFC.

Kedua hasil ini berasumsi bahwa aksioma Zermelo-Fraenkel tidak

bertentangan; asumsi ini diterima kebenarannya secara luas/umum.

Hipotesis continuum bukan pernyataan pertama yang

menunjukkan independensi dari ZFC. Satu konsekuensi kemudian dari

teorema ketidaklengkapan Gödel, yang diterbitkan dalam 1931, adalah

bahwa ada suatu pernyataan formal kekonsistenan ZFC yang independen

pada ZFC. Statemen kekonsistenan ini berasal dari suatu yang

metamatematis, dibanding sifat matematis semata. Hipotesis continuum

dan aksioma pemilihan adalah di antara pernyataan-pernyataan

matematis pertama yang menunjukkan kebebasan teori himpunan ZF.

Pembuktian independensi ini tidak lengkap sampai Paul Cohen

mengembangkannya pada tahun 1960-an.

Hipotesis Continuum berhubungan erat dengan banyak statemen

di dalam analisis, topologi himpunan titik, dan teori ukuran. Sebagai hasil

dari keindependenannya, banyak konjektur substansif dalam lapangan

yang sudah ditunjukkan keindependenannya dengan baik.

Sampai sejauh ini, CH indepenen terhadap semua large cardinal

axioms yang dikenal dalam konteks ZFC.

11. Pembuktian sederhana

Pembuktian sederhana biasanya tidak menggunakan analisis yang

rumit. Di masa lalu ada teorema-teorema khusus, misalnya Teorema

Bilangan Prima, yang dibuktikan dengan menggunakan "matematika

tinggi". Namun dalam perjalanan waktu, bukti-bukti itu telah dapat

dibuktikan ulang dengan teknik-teknik yang sederhana.

Contoh:

Akan dibuktikan bahwa ”Kuadrat setiap bilangan bulat positif berbentuk

3k atau 3k + 1”.

14

Bukti:

Misalkan a bilangan bulat positif. Akan dibuktikan bahwa a = 3k atau a ≠

3k, yaitu a = 3k + 1 atau a = 3k + 2.

a. Jika a kelipatan 3, maka a = 3m sehingga a2 = 9m2 = 3(3m2). Misalkan k

= 3m2, maka a = 3k.

b. Jika a bukan kelipatan 3, maka a berbentuk a = 3m +1 atau a = 3m + 2.

Untuk a = 3m + 1, maka a2 = (3m + 1)2 = 9m2 + 6m + 1 = 3(3m2+ 2m) + 1.

Misalkan k = 3m2 + 2m, maka a = 3k + 1.

Untuk a = 3m + 2, maka a2 =(3m + 2)2 = 9m2 + 12m + 4 = 3(3m2+ 4m+1)+1.

Misalkan k = 3m2 + 4m + 1, maka a = 3k + 1.

Dengan demikian terbukti bahwa kuadrat setiap bilangan bulat positif

berbentuk 3k atau 3k + 1. ����

12. Pembuktian dengan counter example

Counter example memiliki peran yang sangat penting dalam

matematika. Suatu pembuktian yang rumit mungkin merupakan satu-

satunya cara untuk menunjukkan kebenaran teorema tertentu, sebuah

counter example tunggal adalah cukup untuk menyangkal kebenaran dari

suatu pernyataan.

Contoh:

Bentuk , n bilangan bulat positif merupakan bilangan prima.

Bukti:

Untuk n = 1, 2, 3, dan 4 diperoleh merupakan bilangan prima,

tetapi untuk diperoleh ,

memiliki faktor lain selain 1 dan dirinya sendiri. Dengan kata lain,

bukan bilangan prima tapi bilangan komposit. ����

Kesimpulannya: ketika mensubstitusikan suatu bilangan ke bentuk

, tidak bisa mengasumsikan itu merupakan bilangan prima atau

15

komposit, kecuali jika diketahui secara pasti dengan alasan yang jelas. Hal

ini berlaku juga dalam pembuktian konvers dari suatu pernyataan.

Konvers dari pernyataan “Jika P maka Q” adalah pernyataan “Jika Q

maka P”

Contoh: Bilangan rasional dan irrasional

Jika dan adalah bilangan rasional, maka tentukan bentuk

Bukti:

Misalkan a dan b bilangan rasional, yaitu dan untuk suatu

bilangan bulat tertentu dengan tidak nol. Jumlah dari

Menurut definisi, bentuk juga merupakan bilangan rasional.

Konversi pernyataan di atas: ”Jika dan adalah bilangan real

sedemikian sehingga adalah bilangan rasional, maka dan adalah

bilangan rasional”. Pernyataan ini adalah salah. Hal ini dapat dibuktikan

dengan counter example: Ambil dan dua bilangan

irasional, tetapi yang merupakan bilangan rasional. ����

13. Pembuktian well defined (terdefinisi dengan baik)

Untuk memahami pembuktian bahwa sesuatu itu terdefinisi

dengan baik, perhatikan contoh berikut.

Contoh: Aritmetika Kongruensi

Untuk suatu bilangan bulat dan bilangan bulat positif , dikatakan

kongruen modulo (ditulis mod ), jika habis dibagi

oleh . Dengan kata lain ada bilangan bulat sedemikian sehingga

. Contoh, mod karena .

Bilangan dan merupakan perwakilan ‘bilangan’ yang sama dalam

16

modulo . Jadi ‘bilangan’ adalah suatu sistem dan di dalamnya adalah

. Contoh, m = 0 mod(m) sehingga 0 tidak dimasukkan.

Hal ini menghasilkan perhitungan dengan ‘bilangan’ baru. Contoh:

definisikan penjumlahan modulo dengan penjumlahan standar. Tetapi

sangat memungkinkan munculnya masalah. Jika mod dan

mod , akan didapatkan hasil yang sama, yaitu penjumlahan

atau .

Teorema

Penjumlahan adalah well defined modulo , yaitu, jika mod dan

mod , maka mod .

Bukti:

Akan ditunjukkan bahwa ada suatu bilangan bulat sedemikian sehingga

. Karena mod dan mod , maka

ada bilangan bulat dan sedemikian sehingga dan

. Dengan demikian, .

Misalkan , maka sehingga disimpulkan

mod . ����

Berdasarkan contoh di atas, well defined berarti tidak menyebabkan

suatu inkonsistensi internal dan bebas kontradiksi. Untuk memahami

dengan baik ide ini, perhatikan contoh yang tidak well defined berikut.

Contoh: Tidak well defined

Gunakan perhitungan modulo, dengan pembagian. Perhatikan bilangan

bulat dengan genap. Misalkan dalam perhitungan modulo 2,

maka menghasilkan solusi tunggal untuk persamaan mod

. Tetapi, ada beberapa bilangan bulat yang memenuhi persamaan

tersebut. Jadi, tidak well defined.

17

Contoh: Fungsi modulo

Dalam sistem bilangan modulo , diwakili oleh yang

secara tradisional dikatakan himpunan . Misalkan, memiliki 4

anggota, yaitu . Semua bilangan bulat yang lain hanya

merupakan nama lain dari keempat bilangan itu. Contoh, mod

dan mod .

Teorema

Fungsi dengan adalah well defined.

Bukti:

Akan dibuktikan mod , yaitu habis dibagi 4.

Misalkan, mod , maka habis dibagi 4. Perhatikan bahwa,

. Karena a – b habis dibagi 4, maka 2(a – b)

juga habis dibagi 4, sehingga mod (4). ����

14. Pembuktian Pigeon Hole (Lubang merpati)

Prinsip Pigeon Hole (Lubang Merpati) tidak lebih dari komentar

yang jelas: ”jika memiliki sedikit lubang merpati daripada merpati dan

semua merpati akan dimasukkan ke dalam lubangnya, maka hasilnya

haruslah minimal satu lubang merpati dengan lebih dari satu merpati. Hal

itu mengejutkan untuk digunakan menjadi suatu strategi pembuktian.

Contoh:

Teorema

Di antara setiap bilangan bulat positif , ada dua yang berbeda yang

dapat dibagi oleh .

Bukti

Misalkan terdapat bilangan-bilangan . Untuk setiap

diperoleh sisa hasil bagi oleh . (Jadi mod dan

hanya bernilai ). Ada kemungkinan nilai untuk setiap

18

, tetapi ada N ri. Dengan menggunakan aturan lubang merpati, ada dua

ri yang sama, untuk beberapa pasangan dan . Tetapi kemudian

ai yang bersesuaian memiliki sisa yang sama ketika dibagi oleh . Jadi

habis dibagi oleh . ����

15. Pembuktian Jika dan Hanya Jika

Beberapa teorema berbentuk “P jika dan hanya jika Q”. Dengan

kata lain “Q adalah syarat perlu dan cukup untuk P”. Hal tersebut berarti

dua hal: “Jika P maka Q” dan “Jika Q maka P”. Jadi untuk membuktikan

teorema “Jika dan hanya jika”, harus dibuktikan kedua implikasi tersebut.

Contoh: Pembagian

Dalam contoh ini digunakan fakta yang sering digunakan pada bilangan

bulat, yaitu algoritma pembagian:”jika dan bilangan bulat, maka ada

dua bilangan bulat lain dan , dimana sedemikian sehingga

. Contoh, jika dan , maka .

Teorema

Jika suatu bilangan bulat, maka tidak habis dibagi oleh jika dan

hanya jika habis dibagi oleh .

Bukti

(�) Akan dibuktikan jika a tidak habis dibagi 3, maka a2 - 1 habis dibagi 3.

Misalkan a = 3q + r denga r = 0, 1, atau 2. Karena a tidak habis dibagi 3,

maka r ≠ 0. Jika r = 1, maka a – 1 = 3q sehingga a2 – 1 = (a – 1) (a + 1) habis

dibagi 3. Jika r = 2, maka a2 = (3q + 2)2 = 9q2 + 12q + 4 atau a2 – 1 = 9q2 +

12q + 3 = 3 (3q2 + 4q + 1) yang habis dibagi 3.

() Akan dibuktikan jika a2 - 1 habis dibagi 3, maka a tidak habis dibagi 3.

Karena a2 – 1 habis dibagi 3, maka habis dibagi 3.

19

Karena adalah bilangan prima, maka harus habis membagi atau

. Dalam kasus lain, jelas bahwa tidak habis membagi .

Berdasarkan kedua pembuktian di atas disimpulkan teorema terbukti. ����

16. Pembuktian unwinding definition (menguraikan definisi)

Satu dari banyak pertanyaan yang sering dikeluhkan siswa dalam

pembuktian adalah “Bagaimana memulainya?”. Jawabannya sederhana,

yaitu: uraikan definisi. Pertama, perhatikan apa yang ditanyakan dalam

pembuktian. Apakah semua sudah melibatkan yang sudah didefinisikan

(dalam kuliah atau dalam teks atau dalam masalahnya)? Tulis definisinya.

Apa yang diasumsikan? Apakah melibatkan definisi? Jika ya, tulis

kembali. Kadang-kadang teorema sesuai dengan permasalahannya. Jika

ya, tuliskan. Jangan takut melakukan sesuatu yang diketahui untuk

mencoba membuktikannya.

Contoh: Faktor persekutuan terbesar (FPB)

FPB dari dua bilangan bulat positif dan adalah bilangan gcd

yang memenuhi dua sifat: (1) habis membagi dan , (2) jika adalah

bilangan bulat positif lain yang habis membagi dan , maka .

Dengan kata lain gcd seperti operasi biner.

Teorema

Operasi biner gcd adalah asosiatif, yaitu untuk bilangan bulat positif

dan

gcd(gcd( ), ) = gcd( ,gcd( ))

Uraian Strategi

Apa yang harus dibuktikan? Dua gcd adalah sama. Dari mana memulai?

Misalkan adalah gcd nya, gcd(gcd( ), ). Apa artinya? Hal itu

berarti (1) habis membagi gcd( ) dan , (2) Jika adalah bilangan

bulat positif lain yang habis membagi gcd( ) dan maka . Harus

20

dibuktikan = gcd( ,gcd( )). Apa artinya? Harus membuktikan dua hal

(1) habis membagi dan gcd , (2) Jika adalah bilangan bulat

positif lain yang habis membagi dan gcd maka .

(1) membagi gcd( ), harus membagi . Diketahui membagi ,

jadi harus membagi gcd .

(2) Sekarang misalkan membagi dan gcd . Maka,

membagi dan , jadi membagi gcd( ) juga. Tetapi kemudian

asumsinya . Dan ini semua memerlukan pembuktian.

Bukti Teorema

Misalkan Maka membagi dan , dan akibatnya

membagi dan gcd( ). Jika membagi dan gcd( ), maka harus

membagi gcd( ) dan , dan akibatnya . Jadi gcd( , gcd( )).����

21

Catatan

Acapkali di akhir penulisan pembuktian, ada tulisan "QED". Ini artinya

adalah Quod Erat Demonstrandum, yaitu bahasa Latin untuk "yaitu yang

diminta untuk dibuktikan". Sering juga tulisan QED itu diganti dengan

halmos atau nisan, lambang kecil persegi panjang tegak, � atau kotak kecil

kosong ���� , yang menandai berakhirnya pembuktian.

22

Daftar Pustaka

Albert R. Meyer (2007). Course Notes, Week 1, 6.042J/18.062], Spring '07:

Albert R. Meyer, Radhika Nagpal (2002). Course Notes 1, 6.042J/18.062J, Fall '02: Mathematics for Computer Science. Massachusetts Institute of Technology.

Math Forum Ask Dr_ Math FAQ False Proofs and Classic Fallacies. http://mathforum.org/dr.math/faq/faq.false.proof.html. Online. Diakses 28 Nopember 2007.

Mathematics for Computer Science. Revised March 22, 2007, Massachusetts Institute of Technology.

Proofs in Mathematics. http://www.cut-the-knot.org/proofs/index.shtml. Online. Diakses 28 Nopember 2007

Proofs Without Words. http://www.cut-the-knot.org/ctk/pww.shtml. Online. Diakses 28 Nopember 2007.

Pythagorean Theorem. http://www.cut-the-knot.org/pythagoras/index. shtml. Online. Diakses 28 Nopember 2007.

Randomness and Mathematical Proof. http://www.umcs.maine.edu/ ~chaitin/sciamer.html. Online. Diakses 28 Nopember 2007.

The nature of mathematical proof. http://www.royalsoc.ac.uk/ downloaddoc.asp?id=1547. Online. Diakses 28 Nopember 2007.

Wikipedia. http://en.wikipedia.org/wiki/Mathematical proof. Online. Diakses 26 September 2007.

Wikipedia. http://en.wikipedia.org/wiki/Mathematical_proof. Online. Dikases 28 Nopember 2007.

Wikipedia. http://id.wikipedia.org/wiki/Matematika. Online. Diakses 28 Nopember 2007.

23

Lampiran I: Sistem Aksioma Zermelo-Fraenkel dengan Aksioma Pemilihan (Axiom of Choice), ZFC

Aksioma Ekstensionalitas

Dua himpunan adalah sama jika keduanya memiliki anggota yang sama.

( ) yxyzxzz =⇒∈⇔∈∀ }{

Aksioma Pasangan

Untuk sebarang dua himpunan x dan y, ada suatu himpunan {x,y} yang

anggotanya hanyalah x dan y itu.

Aksioma Gabungan

Gabungan suatu kumpulan himpunan, z, adalah himpunan juga.

( ) ( )( )[ ][ ] uxzyyxyxu ∈⇔∈∧∈∃∀∃

Aksioma Himpunan Takberhingga

Ada suatu himpunan takberhingga, khususnya suatu himpunan

takkosong x sedemikian sehingga untuk sebarang himpunan y ∈ x,

himpunan {y} adalah juga anggota himpunan x.

Aksioma Subhimpunan, Aksioma Himpunan Bagian

Untuk sebarang himpunan x dan sebarang pernyataan P(y), ada suatu

himpunan yang anggotanya adalah khusus unsur y e x yang memenuhi

pernyataan P(y).

Aksioma Himpunan Kuasa

Semua subhimpunan suatu himpunan membentuk sebuah himpunan. Aksioma Penggantian

Peta sebuah himpunan oleh suatu fungsi, adalah sebuah himpunan. Aksioma Dasar, Aksioma Fondasi

Untuk tiap himpunan takkosong x, ada himpunan y ∈ x sedemikian

sehingga x dan y merupakan himpunan lepas (disjoin). (Aksioma yang

24

sangat teknis ini bertujuan menangkap pengertian bahwa himpunan

dibangun secara bertahap dari himpunan yang lebih sederhana.

Khususnya, aksioma ini mencegah suatu himpunan dari menjadi

anggotanya sendiri.)

Aksioma Pemilihan. Axiom of Choice

Sebuah anggota dapat dipilih dari tiap himpunan dalam suatu kumpulan

himpunan takkosong. Lebih khusus lagi, jika x adalah suatu himpunan,

dan tiap anggota dari x adalah himpunan yang takkosong, maka ada

suatu fungsi pemilihan, g, sedemikian sehingga g(y) ∈ y untuk tiap y ∈x.

25

Lampiran II: Himpunan Bilangan

Secara intuitif, himpunan adalah kumpulan objek; objek yang terkandung

dalam himpunan disebut anggota, unsur, atau elemen himpunan.

Beberapa himpunan bilangan dan lambangnya yang sering digunakan

dalam matematika adalah yang berikut ini:

R : Himpunan bilangan real,

Q : Himpunan bilangan rasional, dan Q adalah himpunan semua

bilangan yang berbentuk q

pdengan p dan q bilangan bulat serta

q ≠ 0.

Z : Himpunan bilangan bulat, dan Z ={..., - 2, -1, 0, 1, 2, ...}

N : Himpunan bilangan asli, atau himpunan bilangan bulat tak

negatif, dan N=(0, 1, 2, 3, ...}

Z+ : Himpunan bilangan bulat positif, dan Z+ = {l, 2, 3, ...}

Z+ ⊂ N ⊂ Z ⊂ Q ⊂ R