Құрылымдық теориядағы ағаштар туралы түсініктер

Кіріспе

Жинақ теориясындағы ағаш туралы басқа түсініктер

Жинақ теориясында ағаш – бұл жартылай реттелген жиынтық (T, <), онда әрбір t ∈ T үшін {s ∈ T : s < t} жиынтығы < қатынасы бойынша жақсы реттелген. Көбінесе ағаштардың тек бір тамыры (яғни, ең кішкентай элементі) бар деп қарастырылады, себебі осы саланың ерекше зерттелетін сұрақтарын бір тамырлы ағаштарға қатысты сұрақтарға дейін жеңілдетуге болады.

Анықтама

Ағаш – бұл ішінара реттелген жиын (посет) (T, <) болып табылады, мұнда әрбір t ∈ T үшін {s ∈ T : s < t} жиыны < қатынасы бойынша жақсы реттелген. Атап айтқанда, әр жақсы реттелген жиын (T, <) – ағаш. Әрбір t ∈ T үшін {s ∈ T : s < t} жиынының реттік түрі t-ның биіктігі деп аталады және ht(t, T) деп белгіленеді. T-ның биіктігі – T-ның әрбір элементінің биіктігінен үлкен ең кіші ординал болып табылады. Көбінесе ағаштардың тек бір тамыры бар деп есептеледі. Жинақтар теориясындағы ағаштар көбінесе тамырды ең үлкен түйін етіп, төмен қарай өседі деп анықталады. Бір тамырлы ағаштарды график теориясы мағынасында екі тәсілдің бірімен тамырлы ағаш ретінде қарастыруға болады: ағаш (график теориясы) немесе тривиальды түрде толық график ретінде. Бірінші жағдайда график – ішінара реттелген жиынның бағытталмаған Хассе диаграммасы, ал екінші жағдайда график – ішінара реттелген жиынның негізгі (бағытталмаған) графигі. Дегенмен, егер T ағашының биіктігі > ω болса, онда Хассе диаграммасының анықтамасы қолданылмайды. Мысалы, жартылай реттелген жиынның Хассе диаграммасы жоқ, себебі ω-ның алдындағы элемент жоқ. Сондықтан мұндай жағдайда биіктігі ω-дан артық болмауы керек. Ағаштың тармағы – ағаштағы ең үлкен тізбек (яғни, тармақтың кез келген екі элементі салыстырылады, ал тармақтағы ағаштың кез келген элементі тармақтағы кем дегенде бір элементпен салыстырылмайды). Тармақтың ұзындығы – тармаққа рет бойынша изоморфты ординал. Кез келген ординал α үшін T-ның α-шы деңгейі – T-ның биіктігі α-ға тең барлық элементтерінің жиыны. Ағаш κ-ағаш деп аталады, егер және тек қана оның биіктігі κ-ға тең болса және әрбір деңгейі κ-ның кардиналдығынан кіші болса. Ағаштың ені – оның деңгейлерінің кардиналдықтарының жоғарғы шегі. Кез келген бір тамырлы ағаш кездесетін жартылай тор құрайды, мұнда кездесу (ортақ ата-баба) ата-бабалардың қиылысының ең үлкен элементімен беріледі, ол бос емес және шекті жақсы реттелген болғандықтан, ең үлкен элементі бар. Бір тамырсыз ата-аналардың қиылысы бос болуы мүмкін (екі элементтің ортақ ата-бабалары болуы міндетті емес), мысалы, элементтер салыстырылмаған жағдайда; ал егер ата-бабалардың саны шексіз болса, онда ең үлкен элемент болуы міндетті емес – мысалы, элементтер салыстырылмаған жағдайда. Ағаштың кіші ағашы – ағаш, мұнда және төмен қарай жабық, яғни егер және болса, онда .

A tree is a partially ordered set (poset) (T, <) such that for each t ∈ T, the set {s ∈ T : s < t} is well ordered by the relation <. In particular, each well ordered set (T, <) is a tree. For each t ∈ T, the order type of {s ∈ T : s < t} is called the height of t, denoted ht(t, T). The height of T itself is the least ordinal greater than the height of each element of T. A root of a tree T is an element of height 0. Frequently trees are assumed to have only one root. Trees in set theory are often defined to grow downward making the root the greatest node. Trees with a single root may be viewed as rooted trees in the sense of graph theory in one of two ways: either as a tree (graph theory) or as a trivially perfect graph. In the first case, the graph is the undirected Hasse diagram of the partially ordered set, and in the second case, the graph is simply the underlying (undirected) graph of the partially ordered set. However, if T is a tree of height > ω, then the Hasse diagram definition does not work. For example, the partially ordered set does not have a Hasse Diagram, as there is no predecessor to ω. Hence a height of at most ω is required in this case. A branch of a tree is a maximal chain in the tree (that is, any two elements of the branch are comparable, and any element of the tree not in the branch is incomparable with at least one element of the branch). The length of a branch is the ordinal that is order isomorphic to the branch. For each ordinal α, the α th level of T is the set of all elements of T of height α. A tree is a κ tree, for an ordinal number κ, if and only if it has height κ and every level has cardinality less than the cardinality of κ. The width of a tree is the supremum of the cardinalities of its levels. Any single rooted tree of height forms a meet semilattice, where meet (common ancestor) is given by maximal element of intersection of ancestors, which exists as the set of ancestors is non empty and finite well ordered, hence has a maximal element. Without a single root, the intersection of parents can be empty (two elements need not have common ancestors), for example where the elements are not comparable; while if there are an infinite number of ancestors there need not be a maximal element – for example, where are not comparable. A subtree of a tree is a tree where and is downward closed under , i. e., if and then .

Жинақ теориясының қасиеттері

Шексіз ағаш теориясында түсінікті айтылған, бірақ қиын мәселелер бар. Мұндай мысалдардың бірі – Курепа болжамы және Суслин болжамы. Бұл екі мәселенің екеуі де Зермело-Франкель жиын теориясынан тәуелсіз екені белгілі. Кёниг леммасы бойынша, кез келген ω ағашының шексіз тармағы болады. Ал ZFC теоремасы бойынша, санаусыз бұтақтары мен санаусыз деңгейлері жоқ санаусыз ағаштар бар; мұндай ағаштар Аронсжайн ағаштары деп аталады. Егер берілген кардинал саны κ болса, κ Суслин ағашы – бұл κ биіктігіндегі, κ өлшеміндегі тізбектері немесе антитізбектері жоқ ағаш. Атап айтқанда, егер κ жеке болса, онда κ Аронсжайн ағашы және κ Суслин ағашы бар. Шындығында, кез келген шексіз кардинал κ үшін, кез келген κ Суслин ағашы κ Аронсжайн ағашы болып табылады (керісінше дұрыс емес). Суслин болжамы бастапқыда белгілі бір толық реттелу туралы сұрақ ретінде қойылған, бірақ ол келесіге тең: кез келген ω1 биіктігіндегі ағаштың ω1 кардиналдығында антитізбегі немесе ω1 ұзындығындағы тармағы болады. Егер (T,<) ағаш болса, онда < рефлексивті жабылуы ≤, T-дағы префикс реті болады. Керісінше дұрыс емес: мысалы, Z бүтін сандар жиынындағы ≤ жалпы және, демек, префикс реті, бірақ (Z,<) жиын теориялық ағаш емес, себебі мысалы, {n ∈ Z: n < 0} жиынында ең кіші элемент жоқ.

Шексіз ағаштардың мысалдары

Болсын – ординал сан, ал – жиын. Егер функцияның анықталу облысы функцияның анықталу облысының нағыз қосалқы жиыны болса және екі функция анықталу облысында сәйкес келсе, онда ол жиындық-теориялық ағаш деп анықталады. Оның түбірі – бос жиындағы бірегей функция, ал оның биіктігі – . Ағаш бойымен барлық функциялардың біріктірілуі – функцияны береді , яғни, жиынның мүшелерінің обобщенді тізбегі. Егер – лимит ординалы болса, ешбір тармақта максималды элемент ("жапырақ") болмайды. Суретте және үшін мысал келтірілген. Компьютер ғылымындағы әрбір ағаш дерек құрылымы – жиындық-теориялық ағаш болып табылады: екі түйін үшін , егер – тура ұрпағы болса, деп анықталады. Тамыр, түйін биіктігі және тармақ ұзындығы ұғымдары сәйкес келеді, ал ағаш биіктігі ұғымдары бірлікке қана ерекшеленеді. Автоматтар теориясында қарастырылатын шексіз ағаштар (мысалы, ағаш (автоматтар теориясы)) де жиындық-теориялық ағаштар болып табылады, олардың ағаш биіктігі дейін жетеді. Граф теориялық ағашты, тамыр түйінін таңдап және егер және түйіндерінен бастап соңғы түйінге дейінгі (бірегей) бағытталмаған жолда жатса, жиындық-теориялық ағашқа айналдыруға болады. Әрбір Кантор ағашы, Курепа ағашы және Лавер ағашы – жиындық-теориялық ағаш болып табылады.