Жақсы дерлік реттеулер және математикалық салыстырулар

Кіріспе

Математикалық ұғым, объектілерді салыстыру үшін

Математикада, әсіресе реттік теорияда, жиынтақтағы жақсы квазиреттік немесе wqo – бұл жиынның әрбір шексіз тізбегінде өсумен жұп элементтері болатын квазиреттік.

Мотивация

Жақсы негізделген индукция жақсы негізделген қатынасы бар кез келген жиынтыққа қолданылуы мүмкін, сондықтан квазиреттің жақсы негізделгендігі қызығушылық тудырады. (Бұл жерде терминологияны шартты түрде қолдана отырып, сәйкес қатаң рет жақсы негізделген қатынас болса, квазирет жақсы негізделген деп есептеледі.) Дегенмен, жақсы негізделген квазиреттер класы кейбір операциялар бойынша жабық емес – яғни, квазирет бастапқы жиынтықтан туындаған құрылымдар жиынтығында жаңа квазирет алу үшін қолданылғанда, осы квазирет жақсы негізделмеген болуы мүмкін. Бастапқы жақсы негізделген квазиреттеуге қатаң шектеулер қою арқылы, туындаған квазиреттеулердің де жақсы негізделгендігін қамтамасыз етуге болады. Мұның мысалы – қуат жиыны операциясы. Жиынтық үшін берілген квазиреттеуді пайдаланып, оның қуат жиынында квазиретті былай анықтауға болады: егер және тек қана оның әрбір элементі үшін, берілген элементке қатысты үлкен элемент табылатын болса. Осы қуат жиынындағы квазиреттің жақсы негізделмеуі мүмкін екенін көрсетуге болады, бірақ егер бастапқы квазиреттеу жақсы квазиреттеу болса, онда ол жақсы негізделген болады.

Ресми анықтама

Жинақтағы жақсы квазиреттеу – бұл квазиреттеу (яғни рефлексивті, транзитивті екілік қатынас), онда жинақтың кез келген шексіз тізбегінде өсуге бағытталған жұп болады. Жинақ жақсы квазиреттелген деп аталады, немесе қысқаша wqo. Жақсы жартылай реттеу немесе wpo – бұл дұрыс реттеу қатынасы болып табылатын wqo, яғни антисимметриялы. Wqo-ны анықтаудың тағы бір жолы – олар шексіз қатаң түрде кемитін тізбектерді ( түрінде) немесе жұп-жұп салыстыруға келмейтін элементтердің шексіз тізбектерін қамтымайтын квазиреттеулер деп айту. Сондықтан, квазиреттеу (X, ≤) wqo болады, егер және тек қана (X, <) жақсы негізделген және шексіз антижелілері болмаса.

Қатарлық тип

Жақсы түрде ішінара реттелген болсын. Элементтердің (қажетті түрде шекті) тізбегі, онда ешқандай жұп элементтер бір-бірінен үлкен немесе кіші болмайтын жағдайда, әдетте "жаман тізбек" деп аталады. "Жаман тізбектер ағашы" – әрбір жаман тізбек үшін бір түйін болатын және әрбір бос емес жаман тізбектің түйінін оның "аталық" түйінімен байланыстыратын ағаш. Ағаштың түбірі бос тізбекке сәйкес келеді. Ағашта шексіз жаман тізбек болмағандықтан, түбірден басталатын шексіз жол да болмайды. Сондықтан, ағаштың әрбір түйіні ординалдық биіктікке ие, ол трансфиниттік индукция арқылы анықталады. Ағаштың ординалдық түрі, деп белгіленетін, – түбірдің ординалдық биіктігіне тең. Ішінара реттіліктің сызықтықталуы – ішінара реттілікті толық реттілікке кеңейту. Кез келген сызықтықталудың ординалдық түрінің жоғарғы шегі екенін тексеру оңай. Де Йонг және Парик шын мәнінде, максималды ординалдық түрге жететін сызықтықталудың әрқашан болатынын дәлелдеді.

Мысалдар

, стандартты ретпен саналатын табиғи сандар жиыны, жақсы жартылай рет (әрине, жақсы рет). Дегенмен, , оң және теріс бүтін сандар жиыны жақсы квази-рет емес, себебі ол жақсы негізделмеген (1-суретті қараңыз). , бөлінгіштік бойынша реттелген табиғи сандар жиыны жақсы квази-рет емес: жай сандар шексіз антижелтесі (2-суретті қараңыз). , компоненттік ретпен табиғи сандардың векторларының жиынтығы (мұнда шектелген) жақсы ішінара рет (Диксонның леммасы; 3-суретті қараңыз). Жалпы, егер жақсы квази-рет болса, онда барлық үшін де жақсы квази-рет болады. кем дегенде екі элементі бар кез келген шекті жиын үшін. Лексикографиялық түрде (дәптердегідей) реттелген сөздер жиыны жақсы квази-рет емес, өйткені ол шексіз төмендеу тізбегін қамтиды. Сол сияқты, префикс қатынасы бойынша реттелген жақсы квази-рет емес, себебі бұл тізбек осы ішінара реттің шексіз антижелтесі болып табылады. Алайда, субтізбек қатынасы бойынша реттелген жақсы жартылай рет болып табылады. (Егер бір элементтен ғана тұрса, бұл үш ішінара рет бірдей болады.) Жалпы, , ендіру арқылы реттелген шекті тізбектер жиыны жақсы квази-рет болады, егер және тек қана жақсы квази-рет болса (Хигман леммасы). Еске сала кетейік, тізбегін тізбегіне ендіру үшін тізбегінен тізбегінің ұзындығымен бірдей және оның әрбір мүшесімен үстем болатын субтізбек табу керек. Хигман леммасы шексіз тізбектерге қолданылмайды. Хигман леммасын кез келген ұзындығы бар тізбектерге жалпылау үшін жақсы квази-реттер енгізілді. Wqo элементтерімен белгіленген түйіндері бар шекті ағаштар арасындағы ендіру wqo болып табылады (Крускалдың ағаш теоремасы). Wqo элементтерімен белгіленген түйіндері бар шексіз ағаштар арасындағы ендіру wqo болып табылады (Нэш Уильямс теоремасы). Саналатын шашыраңқы сызықтық реттік типтер арасындағы ендіру жақсы квази-рет (Лавер теоремасы). Саналатын Буль алгебралары арасындағы ендіру жақсы квази-рет. Бұл Лавер теоремасы мен Кетонен теоремасынан туындайды. "Граф кіші" деп аталатын ендіру түсінігімен реттелген шекті графтар жақсы квази-рет (Робертсон–Сеймур теоремасы). Индукциялық субграф қатынасы бойынша реттелген шекті ағаш тереңдігінің графтары, сондай-ақ индукциялық субграфтар бойынша реттелген кографтар да жақсы квази-рет құрайды.

, the set of natural numbers with standard ordering, is a well partial order (in fact, a well order). However, , the set of positive and negative integers, is not a well quasi order, because it is not well founded (see Pic.1). , the set of natural numbers ordered by divisibility, is not a well quasi order: the prime numbers are an infinite antichain (see Pic.2). , the set of vectors of natural numbers (where is finite) with component wise ordering, is a well partial order (Dickson's lemma; see Pic.3). More generally, if is well quasi order, then is also a well quasi order for all Let be an arbitrary finite set with at least two elements. The set of words over ordered lexicographically (as in a dictionary) is not a well quasi order because it contains the infinite decreasing sequence Similarly, ordered by the prefix relation is not a well quasi order, because the previous sequence is an infinite antichain of this partial order. However, ordered by the subsequence relation is a well partial order. (If has only one element, these three partial orders are identical.) More generally, , the set of finite sequences ordered by embedding is a well quasi order if and only if is a well quasi order (Higman's lemma). Recall that one embeds a sequence into a sequence by finding a subsequence of that has the same length as and that dominates it term by term. When is an unordered set, if and only if is a subsequence of , the set of infinite sequences over a well quasi order , ordered by embedding, is not a well quasi order in general. That is, Higman's lemma does not carry over to infinite sequences. Better quasi orderings have been introduced to generalize Higman's lemma to sequences of arbitrary lengths. Embedding between finite trees with nodes labeled by elements of a wqo is a wqo (Kruskal's tree theorem). Embedding between infinite trees with nodes labeled by elements of a wqo is a wqo (Nash Williams' theorem). Embedding between countable scattered linear order types is a well quasi order (Laver's theorem). Embedding between countable boolean algebras is a well quasi order. This follows from Laver's theorem and a theorem of Ketonen. Finite graphs ordered by a notion of embedding called "graph minor" is a well quasi order (Robertson–Seymour theorem). Graphs of finite tree depth ordered by the induced subgraph relation form a well quasi order, as do the cographs ordered by induced subgraphs.

Берілгеннен жаңа wpo-ларды құру

Let және be екі бірікпес wpo жиынтығы. Егер және тек егер үшін бірдей болса, онда , және , ординалдардың табиғи қосындысын білдіреді. wpo жиынын келтірсек, элементтерінің ішінара реттелген элементтермен белгіленген барлық шекті тамырлы ағаштар жиыны болсын. Ағаш ендіру қатынасы бойынша ішінара реттеңіз. Крускальдың ағаш теоремасы бойынша, wpo. Бұл нәтиже тіпті (белгісі жоқ ағаштарға сәйкес келетін) жағдай үшін де маңызды, онда ол кішкентай Веблен ординалына тең. Жалпы, егер санаулы болса, онда ординалдық құлдырау функциясы тұрғысынан жоғарғы шек болады. (Бұл ординалдық белгілеуде кішкентай Веблен ординалы тең.)

WQ-ның ішінара тапсырысқа қарсы

Іс жүзінде, wqo-ның бір амалдары көбінесе реттеулер емес (жоғарыдағы мысалдарды қараңыз), және теория антисимметрия талап етілмесе техникалық тұрғыдан тегіс болады, сондықтан ол wqo-ны негізгі ұғым ретінде пайдаланады. Екінші жағынан, Milner 1985 жұмысына сәйкес, жартылай реттеулерді қарастыру ішінара реттеулерге қарағанда ешқандай нақты жалпылауға жеткізбейді, бұл тек ыңғайлырақ. Wpo – бұл wqo екенін және wqo-ның ядросынан туындаған баламалық кластар арасындағы wpo-ға wqo әкелетінін ескеріңіз. Мысалы, егер бөлінгіштік бойынша реттесек, онда және тек егер , сонда болады.

Шексіз өсіп келе жатқан кіші тізбектер

Егер wqo болса, онда кез келген шексіз тізбекте шексіз өсетін кіші тізбек болады (бар). Мұндай кіші тізбек кейде "толық" деп аталады. Бұл Рамзи аргументімен дәлелдеуге болады: берілген тізбек үшін, оң жағында өзінен үлкен немесе тең элементі жоқ индекстер жиынын қарастырайық, яғни, егер тізбек шексіз болса, онда алынған кіші тізбек wqo екендігі туралы болжамға қайшы келеді. Демек, жиын шекті, ал оның кез келген индексінен үлкен кез келген индекс шексіз өсетін кіші тізбектің бастапқы нүктесі ретінде қолданылуы мүмкін. Мұндай шексіз өсетін кіші тізбектердің болуы кейде жақсы квази-реттелудің анықтамасы ретінде қарастырылады, бұл эквивалентті ұғымға алып келеді.

Wqos қасиеттері

Квазиреттеме берілген болжамда, егер және тек қана wqo болса, онда анықталған квазиреттеме жақсы негізделген.