Widget HTML Atas

Induksi Matematika

Induksi matematika merupakan metode pembuktian yang penting dan akan sering digunakan di dalam matematika. Metode ini digunakan untuk membuktikan kevalidan suatu pernyataan yang berlaku untuk semua bilangan asli $\mathbb{N}$.

Induksi Matematika

Teorema Sifat Terurut Baik dari $\mathbb{N}$
Setiap subset tak kosong dari $\mathbb{N}$ mempunyai elemen terkecil.

Pernyataan yang lebih detail dari sifat ini adalah sebagai berikut: Jika $S$ adalah subset dari $\mathbb{N}$ dan $S \neq \emptyset$, maka terdapat elemen $m \in S$ sedemikian hingga $m \leq k$ untuk semua $k \in S$.

Prinsip Induksi Matematika Jika $S$ adalah subset dari $\mathbb{N}$ yang memiliki sifat-sifat:
(1). $1 \in S$
(2). Jika $k \in S$, maka $k + 1 \in S$ maka S = $\mathbb{N}$.

Bukti :

Jika diandaikan $S \neq \mathbb{N}$, maka himpunan $\mathbb{N}\backslash S$ tidak kosong, dan selanjutnya dengan Teorema , $\mathbb{N}\backslash S$ memuat elemen terkecil. Misalkan $m$ adalah elemen terkecil dari $\mathbb{N}\backslash S$. Berdasarkan hipotesis (1), $1 \in S$, maka $m \neq 1$. Selanjutnya $m > 1$, sehingga $m-1$ juga bilangan asli. Karena $m-1 < m$ dan karena $m$ elemen terkecil dari $\mathbb{N}$ sedemikian hingga $m \notin S$, maka $m-1$ di dalam $S$.


Sekarang, berdasarkan hipotesis (2) untuk elemen $k = m -1$ di dalam $S$, disimpulkan $k + 1 = (m-1) + 1 = m$ di dalam $S$. Kesimpulan ini kontradiksi dengan $m$ bukan elemen di $S$. Ini berarti pengandaian salah. Yang benar $S = N$.

Prinsip induksi matematika juga sering dinyatakan dengan rumusan sebagai berikut:

Untuk setiap $n \in \mathbb{N}$, misalkan $P(n)$ pernyataan yang bergantung pada $n$. Jika
(1') $P(1)$ benar
(2') Jika $P(k)$ benar, maka $P(k + 1)$ benar, maka $P(n)$ benar untuk semua $n \in \mathbb{N}$.
Hubungan dengan versi sebelumnya dibuat dengan memisalkan $S := \{n \in \mathbb{N} : P(n)\,\,\, \text{benar}\}$.


Contoh-contoh berikut memberikan gambaran bagaimana Prinsip Induksi Matematika digunakan untuk membuktikan pernyataan-pernyataan yang bergantung pada bilangan asli.


Sumber : Bartle, Sherbert. Introduction To Real Analysis 2ed John Wiley and Sons

No comments for "Induksi Matematika"