Maximala och minimala element - Maximal and minimal elements

I matematik , särskilt i ordningens teori , en maximal del av en delmängd S av något förbeställda uppsättning är ett element av S som inte är mindre än någon annan beståndsdel i S . En minimal del av en delmängd S av något förbeställda uppsättning definieras dually som en del av S som inte är större än något annat element i S .

Föreställningarna om maximala och minimala element är svagare än de för största element och minst element som också är kända respektive som maximala och lägsta. Högsta till en delmängd av en förbeställd uppsättning är ett element som är större än eller lika med något annat element av och minimiet av definieras igen dualt. I det särskilda fallet med en delvis ordnad uppsättning , medan det kan vara högst ett maximum och högst ett minimum kan det finnas flera maximala eller minimala element. Specialiserar oss vidare på totalt beställda uppsättningar , föreställningarna om maximalt element och maximalt sammanfallande, och föreställningarna om minimalt element och minimum sammanfaller. ${\ displaystyle S}$${\ displaystyle S}$${\ displaystyle S,}$${\ displaystyle S}$

Som ett exempel i samlingen

ordnat efter inneslutning är elementet { d , o } minimalt eftersom det inte innehåller några uppsättningar i samlingen, elementet { g , o , a , d } är maximalt eftersom det inte finns några uppsättningar i samlingen som innehåller det, elementet { d , o , g } är ingen av och elementet { o , a , f } är både minimalt och maximalt. Däremot finns varken ett maximum eller ett minimum för${\ displaystyle S.}$

Zorns lemma säger att varje delvis ordnad uppsättning för vilken varje helt ordnad delmängd har en övre gräns innehåller minst ett maximalt element. Detta lemma motsvarar det välordnade teoremet och valet axiom och innebär stora resultat i andra matematiska områden som Hahn-Banach-satsen , Kirszbraun-satsen , Tychonoffs sats , förekomsten av en Hamel-grund för varje vektorutrymme och förekomsten av en algebraisk stängning för varje fält .

Definition

Låt vara en förbeställd uppsättning och låt Ett maximalt element av med avseende på är ett sådant element${\ displaystyle (P, \ leq)}$${\ displaystyle S \ subseteq P.}$ ${\ displaystyle S}$${\ displaystyle \, \ leq \,}$${\ displaystyle m \ i S}$

om tillfredsställer då nödvändigtvis${\ displaystyle s \ i S}$${\ displaystyle m \ leq s,}$${\ displaystyle s \ leq m.}$

På samma sätt kan a minimala element avmed avseende på${\ displaystyle S}$${\ displaystyle \, \ leq \,}$är ettsådant element${\ displaystyle m \ i S}$

om tillfredsställer då nödvändigtvis${\ displaystyle s \ i S}$${\ displaystyle s \ leq m,}$${\ displaystyle m \ leq s.}$

På motsvarande sätt är ett minimalt element av med avseende på om och bara om är ett maximalt element av med avseende på var per definition, om och bara om (för alla ). ${\ displaystyle m \ i S}$${\ displaystyle S}$${\ displaystyle \, \ leq \,}$${\ displaystyle m}$${\ displaystyle S}$${\ displaystyle \, \ geq, \,}$${\ displaystyle q \ geq p}$${\ displaystyle p \ leq q}$${\ displaystyle p, q \ i P}$

Om delmängden inte är specificerad bör det antas att Explicitly a${\ displaystyle S}$${\ displaystyle S: = P.}$maximalt element (respektiveminimalt element)av${\ displaystyle (P, \ leq)}$är ett maximalt (resp. minimalt) element avmed avseende på${\ displaystyle S: = P}$${\ displaystyle \, \ leq.}$

Om den förbeställda uppsättningen också råkar vara en delvis ordnad uppsättning (eller mer allmänt, om begränsningen är en delvis ordnad uppsättning) då är ett maximalt element av om och bara om den inte innehåller något element som är strikt större än uttryckligen, betyder det att det inte finns existera något element så att och Karakteriseringen för minimala element erhålls genom att använda i stället för${\ displaystyle (P, \ leq)}$${\ displaystyle (S, \ leq)}$${\ displaystyle m \ i S}$${\ displaystyle S}$${\ displaystyle S}$${\ displaystyle m;}$${\ displaystyle s \ i S}$${\ displaystyle m \ leq s}$${\ displaystyle m \ neq s.}$${\ displaystyle \, \ geq \,}$${\ displaystyle \, \ leq.}$

Existens och unikhet

Maximala element behöver inte existera.

Exempel 1: Låt där betecknar de reella talen . För alla utom (det vill säga, men inte ).${\ displaystyle S = [1, \ infty) \ subseteq \ mathbb {R}}$${\ displaystyle \ mathbb {R}}$${\ displaystyle m \ i S,}$ ${\ displaystyle s = m+1 \ i S}$${\ displaystyle m <s}$${\ displaystyle m \ leq s}$${\ displaystyle m = s}$

Exempel 2: Låt var betecknar de rationella talen och var är irrationellt.${\ displaystyle S = \ {s \ in \ mathbb {Q} ~: ~ 1 \ leq s^{2} \ leq 2 \},}$${\ displaystyle \ mathbb {Q}}$${\ displaystyle {\ sqrt {2}}}$

I allmänhet är endast en delordning om If är ett maximalt element och då är det fortfarande möjligt att varken eller Detta lämnar möjligheten att det finns mer än ett maximalt element. ${\ displaystyle \, \ leq \,}$${\ displaystyle S.}$${\ displaystyle m}$${\ displaystyle s \ i S,}$${\ displaystyle s \ leq m}$${\ displaystyle m \ leq s.}$

Exempel 3: I staketet är alla minimala och alla är maximala, som visas på bilden.${\ displaystyle a_ {1} <b_ {1}> a_ {2} <b_ {2}> a_ {3} <b_ {3}> \ ldots,}$${\ displaystyle a_ {i}}$${\ displaystyle b_ {i}}$

Exempel 4: Låt A vara en uppsättning med minst två element och låt vara delmängden av kraftuppsättningen som består av singleton -delmängder , delvis ordnad av Detta är den diskreta positionen där inga två element är jämförbara och därmed varje element är maximalt (och minimalt ); dessutom för alla distinkta varken eller${\ displaystyle S = \ {\ {a \} ~: ~ a \ i A \}}$ ${\ displaystyle \ wp (A)}$${\ displaystyle \, \ subseteq.}$${\ displaystyle \ {a \} \ i S}$${\ displaystyle a, b \ i A,}$${\ displaystyle \ {a \} \ subseteq \ {b \}}$${\ displaystyle \ {b \} \ subseteq \ {a \}.}$

Största element

För en delvis ordnad uppsättning av irreflexive kärna av betecknas och definieras av om och för godtyckliga medlemmar exakt ett av följande fall gäller: ${\ displaystyle (P, \ leq),}$${\ displaystyle \, \ leq \,}$${\ displaystyle \, <\,}$${\ displaystyle x <y}$${\ displaystyle x \ leq y}$${\ displaystyle x \ neq y.}$${\ displaystyle x, y \ i P,}$

1. ${\ displaystyle x <y}$;
2. ${\ displaystyle x = y}$;
3. ${\ displaystyle y <x}$;
4. ${\ displaystyle x}$och är makalösa.${\ displaystyle y}$

Med en delmängd och några${\ displaystyle S \ subseteq P}$${\ displaystyle x \ i S,}$

• om fall 1 aldrig gäller för någon då är ett maximalt element av enligt definitionen ovan;${\ displaystyle y \ i S,}$${\ displaystyle x}$${\ displaystyle S,}$
• om fall 1 och 4 aldrig gäller för något så kallas det största elementet av${\ displaystyle y \ i S,}$${\ displaystyle x}$${\ displaystyle S.}$

Således är definitionen av ett största element starkare än det för ett maximalt element.

På motsvarande sätt kan ett största element i en delmängd definieras som ett element av det som är större än varje annat element i En delmängd kan ha högst ett största element. ${\ displaystyle S}$${\ displaystyle S}$${\ displaystyle S.}$

Det största elementet av om det finns, är också ett maximalt element av och det enda. Genom kontraposition , om den har flera maximala element, kan den inte ha ett största element; se exempel 3. Om den uppfyller det stigande kedjetillståndet har en delmängd av det största elementet om, och bara om , det har ett maximalt element. ${\ displaystyle S,}$${\ displaystyle S,}$${\ displaystyle S}$${\ displaystyle P}$${\ displaystyle S}$${\ displaystyle P}$

När begränsningen av till är en total ordning ( i den översta bilden är ett exempel), sammanfaller föreställningarna om maximalt element och största element. Detta är inte en nödvändig förutsättning: när som helst har det största elementet sammanfaller också föreställningarna, som anges ovan. Om föreställningarna om maximalt element och största element sammanfaller på varje tvåelementundersättning av då är en total ordning på${\ displaystyle \, \ leq \,}$${\ displaystyle S}$${\ displaystyle S = \ {1,2,4 \}}$${\ displaystyle S}$${\ displaystyle S}$${\ displaystyle P.}$${\ displaystyle \, \ leq \,}$${\ displaystyle P.}$

Regisserade uppsättningar

I en helt ordnad uppsättning sammanfaller termerna maximalt element och största element, varför båda termerna används omväxlande i fält som analys där endast totala order beaktas. Denna observation gäller inte bara totalt beställda delmängder av någon delvis ordnad uppsättning, utan också deras ordningsteoretiska generalisering via riktade uppsättningar . I en riktad uppsättning har varje elementpar (särskilt par av ojämförliga element) en gemensam övre gräns inom uppsättningen. Om en riktad uppsättning har ett maximalt element, är det också dess största element, och därmed dess enda maximala element. För en riktad uppsättning utan maximala eller största element, se exempel 1 och 2 ovan .

Liknande slutsatser gäller för minimala element.

Ytterligare inledande information finns i artikeln om orderteori .

Egenskaper

• Varje ändlig icke -förlustad delmängd har både maximala och minimala element. En oändlig delmängd behöver inte ha någon av dem, till exempel heltal med den vanliga ordningen.${\ displaystyle S}$ ${\ displaystyle \ mathbb {Z}}$
• Uppsättningen av maximala element i en delmängd är alltid en antikedja , det vill säga att inga två olika maximala element är jämförbara. Detsamma gäller minimala element.${\ displaystyle S}$${\ displaystyle S}$

Exempel

• I Pareto -effektivitet är ett Pareto -optimalt ett maximalt element med avseende på den delvisa ordningen för Pareto -förbättring, och uppsättningen av maximala element kallas Pareto -gränsen.
• Inom beslutsteorin är en tillåtet beslutsregel ett maximalt element med avseende på den delvisa ordningen för dominerande beslutsregel .
• I modern portföljteori kallas uppsättningen maximala element med avseende på produktordningen för risk och avkastning för den effektiva gränsen .
• I uppsättningsteorin är en uppsättning begränsad om och bara om varje icke-tom familj av delmängder har ett minimalt element när det ordnas av inkluderingsrelationen .
• I abstrakt algebra behövs konceptet med en maximal gemensam divisor för att generalisera största gemensamma divisorer till nummersystem där de gemensamma delarna av en uppsättning element kan ha mer än ett maximalt element.
• I beräkningsgeometri är maxima för en punktuppsättning maximal med avseende på den ordnade delen av koordinatvis dominans.

Konsumentteori

Inom ekonomi kan man slappna av antisymmetriens axiom genom att använda förbeställningar (i allmänhet totala förbeställningar ) istället för delordningar; begreppet analogt med maximalt element är mycket likt, men olika terminologi används, som beskrivs nedan.

I konsumentteorin är konsumtionsutrymmet en viss uppsättning , vanligtvis den positiva orthanten av något vektorutrymme så att var och en representerar en förbrukningsmängd som anges för varje befintlig vara i ekonomin. Konsumenternas preferenser representeras vanligtvis av en total förbeställning så att och lyder: är högst lika föredragen som . När och det tolkas att konsumenten är likgiltig mellan och men inte är någon anledning att dra slutsatsen att preferensrelationer aldrig antas vara antisymmetriska. I detta sammanhang sägs för vilket element som helst vara ett maximalt element om ${\ displaystyle X}$${\ displaystyle x \ i X}$ ${\ displaystyle \ preceq}$${\ displaystyle x, y \ i X}$${\ 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 \ i B}$

innebär att det tolkas som ett konsumtionspaket som inte domineras av något annat paket i den meningen att det är och inte${\ displaystyle y \ preceq x}$${\ displaystyle x \ prec y,}$${\ displaystyle x \ preceq y}$${\ displaystyle y \ preceq x.}$

Det bör noteras att den formella definitionen ser mycket ut som den för ett största element för en ordnad uppsättning. Men när det bara är en förbeställning uppträder ett element med egenskapen ovan väldigt mycket som ett maximalt element i en beställning. Till exempel är ett maximalt element inte unikt för utesluter inte möjligheten att (medan och inte antyder utan helt enkelt likgiltighet ). Tanken med det största elementet för en preferensförbeställning skulle vara det mest föredragna valet. Det vill säga några med ${\ displaystyle \ preceq}$${\ displaystyle x}$${\ displaystyle x \ i B}$${\ 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 \ i B}$

innebär ${\ displaystyle y \ prec x.}$

En uppenbar tillämpning är definitionen av efterfrågekorrespondens. Låt vara klassen av funktionaliteter på . Ett element kallas ett prisfunktionellt eller prissystem och kartlägger varje konsumtionspaket till dess marknadsvärde . Den budget korrespondens är en korrespondens kartläggning varje pris systemet och alla inkomstnivå i en delmängd ${\ displaystyle P}$${\ displaystyle X}$${\ displaystyle p \ i P}$${\ displaystyle x \ i X}$${\ displaystyle p (x) \ in \ mathbb {R} _ {+}}$${\ displaystyle \ Gamma \ colon P \ times \ mathbb {R} _ {+} \ högerpil X}$

Den efterfrågan korrespondens kartor varje pris och alla inkomstnivå i uppsättningen -maximal delar av . ${\ displaystyle p}$${\ displaystyle m}$${\ displaystyle \ preceq}$${\ displaystyle \ Gamma (p, m)}$

Det kallas efterfrågekorrespondens eftersom teorin förutsäger att för och givet kommer det rationella valet av en konsument att vara något element${\ displaystyle p}$${\ displaystyle m}$${\ displaystyle x^{*}}$${\ displaystyle x^{*} \ i D (p, m).}$

Relaterade föreställningar

En delmängd av en delvis ordnad uppsättning sägs vara kofinal om det för varje finns en sådan att varje kofinal delmängd av en delvis ordnad uppsättning med maximala element måste innehålla alla maximala element. ${\ displaystyle Q}$${\ displaystyle P}$${\ displaystyle x \ i P}$${\ displaystyle y \ i Q}$${\ displaystyle x \ leq y.}$

En delmängd av en partiellt ordnad uppsättning sägs vara en lägre uppsättning av om den är nedåt stängt: om och sedan Varje undre uppsättning av en ändlig ordnad uppsättning är lika med den minsta undre uppsättning innehåller alla maximala element av${\ displaystyle L}$${\ displaystyle P}$${\ displaystyle P}$${\ displaystyle y \ i L}$${\ displaystyle x \ leq y}$${\ displaystyle x \ i L.}$${\ displaystyle L}$${\ displaystyle P}$${\ displaystyle L.}$

Se även

• Största element och minst element  - Element ≥ (eller ≤) varandra element
• Infimum och supremum  - Största nedre gränsen och minst övre gränsen
• Övre och nedre gränser  - Majorant och minorant i matematik

Anteckningar

Bevis

Referenser