Urutan rapi

Dalam matematika, sebuah urutan rapi atau relasi rapi) pada sebuah himpunan  adalah sebuah urutan total pada  dengan sifat bahwa setiap himpunan bagian takkosong  memiliki sebuah unsur terkecil dalam urutannya. Himpunan  bersama dengan relasi urutan rapi kemudian disebut sebuah himpunan terurut rapi. Dalam beberapa artikel dan buku ajar akademik, istilah ini sebagai gantinya ditulis sebagai urut rapi, terurut rapi, dan pengurutan rapi.

Setiap himpunan terurut rapi takkosong memiliki sebuah unsur terkecil. Setiap unsur  mengenai sebuah himpunan terurut rapi, kecuali sebuah unsur terbesar mungkin; memiliki sebuah penerus tunggal (unsur selanjutnya), yaitu unsur terkecil dari himpunan bagian semua unsur lebih besar dari . Mereka mungkin menjadi unsur-unsur selain unsur terkecil yang tidak memiliki pendahulunya (lihat Bilangan asli di bawah untuk sebuah contoh). Dalam sebuah himpunan terurut , setiap himpunan bagian  yang memiliki sebuah batas atas memiliki sebuah batas atas terkecil, yaitu unsur terkecil dari himpunan bagian semua batas atas  di .

Jika  adalah sebuah urutan rapi taksempurna, maka  adalah sebuah urutan rapi sempurna. Sebuah hubungan ialah sebuah urutan rapi sempurna jika dan hanya jika merupakan sebuah urutan total sempurna beralasan. Perbedaan antara urutan rapi sempurna dan taksempurna sering kali diabaikan ketika mereka dengan mudah melakukan antarubahan.

Setiap himpunan terurut rapi adalah isomorfik urutan dengan tunggal ke sebuah bilangan ordinal tunggal, disebut tipe urutan dari himpunan terurut rapi. Teorema urutan rapi, yang setara dengan aksioma pemilihan, menyatakan bahwa setiap himpunan dapat menjadi terurut rapi. Jika sebuah himpunan adalah terurut rapi (atau bahkan jika hanya mengakui sebuah relasi beralasan), teknik pembuktian induksi transitif dapat digunakan bahwa sebuah pernyataan yang diberikan adalah benar untuk semua unsur dari himpunan.

Pengamatannya bahwa bilangan asli adalah terurut rapi oleh relasi lebih kecil dari biasa secara umum disebut prinsip urutan rapi (untuk bilangan asli).

Bilangan ordinal 
Setiap himpunan terurut rapi adalah isomorfik urutan dengan tunggal ke sebuah bilangan ordinal tunggal, disebut tipe urutan dari himpunan terurut rapi. Posisi setiap unsur dalam himpunan terurut juga diberikan oleh sebuah bilangan ordinal. Dalam kasus himpunan hingga, operasi dasar pencacahan, untuk mencari bilangan ordinal objek khusus, atau untuk mencari objek dengan sebuah bilangan ordinal khusus, berpadan dengan menunjukkan bilangan ordinal satu oleh satu ke objeknya. Ukuran (jumlah unsur, bilangan kardinal) himpunan hingga sama dengan tipe urutan. Menghitung dalam sehari-hari berarti biasanya dimulai dari satu, jadi ini menunjukkan untuk setiap objek, ukuran dari ruas awal dengan objek itu sebagai unsur terakhir. Perhatikan bahwa bilangan-bilangan ini lebih dari satu, bilangan ordinal formal menurut urutan isomorfik, karena ini sama dengan bilangan objek lebih awal (yang berpadan dengan menghitung dari nol). Demikian untuk  terhingga, ungkapan "unsur ke-" mengenai sebuah himpunan teruru rapi membutuhkan konteks untuk mengetahui apakah ini menghitung dari nol atau satu. Dalam sebuah notasi "unsur ke-" dimana  dapat juga menjadi sebuah ordinal takhingga, ini akan biasanya hitung dari nol.

Untuk sebuah himpunan takhingga, tipe urutan menentukan kekardinalan, tapi bukan sebaliknya: himpunan terurut rapi mengenai sebuah kekardinalan khusus dapat memiliki banyak tipe urutan yang berbeda, lihat Bagian#Bilangan asli untuk sebuah contoh yang sederhana. Untuk sebuah himpunan takhingga tercacah, himpunan tipe urutan mungkin bahkan taktercacahkan.

Contoh dan contoh lawan

Bilangan asli 
Pengurutan standar  dari bilangan asli adalah sebuah pengurutan rapi dan memiliki sifat tambahan bahwa setiap bilangan asli taknol memiliki sebuah pendahulu tunggal.

Pengurutan rapi lainnya dari bilangan asli diberikan dengan menentukan bahwa semua bilangan genap lebih besar dari semua bilangan ganjil, dan pengurutan biasa berlaku dalam bilangan genap dan ganjil:

Ini adalah sebuah himpunan terurut rapi tipe urutan . Setiap unsur memiliki sebuah penerus (tidak ada unsur terbesar). Dua unsur kekurangan sebuah pendahulu: 0 dan 1.

Bilangan bulat 
Tidak seperti pengurutan standar  dari bilangan asli, pengurutan standar  dari bilangan bulat bukanlah sebuah pengurutan rapi, karena, contohnya, himpunan bilangan bulat negatif tidak berisi sebuah unsur lebih kecil.

Relasi  ini adalah sebuah contoh pengurutan rapi dari bilangan bulat:  jika dan hanya jika salah satu syarat berikut berlaku:

 
  adalah positif,  adalah negatif
  dan  adalah keduanya positif, dan 
  dan  adalah keduanya negatif, dan 

Relasi  ini dapat divisualisasikan sebagai berikut:

 isomorfik dengan bilangan ordinal .

Relasi lainnya untuk urutan rapi, bilangan bulat adalah definisi berikut:  jika dan hanya jika ( atau ( dan )). Urutan rapi ini dapat divisualisasikan sebagai berikut:

Ini memiliki tipe urutan .

Bilangan real 
Pengurutan standar  mengenai suatu selang real bukan sebuah pengurutan rapi, karena, contohnya, selang buka  tidak berisi sebuah unsur terkecil. Dari aksioma teori himpunan Zermelo–Fraenkel mengenai teori himpunan (termasuk aksioma pemilihan), salah satunya dapat menunjukkan bahwa ada sebuah urutan rapi dari bilangan real. Juga Waclaw Sierpiński membuktikan bahwa teori himpunan Zermelo–Fraenkel + Hipotesis kontinum rampat menyiratkan aksioma pemilihan dan karena itu sebuah urutan rapi dari real. Namun, ini mungkin untuk menunjukkan bahwa aksioma teori himpunan Zermelo–Fraenkel + Hipotesis kontinum rampat sendiri tidak cukup untuk membuktikan keberadaan mengenai sebuah urutan rapi (oleh sebuah rumus) terdefinisikan dari real. Namun ini konsisten dengan teori himpunan Zermelo–Fraenkel yang sebuah urutan rapi terdefinisikan dari real ada—contohnya, ini konsisten dengan teori himpunan Zermelo–Fraenkel bahwa V=L, dan ini mengikuti dari teori himpunan Zermelo–Fraenkel + V=L yang sebuah rumus khusus urutan rapi real, atau bahkan suatu himpunan.

Sebuah himpunan bagian taktercacahkan dari bilangan ral dengan pengurutan standar  tidak dapat menjadi sebuah urutan rapi. Andaikan  adalah sebuah himpunan bagian terurut rapi  oleh . Untuk setiap  dalam , misalkan  menjadi penerus dari  dalam pengurutan  pada  (kecuali  adalah unsur terkecil ). Misalkan  yang unsur-unsurnya takkosong dan selang lepas. Masing-masing selang berisi setidaknya satu bilangan rasional, jadi ada sebuah fungsi injektif dari  ke . Terdapat sebuah injeksi dari  yang dapat dipetakan ke nol setelahnya). Dan ini terkenal bahwa ada sebuah injeksi dari  ke bilangan asli (yang dapat menjadi terpilih untuk menghindar pencapaian ke nol). Demikian terdapat sebuah injeksi dari  ke bilangan asli yang berarti bahwa  adalah tercacahkan. Di sisi lain, sebuah himpunan bagian takhingga tercacah dari real dapat atau tidak dapat menjadi sebuah urutan rapi dengan standar "". Contohnya,

 Bilangan asli adalah sebuah urutan rapi terhadap pengurutan standar .
 Himpunan  tidak memiliki unsur terkecil dan oleh karena bukan sebuah urutan rapi terhadap pengurutan standar .

Contoh mengenai urutan rapi:

 Himpunan bilangan  memiliki tipe urutan .
 Himpunan bilangan  memiliki tipe urutan . Himpunan sebelumnya merupakan himpunan titik limit dalam himpunan. Dalam himpunan bilangan real, baik dengan topologi biasa atau topologi urutan, 0 juga sebuah titik limit dari himpunan. Ini juga merupakan sebuah titik limit dari himpunan titik limit.
 Himpunan bilangan  memiliki tipe urutan . Dengan topologi urutan mengenai himpunan ini, 1 merupakan sebuah titik limit dari himpunan. Dalam topologi biasa (atau dengan setara, topologi urutan) dari bilangan real ini tidak.

Perumusan setara 
Jika sebuah himpunan adalah terurut total, maka hal berikut setara dengan satu sama lain:

 Himpunannya adalah terurut rapi. Yaitu, setiap himpunan bagian takkosong memiliki sebuah unsur terkecil.
 Induksi transfinit dapat bekerja untuk seluruh himpunan terurut.
 Setiap barisan menurun sempurna mengenai unsur-unsur dari himpunan harus mengakhiri setelah hanya langkap yang terhingga banyaknya (mengasumsi aksioma pemilihan tergantung).
 Setiap subpengurutan adalah isomorfik untuk sebuah ruas awal.

Topologi urutan 
Setiap himpunan terurut rapi dapat dibuat menjadi sebuah ruang topologis dengan memberkahinya dengan topologi urutan.

Terhadap topologi ini, dapat menjadi dua jenis unsur:

 titik pencil — terdapat minimum dan unsur dengan sebuah pendahulu.
 titik limit — tipe ini tidak berlangsung dalam himpunan hingga, dan dapat atau tidak dapat berlangsung dalam sebuah himpunan takhingga, himpunan takhingga tanpa titik limit adalah himpunan tipe urutan , contohnya .

Untuk himpunan bagian, kita dapat membedakan:

 Himpunan bagian dengan sebuah maksimum (yakni, himpunan bagian yang terbatas oleh mereka sendiri), ini dapat menjadi sebuah titik pencil atau sebuah titik limit dari seluruh himpunan, dalam kasus terakhir, ini dapat atau tidak dapat juga menjadi sebuah titik limit dari himpunan bagian.
 Himpunan bagian yang tak terbatas oleh mereka sendiri tapi terbatas dalam seluruh himpunan, mereka tidak memiliki maksimum, tapi sebuah supremum di luar himpunan bagian, jika himpunan bagian adalah takkosong, supremum ini adalah sebuah titik limit dari himpunan bagian dan karena itu juga dari seluruh himpunan; jika himpunan bgian adalah kosong, supremum ini adaloah minimum dari seluruh himpunan.
 Himpunan bagian yang tak terbatas dalam seluruh himpunan.

Sebuah himpunan bagian adalah kofinal dalam seluruh himpunan jika dan hanya jika hal tersebut adalah takterbatas dalam seluruh himpunan atau memiliki sebuah maksimum yang juga maksimum dari seluruh himpunan.

Sebuah himpunan terurut rapi sebagai ruang topologis adalah sebuah ruang tercacah pertama jika dan hanya jika hal tersebut memiliki tipe urutan lebih kecil atau sama dengan  (omega-satu), yakni, jika dan hanya jika himpunannya tercacahkan atau memiliki tipe urutan taktercacahkan yang terkecil.

Lihat pula 

 Pohon (teori himpunan), perampatan
 Bilangan ordinal
 Himpunan beralasan
 Urutan parsial baik
 Pra-pengurutan rapi
 Himpunan berarah

Referensi 

 

Bilangan ordinal
Keberalasanan
Teori tatanan
Relasi biner