Osittain tilattu setti

Osittain järjestetty joukko on matemaattinen käsite, joka formalisoi järjestyksen intuitiiviset ideat, elementtien järjestyksen tiettyyn järjestykseen. Epämuodollisesti joukko on osittain järjestetty, jos on määritelty, mitkä alkiot seuraavat mitäkin (mitkä alkiot ovat suurempia kuin mitä). Yleisesti ottaen voi käydä ilmi, että jotkin elementtiparit eivät liity " seuraa "-suhteeseen .

Abstraktina esimerkkinä voimme antaa joukon osajoukkoja kolmen elementin joukosta ( tietyn joukon Boolen arvo), jotka on järjestetty inkluusiosuhteen mukaan. $\{x,y,z\}$

Määritelmä ja esimerkit

Järjestysrelaatio joukossatai osittaisjärjestys on binäärirelaatio (jokin joukon määrittelemä ) , joka täyttää seuraavat ehdot [1] : $M$ $\varphi$ $M$ $R_{{\varphi }}\subset M\times M$

Heijastuskyky : $\forall a\;(a\varphi a)$
Transitiivisuus : $\forall a,b,c\;(a\varphi b)\wedge (b\varphi c)\Rightarrow a\varphi c$
Antisymmetria : $\forall a,b\;(a\varphi b)\wedge (b\varphi a)\Rightarrow a=b$

Joukkoa , jolle osittaisen järjestyksen relaatio on annettu, kutsutaan osittain järjestetyksi . Tarkemmin sanottuna [2] , silloin osittain järjestetty joukko on pari , jossa on joukko ja on osittaisen järjestyksen relaatio . $M$ $\langle M,\varphi \rangle$ $M$ $\varphi$ $M$

Osittain järjestetyn joukon mitta on yhtä suuri kuin lineaaristen tilausten joukon enimmäismäärä ( ). Tämä määritelmä perustuu osittaisen järjestyksen laajennettavuuden ominaisuuteen lineaariseen järjestykseen. $\langle M,\varphi \rangle$ ${\näyttötyyli <_{i))$ $minä\minässä$

Terminologia ja merkintätapa

Osittainen järjestyssuhde merkitään yleensä symbolilla , analogisesti reaalilukujoukon suhteen "pienempi tai yhtä suuri" kanssa . Lisäksi, jos , niin sanomme, että elementti ei ylitä , tai että se on alisteinen . $\leqslant$ $a\leqslant b$ $a$ $b$ $a$ $b$

Jos ja , he kirjoittavat ja sanovat, että se on pienempi kuin tai että se on tiukasti alisteinen . $a\leqslant b$ $a \neq b$ $a<b$ $a$ $b$ $a$ $b$

Joskus, jotta voidaan erottaa mielivaltainen järjestys tietyssä joukossa tunnetusta "pienempi tai yhtä suuri" suhteesta reaalilukujen joukossa, käytetään erikoissymboleja ja asemesta ja vastaavasti. $\leqslant$ $<$ $\preccurlyeq$ $\prec$

Tiukka ja ei-tiukka järjestys

Relektiivistä suhdetta, joka täyttää refleksiivisuuden, transitiivisuuden ja antisymmetrian ehdot, kutsutaan myös ei -tiukkaksi eli refleksiiviseksi järjestykseksi . Jos refleksiivisuuden ehto korvataan antireflexiivisuuden ehdolla (niin antisymmetrian ominaisuus korvataan epäsymmetrialla):

\forall a\;\neg (a\varphi a)

niin saamme tiukan tai antirefleksiivisen järjestyksen määritelmän .

Jos on ei-tiukka järjestys joukossa , niin relaatio , joka määritellään seuraavasti: $\leqslant$ $M$ $<$

a<b\;{\overset {{\mathrm {def}}}{\Longleftrightarrow }}\;(a\leqslant b)\wedge (a\neq b)

on tiukka määräys . Päinvastoin, jos on tiukka järjestys, niin suhde määritellään muodossa $M$ $<$ $\leqslant$

a\leqslant b\;{\overset {{\mathrm {def}}}{\Longleftrightarrow }}\;(a<b)\vee (a=b)

on ei-tiukka määräys.

Siksi on sama, määritetäänkö sarjalle ei-tiukka järjestys vai tiukka järjestys . Tuloksena on sama rakenne. Ero on vain terminologiassa ja merkinnöissä.

Intervalli

Suljetulla aikavälillä [ a , b ] on joukko elementtejä x , jotka tyydyttävät epäyhtälön (eli ja ). Väli sisältää ainakin alkiot a ja b . $a\leqslant b$ $a\leqslant x\leqslant b$ $a\leqslant x$ $x\leqslant b$

Jos käytämme tiukkaa epäyhtälöä "<", saamme avoimen välin ( a , b ), joukon elementtejä x , jotka tyydyttävät epäyhtälön a < x < b (eli a < x ja x < b ). Avoin väli voi olla tyhjä, vaikka a < b . Esimerkiksi kokonaislukujen avoin väli (1,2) on tyhjä, koska ei ole sellaisia kokonaislukuja i , joiden 1 < i < 2.

Joskus määritelmää laajennetaan sallimaan a > b . Tässä tapauksessa väli on tyhjä.

Puoliavoimet välit [ a , b ) ja ( a , b ] määritellään samalla tavalla.

Poset on paikallisesti äärellinen , jos jokainen intervalli on äärellinen. Esimerkiksi kokonaisluvut ovat paikallisesti äärellisiä luonnollisessa järjestyksessään. Suoratulon ℕ×ℕ leksikografinen järjestys ei ole paikallisesti äärellinen, koska esimerkiksi . $(1,2)\leqslant (1,3)\leqslant (1,4)\leqslant (1,5)\leqslant \ldots \leqslant (2,1)$

Posettien intervallin käsitettä ei pidä sekoittaa tiettyyn poset-luokkaan, joka tunnetaan nimellä intervallijärjestykset .

Esimerkkejä

Reaalilukujoukko on osittain järjestetty suhteessa "pienempi tai yhtä suuri" - . $\mathbb {R}$ $\leqslant$

Antaa olla kaikkien segmentille määriteltyjen reaaliarvoisten funktioiden joukko , eli muodon funktioita $M$ $[a,b]$

f\colon [a,b]\to {\mathbb {R}}

Otetaan käyttöön järjestyssuhde seuraavasti : , jos epäyhtälö pätee kaikkiin . Ilmeisesti käyttöön otettu relaatio on todellakin osittaisen järjestyksen relaatio. $\leqslant$ $M$ $f\leqslant g$ $x\in[a,b]$ $f(x)\leqslant g(x)$

Olkoon vähän settiä. Kaikkien osajoukkojen joukko (ns. boolean ) on osittain järjestetty sisällyttämisen mukaan . $M$ ${\mathcal {P}}(M)$ $M$ $M\subseteq N$

Kaikkien luonnollisten lukujen joukko on osittain järjestetty jakosuhteen avulla . $\mathbb {N}$ $m\mid n$

Aiheeseen liittyvät määritelmät

Vertaansa vailla olevat elementit

Jos ja ovat reaalilukuja , vain yksi seuraavista suhteista pätee: $a$ $b$

a<b,\qquad a=b,\qquad b<a

Jos ja ovat mielivaltaisen osittain järjestetyn joukon elementtejä, on neljäs looginen mahdollisuus: mikään edellä olevista kolmesta suhteesta ei täyty. Tässä tapauksessa elementtejä ja kutsutaan vertailukelpoisiksi . Jos esimerkiksi on joukko reaaliarvoisia funktioita segmentillä , niin elementit ja ovat verrattomia. Vertailemattomien elementtien olemassaolon mahdollisuus selittää termin "osittain järjestettävä joukko" merkityksen . $a$ $b$ $a$ $b$ $M$ $[0,1]$ $f(x) = x$ $g(x) = 1-x$

Vähimmäis/suurin ja pienin/suurin elementti

Koska osittain järjestetyssä joukossa voi olla pareja vertaansa vailla olevia alkioita, otetaan käyttöön kaksi erilaista määritelmää: minimielementti ja pienin alkio .

Elementin sanotaan olevan minimaalinen , jos elementtiä ei ole olemassa . Toisin sanoen, on vähimmäiselementti, jos jollekin elementille joko , tai , tai ja ovat vertailukelpoisia. Elementtiä kutsutaan pienimmäksi , jos jollekin elementille epäyhtälö pätee . Ilmeisesti mikä tahansa pienin elementti on myös minimaalinen, mutta päinvastoin ei yleensä pidä paikkaansa: minimielementti ei välttämättä ole pienin, jos on elementtejä , jotka eivät ole vertailukelpoisia . $a \ in M$ $b<a$ $a$ $b\in M$ $b>a$ $b=a$ $b$ $a$ $a$ $b\in M$ $b\geqslant a$ $a$ $b$ $a$

On selvää, että jos joukossa on pienin elementti, se on ainutlaatuinen. Mutta minimaalisia elementtejä voi olla useita. Esimerkkinä voidaan harkita luonnollisten lukujen joukkoa ilman yksikköä, jotka on järjestetty jakosuhteen mukaan . Tässä minimielementit ovat alkulukuja , mutta pienintä elementtiä ei ole olemassa. ${\mathbb {N}}\setminus \{1\}=\{2,3,\ldots \}$ $\mid$

Suurimman ja suurimman elementin käsitteet esitellään samalla tavalla.

Ylä- ja alapinnat

Antaa olla osajoukko osittain järjestynyt joukko . Elementtiä kutsutaan ylärajaksi, jos mikään elementti ei ylitä . Joukon alarajan käsite esitellään samalla tavalla . $A$ $\langle M,\leqslant \rangle$ $olet M$ $A$ $a\in A$ $u$ $A$

Mikä tahansa elementti, joka on suurempi kuin jokin yläpinta , on myös yläpinta . Ja mikä tahansa elementti, joka on pienempi kuin jokin infimum , on myös infimum . Nämä pohdinnat johtavat pienimmän ylärajan ja suurimman alarajan käsitteiden käyttöönottoon . $A$ $A$ $A$ $A$

Ylempi ja alempi joukko

Osittain järjestetyn joukon elementille ylempi joukko on kaikkien elementtien joukko, jota edeltää ( ). $m$ $\langle M,\leqslant \rangle$ $M\uparrow m$ $m$ $\{x\in M\mid m\leqslant x\}$

Alempi joukko määritellään kaksoisjoukoksi kaikkien annettua elementtiä edeltävien elementtien joukoksi: . $M\downarrow m{\stackrel {{\mathrm {def}}}{=}}\{x\in M\mid x\leqslant m\}$

Katkoehdot

Osittain järjestetyn joukon sanotaan täyttävän tiukasti kasvavan ketjun lopetusehdon, jos ei ole ääretöntä tiukasti kasvavaa sekvenssiä . Tämä ehto vastaa ei-tiukasti kasvavien ketjujen stabilointiehtoa : mikä tahansa ei-tiukasti kasvava sen elementtien sarja stabiloituu. Eli mille tahansa muodon sekvenssille $M$ ${\näyttötyyli (a_{i}\,<\,a_{i+1})}$ $(a_{i}\,\leqslant \,a_{i+1})$

a_{1}\,\leqslant \,a_{2}\,\leqslant \,a_{3}\,\leqslant \,\cdots

on olemassa sellainen luonnollinen $n,$

a_{n}=a_{{n+1}}=a_{{n+2}}=\cdots .

Määritelty samalla tavalla väheneville ketjuille, sitten ilmeisesti täyttää laskevan ketjun lopetusehdon, jos ja vain jos jokin ei-tiukasti laskeva sen elementtien sarja stabiloituu. Näitä käsitteitä käytetään usein yleisalgebrassa - katso esimerkiksi Noetherian ring , Artinian rengas . $M$

Erikoistyypit osittain tilatut sarjat

Lineaarisesti järjestetyt sarjat

Olkoon osittain tilattu setti. Jos missä tahansa kahdessa elementissä ovat vertailukelpoisia, joukkoa kutsutaan lineaarisesti järjestetyksi . Lineaarisesti järjestettyä joukkoa kutsutaan myös täydellisesti järjestetyksi joukoksi tai yksinkertaisesti järjestetyksi joukoksi [3] . Siten lineaarisesti järjestetyssä joukossa mille tahansa kahdelle elementille ja , yksi ja vain yksi suhteista pätee: joko , tai , tai . $\langle M,\leqslant \rangle$ $M$ $M$ $a$ $b$ $a<b$ $a=b$ $b<a$

Myös mitä tahansa osittain järjestetyn joukon lineaarisesti järjestettyä osajoukkoa kutsutaan ketjuksi , eli osittain järjestetyn joukon ketju on sen osajoukko, jossa mitkä tahansa kaksi elementtiä ovat vertailukelpoisia. $\langle M, \leqslant \rangle$

Yllä olevista esimerkeistä osittain järjestetyistä joukoista vain reaalilukujen joukko on lineaarisesti järjestetty. Joukko reaaliarvoisia funktioita välillä (ehdon alla ), Boolen (for ), luonnolliset luvut, joilla on jakosuhde, eivät ole lineaarisesti järjestettyjä. $[a,b]$ $a<b$ ${\mathcal {P}}(M)$ $|M|\geqslant 2$

Lineaarisesti järjestetyssä joukossa pienimmän ja minimin sekä suurimman ja maksimin käsitteet ovat samat.

Hyvin tilatut sarjat

Lineaarisesti järjestettyä joukkoa kutsutaan hyvin järjestetyksi , jos jokaisessa sen ei-tyhjässä osajoukossa on pienin alkio [4] . Tällaista joukon järjestystä kutsutaan täydelliseksi järjestykseksi tilanteessa, jossa sitä ei voida sekoittaa täydelliseen järjestykseen täydellisen osittain järjestetyn joukon merkityksessä .

Klassinen esimerkki hyvin järjestetystä joukosta on luonnollisten lukujen joukko . Väite, että mikä tahansa ei-tyhjä osajoukko sisältää pienimmän elementin, vastaa matemaattisen induktion periaatetta . Esimerkki lineaarisesti järjestetystä, mutta ei hyvin järjestetystä joukosta on luonnollisesti järjestetty ei-negatiivisten lukujen joukko . Itse asiassa sen osajoukossa ei ole pienintä elementtiä. $\mathbb {N}$ $\mathbb {N}$ ${\mathbb {R}}_{{+}}=\{x:x\geqslant 0\}$ $\{x:x>1\}$

Hyvin järjestetyillä joukoilla on poikkeuksellisen tärkeä rooli yleisessä joukkoteoriassa .

Koko poset

Täydellinen poset on poset, jolla on pohja – ainoa elementti, joka edeltää mitä tahansa muuta elementtiä ja jolla jokaisella suunnatulla osajoukolla on tarkka yläraja [5] . Täydellisiä osittain järjestettyjä joukkoja käytetään λ-laskennassa ja tietojenkäsittelytieteessä , erityisesti niihin otetaan käyttöön Scott-topologia , jonka pohjalta rakennetaan johdonmukainen malli λ-laskennasta ja denotaatiosemantiikasta . Täydellisen osittain järjestetyn joukon erikoistapaus on täydellinen hila - jos jollakin osajoukolla, ei välttämättä suunnatulla, on pienin yläraja, niin se osoittautuu täydelliseksi hilaksi.

Järjestetty joukko on täydellinen osittain järjestetty joukko, jos ja vain jos jokaisella funktion monotonilla järjestyksen ( ) suhteen on vähintään yksi kiinteä piste : . $M$ $f\colon M\rightarrow M$ $a\leqslant b\Rightarrow f(a)\leqslant f(b)$ $\olemassa _{{x\in M}}f(x)=x$

Mikä tahansa setti voidaan muuttaa täydelliseksi osittain tilatuksi ottamalla pohja pois ja määrittämällä järjestys kuten kaikki sarjan elementit . $M$ $\bot$ $\leqslant$ $\bot \leqslant m$ $m\leqslant m$ $m$ $M$

Lauseet osittain järjestetyistä joukoista

Peruslauseita osittain järjestetyistä joukoista ovat Hausdorffin maksimiperiaate ja Kuratowski-Zornin lemma . Jokainen näistä lauseista vastaa valinnan aksioomaa .

Luokkateoriassa

Jokaista asettelua (ja jokaista ennakkotilausta ) voidaan tarkastella kategoriana , jossa jokainen morfismijoukko koostuu enintään yhdestä elementistä. Tämä luokka voidaan määritellä esimerkiksi seuraavasti: jos A ≤ B (ja muuten tyhjä joukko); morfismin koostumussääntö: ( y , z )∘( x , y ) = ( x , z ). Jokainen ennakkotilausluokka vastaa osittain tilattua sarjaa. ${\mathrm {Hom}}(A,B)$ ${\mathrm {Hom}}(A,B)=\{(A,B)\}$

Funktori luokkakohtaisesti järjestetystä joukosta (eli kaaviosta , jonka indeksiluokka on poset) on kommutoiva kaavio .

Muistiinpanot

↑ Kolmogorov, 2004 , s. 36.
↑ Aleksandrov, 1977 , s. 78.
↑ Kolmogorov, 2004 , s. 38.
↑ Kolmogorov, 2004 , s. 40.
↑ Barendregt, 1985 , s. 23.

Kirjallisuus

Aleksandrov PS Johdatus joukkoteoriaan ja yleiseen topologiaan. — M .: Nauka , 1977. — 368 s.
Barendregt, Henk. Lambda-laskenta. Sen syntaksi ja semantiikka = The Lambda Calculus. Sen syntaksi ja semantiikka. — M .: Mir , 1985. — 606 s. - 4800 kappaletta.
Kolmogorov AN, Fomin SV Funktioteorian ja funktionaalisen analyysin elementit. - 7. painos — M .: Fizmatlit , 2004. — 572 s. — ISBN 5-9221-0266-4 .
Hausdorff F. Joukkoteoria. - 4. painos — M .: URSS , 2007. — 304 s. - ISBN 978-5-382-00127-2 .
Gurov S.I. Boolen algebrat, järjestetyt joukot, hilat: Määritelmät, ominaisuudet, esimerkit. - 2. painos — M .: Librokom , 2013. — 352 s. - ISBN 978-5-397-03899-7 .