Relasi biner | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Simbol "✓" menunjukkan bahwa sifat kolom diperlukan dalam definisi baris. Misalnya, definisi relasi ekuivalen diperlukan menjadi simetris. Semua definisi secara diam-diam memerlukan ketransitifan dan refleksivitas. |
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).
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.
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.
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: x R y jika dan hanya jika salah satu syarat berikut berlaku:
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 .
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.[1] 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,
Contoh mengenai urutan rapi:
Jika sebuah himpunan adalah terurut total, maka hal berikut setara dengan satu sama lain:
Setiap himpunan terurut rapi dapat dibuat menjadi sebuah ruang topologis dengan memberkahinya dengan topologi urutan.
Terhadap topologi ini, dapat menjadi dua jenis unsur:
Untuk himpunan bagian, kita dapat membedakan:
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.