Elementy maksymalne i minimalne - Maximal and minimal elements

W matematyce , zwłaszcza w teorii kolejności , A ilość elementów z podzbioru S niektórych preordered zestaw jest elementem S , który nie jest mniejszy niż inny element S . Minimalna elementu podzbioru S niektórych preordered zestawu jest określony podwójnie jako element S , która jest nie większa niż jakiegokolwiek innego elementu S .

Pojęcia elementów maksymalnych i minimalnych są słabsze niż elementy największego i najmniejszego elementu, które znane są również odpowiednio jako maksimum i minimum. Maksimum podzbioru wcześniej uporządkowanego zbioru jest elementem, którego jest większy lub równy każdemu innemu elementowi, a minimum jest ponownie zdefiniowane podwójnie. W szczególnym przypadku zbioru częściowo uporządkowanego , przy czym może być co najwyżej jedno maksimum i co najwyżej jedno minimum, może być wiele elementów maksymalnych lub minimalnych. Specjalizując się dalej w zbiorach całkowicie uporządkowanych , pojęcia elementu maksymalnego i maksimum pokrywają się, a pojęcia elementu minimalnego i minimum pokrywają się. ${\displaystyle S}$${\displaystyle S}$${\displaystyle S}$${\displaystyle S}$

Na przykład w kolekcji

uporządkowany według zawierania , element { d , o } jest minimalny, ponieważ nie zawiera żadnych zestawów w kolekcji, element { g , o , a , d } jest maksymalny, ponieważ w kolekcji nie ma zestawów, które go zawierają, element { d , o , g } nie jest żadnym, a element { o , a , f } jest zarówno minimalny, jak i maksymalny. Dla kontrastu nie istnieje ani maksimum, ani minimum dla${\ Displaystyle S.}$

Lemat Zorna mówi, że każdy częściowo uporządkowany zbiór, dla którego każdy całkowicie uporządkowany podzbiór ma górną granicę, zawiera przynajmniej jeden element maksymalny. Ten lemat jest równoznaczne z twierdzeniem dobrze zamawiania i aksjomatu wyboru i pociąga za sobą poważne wyniki w innych dziedzinach matematycznych, takich jak twierdzenia Hahna-Banacha The twierdzenie Kirszbraun , Twierdzenie Tichonowa , istnienie podstawy Hamel dla każdej przestrzeni wektorowej, a istnienie algebraicznych zamknięcia dla każdego pola .

Definicja

Pozwolić być preordered zestaw i niech A maksymalny element w odniesieniu do to element taki, że ${\displaystyle (P,\leq)}$${\displaystyle S\subseteq P.}$ ${\displaystyle S}$${\displaystyle \,\leq \,}$${\ Displaystyle m \ w S}$

jeśli spełnia, to koniecznie${\ Displaystyle s \ w S}$${\displaystyle m\leq s}$${\displaystyle s\leq m.}$

Podobnie, a minimalny element wstosunku do${\displaystyle S}$${\displaystyle \,\leq \,}$jest elementemtakim, że ${\ Displaystyle m \ w S}$

jeśli spełnia, to koniecznie${\ Displaystyle s \ w S}$${\displaystyle s\leq m}$${\displaystyle m\leq s.}$

Równoważnie, jest minimalnym elementem w odniesieniu do wtedy i tylko wtedy, gdy jest maksymalnym elementem w odniesieniu do gdzie z definicji, wtedy i tylko wtedy, gdy (dla wszystkich ). ${\ Displaystyle m \ w S}$${\displaystyle S}$${\displaystyle \,\leq \,}$${\ Displaystyle m}$${\displaystyle S}$${\displaystyle \,\geq ,\,}$${\displaystyle q\geq p}$${\displaystyle p\leq q}$${\displaystyle p,q\wp}$

Jeżeli podzbiór nie jest określony, należy założyć, że Jawnie, a${\displaystyle S}$${\ Displaystyle S: = P.}$Element ilość (odpowiedniominimalny elementu)o${\displaystyle (P,\leq)}$to ilość (odp. minimalny) elementw odniesieniu do${\displaystyle S:=P}$${\displaystyle \\leq.}$

Jeśli wcześniej uporządkowany zbiór również jest zbiorem częściowo uporządkowanym (lub bardziej ogólnie, jeśli ograniczeniem jest zbiór częściowo uporządkowany), to jest to maksymalny element wtedy i tylko wtedy, gdy nie zawiera elementu ściśle większego niż jawnie, oznacza to, że nie ma istnieje dowolny element taki, że i Charakterystykę minimalnych elementów uzyskuje się za pomocą zamiast${\displaystyle (P,\leq)}$${\displaystyle (S,\leq)}$${\ Displaystyle m \ w S}$${\displaystyle S}$${\displaystyle S}$${\displaystyle m;}$${\ Displaystyle s \ w S}$${\displaystyle m\leq s}$${\displaystyle m\neq s.}$${\displaystyle \,\geq \,}$${\displaystyle \\leq.}$

Istnienie i wyjątkowość

Elementy maksymalne nie muszą istnieć.

Przykład 1: Niech gdzie oznacza liczby rzeczywiste . Dla wszystkich, ale (to znaczy, ale nie ).${\ Displaystyle S = [1, \ infty ) \ subseteq \ mathbb {R}}$${\ Displaystyle \ mathbb {R}}$${\displaystyle m\w S}$ ${\ Displaystyle s = m + 1 \ w S}$${\displaystyle m<s}$${\displaystyle m\leq s}$${\displaystyle m=s}$

Przykład 2: Niech gdzie oznacza liczby wymierne, a gdzie jest niewymierne.${\ Displaystyle S = \ {s \ w \ mathbb {Q} ~: ~ 1 \ równoważnik s ^ {2} \ równoważnik 2 \}}$${\ Displaystyle \ mathbb {Q}}$${\displaystyle {\sqrt {2}}}$

Ogólnie rzecz biorąc, jest tylko częściowym porządkiem na If jest elementem maksymalnym, a następnie pozostaje możliwe, że ani ani To pozostawia otwartą możliwość, że istnieje więcej niż jeden maksymalny element. ${\displaystyle \,\leq \,}$${\ Displaystyle S.}$${\ Displaystyle m}$${\displaystyle s\w s}$${\displaystyle s\leq m}$${\displaystyle m\leq s.}$

Przykład 3: W ogrodzeniu wszystkie są minimalne i wszystkie są maksymalne, jak pokazano na obrazku.${\displaystyle a_{1}<b_{1}>a_{2}<b_{2}>a_{3}<b_{3}>\ldots ,}$${\displaystyle a_{i}}$${\displaystyle b_{i}}$

Przykład 4: Niech A będzie zbiorem składającym się z co najmniej dwóch elementów i niech będzie podzbiorem zbioru potęgowego składającego się z pojedynczych podzbiorów , częściowo uporządkowanych przez Jest to zbiór dyskretny w którym żadnedwa elementy nie sąporównywalne a zatem każdy element jestmaksymalny (i minimalny ); co więcej, dla żadnego odrębnego ani ani${\ Displaystyle S = \ {\ {a \} ~: ~ a \ w A \}}$ ${\ Displaystyle \ wp (A)}$${\displaystyle \,\subseteq.}$${\ Displaystyle \ {a \} \ w S}$${\displaystyle a,b\w a,}$${\ Displaystyle \ {a \} \ subseteq \ {b \}}$${\ Displaystyle \ {b \} \ subseteq \ {a \}.}$

Największe elementy

Przez częściowy porządek irreflexive jądro z oznaczamy jako i jest określony przez jeśli i dla dowolnych członków dokładnie dotyczy jeden z poniższych przypadków: ${\displaystyle (P,\leq)}$${\displaystyle \,\leq \,}$${\displaystyle \,<\,}$${\displaystyle x<y}$${\displaystyle x\leq y}$${\displaystyle x\neq y.}$${\displaystyle x,y\wp}$

1. ${\displaystyle x<y}$;
2. ${\displaystyle x=y}$;
3. ${\displaystyle y<x}$;
4. ${\displaystyle x}$i są nieporównywalne.${\displaystyle y}$

Biorąc pod uwagę podzbiór i trochę${\displaystyle S\subseteq P}$${\displaystyle x\wS}$

• jeśli przypadek 1 nigdy nie dotyczy żadnego, to jest to maksymalny element, jak zdefiniowano powyżej;${\ Displaystyle y \ w S}$${\displaystyle x}$${\displaystyle S}$
• jeśli przypadek 1 i 4 nie stosuje się do jakichkolwiek wtedy nazywany jest największym elementem z${\ Displaystyle y \ w S}$${\displaystyle x}$${\ Displaystyle S.}$

Zatem definicja największego pierwiastka jest silniejsza niż maksymalnego pierwiastka.

Odpowiednio, największy element podzbioru można zdefiniować jako element, który jest większy niż każdy inny element podzbioru A może mieć co najwyżej jeden największy element. ${\displaystyle S}$${\displaystyle S}$${\ Displaystyle S.}$

Największym elementem, jeśli istnieje, jest jednocześnie elementem maksymalnym i jedynym. Przez kontrapozycji , jeśli ma kilka elementów maksymalnych, to nie może mieć największe elementu; patrz przykład 3. Jeśli spełnia warunek łańcuch rosnąco , podzbiór z ma największy element, wtedy i tylko wtedy , posiada jeden element maksymalny. ${\displaystyle S}$${\displaystyle S}$${\displaystyle S}$${\displaystyle P}$${\displaystyle S}$${\displaystyle P}$

Gdy ograniczenie do jest porządkiem całkowitym ( na górnym obrazku jest przykład), to pojęcia elementu maksymalnego i elementu największego pokrywają się. Nie jest to warunek konieczny: tam, gdzie występuje największy element, pojęcia są również zbieżne, jak wspomniano powyżej. Jeśli pojęcia element maksymalny i najlepszych elementów pokrywają się na każdym dwuelementowej podzbioru z czym jest w sumie w celu${\displaystyle \,\leq \,}$${\displaystyle S}$${\displaystyle S=\{1,2,4\}}$${\displaystyle S}$${\displaystyle S}$${\displaystyle P.}$${\displaystyle \,\leq \,}$${\displaystyle P.}$

Wyreżyserowane zestawy

W całkowicie uporządkowanym zestawie terminy element maksymalny i element największy pokrywają się, dlatego oba terminy są używane zamiennie w dziedzinach takich jak analiza, w których brane są pod uwagę tylko rzędy całkowite. Ta obserwacja odnosi się nie tylko do całkowicie uporządkowanych podzbiorów dowolnego częściowo uporządkowanego zbioru, ale także do ich teoretycznego uogólnienia na podstawie zbiorów skierowanych . W zbiorze skierowanym każda para elementów (zwłaszcza pary elementów nieporównywalnych) ma wspólne ograniczenie górne w zbiorze. Jeżeli zbiór skierowany ma element maksymalny, to jest jednocześnie jego największym elementem, a więc jedynym maksymalnym elementem. Dla skierowanego zestawu bez elementów maksymalnych lub największych, zobacz przykłady 1 i 2 powyżej .

Podobne wnioski są prawdziwe dla elementów minimalnych.

Dalsze informacje wprowadzające znajdują się w artykule dotyczącym teorii zamówień .

Nieruchomości

• Każdy skończony niepusty podzbiór zawiera zarówno elementy maksymalne, jak i minimalne. Nieskończony podzbiór nie musi mieć żadnego z nich, na przykład liczb całkowitych o zwykłej kolejności.${\displaystyle S}$ ${\ Displaystyle \ mathbb {Z}}$
• Zbiór maksymalnych elementów podzbioru jest zawsze antyłańcuchem , to znaczy , że żadne dwa różne maksymalne elementy nie są porównywalne. To samo dotyczy elementów minimalnych.${\displaystyle S}$${\displaystyle S}$

Przykłady

• W wydajności Pareto , A optymalna Pareto jest elementem ilość w stosunku do częściowego celu poprawy Pareto, a zbiór elementów maksymalnej nazywa się granicę Pareto.
• W teorii decyzji , reguła dopuszczalny decyzja jest element maksymalny w odniesieniu do częściowego porządku dominuje regułę decyzyjną .
• We współczesnej teorii portfela zbiór maksymalnych elementów w odniesieniu do kolejności produktów na ryzyko i zwrot nazywa się granicą efektywną .
• W teorii mnogości , zbiór jest skończony , wtedy i tylko wtedy, gdy każdy niepusty rodzina z podzbiorów ma minimalny elementu, gdy zamówione przez relację inkluzji .
• W algebrze abstrakcyjnej pojęcie maksymalnego wspólnego dzielnika jest potrzebne do uogólnienia największych wspólnych dzielników na systemy liczbowe, w których wspólne dzielniki zbioru elementów mogą mieć więcej niż jeden maksymalny element.
• W geometrii obliczeniowej The maksima zbioru punktów jest ilość w zakresie częściowego rzędu coordinatewise dominacji.

Teoria konsumenta

W ekonomii można rozluźnić aksjomat antysymetrii, używając preorderów (ogólnie preorderów całkowitych ) zamiast zamówień częściowych; pojęcie analogiczne do elementu maksymalnego jest bardzo podobne, ale stosuje się inną terminologię, jak opisano poniżej.

W teorii konsumenta przestrzeń konsumpcji jest pewnym zbiorem , zwykle dodatnim ortantem pewnej przestrzeni wektorowej, tak że każda reprezentuje ilość konsumpcji określoną dla każdego istniejącego towaru w gospodarce. Preferencje konsumenta są zwykle reprezentowane przez całkowite zamówienie w przedsprzedaży, tak że i brzmi: jest co najwyżej tak preferowane jak . Kiedy i to jest interpretowany, że konsument jest obojętne , a jednak nie jest powód, aby stwierdzić, że preferencje stosunki nigdy nie są traktowane jako antysymetryczny. W tym kontekście dla dowolnego elementu mówi się, że jest elementem maksymalnym, jeśli ${\ Displaystyle X}$${\ Displaystyle x \ w X}$ ${\displaystyle \preceq}$${\displaystyle x,y\wX}$${\displaystyle x\preceq y}$${\displaystyle x}$${\displaystyle y}$${\displaystyle x\preceq y}$${\displaystyle y\preceq x}$${\displaystyle x}$${\displaystyle y}$${\displaystyle x=y.}$${\displaystyle B\subseteq X}$${\displaystyle x\wb}$

oznacza, że jest interpretowany jako wiązka zużycia, która nie jest zdominowana przez żaden inny wiązka w tym sensie, że jest, a nie${\displaystyle y\preceq x}$${\displaystyle x\prec y}$${\displaystyle x\preceq y}$${\displaystyle y\preceq x.}$

Należy zauważyć, że definicja formalna bardzo przypomina definicję największego elementu dla uporządkowanego zbioru. Jednak gdy jest tylko preorderem, element z powyższą właściwością zachowuje się bardzo podobnie jak maksymalny element w kolejności. Na przykład element maksymalny nie jest unikalny, ponieważ nie wyklucza możliwości, że (podczas i nie implikują, ale po prostu obojętność ). Pojęciem największego elementu w przedsprzedaży preferencji byłoby pojęcie najkorzystniejszego wyboru. To znaczy, niektóre z ${\displaystyle \preceq}$${\displaystyle x}$${\displaystyle x\wb}$${\displaystyle y\preceq x}$${\displaystyle x\preceq y}$${\displaystyle y\preceq x}$${\displaystyle x\preceq y}$${\displaystyle x=y}$${\displaystyle x\sim y}$${\displaystyle x\wb}$

implikuje ${\displaystyle y\prec x.}$

Oczywistym zastosowaniem jest definicja korespondencji na żądanie. Niech będzie klasą funkcjonałów na . Element nazywany jest funkcjonałem ceny lub systemem cen i odwzorowuje każdą wiązkę zużycia na jego wartość rynkową . Korespondencja budżet jest korespondencja mapowania dowolny system cen i dowolny poziom dochodów w podgrupie ${\displaystyle P}$${\ Displaystyle X}$${\displaystyle p\wp}$${\ Displaystyle x \ w X}$${\ Displaystyle p (x) \ w \ mathbb {R} _ {+}}$${\ Displaystyle \ Gamma \ dwukropek P \ razy \ mathbb {R} _ {+} \ Rightarrow X}$

Korespondencja popyt odwzorowuje każdą cenę oraz wszelkie poziom dochodów do zestawu -maximal elementów . ${\displaystyle p}$${\ Displaystyle m}$${\displaystyle \preceq}$${\ Displaystyle \ Gamma (p, m)}$

Nazywa się to korespondencją popytową, ponieważ teoria przewiduje, że za i dany racjonalny wybór konsumenta będzie pewnym elementem${\displaystyle p}$${\ Displaystyle m}$${\ Displaystyle x ^ {*}}$${\ Displaystyle x ^ {*} \ w D (p, m).}$

Powiązane pojęcia

O podzbiorze częściowo uporządkowanego zbioru mówimy, że jest kofinalny, jeśli dla każdego istnieje coś takiego, że Każdy kofinalny podzbiór zbioru częściowo uporządkowanego z elementami maksymalnymi musi zawierać wszystkie elementy maksymalne. ${\displaystyle Q}$${\displaystyle P}$${\displaystyle x\wp}$${\ Displaystyle y \ w Q}$${\displaystyle x\leq y.}$

Podgrupa o częściowy porządek jest mówi się, że dolny zestaw z , jeżeli jest on w dół zamknięty: Jeżeli i wtedy każdy dolny zestaw skończonej uporządkowanym jest równa najmniejszej dolnego zestawu zawierającego wszystkie elementy z maksymalnych${\ Displaystyle L}$${\displaystyle P}$${\displaystyle P}$${\ Displaystyle y \ w L}$${\displaystyle x\leq y}$${\displaystyle x\wl.}$${\ Displaystyle L}$${\displaystyle P}$${\ Displaystyle L.}$

Zobacz też

• Największy i najmniejszy element  – Element ≥ (lub ≤) każdy inny element
• Infimum i supremum  – największa dolna granica i najmniejsza górna granica
• Granice górne i dolne  – majorant i minorant w matematyce

Uwagi

Dowody

Bibliografia