Hyvin tilattu setti

Hyvin järjestetty joukko on lineaarisesti järjestetty joukko M siten, että missä tahansa sen ei-tyhjissä osajoukoissa on minimialkio. Toisin sanoen se on hyvin perusteltu joukko lineaarisella järjestyksellä.

Esimerkkejä

Tyhjä sarja on hyvin järjestyksessä.
Yksinkertaisin esimerkki äärettömästä hyvin järjestetystä joukosta on luonnollisten lukujen joukko luonnollisella järjestyksellä.
Kokonaislukujoukko ei ole täysin järjestetty, koska esimerkiksi negatiivisten lukujen joukossa ei ole pienintä . Se voidaan kuitenkin tehdä melko järjestyneeksi määrittelemällä epästandardi "pienempi tai yhtä suuri" relaatio [1] , jonka merkitsemme ja määrittelemme seuraavasti: $\preccurlyeq$

a\preccurlyeq b,

jos joko tai tai ja

a=b,

|a|<|b|,

|a|=|b|

a<0<b.

Silloin kokonaislukujen järjestys on: Erityisesti on pienin negatiivinen luku.

0\preccurlyeq -1\preccurlyeq 1\preccurlyeq -2\preccurlyeq 2\dots

-yksi

Yksinkertaisin esimerkki lukemattomasta hyvin järjestetystä joukosta on kaikkien laskettavien järjestyslukujen kokoelma, jotka on järjestetty suhteessa . Jos oletetaan jatkumohypoteesi, sen teho on yhtä suuri kuin jatkumon teho. $\sisään$

Zermelon lauseen mukaan , jos hyväksyy valinnan aksiooman , niin mikä tahansa joukko voidaan järjestää hyvin. Lisäksi väite, että jokaisella joukolla on täydellinen järjestys, vastaa valinnan aksioomaa. Erityisesti valinnan aksiooman läsnä ollessa reaalilukujen joukko voidaan järjestää täysin.
Jos X ja Y ovat kaksi hyvin järjestettyä joukkoa, ne ovat joko isomorfisia keskenään tai täsmälleen yksi niistä on isomorfinen toisen alkusegmentin kanssa.

N. K. Vereshchagin, A. Shen. Osa 1. Joukkoteorian alkua // Matemaattisen logiikan ja algoritmien teorian luentoja. — 2. painos, korjattu. - M .: MTSNMO , 2002. - 128 s.

↑ Donald Knuth . Ohjelmoinnin taito, osa I. Perusalgoritmit. - M .: Mir , 1976. - S. 571 (15b). — 736 s.