Квазиден жақсы тапсырыс беру - Better-quasi-ordering

Жылы тапсырыс теориясы а квазидай тапсырыс беру немесе bqo Бұл квази-тапсырыс ол нашар массивтің белгілі бір түрін қабылдамайды. Кез-келген жақсы квази-тапсырыс - бұл жақсы квазиге тапсырыс беру.

Мотивация

Дегенмен жақсы квазиге тапсырыс беру тартымды ұғым, көптеген маңызды инфинитарлық операциялар квази тәртіпті сақтамайды. Байланысты мысал Ричард Радо мұны суреттейді.^[1] 1965 жылғы мақалада Криспин Нэш-Уильямс деген неғұрлым күшті ұғымды тұжырымдады квазидай тапсырыс беру сыныбы екенін дәлелдеу үшін ағаштар биіктік ω астында жақсы тапсырыс берілген топологиялық минор қатынас.^[2] Содан бері көптеген квази-тапсырыстар жақсы квази-ордерлер екендігі дәлелденіп, олардың квази-ордерлер екенін дәлелдеді. Мысалы, Ричард Лавер құрылған Лавер теоремасы (бұрын болжам Ролан Фрайзе ) шашыраңқы класс екенін дәлелдеу арқылы сызықтық тәртіп түрлері квазидай реттелген.^[3] Жақында, Карлос Мартинес-Ранеро дәлелдеді дұрыс мәжбүрлеу аксиомасы, сыныбы Aronszajn сызықтары кірістіру қатынасында жақсырақ квазиге тапсырыс берілген.^[4]

Анықтама

Жақсы квази тәртіпті теорияда жазу жиі кездеседі ${ displaystyle {_ {*}} x}$ реттілік үшін ${ displaystyle x}$ бірінші мерзім алынып тасталса. Жазыңыз ${ displaystyle [ omega] ^ {< omega}}$ ақырлы жиынтығы үшін, қатаң түрде өседі тізбектер терминдерімен ${ displaystyle omega}$және қатынасты анықтаңыз ${ displaystyle triangleleft}$ қосулы ${ displaystyle [ omega] ^ {< omega}}$ келесідей: ${ displaystyle s triangleleft t}$ егер бар болса ${ displaystyle u in [ omega] ^ {< omega}}$ осындай ${ displaystyle s}$ қатаң бастапқы сегменті болып табылады ${ displaystyle u}$ және ${ displaystyle t = {} _ {*} u}$. Қатынас ${ displaystyle triangleleft}$ емес өтпелі.

A блок ${ displaystyle B}$ шексіз ішкі жиыны болып табылады ${ displaystyle [ omega] ^ {< omega}}$ құрамында бастапқы сегмент бар^{[түсіндіру қажет ]} шексіз ішкі жиынының ${ displaystyle bigcup B}$. Квази-тапсырыс үшін ${ displaystyle Q}$, а ${ displaystyle Q}$-қалып - бұл кейбір блоктардың функциясы ${ displaystyle B}$ ішіне ${ displaystyle Q}$. A ${ displaystyle Q}$-қалып ${ displaystyle f қос нүкте B ден Q}$ деп айтылады жаман егер ${ displaystyle f (s) not leq _ {Q} f (t)}$^{[түсіндіру қажет ]} әр жұп үшін ${ displaystyle s, t in B}$ осындай ${ displaystyle s triangleleft t}$; басқаша ${ displaystyle f}$ болып табылады жақсы. Квазиге тапсырыс беру ${ displaystyle Q}$ а деп аталады квазидай тапсырыс беру егер жаман болмаса ${ displaystyle Q}$-қалып.

Осы анықтамамен жұмыс істеуді жеңілдету үшін Нэш-Уильямс а тосқауыл элементтері жұптасатын блок болу теңдесі жоқ қосу қатынасы бойынша ${ displaystyle subset}$. A ${ displaystyle Q}$- массив Бұл ${ displaystyle Q}$- домені кедергі болатын үлгі. Кез-келген блокта тосқауыл бар екенін байқап, оны көруге болады ${ displaystyle Q}$ жаман емес болса ғана жақсы квази-тапсырыс ${ displaystyle Q}$- массив.

Симпсонның балама анықтамасы

Симпсон баламалы анықтамасын енгізді квазидай тапсырыс беру жөнінде Borel функциялары ${ displaystyle [ omega] ^ { omega} дейін Q}$, қайда ${ displaystyle [ omega] ^ { omega}}$, шексіз жиындарының жиынтығы ${ displaystyle omega}$, әдеттегідей беріледі өнім топологиясы.^[5]

Келіңіздер ${ displaystyle Q}$ квази-тапсырыс беруші болыңыз ${ displaystyle Q}$ бірге дискретті топология. A ${ displaystyle Q}$- массив бұл Borel функциясы ${ displaystyle [A] ^ { omega} дейін Q}$ кейбір шексіз ішкі жиын үшін ${ displaystyle A}$ туралы ${ displaystyle omega}$. A ${ displaystyle Q}$- массив ${ displaystyle f}$ болып табылады жаман егер ${ displaystyle f (X) not leq _ {Q} f ({_ {*}} X)}$ әрқайсысы үшін ${ displaystyle X in [A] ^ { omega}}$;${ displaystyle f}$ болып табылады жақсы басқаша. Квазиге тапсырыс беру ${ displaystyle Q}$ Бұл квазидай тапсырыс беру егер жаман болмаса ${ displaystyle Q}$- осы мағынада массив.

Негізгі теоремалар

Квазиге тәртіпті жақсарту теориясының көптеген негізгі нәтижелері Симпсонның мақаласында кездесетін Минималды жаман массив лемманың салдары болып табылады.^[5] келесідей. Лавердің қағазын қараңыз,^[6] Мұнда нәтиже ретінде Минималды жаман массив леммасы алғаш рет айтылды. Техника Нэш-Уильямстың 1965 жылғы түпнұсқалық мақаласында болған.

Айталық ${ displaystyle (Q, leq _ {Q})}$ Бұл квази-тапсырыс.^{[түсіндіру қажет ]} A ішінара рейтинг ${ displaystyle leq '}$ туралы ${ displaystyle Q}$ Бұл негізделген ішінара тапсырыс беру туралы ${ displaystyle Q}$ осындай ${ displaystyle q leq 'r - q leq _ {Q} r}$. Жаман үшін ${ displaystyle Q}$- массивтер (Симпсон мағынасында) ${ displaystyle f қос нүкте [A] ^ { omega} дейін Q}$ және ${ displaystyle g қос нүкте [B] ^ { omega} дейін Q}$, анықтаңыз:

${ displaystyle g leq ^ {*} f { text {if}} B subseteq A { text {and}} g (X) leq 'f (X) { text {for}}} X [B] ^ { omega}} ішінде$

${ displaystyle g <^ {*} f { text {if}} B subeteq A { text {and}} g (X) <'f (X) { text {for}}} X in [ B] ^ { омега}}$

Біз жаман дейміз ${ displaystyle Q}$- массив ${ displaystyle g}$ болып табылады минималды жаман (ішінара рейтингке қатысты) ${ displaystyle leq '}$) егер жаман болмаса ${ displaystyle Q}$- массив ${ displaystyle f}$ осындай ${ displaystyle f <^ {*} g}$. Анықтамалары ${ displaystyle leq ^ {*}}$ және ${ displaystyle <'}$ ішінара рейтингке байланысты ${ displaystyle leq '}$ туралы ${ displaystyle Q}$. Қатынас ${ displaystyle <^ {*}}$ қатынастың қатаң бөлігі болып табылмайды ${ displaystyle leq ^ {*}}$.

Теорема (Минималды жаман массив леммасы). Келіңіздер ${ displaystyle Q}$ болуы а квази-тапсырыс ішінара рейтингпен жабдықталған және делік ${ displaystyle f}$ жаман ${ displaystyle Q}$- массив. Содан кейін минималды жаман нәрсе бар ${ displaystyle Q}$- массив ${ displaystyle g}$ осындай ${ displaystyle g leq ^ {*} f}$.

Сондай-ақ қараңыз

• Жақсы тапсырыс
• Жақсы тапсырыс

Әдебиеттер тізімі