Prinsip Induksi Kuat

Selain Prinsip Induksi Matematika ‘biasa’ yang telah dibahas pada hari Sabtu yang lalu, ada Prinsip Induksi Kuat. Misalkan adalah pernyataan yang terkait dengan bilangan asli Prinsip Induksi Kuat berbunyi sebagai berikut: Jika

• benar, dan
• jika benar, maka benar,

maka benar untuk setiap bilangan asli

Baik Prinsip Induksi Matematika maupun Prinsip Induksi Kuat dapat diperumum untuk pernyataan dengan (alih-alih ) Persisnya, jika

• benar, dan
• jika benar, maka benar,

maka benar untuk setiap bilangan asli

Demikian juga jika

• benar, dan
• jika benar, maka benar,

maka benar untuk setiap bilangan asli

Contoh aplikasi Prinsip Induksi Kuat adalah dalam pembuktian Teorema Dasar Aritmetik, yang menyatakan bahwa setiap bilangan asli dapat dinyatakan secara tunggal sebagai hasil kali bilangan-bilangan prima.

Jelas bahwa pernyataan di atas benar untuk karena adalah bilangan prima dan Selanjutnya misalkan pernyataan benar untuk Kita akan menyelidiki kebenaran pernyataan untuk Jika adalah bilangan prima, maka pernyataan tentu saja benar. Jadi, misalkan bukan bilangan prima. Dalam hal ini, mempunyai faktor prima, sebutlah sehingga dengan Di sini mungkin merupakan bilangan komposit, tetapi — menurut hipotesis — dapat ditulis sebagai hasil kali bilangan-bilangan prima. Jadi, pun dapat dinyatakan sebagai hasil kali bilangan-bilangan prima.

*

Bandung, 09-02-2019