Funkcja zachowująca limit (teoria porządku)
W matematycznym obszarze teorii porządku często mówi się o funkcjach , które zachowują pewne granice, tj. pewną supremę lub infimę . . Z grubsza mówiąc, te funkcje odwzorowują supremum/infimum zbioru na supremum/infimum obrazu zbioru. W zależności od rodzaju zbiorów, dla których funkcja spełnia tę właściwość, może zachować skończoną, skierowaną, niepustą lub po prostu dowolną supremę lub infimę. Każdy z tych wymogów pojawia się naturalnie i często w wielu obszarach teorii porządku i istnieją różne ważne relacje między tymi pojęciami i innymi pojęciami, takimi jak monotoniczność . Jeśli implikacja zachowania granic jest odwrócona, tak że istnienie granic w zakresie funkcji implikuje istnienie granic w dziedzinie, to otrzymuje się funkcje, które odzwierciedlają granice .
Celem niniejszego artykułu jest wyjaśnienie definicji tych podstawowych pojęć, co jest konieczne, ponieważ literatura nie zawsze jest w tym miejscu spójna, oraz przedstawienie ogólnych wyników i wyjaśnień dotyczących tych zagadnień.
Tło i motywacja
W wielu wyspecjalizowanych obszarach teorii porządku ogranicza się do klas zbiorów częściowo uporządkowanych , które są kompletne pod względem pewnych konstrukcji granicznych. Na przykład w teorii sieci interesują nas rzędy, w których wszystkie skończone niepuste zbiory mają zarówno najmniejszą górną granicę, jak i największą dolną granicę. Z drugiej strony w teorii dziedzin koncentruje się na zbiorach częściowo uporządkowanych, w których każdy skierowany podzbiór ma supremum. Kompletne kraty i rzędy z najmniejszym elementem („puste supremum”) dostarczają dalszych przykładów.
We wszystkich tych przypadkach granice odgrywają główną rolę w teoriach, wspieranych przez ich interpretacje w praktycznych zastosowaniach każdej dyscypliny. Interesuje nas również określenie odpowiednich odwzorowań między takimi zamówieniami. Z algebraicznego punktu widzenia oznacza to, że chce się znaleźć odpowiednie pojęcia homomorfizmów dla rozważanych struktur. Osiąga się to poprzez uwzględnienie tych funkcji, które są kompatybilne z konstrukcjami charakterystycznymi dla poszczególnych zamówień. Na przykład homomorfizmy kratowe to te funkcje, które zachowują niepuste skończone suprema i infima, czyli obraz supremum/infimum dwóch elementów jest właśnie supremum/infimum ich obrazów. W teorii dziedzin często mamy do czynienia z tak zwanymi ciągłymi Scotta , które zachowują wszystkie skierowane supremy.
Podstawy dla podanych poniżej definicji i terminologii można znaleźć w teorii kategorii , gdzie rozważa się granice (i współograniczenia ) w bardziej ogólnym sensie. Kategoryczna koncepcja funktorów zachowujących granice i odzwierciedlających granice jest całkowicie zgodna z teorią rzędów, ponieważ rzędy można traktować jako małe kategorie zdefiniowane jako kategorie pozetowe z określoną dodatkową strukturą.
Definicja formalna
Rozważmy dwa częściowo uporządkowane zbiory P i Q oraz funkcję f od P do Q . Ponadto niech S będzie podzbiorem P , który ma najmniejszą górną granicę s . Wtedy f zachowuje supremum S , jeśli zbiór f ( S ) = { f ( x ) | x w S } ma najmniejszą górną granicę w Q , która jest równa f ( s ), tj
- fa (nad S ) = na górze fa ( S )
Zauważ, że ta definicja składa się z dwóch wymagań: supremum zbioru f ( S ) istnieje i jest równe f ( s ). Odpowiada to wspomnianej wyżej paraleli z teorią kategorii, ale nie zawsze jest wymagane w literaturze. W rzeczywistości w niektórych przypadkach można osłabić definicję, wymagając, aby tylko istniejąca suprema była równa f ( s ). Jednak Wikipedia działa zgodnie z powszechnym pojęciem podanym powyżej i wyraźnie określa drugi warunek, jeśli jest to wymagane.
Z podanej powyżej podstawowej definicji można wyprowadzić szeroki zakres użytecznych właściwości. Mówi się, że funkcja f między posetami P i Q zachowuje supremę skończoną, niepustą, skierowaną lub arbitralną, jeśli zachowuje supremę odpowiednio wszystkich skończonych, niepustych, skierowanych lub arbitralnych zbiorów. Zachowanie niepustej skończonej supremy można również zdefiniować tożsamością f ( x v y ) = f ( x ) v f ( y ), zachowując dla wszystkich elementów x i y , gdzie zakładamy, że v jest funkcją całkowitą w obu rzędach.
W dwojaki sposób definiuje się właściwości dla zachowania infimy.
Warunek „przeciwny” do zachowania granic nazywamy odbiciem. Rozważmy funkcję f jak powyżej i podzbiór S z P , taki że sup f ( S ) istnieje w Q i jest równe f ( s ) dla pewnego elementu s z P . Wtedy f odzwierciedla supremum S , jeśli sup S istnieje i jest równe s . Jak już wykazano dla zachowania, można uzyskać wiele dodatkowych własności, biorąc pod uwagę pewne klasy zbiorów S i dualizując definicję do infima.
Przypadki specjalne
Niektóre szczególne przypadki lub właściwości wywodzące się z powyższego schematu są znane pod innymi nazwami lub mają szczególne znaczenie dla niektórych obszarów teorii porządku. Na przykład funkcje, które zachowują puste supremum, to te, które zachowują najmniejszy element. Ponadto, ze względu na motywację wyjaśnioną wcześniej, wiele funkcji zachowujących granice pojawia się jako specjalne homomorfizmy dla pewnych struktur porządku. Niektóre inne wybitne przypadki podano poniżej.
Zachowanie wszystkich granic
Ciekawa sytuacja ma miejsce, gdy funkcja zachowuje całą supremę (lub infimę). Dokładniej, wyraża się to stwierdzeniem, że funkcja zachowuje wszystkie istniejące suprema (lub infima) i równie dobrze może się zdarzyć, że rozważane pozycje nie są kompletnymi sieciami. Na przykład (monotoniczne) połączenia Galois mają tę właściwość. I odwrotnie, na mocy teoretycznego twierdzenia o funktorze sprzężonym, odwzorowania, które zachowują wszystkie suprema/infima, mogą być zagwarantowane jako część unikalnego połączenia Galois, o ile spełnione są pewne dodatkowe wymagania.
Dystrybucja
Krata L jest rozdzielna , jeśli dla wszystkich x , y i z w L , znajdziemy
Ale to po prostu mówi, że funkcja meet ^: L -> L zachowuje supremę binarną . W teorii sieci wiadomo, że warunek ten jest równoważny jego podwójnemu, czyli funkcji v: L -> L zachowującej infimy binarne. W podobny sposób widać, że prawo nieskończonej rozdzielności
kompletnych algebr Heytinga (patrz także topologia bezsensowna ) jest równoważne funkcji meet ^ zachowującej dowolne supremy. Warunek ten nie implikuje jednak jego dwoistości.
Ciągłość Scotta
Funkcje, które zachowują ukierunkowaną supremę, nazywane są ciągłą Scotta lub czasami po prostu ciągłą , jeśli nie powoduje to nieporozumień z odpowiednią koncepcją analizy i topologii . Podobne użycie terminu ciągłe dla zachowania granic można również znaleźć w teorii kategorii.
Ważne właściwości i wyniki
Powyższa definicja zachowania granic jest dość mocna. Rzeczywiście, każda funkcja, która zachowuje przynajmniej supremę lub infimę łańcuchów dwuelementowych, tj. zbiorów dwóch porównywalnych elementów, jest z konieczności monotoniczna. Dlatego wszystkie wymienione powyżej specjalne właściwości konserwujące powodują monotoniczność.
Opierając się na fakcie, że niektóre ograniczenia można wyrazić w kategoriach innych, można wyprowadzić powiązania między właściwościami zachowania. Na przykład funkcja f zachowuje supremę ukierunkowaną wtedy i tylko wtedy, gdy zachowuje supremę wszystkich ideałów. Co więcej, odwzorowanie f z posetu, w którym istnieje każde niepuste skończone supremum (tzw. sup-semilattice) zachowuje arbitralną supremę wtedy i tylko wtedy, gdy zachowuje zarówno ukierunkowaną, jak i skończoną (ewentualnie pustą) supremę.
Jednak nie jest prawdą, że funkcja, która zachowuje całą supremę, zachowałaby również całą infimę lub odwrotnie.