Maximální a minimální prvky - Maximal and minimal elements

Hasseův diagram sady P z dělitele 60, částečně seřazeno podle vztahu "X rozděluje yČervená podmnožina S = {1,2,3,4} má dva maximální prvky, viz. 3 a 4 a jeden minimální prvek, viz. 1, což je také jeho nejmenší prvek.

v matematika, speciálně v teorie objednávek, a maximální prvek a podmnožina S některých částečně objednaná sada (poset) je prvek S to není menší než jakýkoli jiný prvek v S. A minimální prvek podmnožiny S je definována část částečně uspořádané množiny duálně jako prvek S to není větší než jakýkoli jiný prvek v S.

Pojmy maximální a minimální prvky jsou slabší než pojmy největší prvek a nejméně prvek které jsou rovněž známy jako maximální a minimální. Maximum podmnožiny S částečně uspořádané množiny je prvek S který je větší nebo roven jakémukoli jinému prvku Sa minimum S je opět definováno duálně. Zatímco částečně uspořádaná sada může mít maximálně jeden každý maximální a minimální, může mít více maximálních a minimálních prvků.^[1]^[2] Pro zcela objednané sady, pojmy maximálního prvku a maxima se shodují a pojmy minimálního prvku a minima se shodují.

Jako příklad v kolekci

S = {{d, Ó}, {d, Ó, G}, {G, Ó, A, d}, {Ó, A, F}}

objednáno někým zadržování, prvek {d, Ó} je minimální, protože neobsahuje žádné sady v kolekci, prvek {G, Ó, A, d} je maximální, protože v kolekci nejsou žádné sady, které ji obsahují, prvek {d, Ó, G} není ani jeden, a prvek {Ó, A, F} je minimální i maximální. Naproti tomu u maxima ani minima neexistuje S.

Zornovo lemma uvádí, že každá částečně objednaná množina, pro kterou má každá zcela objednaná podmnožina horní hranice obsahuje alespoň jeden maximální prvek. Toto lemma je ekvivalentní s věta o řádném uspořádání a axiom volby^[3] a implikuje významné výsledky v jiných matematických oblastech, jako je Hahnova – Banachova věta, Kirszbraunova věta, Tychonoffova věta, existence a Hamelův základ pro každý vektorový prostor a existenci algebraické uzavření pro každého pole.

Definice

Nechat ${ displaystyle (P, leq)}$ být částečně objednanou sadou a ${ displaystyle S subseteq P}$ . Pak ${ displaystyle m v S}$ je maximálním prvkem ${ displaystyle S}$ -li ${ displaystyle S}$ neobsahuje žádný prvek větší než ${ displaystyle m}$ , formálně: pokud neexistuje ${ displaystyle s v S}$ takové, že oba ${ displaystyle m leq s}$ a ${ displaystyle m neq s.}$

Definice minimálních prvků se získá použitím ≥ místo ≤.

Existence a jedinečnost

A plot sestává pouze z minimálních a maximálních prvků (příklad 3).

Maximální prvky nemusí existovat.

Příklad 1: Nechat S = [1,∞) ⊂ ℝ, pro všechny m∈S my máme s=m+1∈S ale m<s (to znamená, m≤s ale ne m=s).

Příklad 2: Nechat S = {s∈ℚ: 1≤s²≤2} ⊂ ℚ a pamatujte si to

{ displaystyle { sqrt {2}}}

∉ℚ.

Obecně ≤ je pouze částečná objednávka S. Li m je maximální prvek a s∈S, zůstává možnost, že ani jeden s≤m ani m≤s. To ponechává otevřenou možnost, že existuje mnoho maximálních prvků.

Příklad 3: V plot A₁ < b₁ > A₂ < b₂ > A₃ < b₃ > ..., všechny A_i jsou minimální a všechny b_i jsou maximální, viz obrázek.

Příklad 4: Nechat A být soubor s alespoň dvěma prvky a nechat S={{A}: A∈A} být podmnožinou souboru napájecí sada P(A) skládající se z singletons, částečně seřazeno podle ⊂. Toto je diskrétní poset - žádné dva prvky nejsou srovnatelné - a tedy každý prvek {A}∈S je maximální (a minimální) a pro jakékoli odlišné A′,A" ani {A′} ⊂ {A″} Ani {A″} ⊂ {A′}.

Největší prvky

U částečně objednané sady $(P, \leq)$ , ireflexivní jádro z $\leq$ je označen jako $<$ a je definována $X < y$ -li $X \leq y$ a $X \neq y$ . Pro svévolné členy $X, y \in P$ , platí přesně jeden z následujících případů:

$X < y$ ,
$X = y$ ,
$y < X$ ,
$X$ a $y$ jsou nesrovnatelné.

Vzhledem k podmnožině $S \subseteq P$ a nějaký $X \in S$ ,

pokud případ 1 nikdy neplatí pro žádný $y \in S$ , pak $X$ je maximálním prvkem $S$ , jak je definováno výše;
pokud případ 1 a 4 nikdy neplatí pro žádný $y \in S$ , pak $X$ se nazývá a největší prvek z $S$ .

Definice největšího prvku je tedy silnější než definice maximálního prvku.

Ekvivalentně největší prvek podmnožiny $S$ lze definovat jako prvek $S$ to je větší než u všech ostatních prvků $S$ . Podmnožina může mít maximálně jeden největší prvek.^{[poznámka 1]}

Největší prvek $S$ , pokud existuje, je také maximálním prvkem $S$ ,^{[poznámka 2]} a jediný.^{[Poznámka 3]}Podle kontrapozice, pokud $S$ má několik maximálních prvků, nemůže mít největší prvek; viz příklad 3. If $P$ uspokojuje vzestupný stav řetězu podmnožina $S$ z $P$ má největší prvek pokud, a pouze pokud, má jeden maximální prvek.^{[poznámka 4]}

Když omezení $\leq$ na $S$ je celková objednávka ( $S = { 1, 2, 4$ } na horním obrázku je příklad), pak se pojmy maximálního prvku a největšího prvku shodují.^{[poznámka 5]} To není nutná podmínka: kdykoli $S$ má největší prvek, shodují se také pojmy, jak je uvedeno výše. Pokud se pojmy maximálního prvku a největšího prvku shodují v každé podmnožině dvou prvků $S$ z $P$ , pak $\leq$ je celková objednávka dne $P$ .^{[poznámka 6]}

Řízené sady

V úplně objednaná sada, termíny maximální prvek a největší prvek se shodují, a proto se oba termíny používají zaměnitelně v polích jako analýza kde jsou brány v úvahu pouze celkové objednávky. Toto pozorování se vztahuje nejen na zcela uspořádané podmnožiny libovolného posetu, ale také na jejich teoretické zobecnění řádu pomocí řízené sady. V řízené sadě má každá dvojice prvků (zejména dvojice neporovnatelných prvků) společnou horní mez v rámci sady. Pokud má směrovaná množina maximální prvek, je to také jeho největší prvek,^{[poznámka 7]} a tedy jeho jediný maximální prvek. Směrovanou množinu bez maximálních nebo největších prvků viz příklady 1 a 2 výše.

Podobné závěry platí pro minimální prvky.

Další úvodní informace najdete v článku o teorie objednávek.

Vlastnosti

Každá konečná neprázdná podmnožina S má maximální i minimální prvky. Nekonečný substit nemusí mít žádný z nich, např. ℤ v obvyklém pořadí.
Sada maximálních prvků podmnožiny S je vždy proti řetězu, tj. žádné dva různé maximální prvky S jsou srovnatelné. Totéž platí pro minimální prvky.

Příklady

v Paretova účinnost, a Pareto optimální je maximální prvek s ohledem na dílčí pořadí vylepšení Pareto a sada maximálních prvků se nazývá Paretova hranice.
v teorie rozhodování, an pravidlo přípustného rozhodnutí je maximální prvek vzhledem k částečnému pořadí dominující rozhodovací pravidlo.
v moderní teorie portfolia, množina maximálních prvků vzhledem k objednávka produktu o riziku a návratnosti the efektivní hranice.
v teorie množin, sada je konečný právě když každý není prázdný rodina z podmnožiny má minimální prvek, pokud je objednán vztah zahrnutí.
v abstraktní algebra, pojem a maximální společný dělitel je třeba zobecnit největší společní dělitelé na číselné systémy, ve kterých společné dělitele sady prvků mohou mít více než jeden maximální prvek.
v výpočetní geometrie, maxima množiny bodů jsou maximální s ohledem na dílčí řád dominance souřadnic.

Teorie spotřebitele

V ekonomii lze uvolnit axiom antisymetrie pomocí předobjednávek (obecně totální předobjednávky ) místo dílčích objednávek; pojem analogický k maximálnímu prvku je velmi podobný, ale používá se odlišná terminologie, jak je podrobně uvedeno níže.

v teorie spotřebitele spotřeba prostoru je nějaká sada ${ displaystyle X}$ , obvykle kladný orthant nějakého vektorového prostoru tak, aby každý ${ displaystyle x v X}$ představuje množství spotřeby specifikované pro každou existující komoditu v ekonomice. Předvolby spotřebitele obvykle zastupuje a celková předobjednávka ${ displaystyle preceq}$ aby ${ displaystyle x, y v X}$ a ${ displaystyle x preceq y}$ zní: ${ displaystyle x}$ je maximálně stejně výhodné jako ${ displaystyle y}$ . Když ${ displaystyle x preceq y}$ a ${ displaystyle y preceq x}$ vykládá se, že spotřebitel je lhostejný mezi ${ displaystyle x}$ a ${ displaystyle y}$ ale není důvod k závěru, že ${ displaystyle x = y}$ „Přednostní vztahy se nikdy nepředpokládají jako antisymetrické. V této souvislosti pro všechny ${ displaystyle B podmnožina X}$ , voláme ${ displaystyle x v B}$ A maximální prvek -li

{ displaystyle v B}

naznačuje

{ displaystyle y preceq x}

a je interpretován jako balíček spotřeby, kterému nedominuje žádný jiný balíček v tom smyslu ${ displaystyle x prec y}$ , to je ${ displaystyle x preceq y}$ a ne ${ displaystyle y preceq x}$ .

Je třeba poznamenat, že formální definice vypadá velmi podobně jako největší prvek pro uspořádanou množinu. Kdy však ${ displaystyle preceq}$ je pouze předobjednávka, prvek ${ displaystyle x}$ s výše uvedenou vlastností se chová velmi podobně jako maximální prvek v objednávce. Například maximální prvek ${ displaystyle x v B}$ není jedinečný pro ${ displaystyle y preceq x}$ nevylučuje možnost, že ${ displaystyle x preceq y}$ (zatímco ${ displaystyle y preceq x}$ a ${ displaystyle x preceq y}$ nenaznačují ${ displaystyle x = y}$ ale prostě lhostejnost ${ displaystyle x sim y}$ ). Představa největšího prvku předobjednávky preferencí by byla nejvýhodnější výběr. To je, někteří ${ displaystyle x v B}$ s

{ displaystyle v B}

naznačuje

{ displaystyle y prec x.}

Zjevnou aplikací je definice poptávkové korespondence. Nechat ${ displaystyle P}$ být třídou funkcionářů na ${ displaystyle X}$ . Prvek ${ displaystyle p v P}$ se nazývá a cena funkční nebo cenový systém a mapuje každý balíček spotřeby ${ displaystyle x v X}$ do své tržní hodnoty ${ displaystyle p (x) in mathbb {R} _ {+}}$ . The rozpočtová korespondence je korespondence ${ displaystyle Gamma dvojtečka P krát mathbb {R} _ {+} rightarrow X}$ mapování jakéhokoli cenového systému a jakékoli úrovně příjmů do podmnožiny

{ Displaystyle Gamma (p, m) = {x v X mid p (x) leq m }.}

The požadovat korespondenci mapuje jakoukoli cenu ${ displaystyle p}$ a jakákoli úroveň příjmu ${ displaystyle m}$ do sady ${ displaystyle preceq}$ -maximální prvky ${ displaystyle Gamma (p, m)}$ .

{ displaystyle D (p, m) = { velký {} x v X polovině x}

je maximálním prvkem

{ displaystyle Gamma (p, m) { velký }}}

.

Říká se tomu poptávková korespondence, protože to teorie předpovídá ${ displaystyle p}$ a ${ displaystyle m}$ daný, racionální volba spotřebitele ${ displaystyle x ^ {*}}$ bude nějaký prvek ${ displaystyle x ^ {*} v D (p, m)}$ .

Související pojmy

Podmnožina ${ displaystyle Q}$ částečně objednané sady ${ displaystyle P}$ se říká, že je konečný pokud pro každého ${ displaystyle x v P}$ nějaké existují ${ displaystyle v Q}$ takhle ${ displaystyle x leq y}$ . Každá koncová podmnožina částečně uspořádané množiny s maximálními prvky musí obsahovat všechny maximální prvky.

Podmnožina ${ displaystyle L}$ částečně objednané sady ${ displaystyle P}$ se říká, že je spodní sada z ${ displaystyle P}$ pokud je dolů zavřený: pokud ${ displaystyle y v L}$ a ${ displaystyle x leq y}$ pak ${ displaystyle x v L}$ . Každá nižší sada ${ displaystyle L}$ konečné objednané množiny ${ displaystyle P}$ se rovná nejmenší spodní sadě obsahující všechny maximální prvky ${ displaystyle L}$ .

Viz také

Poznámky

^ Li $G 1$ a $G 2$ jsou tedy největší $G 1 \leq G 2$ a $G 2 \leq G 1$ , a tedy $G 1 = G 2$ podle antisymetrie.
^ Li $G$ je největším prvkem $S$ a $s \in S$ , pak $s \leq G$ . Podle antisymetrie, toto vykresluje ( $G \leq s$ a $G \neq s$ ) nemožné.
^ Li $m'$ je tedy maximální prvek $m' \leq G$ od té doby $G$ je tedy největší $m' = G$ od té doby $m'$ je maximální.
^ Jen když: viz výše. - Li: Předpokládejme rozpor $S$ má jen jeden maximální prvek, $m$ , ale žádný největší prvek. Od té doby $m$ není největší, někteří $s 1 \in S$ musí existovat, což je nesrovnatelné s $m$ . Proto $s 1 \in S$ nemůže být maximální, to znamená, $s 1 < s 2$ pro některé musí vydržet $s 2 \in S$ . Ten druhý musí být nesrovnatelný s $m$ také od té doby $m < s 2$ je v rozporu $m$ je maximální, zatímco $s 2 \leq m$ je v rozporu s nesrovnatelností $m$ a $s 1$ . Opakováním tohoto argumentu nekonečný vzestupný řetězec $s 1 < s 2 < \cdot\cdot\cdot < s n < \cdot\cdot\cdot$ lze nalézt (takové, že každý $s i$ je nesrovnatelný s $m$ a ne maximální). To je v rozporu se vzestupným stavem řetězu.
^ Nechat $m \in S$ být maximálním prvkem pro všechny $s \in S$ buď $s \leq m$ nebo $m \leq s$ . Ve druhém případě to vyžaduje definice maximálního prvku $m = s$ , takže z toho vyplývá $s \leq m$ . Jinými slovy, $m$ je největší prvek.
^ Li $A, b \in P$ byly tedy nesrovnatelné $S = {A, b$ } bude mít dva maximální, ale žádný největší prvek, který by byl v rozporu s náhodou.
^ Nechat ${ displaystyle m v D}$ být maximální. Předpokládejme, že je rozpor nějaký svévolný ${ displaystyle x v D}$ je nesrovnatelný s ${ displaystyle m}$ , pak společná horní mez ${ displaystyle u}$ z ${ displaystyle m}$ a ${ displaystyle x}$ je srovnatelná s ${ displaystyle x}$ a proto se nemohou rovnat ${ displaystyle m}$ , proto ${ displaystyle m$ , což je v rozporu s maximálností. Proto ${ displaystyle m}$ je největší prvek.

Reference

^ Richmond, Bettina; Richmond, Thomas (2009), Diskrétní přechod k pokročilé matematice, American Mathematical Society, str. 181, ISBN 978-0-8218-4789-3.
^ Scott, William Raymond (1987), Skupinová teorie (2. vyd.), Dover, str. 22, ISBN 978-0-486-65377-8
^ Jech, Thomas (2008) [původně publikováno v roce 1973]. Axiom výběru. Dover Publications. ISBN 0-486-46624-8.

[4] Li $G 1$ a $G 2$ jsou tedy největší $G 1 \leq G 2$ a $G 2 \leq G 1$ , a tedy $G 1 = G 2$ podle antisymetrie.

[5] Li $G$ je největším prvkem $S$ a $s \in S$ , pak $s \leq G$ . Podle antisymetrie, toto vykresluje ( $G \leq s$ a $G \neq s$ ) nemožné.

[6] Li $m'$ je tedy maximální prvek $m' \leq G$ od té doby $G$ je tedy největší $m' = G$ od té doby $m'$ je maximální.

[7] Jen když: viz výše. - Li: Předpokládejme rozpor $S$ má jen jeden maximální prvek, $m$ , ale žádný největší prvek. Od té doby $m$ není největší, někteří $s 1 \in S$ musí existovat, což je nesrovnatelné s $m$ . Proto $s 1 \in S$ nemůže být maximální, to znamená, $s 1 < s 2$ pro některé musí vydržet $s 2 \in S$ . Ten druhý musí být nesrovnatelný s $m$ také od té doby $m < s 2$ je v rozporu $m$ je maximální, zatímco $s 2 \leq m$ je v rozporu s nesrovnatelností $m$ a $s 1$ . Opakováním tohoto argumentu nekonečný vzestupný řetězec $s 1 < s 2 < \cdot\cdot\cdot < s n < \cdot\cdot\cdot$ lze nalézt (takové, že každý $s i$ je nesrovnatelný s $m$ a ne maximální). To je v rozporu se vzestupným stavem řetězu.

[8] Nechat $m \in S$ být maximálním prvkem pro všechny $s \in S$ buď $s \leq m$ nebo $m \leq s$ . Ve druhém případě to vyžaduje definice maximálního prvku $m = s$ , takže z toho vyplývá $s \leq m$ . Jinými slovy, $m$ je největší prvek.

[9] Li $A, b \in P$ byly tedy nesrovnatelné $S = {A, b$ } bude mít dva maximální, ale žádný největší prvek, který by byl v rozporu s náhodou.

[10] Nechat ${ displaystyle m v D}$ být maximální. Předpokládejme, že je rozpor nějaký svévolný ${ displaystyle x v D}$ je nesrovnatelný s ${ displaystyle m}$ , pak společná horní mez ${ displaystyle u}$ z ${ displaystyle m}$ a ${ displaystyle x}$ je srovnatelná s ${ displaystyle x}$ a proto se nemohou rovnat ${ displaystyle m}$ , proto ${ displaystyle m$ , což je v rozporu s maximálností. Proto ${ displaystyle m}$ je největší prvek.

[1] Richmond, Bettina; Richmond, Thomas (2009), Diskrétní přechod k pokročilé matematice, American Mathematical Society, str. 181, ISBN 978-0-8218-4789-3.

[2] Scott, William Raymond (1987), Skupinová teorie (2. vyd.), Dover, str. 22, ISBN 978-0-486-65377-8

[3] Jech, Thomas (2008) [původně publikováno v roce 1973]. Axiom výběru. Dover Publications. ISBN 0-486-46624-8.

[1]

[2]

[3]

[poznámka 1]

[poznámka 2]

[Poznámka 3]

[poznámka 4]

[poznámka 5]

[poznámka 6]

[poznámka 7]