Cóż-quasi-zamawianie - Well-quasi-ordering

W matematyce , a konkretnie w teorii porządku , dobrze-quasi-porządkowanie lub wqo jest quasi-porządkowaniem takim, że każda nieskończona sekwencja elementów z zawiera rosnącą parę z . ${\displaystyle x_{0},x_{1},x_{2},\ldots}$${\ Displaystyle X}$${\displaystyle x_{i}\leq x_{j}}$${\displaystyle i<j}$

Motywacja

Uzasadniona indukcja może być zastosowana na dowolnym zbiorze z ugruntowaną relacją, dlatego interesuje nas, kiedy quasi-porządek jest ugruntowany. (Tutaj, przez nadużycie terminologii, mówi się , że quasiorder jest dobrze uzasadniony, jeśli odpowiadający mu ścisły porządek jest dobrze ugruntowaną relacją.) Jednak klasa dobrze uzasadnionych quasiporządków nie jest zamykana w pewnych operacjach — to znaczy, gdy quasi-porządek jest używany do uzyskania nowego quasi-porządku na zbiorze struktur wyprowadzonych z naszego pierwotnego zbioru, ten quasi-porządek okazuje się nieuzasadniony. Nakładając silniejsze ograniczenia na oryginalne, dobrze ugruntowane quasiordering, można mieć nadzieję, że nasze pochodne quasiorderings są nadal dobrze ugruntowane. ${\displaystyle \leq}$${\displaystyle x\leq y\land y\nleq x}$

Przykładem tego jest działanie zestawu mocy . Mając dane quasiorderze dla zbioru można zdefiniować quasiorder na potęgę zbioru przez ustawienie wtedy i tylko wtedy, gdy dla każdego elementu można znaleźć jakiś element, który jest większy od niego względem . Można pokazać, że to quasi-porządkowanie nie musi być dobrze ugruntowane, ale jeśli weźmie się oryginalne quasi-porządkowanie za dobrze-quasi-porządkowanie, to tak jest. ${\displaystyle \leq}$${\ Displaystyle X}$${\ Displaystyle \ Leq ^ {+}}$${\ Displaystyle X}$${\ Displaystyle P (X)}$${\ Displaystyle A \ leq ^ {+} B}$${\ Displaystyle A}$${\ Displaystyle B}$${\displaystyle \leq}$${\ Displaystyle P (X)}$

Formalna definicja

Dobrze quasi zamawiania na zestawie jest quasi zamawiania (tj zwrotny , przechodni związek binarny ) tak, że każdy nieskończony sekwencję elementów z obejmuje coraz więcej pary z . Mówi się, że zestaw jest dobrze uporządkowany , lub w skrócie wqo . ${\ Displaystyle X}$ ${\displaystyle x_{0},x_{1},x_{2},\ldots}$${\ Displaystyle X}$${\displaystyle x_{i}\leq x_{j}}$${\displaystyle i<j}$${\ Displaystyle X}$

Dobrze częściowy porządek lub WPO , jest wqo że jest właściwa relacja zamawiania, to znaczy że jest antysymetryczny .

Wśród innych sposobów definiowania wqo's można powiedzieć, że są to quasi-porządkowania, które nie zawierają nieskończonych ciągów ściśle malejących (formy ) ani nieskończonych ciągów parami nieporównywalnych elementów. Stąd quasi-porządek ( X , ≤) jest wqo wtedy i tylko wtedy, gdy ( X , <) jest dobrze uzasadniony i nie ma nieskończonych antyłańcuchów . ${\displaystyle x_{0}>x_{1}>x_{2}>\cdots}$

Przykłady

Rys.1: Liczby całkowite w zwykłej kolejności

Rys.2: Diagram Hassego liczb naturalnych uporządkowanych według podzielności

Rys.3: Diagram Hassego z kolejnością komponentów${\ Displaystyle \ mathbb {N} ^ {2}}$

• ${\ Displaystyle (\ mathbb {N} , \ leq )}$, zbiór liczb naturalnych o standardowym uporządkowaniu, jest porządkiem dobrze częściowym (w rzeczywistości porządkiem prawidłowym ). Jednak zbiór liczb całkowitych dodatnich i ujemnych nie jest dobrym quasi-rządem, ponieważ nie jest dobrze uzasadniony (patrz rys. 1).${\ Displaystyle (\ mathbb {Z} , \ leq )}$

• ${\ Displaystyle (\ mathbb {N} , |)}$, zbiór liczb naturalnych uporządkowanych według podzielności, nie jest dobrym quasi-porządkiem: liczby pierwsze są nieskończonym antyłańcuchem (patrz rys. 2).

• ${\ Displaystyle (\ mathbb {N} ^ {k} \ leq)}$, zbiór wektorów liczb naturalnych (gdzie jest skończony) z uporządkowaniem składowym , jest porządkiem dobrze cząstkowym ( lemat Dicksona ; patrz Rys.3). Bardziej ogólnie, jeśli jest dobrze quasi-porządkiem, to jest również dobrze-quasi-porządkiem dla wszystkich .${\displaystyle k}$${\displaystyle k}$${\displaystyle (X,\leq)}$${\ Displaystyle (X ^ {k}, \ leq ^ {k})}$${\displaystyle k}$

• Niech będzie dowolnym zbiorem skończonym z co najmniej dwoma elementami. Zestaw z słowy przez uporządkowane leksykograficznie (jak w słowniku) jest nie dobrze prawie rzędu, ponieważ zawiera sekwencję nieskończoną maleje . Podobnie, relacja uporządkowana według prefiksu nie jest dobrze-quasi-porządkiem, ponieważ poprzednia sekwencja jest nieskończonym antyłańcuchem tego częściowego porządku. Jednak uporządkowanie według relacji podciągu jest porządkiem częściowym. (Jeśli ma tylko jeden element, te trzy częściowe zamówienia są identyczne.)${\ Displaystyle X}$${\ Displaystyle X ^ {*}}$ ${\ Displaystyle X}$${\displaystyle b,ab,aab,aaab,\ldots}$${\ Displaystyle X ^ {*}}$${\ Displaystyle X ^ {*}}$${\ Displaystyle X}$

• Bardziej ogólnie, zbiór skończonych ciągów uporządkowanych przez osadzanie jest dobrze-quasi-porządkiem wtedy i tylko wtedy, gdy jest dobrze-quasi-porządkiem ( lemat Higmana ). Przypomnijmy, że osadza się sekwencję w sekwencji , znajdując podciąg, który ma taką samą długość jak i który dominuje w nim termin po terminie. When jest zbiorem nieuporządkowanym, wtedy i tylko wtedy, gdy jest podciągiem .${\ Displaystyle (X ^ {*}, \ leq)}$${\ Displaystyle X}$${\displaystyle (X,\leq)}$${\ Displaystyle u}$${\displaystyle v}$${\displaystyle v}$${\ Displaystyle u}$${\ Displaystyle (X, =)}$${\displaystyle u\leq v}$${\ Displaystyle u}$${\displaystyle v}$

• ${\ Displaystyle (X ^ {\ omega}, \ leq)}$, zbiór nieskończonych ciągów nad dobrze-quasi-porządkiem , uporządkowany przez osadzanie, nie jest ogólnie dobrze-quasi-porządkiem. Oznacza to, że lemat Higmana nie przenosi się na ciągi nieskończone. Wprowadzono lepsze quasi-porządkowanie , aby uogólnić lemat Higmana na sekwencje o dowolnych długościach.${\displaystyle (X,\leq)}$

• Osadzenie pomiędzy drzewami skończonymi z węzłami oznaczonymi elementami wqo jest wqo ( twierdzenie drzewa Kruskala ).${\displaystyle (X,\leq)}$

• Osadzenie między nieskończonymi drzewami z węzłami oznaczonymi elementami wqo jest wqo ( twierdzenie Nasha-Williamsa ).${\displaystyle (X,\leq)}$

• Osadzanie między policzalnymi rozproszonymi typami rzędów liniowych jest dobrym quasi-porządkiem ( twierdzenie Lavera ).

• Osadzanie między policzalnymi algebrami boolowskimi jest dobrym quasi-rządem. Wynika to z twierdzenia Lavera i twierdzenia Ketonena.

• Grafy skończone uporządkowane według pojęcia zanurzenia zwanego „ grafem mniejszym ” są dobrze quasi-rządem ( twierdzenie Robertsona-Seymoura ).

• Wykresy o skończonej głębokości drzewa uporządkowane przez indukowaną relację podgrafu tworzą dobrze-quasi-rząd, podobnie jak cografy uporządkowane przez indukowane podgrafy .

Wqo kontra dobrze częściowe zamówienia

W praktyce manipulacje wqo nie są często porządkowaniem (patrz przykłady powyżej), a teoria jest technicznie gładsza, jeśli nie wymagamy antysymetrii, więc jest zbudowana z wqo jako podstawowym pojęciem. Z drugiej strony, według Milnera 1985, nie uzyskuje się żadnego realnego zysku w ogólności, rozważając raczej quasi-porządki niż rzędy częściowe... po prostu wygodniej jest to zrobić.

Zauważ, że wpo jest wqo, a wqo daje początek wpo między klasami równoważności wywołanymi przez jądro wqo. Na przykład, jeśli uporządkowamy według podzielności, otrzymamy wtedy i tylko wtedy , gdy , więc . ${\ Displaystyle \ mathbb {Z}}$${\displaystyle n\równoważne m}$${\displaystyle n=\pm m}$${\ Displaystyle (\ mathbb {Z} , |) \ w przybliżeniu (\ mathbb {N}, |)}$

Nieskończone rosnące podciągi

Jeśli jest wqo, to każda nieskończona sekwencja zawiera nieskończony rosnący podciąg (z ). Taki podciąg nazywany jest czasem doskonałym . Można to udowodnić za pomocą argumentu Ramseya : mając pewną sekwencję , rozważ zbiór indeksów taki, że nie ma większego ani równego po prawej stronie, tj . z . Jeśli jest nieskończony, to wyekstrahowany podciąg przeczy założeniu, że jest wqo. Tak samo jest skończone, a każdy z indeksem większym niż jakikolwiek in może być użyty jako punkt początkowy nieskończonego rosnącego podciągu. ${\displaystyle (X,\leq)}$${\displaystyle x_{0},x_{1},x_{2},\ldots,}$${\displaystyle x_{n_{0}}\leq x_{n_{1}}\leq x_{n_{2}}\leq \cdots}$${\displaystyle n_{0}<n_{1}<n_{2}<\cdots }$${\ Displaystyle (x_ {i}) _ {i}}$${\ Displaystyle I}$${\displaystyle i}$${\displaystyle x_{i}}$${\displaystyle x_{j}}$${\displaystyle i<j}$${\ Displaystyle I}$${\ Displaystyle I}$${\ Displaystyle X}$${\ Displaystyle I}$${\displaystyle x_{n}}$${\ Displaystyle n}$${\ Displaystyle I}$

Istnienie takich nieskończenie rosnących podciągów jest czasami traktowane jako definicja dobrze quasi-porządku, prowadząc do równoważnego pojęcia.

Właściwości wqos

• Przy danym quasiporządkowaniu quasiporządkowanie zdefiniowane przez jest uzasadnione wtedy i tylko wtedy, gdy jest wqo.${\displaystyle (X,\leq)}$${\ Displaystyle (P (X), \ leq ^ {+})}$${\ Displaystyle A \ równoważnik ^ {+} B \ iff \ dla wszystkich a \ w A \ istnieje b \ w B a \ równoważnik b}$${\displaystyle (X,\leq)}$

• Quasiordering jest wqo wtedy i tylko wtedy, gdy odpowiadający mu porządek częściowy (otrzymany przez iloraz przez ) nie ma nieskończonych sekwencji malejących ani antyłańcuchów . (Można to udowodnić za pomocą argumentu Ramseya, jak powyżej).${\ Displaystyle x \ sim r \ if x \ równoważnik r \ ziemia r \ równoważnik x}$

• Przy dobrze quasi-porządkowaniu dowolna sekwencja podzbiorów zamkniętych w górę ostatecznie stabilizuje się (co oznacza, że ​​istnieje taki, że ; podzbiór jest nazywany w górę- zamkniętym jeśli ): zakładając, że jest przeciwnie , sprzeczność jest osiągana przez wyodrębnienie nieskończonego podciągu nie rosnącego .${\displaystyle (X,\leq)}$${\displaystyle S_{0}\subseteq S_{1}\subseteq\cdots \subseteq X}$${\ Displaystyle n \ w \ mathbb {N}}$${\ Displaystyle S_ {n} = S_ {n + 1} = \ cdots}$${\displaystyle S\subseteq X}$${\ Displaystyle \ forall x, y \ w X, x \ leq r \ klin x \ w S \ strzałka w prawo r \ w s}$${\ Displaystyle \ dla wszystkich ja \ w \ mathbb {N} \ istnieje j \ w \ mathbb {N} j> ja \ istnieje x \ w S_ {j} \ setminus S_ {i}}$

• Biorąc pod uwagę dobrze quasi-zamawiania , każdy podzbiór z ma skończoną liczbę elementów z minimalnym zakresie , bo inaczej minimalnych elementów stanowiłoby nieskończoną antyłańcuch.${\displaystyle (X,\leq)}$${\displaystyle S}$${\ Displaystyle X}$${\displaystyle \leq}$${\displaystyle S}$

Uwagi

^ Tutajx<yoznacza:i${\displaystyle x\leq y}$${\displaystyle y\nleq x.}$

Bibliografia

• Dickson, LE (1913). „Skończoność nieparzystych doskonałych i prymitywnych liczb obfitych z r odrębnymi czynnikami pierwszymi”. American Journal of Mathematics . 35 (4): 413–422. doi : 10.2307/2370405 . JSTOR  2370405 .
• Higman, G. (1952). „Porządkowanie przez podzielność w algebrach abstrakcyjnych”. Procedury Londyńskiego Towarzystwa Matematycznego . 2 : 326–336. doi : 10.1112/plms/s3-2.1.326 .
• Kruskal, JB (1972). „Teoria dobrego quasi-porządkowania: często odkrywana koncepcja” . Czasopismo Teorii Kombinatorycznej . Seria A. 13 (3): 297-305. doi : 10.1016/0097-3165(72)90063-5 .
• Ketonen, Jussi (1978). „Struktura policzalnych algebr Boole'a”. Roczniki Matematyki . 108 (1): 41–89. doi : 10.2307/1970929 . JSTOR  1970929 .
• Milner, EC (1985). „Podstawowa teoria WQO i BQO”. W Rywalu I. (red.). Wykresy i porządek. Rola grafów w teorii zbiorów uporządkowanych i jej zastosowaniach . D. Reidel Publishing Co., s. 487-502. Numer ISBN 90-277-1943-8.
• Gallier, Jean H. (1991). "Co jest takiego specjalnego w twierdzeniu Kruskala i porządkowym Γo? Przegląd niektórych wyników w teorii dowodu" . Roczniki logiki czystej i stosowanej . 53 (3): 199–260. doi : 10.1016/0168-0072(91)90022-E .

Zobacz też

• Lepsze quasi-zamawianie
• Zamawianie w przedsprzedaży
• Dobrze uporządkowany