Drevo (teorija množic)

Za druge pojme drevesa v teoriji množic glej drevo (deskriptivna teorija množic) in drevo (razločitev).

Veja (označeno zeleno) drevesa teorije množic. Tukaj pike predstavljajo elemente, puščice predstavljajo relacijo vrstnega reda, tripičja in črtkane puščice pa predstavljajo (možno neskončno) elemente in povezave brez slike.

Drevo je v teoriji množic takšna delno urejena množica $(T,<)\!\,$, da je za vsak element $t\in T\!\,$ množica $s\in T:s<t\!\,$ dobro urejena z relacijo $<\!\,$. Večinoma se domneva, da imajo drevesa samo en koren (tj. minimalni element), saj se tipična vprašanja, ki se raziskujejo na tem področju, zlahka reducirajo na vprašanja o enokorenskih drevesih.

Definicija

Majhni končni zgledi: Tri delno urejene množice na levi so drevesa (modro); ena veja enega od dreves je poudarjena (teleno). Delno urejena množica na desni (rdeče) ni drevo, ker velja $x_{1}<x_{3}\!\,$ in $x_{2}<x_{3}\!\,$, $x_{1}\!\,$ pa ni primerljiv z $x_{2}\!\,$ (prekinjena oranžna črta).

Drevo je takšna delno urejena množica (poset) $(T,<)\!\,$, da je za vsak element $t\in T\!\,$ množica $s\in T:s<t\!\,$ dobro urejena z relacijo $<\!\,$. Še posebej je vsaka dobro urejena množica $(T,<)\!\,$ drevo. Za vsak element $t\in T\!\,$ se vrstni tip ${s\in T:s<t}\!\,$ imenuje višina $t\!\,$, označena s $\operatorname {ht} (t,T)\!\,$. Višina same množice $T\!\,$ je najmanjša ordinala večja od višine vsakega elementa $T\!\,$. Koren drevesa $T\!\,$ je element z višino enako 0. Pogosto se domneva, da imajo drevesa samo en koren. Drevesa v teoriji množic so pogosto opredeljena tako, da rastejo navzdol, zaradi česar je koren največje vozlišče.

Na drevesa z enim samim korenom se lahko gleda kot koreninska drevesa v smislu teorije grafov na enega od dveh načinov: ali kot drevo (teorija grafov) ali kot trivialno popolni graf. V prvem primeru je graf neusmerjen Hassejev diagram delno urejene množice, v drugem primeru pa je graf preprosto osnovni (neusmerjeni) graf delno urejene množice. Če pa je $T\!\,$ drevo z višino $>\!\,$ ordinalno število|$\omega \!\,$]], potem definicija Hassejevega diagrama ne deluje. Na primer, delno urejena množica $\omega +1=\left\{0,1,2,\dots ,\omega \right\}\!\,$ nima Hassejevega diagrama, ker ni predhodnika $\omega \!\,$. Zato je v tem primeru potrebna višina največ $\omega \!\,$.

Veja drevesa je največja veriga v drevesu (kar pomeni, da sta katera koli dva elementa veje primerljiva in vsak element drevesa, ki ni v veji, je neprimerljiv z vsaj enim elementom veje). Dolžina veje je ordinal, ki je izomorfen po vrstnem redu veji. Za vsak ordinal $\alpha \!\,$ je $\alpha \!\,$-na raven drevesa $T\!\,$ množica vseh elementov $T\!\,$ z višino $\alpha \!\,$. Drevo je $\kappa \!\,$-drevo za ordinalno število $\kappa \!\,$, če in samo če ima višino $\kappa \!\,$ in ima vsaka raven kardinalnost manjšo od kardinalnosti $\kappa \!\,$. Širina drevesa je supremum kardinalnosti njegovih ravni.

Vsako enokorensko drevo višine $\leq \omega$ tvori polmrežo srečanj, kjer je srečanje (skupni prednik) podano z največjim elementom presečišča prednikov, ki obstaja, ker je množica prednikov neprazna in končna dobro urejena, zato ima največji element. Brez enega korena je lahko presečišče staršev prazno (ni nujno, da imata dva elementa skupne prednike), na primer $\left\{a,b\right\}\!\,$, kjer elementi niso primerljivi; medtem ko če obstaja neskončno število prednikov, ni potreben največji element – na primer $\left\{0,1,2,\dots ,\omega _{0},\omega _{0}'\right\}\!\,$, kjer $\omega _{0},\omega _{0}'\!\,$ nista primerljiva.

Poddrevo drevesa $(T,<)\!\,$ je drevo $(T',<)\!\,$, kjer velja $T'\subseteq T\!\,$ in $T'$ je zaprto navzdol pod relacijo $<\!\,$, oziroma, če velja $s,t\in T\!\,$ in $s<t\!\,$, potem je $t\in T'\implies s\in T'\!\,$.

Značilnosti v smislu teorije množic

V teoriji neskončnih dreves je nekaj dokaj preprosto izraženih, a težkih problemov. Primera tega sta Kurepova domneva in Suslinova domneva. Znano je, da sta oba problema neodvisna od Zermelo-Fraenklove teorije množic (ZF). Po Kőnigovi lemi ima vsako $\omega \!\,$-drevo neskončno vejo. Po drugi strani pa obstaja izrek ZFC, ki pravi da obstajajo neštevna drevesa brez neštevnih vej in neštevnih ravni – takšna drevesa so znana kot Aronszajnova drevesa. Glede na kardinalno število $\kappa \!\,$ je $\kappa \!\,$-Suslinovo drevo drevo z višino $\kappa \!\,$, ki nima verig ali antiverig velikosti $\kappa \!\,$. Zlasti, če je $\kappa \!\,$ singularno, potem obstajata $\kappa \!\,$-Aronszajnovo drevo in $\kappa \!\,$-Suslinovo drevo. Pravzaprav je za vsak neskončn kardinal $\kappa \!\,$ vsako $\kappa \!\,$-Suslinovo drevo $\kappa \!\,$-Aronszajnovo drevo (obratno pa ne velja).

Suslinova domneva je bila prvotno postavljena kot vprašanje o določenih totalnih vrstnih redih, vendar je enakovredna izjavi: Vsako drevo z višino $\omega _{1}\!\,$ ima antiverigo za kardinalnost $\omega _{1}\!\,$ ali vejo dolžine $\omega _{1}\!\,$.

Če je $(T,<)\!\,$ drevo, potem je refleksivno zaprtje $\leq \!\,$ od $<\!\,$ predponski vrstni red na $T\!\,$. Obratno ne velja: na primer, običajni vrstni red $\leq \!\,$ na množici celih števil $\mathbb {Z} \!\,$ je vsota in s tem predponski vrstni red, vendar $(\mathbb {Z} ,<)\!\,$ ni drevo v smislu teorije množic, ker na primer množica $\left\{n\in \mathbb {Z} :n<0\right\}\!\,$ nima najmanjšega elementa.

Zgledi končnih dreves

Drevo v smislu teorije množice z višino $\omega \cdot 2\!\,$ in širino $2^{\omega \cdot 2}\!\,$. Vsaka točka odgovarja Vsako vozlišče ustreza stičišču rdeče in zelene črte. Zaradi prostorske omejitve so s polno dolžino prikazane le veje s predpono (0,0,0,...) ali (1,1,1,...).

• naj je $\kappa \!\,$ ordinalno število in naj je $X\!\,$ množica. Naj je $T\!\,$ množica vseh funkcij $f:\alpha \mapsto X\!\,$, kjer velja $\alpha <\kappa \!\,$. Potem je definirana $f<g\!\,$, če je domena $f\!\,$ prava podmnožica domene $g\!\,$ in se funkciji ujemata na domeni $f\!\,$. Potem je $(T,<)\!\,$ drevo v smislu teorije množic. Njegov koren je edinstvena funkcija na prazni množici, njegova višina pa je enaka $\kappa \!\,$. Unija vseh funkcij vzdolž veje vodi do funkcije iz $\kappa \!\,$ v $X\!\,$, kar pomeni posplošeno zaporedje članov $X\!\,$. Če je $\kappa \!\,$ limitni ordinal, nobena veja nima maksimalnega elementa (»lista«). Slika prikazuje zgled za $\kappa =\omega \cdot 2\!\,$ in $X=\{0,1\}\!\,$.

• vsaka drevesna podatkovna struktura v računalništvu je drevo v smislu teorije množic: za dve vozlišči $m,n\!\,$ je definirano $m<n\!\,$ če je $n\!\,$ pravi potomec $m\!\,$. Pojmi koren, višina vozlišča in dolžina veje sovpadajo, pojem višine drevesa pa se razlikuje za eno.

• Infinite trees considered in automata theory (see e.g. tree (automata theory)) are also set-theoretic trees, with a tree height of up to $\omega \!\,$.

• drevo v smislu teorije grafov se lahko pretvori v drevo v smislu teorije množic z izbiro korenskega vozlišča $r\!\,$ in definicijo $m<n\!\,$, če je $m\neq n\!\,$ in $m\!\,$ leži na (edinstveni) neusmerjeni poti iz $r\!\,$ v $n\!\,$.

• vsako Cantorjevo drevo, Kurepovo drevo in Lavrovo drevo je drevo v smislu teorije množic.

Glej tudi

• drevo (deskriptivna teorija množic)
• grafon

Viri

• Jech, Thomas (2002). Set Theory. Springer-Verlag. ISBN 3-540-44085-2.
• Kunen, Kenneth (1980). Set Theory: An Introduction to Independence Proofs. North-Holland. ISBN 0-444-85401-0. Chapter 2, Section 5.
• Monk, J. Donald (1976). Mathematical Logic. New York: Springer-Verlag. str. 517. ISBN 0-387-90170-1.
• Hajnal, András; Hamburger, Peter (1999). Set Theory. Cambridge: Cambridge University Press. ISBN 9780521596671.
• Kechris, Alexander S. (1995). Classical Descriptive Set Theory. Graduate Texts in Mathematics 156. Springer. ISBN 0-387-94374-9. ISBN 3-540-94374-9.