Pembuktian Prinsip Pengurutan yang Baik

Di postingan sebelumnya saya menyinggung prinsip pengurutan yang baik Well-ordering principle

Setiap himpunan tak kosong yang beranggotakan bilangan asli mempunyai elemen terkecil

Prnsip yang teramat jelas, yang terang benerang, sebagai contoh

  • A=\{10,15,17,19,20\}
  • B=\{3,6,9,12 \cdots \}
  • C= \{5,10,15,20 \cdots \}

Jelas ketiga himpunan di atas menpunyai elemen terkecil. Sedangkan I=(0,1), interval terbuka dari 0 sampai 1 tidak mempunyai elemen terkecil. Misalkan ada a \in I elemen terkecil dari I maka kita selalu bisa mengkontruksikan bilangan yang lebih kecil dari a yaitu \frac{a}{2}<a, tentu saja \frac{a}{2} \in I. Itu karena I berisikan anggota bilangan real bukan bilangan asli sehingga tidak berlaku prinsip pengurutan yang baik.

Bukti

Kita akan membuktikan secara kontradiksi dengan metode induksi.

Andaikan S himpunan tak kosong yang beranggotakan bilangan asli dan tidak mempunyai elemen terkecil.

Diberikan

R=\{x \in \mathbb{N}| x\leq s, \forall s \in S \}

Karena S tidak mempunyai elemen terkecil maka R\cap S = \emptyset. Andaikan saja m\in R\cap S maka m akan menjadi elemen terkecil di S padahal S tidak mempunyai elemen terkecil. Jadi jelas haruslah R\cap S = \emptyset. Jelas juga bahwa 1 \in R

Asumsi k\in R maka setiap bilangan asli yang kurang atau sama dengan k juga kurang atau sama dengan s untuk setiap s \in S. Itu berarti 1,2,3 \cdots k \in R, karena R\cap S = \emptyset maka 1,2,3 \cdots k \notin S.

Jika k+1 \in S maka k+1 akan menjadi elemen terkecil di S. Haruslah k+1 \in R

Dengan prinsip induksi matematika, berakibat R= \mathbb{N}. Artinya S = \emptyset yang kontradiksi dengan asumsi S bukan himpunan kosong. Oleh karena itu dapat disimpulkan setiap himpunan tak kosong yang berisikan bilangan asli haruslah mempunyai elemen terkecil.

\square

About Nursatria

Seorang Alumnus Matematika UGM, dengan ilmu yang didapat ketika kuliah (Padahal sering bolos kuliah :p ), saya menyebarkan virus matematika
This entry was posted in pembuktian, Teori Bilangan and tagged , , . Bookmark the permalink.

Silahkan, tinggalkan komentar

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s