Urutan rapi

Relasi biner
Simetrik Antisimetrik Connex Ditemukan baik Telah bersambung Telah bertemu Relasi ekuivalen ✓ ✗ ✗ ✗ ✗ ✗ Praurutan (Kuasiorder) ✗ ✗ ✗ ✗ ✗ ✗ Urutan parsial ✗ ✓ ✗ ✗ ✗ ✗ Praurutan total ✗ ✗ ✓ ✗ ✗ ✗ Urutan total ✗ ✓ ✓ ✗ ✗ ✗ Pra-urutan rapi ✗ ✗ ✓ ✓ ✗ ✗ Kuasi urutan rapi ✗ ✗ ✗ ✓ ✗ ✗ Urutan rapi ✗ ✓ ✓ ✓ ✗ ✗ Kisi ✗ ✓ ✗ ✗ ✓ ✓ Sambungan-semikekisi ✗ ✓ ✗ ✗ ✓ ✗ Pertemuan-semikekisi ✗ ✓ ✗ ✗ ✗ ✓
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 $S$ adalah sebuah urutan total pada $S$ dengan sifat bahwa setiap himpunan bagian takkosong $S$ memiliki sebuah unsur terkecil dalam urutannya. Himpunan $S$ 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 $s$ 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 $s$. Mereka mungkin menjadi unsur-unsur selain unsur terkecil yang tidak memiliki pendahulunya (lihat Bilangan asli di bawah untuk sebuah contoh). Dalam sebuah himpunan terurut $S$, setiap himpunan bagian $T$ yang memiliki sebuah batas atas memiliki sebuah batas atas terkecil, yaitu unsur terkecil dari himpunan bagian semua batas atas $T$ di $S$.

Jika $\leq$ 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 $n$ terhingga, ungkapan "unsur ke-$n$" mengenai sebuah himpunan teruru rapi membutuhkan konteks untuk mengetahui apakah ini menghitung dari nol atau satu. Dalam sebuah notasi "unsur ke-$\beta$" dimana $\beta$ 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 $\leq$ 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:

$0\quad 2\quad 4\quad 6\quad 8\quad \dots \quad 1\quad 3\quad 5\quad 7\quad 9\quad \dots$

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

Bilangan bulat

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

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

1. $x=0$
2. $x$ adalah positif, $y$ adalah negatif
3. $x$ dan $y$ adalah keduanya positif, dan $x\leq y$
4. $x$ dan $y$ adalah keduanya negatif, dan $\left|x\right|\leq \left|y\right|$

Relasi $R$ ini dapat divisualisasikan sebagai berikut:

$0\quad 1\quad 2\quad 3\quad 4\quad \dots \quad -1\quad -2\quad -3\quad \dots$

$R$ isomorfik dengan bilangan ordinal $\omega +\omega$.

Relasi lainnya untuk urutan rapi, bilangan bulat adalah definisi berikut: $x\leq _{\mathbb {Z} }y$ jika dan hanya jika ($\left|x\right|<\left|y\right|$ atau ($\left|x\right|=\left|y\right|$ dan $x\leq y$)). Urutan rapi ini dapat divisualisasikan sebagai berikut:

$0\quad -1\quad 1\quad -2\quad 2\quad -3\quad 3\quad -4\quad 4\quad \dots$

Ini memiliki tipe urutan $\omega$.

Bilangan real

Pengurutan standar $\leq$ mengenai suatu selang real bukan sebuah pengurutan rapi, karena, contohnya, selang buka $(0,1)\subseteq [0,1]$ 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 $\leq$ tidak dapat menjadi sebuah urutan rapi. Andaikan $X$ adalah sebuah himpunan bagian terurut rapi $\mathbb {R}$ oleh $\leq$. Untuk setiap $x$ dalam $X$, misalkan $s(x)$ menjadi penerus dari $x$ dalam pengurutan $\leq$ pada $X$ (kecuali $x$ adalah unsur terkecil $X$). Misalkan $A=\{(x,s(x))\mid x\in X\}$ yang unsur-unsurnya takkosong dan selang lepas. Masing-masing selang berisi setidaknya satu bilangan rasional, jadi ada sebuah fungsi injektif dari $A$ ke $\mathbb {Q}$. Terdapat sebuah injeksi dari $X$ yang dapat dipetakan ke nol setelahnya). Dan ini terkenal bahwa ada sebuah injeksi dari $Q$ ke bilangan asli (yang dapat menjadi terpilih untuk menghindar pencapaian ke nol). Demikian terdapat sebuah injeksi dari $X$ ke bilangan asli yang berarti bahwa $X$ adalah tercacahkan. Di sisi lain, sebuah himpunan bagian takhingga tercacah dari real dapat atau tidak dapat menjadi sebuah urutan rapi dengan standar "$\leq$". Contohnya,

• Bilangan asli adalah sebuah urutan rapi terhadap pengurutan standar $\leq$.
• Himpunan $\left\{{\frac {1}{n}}\colon n=1,2,3\dots \right\}$ tidak memiliki unsur terkecil dan oleh karena bukan sebuah urutan rapi terhadap pengurutan standar $\leq$.

Contoh mengenai urutan rapi:

• Himpunan bilangan $\{-2^{-n}\mid 0\leq n<\omega \}$ memiliki tipe urutan $\omega$.
• Himpunan bilangan $\left\{-2^{-n}-2^{-m-n}\mid 0\leq m,n<\omega \right\}$ memiliki tipe urutan $\omega ^{2}$. 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 $\left\{-2^{-n}\mid 0\leq n<\omega \right\}\cup \{1\}$ memiliki tipe urutan $\omega +1$. 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 $\omega$, contohnya $\mathbb {N}$.

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 _{1}$ (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

• Folland, Gerald B. (1999). Real Analysis: Modern Techniques and Their Applications. Pure and applied mathematics (edisi ke-2nd). Wiley. hlm. 4–6, 9. ISBN 978-0-471-31716-6.